In this post I will explain the thoughts I’ve been having for private solving using multi-party computation (MPC).
To keep things simple, in this post I see intents as unbalanced transactions with resources controlled by the user. Thus, the users can generate the compliance and logic proofs of their intents, and the commitments of the (created) resources. The matched intents form the final balanced transaction. With this perspective, the actions of the final transaction are the matched intents: one action per matched intent.
This post is about how to match intents without revealing the contents of the matched intents. This post is not about how to match intents without revealing which are matched, nor about how to match intents belonging to the same action. (The latter requires collaboration for the generation of the compliance and logic proofs, which I do not address here, but might be worth exploring.)
Resource and transaction deltas. Resource deltas can be seen as Pedersen commitments, where the binding generator G_\mathsf{k} is given by the resource kind and the hiding generator H is fixed
Above q is the resource quantity and r some randomness. In a balanced transaction that contains m_o consumed (old) resources with delta randomness r_1,\ldots,r_{m_o}, and m_n created (new) resources with delta randomness r'_{1},\ldots, r'_{m_n}, the transaction delta, which is the aggregation of the resource deltas, equals
where s_{\mathsf{tx}}:=r_1+\cdots + r_{m_o}-(r'_{1}+\cdots + r'_{m_n}). The delta proof is then a signature (of some message) under the signing/verifying keypair (s_\mathsf{tx},\Delta_\mathsf{tx}).
As a running example, I am going to use the matching of buy/sell orders of two fixed tokens. Say bananas and apples. (There seems to be a tradition using this naming.).
A balanced transaction in the running example consists of one buy intent, one sell intent and the transaction delta proof. The correspondence between the order and the intent is shown in the table and drawing below.
| Order | Intent |
|---|---|
| “Buy X bananas for Y apples” | “Consume an apple resource with quantity=Y, create a banana resource with quantity =X” |
| “Sell X bananas for Y apples” | “Consume a banana resource with quantity=X, create an apple resource with quantity=Y” |
Solving strategies
I think of solving strategies as functions that takes b data items and outputs the m indices of the matched items (if any)
The number of matches m is part of the definition of the solving strategy (i.e. depends on the use case). The batch size b\geq m is a configurable parameter. The larger b the most likely a match will be found, but the more costly to run \mathsf{solve}.
When matching intents, the i-th data item data_i is what is needed to match the i-th intent. After running \mathsf{solve}, the solver retrieves the m matched intents \{intent_i\}_{i\in\mathbb{M}} from the intent pool.
In the running example of matching buying/selling orders, m=2, and the \mathsf{solve} strategy is based on arrival to the order book (the intent pool). Given a batch of b\geq 2 orders, starting from the oldest one, compare with opposite orders until finding one with matching buying/selling prices. Output the pair of indices \mathbb{M} = \{i_1,i_2\} for which the first match occurs (if any).
The data needed to match is the order type, and the selling and buying price. As shown in the following table:
| Data | Intent |
|---|---|
| \mathsf{order}=\mathsf{buy}, X, Y | “Consume an apple resource with quantity=Y, create a banana resource with quantity =X” |
| \mathsf{order}=\mathsf{sell}, X, Y | “Consume a banana resource with quantity=X, create an apple resource with quantity=Y” |
High level overview
The goal is to distribute \mathsf{solve} across a fixed set of n nodes, say n=3. These nodes will run an MPC protocol to compute \mathsf{solve}. The parties involved are:
- the users – the intent owners,
- the solver,
- the MPC nodes.
The process is split in three phases: first input sharing by the users, then MPC execution by the nodes, and last output reconstruction to the solver, who generates the balanced transaction. The input sharing is asynchronous: different users share at different time, and the MPC nodes can run while receiving fresh sharings.
The exact MPC protocol is not important for this informal discussion. Neither the exact secret-sharing scheme used.
Input sharing
The user starts sending their (shielded) intent to the solver who stores it in the intent pool. The user also secret-shares their data, and their delta resource randomness \vec{r}:=(r_1\ldots,r_u) with the MPC nodes.
where ds_i is the data share and rs_{j,i} the randomness share given to the i-th node.
- The data is what is known only by the user but necessary to match the intent. If there is public data, it is communicated in the clear to the nodes, and treated as a constant/public value during the MPC execution.
- The randomness vector \vec{r} has one component per resource in the intent of the user. The randomness is given in appropriate form: for a created resource \mathsf{r}, its delta is \Delta_{\mathsf{r}}:=G_{\mathsf{k}}^qH^{-r} (the additive inverse).
I assume users are honest and share consistent intent/data/randomness triplets.
In the running example, only two resources appear in the intent, one consumed, another created. So the randomness vector shared by each user is \vec{r} = (r_1,-r_2).
Running \mathsf{solve} in MPC
Let a batch of b secret-shared data/intent pairs. The MPC does two things: (1) runs the solving strategy \mathsf{solve} over the data, to find out the indices of the matched intents, and (2) computes the signing key s_{\mathsf{tx}} for the balanced transaction formed by the matched intents.
If \mathsf{solve} needs to match m intents, the MPC is for the function:
\mathsf{match}(data_1,\vec{r}_1\ldots,data_b,\vec{r}_b):
- \mathbb{M}:=\{i_1,\ldots,i_m\}\gets \mathsf{solve}(data_1,\ldots,data_b) // indices of matched data (or empty)
- Compute s_{\mathsf{tx}} = \sum_{j\in\mathbb{M}}(r_{j,1}+\ldots + r_{j,u_j}) // sum of all randomness
- Output set of indices \mathbb{M} and s_{\mathsf{tx}} (or empty)
Recall that in the running example m=2, and the output is the pair of indices \mathbb{M} = \{i_1,i_2\} for which the first match occurs. The signing key is
s_\mathsf{tx} = r_{i_1,1}+r_{i_2,1}-r_{i_1,2}-r_{i_2,2}.
Output reconstruction
The output (\mathbb{M},r_{\mathsf{tx}}) is reconstructed to the solver who can create the final balanced transaction using the output intents \mathsf{tx}:=\{intent_i\}_{i\in\mathbb{M}}. The solver generates the transaction delta proof (a signature) using the reconstructed signing key s_{\mathsf{tx}}, as it holds \Delta_{\mathsf{tx}}= H^{s_\mathsf{tx}}.
The MPC nodes also reconstruct the indices \mathbb{M} for themselves, so that they can remove the corresponding shares and keep running \mathsf{match} on fresh batches.
What is leaked and what is not
The output of \mathsf{match} does not reveal what exactly was matched, because the output intents \{intent_i\}_{i\in\mathbb{M}} conceal this. It also does not leak if in the batch there is another i'_2\neq i_2 such that (i_1,i'_2) is a match (using the resource deltas, the signing key allows to compare i_1 against i_2, but not against any other index.)
But, it is leaked between who the match occurs – the indices \mathbb{M} --, necessary to retrieve the intents from the pool, and to avoid matching twice an intent in two runs of \mathsf{match}.
In the running example, it will not be known which of the output intents intent_{i_1},intent_{i_2} is the buy order and which is the sell order, neither the buying/selling prices.