What is MPC?

Multi-party computation (MPC) is a core cryptographic primitive that has been studied since the early 1980s, but has seen little use in DeFi before Renegade.

To best understand MPC, it is easiest to compare to the "ideal functionality" that MPC implements. In this setting, multiple parties send some private data to a trusted evaluator. Once the evaluator receives all the private data, it computes a function on that data and then sends the function output to all the parties.

Note that the important property here is that the trusted evaluator only sends the output to each party, and is trusted to forget all the private inputs. This allows for computation of a function without needing to reveal the inputs to everyone.

For example, two parties could each hold two private numbers and compute a comparator between the two private values, outputting a single bit to determine who has the larger input (this is Yao's Millionaire's Problem).

The core idea of a MPC protocol is that it lets you implement the above functionality without needing to trust a central party. That is, MPC allows for multiple mutually-distrusting parties to compute a function output on secret input data.

There are two main classes of MPC algorithms: "garbled circuits" and "secret-sharing" algorithms. The secret-shared approaches are typically easier to understand, where "somewhat homomorphic" MPC calculations are done on Shamir Secret Shares of the individual private inputs. Understanding how MPC works on the protocol level is out-of-scope for these docs, but one of the easier-to-understand secret-shared MPC protocols is BGW: See here for an explainer.

Using MPC for Dark Pools

In the context of a dark pool, the use of MPC is natural: The private inputs are each trader's personal order book, and the output of the MPC is a list of any tokens that have been swapped as a result of executing the matching engine on the pairs of order books.

Importantly, note that by using MPC, two traders can anonymously match their orders. Traders never need to reveal orders in-the-clear, and if there is no match between two traders' order books, then no information is leaked (other than the fact that there was no valid counter-order). It's full dark pool functionality, with no trusted dark pool operator!

Note, however, that MPC algorithms on their own don't have any guarantees about the validity of the inputs of each party. This would be a huge problem for the dark pool, as we must have guarantees that each trader actually has appropriate balances for each of their orders. In the next section The MPC-ZKP Architecture, we will see how we combine the idea of MPC with zero-knowledge proofs in order to prove consistency of balances and orders with respect to on-chain state.