Multi-party computation (MPC) and smart contracts are often seen as witchcraft involving a lot of math and weird computer science concepts. But they're fundamentally very simple, and in fact similar in spirit once you abstract things away a bit. Even if you've never heard about MPC and smart contracts, after you finish reading this post these will become crystal clear.
Both MPC and smart contracts compute a program – where "program" means a computer program, that is, a list of instructions along with its associated memory to store variables and results. A program has input values and output values, as in the simple example below:
INPUT: 3 integers X, Y, and Z
OUTPUT: 1 integer
ADD( X, Y, Z ):
RETURN X + Y + Z
This program is just doing the addition of 3 numbers. Its input values are numbers which are added together, and the output value is their sum.
You can think of more complex examples, such as a function SIGN that calculates a digital signature (as for example used to authenticate blockchain transactions), with the following input and output values:
INPUT: 1 message, 1 private key
OUTPUT: 1 signature
Likewise, a signature might be verified using a VERIFY program that, given a signature, a public key, and a message returns Valid or Invalid:
INPUT: 1 message, 1 public key, 1 signature
OUTPUT: 1 value "Valid" or "Invalid"
As we'll see below,
- MPC computes programs by involving multiple parties, where parties send and receive messages and perform some computations, and where parties' input values remain secret for other parties.
- Smart contracts compute programs such that multiple parties verify the correctness of the result, and jointly maintain the memory holding the input and output values.
MPC is a class of protocols, that is, mechanisms where multiple parties who exchange messages and do computations and eventually terminate the protocol. "Parties" usually mean "computers", be it laptops, cloud servers, mobile phones, or dedicated security appliances.
Let me introduce my two friends Summer and Rick, who will be the 2 parties in our 2-party protocols examples: here they jointly compute the addition that we saw above:
As you can see, in this protocol both Summer and Rick know all the input values, as well as the output.
However, when we talk of MPC in cryptography, we actually mean secure MPC, where the goal is to jointly compute a program without learning the values held by other parties. The goals of such protocols is to hide some input values, or even all input values, as in this view of a 2-party protocol for a 2-input program:
At this point, you might realize that secure 2-party addition is impossible, if each party holds one of the 2 operands (because once you learn the result Z, Summer can compute Y = Z – X). But MPC can compute other programs securely:
In the so-called Millionaires' problem, 2 parties want to compare their wealth without revealing how much they hold. In the example below, 2 parties hold respectively X and Y bitcoins, and who to know who has more bitcoins than the other, but without revealing how much they have. This is called secure comparison, and is one of the first programs for which cryptographers created secure MPC protocols, using a technique called garbled circuits:
Another example of MPC is private set intersection (PSI), where 2 parties each have a list of values and want to know which values they have in common, but without revealing their whole lists:
PSI was notably used by Apple in its CSAM content detection protocol.
Last but not least, there's the specific type of MPC that is the favorite of people in the blockchain space, called threshold signing. In this protocol, parties each hold a part of the private key (typically using Shamir secret-sharing), and all receive the message as input, and jointly compute a signature of this message.
"Threshold" means that not all parties have to participate in the protocol in order to compute a signature, but only a subset of a predefined number of parties (4 in the example below) are necessary and sufficient in order to compute a signature:
For details about threshold signing applied to ECDSA signatures (the main signature scheme used by Bitcoin and ECDSA), see our research paper A Survey of ECDSA Threshold Signing.
The security goals of an MPC protocol are the following:
- Correctness: The result of the program must be correct.
- Privacy: Parties only learn the program's output.
- Fairness: If one party learns the output, then all parties do.
As a conclusion, MPC computes programs by involving multiple parties, where parties send and receive messages and perform some computations, and where parties' input values remain secret for other parties.
A smart just like a normal computer program, except that multiple computers run it instead of one computer.
Let's look at this simple program, where two variables x and y are initialized and then modified (imagine that they represent the token balance of blockchain accounts, for example). We can run such a program on a computer:
We can also run the very same program on multiple computers at about the same time:
Then we can have computers talk to each other to verify that they obtain the same result:
And then computers can remember this program, its input and output values, and make sure that all computers share the same memory of previous programs execution. To organize their memory over time, and remember in which order programs were executed, they can use database structures such as a chain of "blocks", where each block records one or more programs' executions:
And that's it, smart contracts compute programs such that multiple parties verify the correctness of the result, and jointly maintain the memory holding the input and output values.
Both MPC and smart contracts run computer programs, where the main differences are that
- With smart contracts, parties all know all the input values, whereas in MPC parties only know their own input values.
- Because of this difference, MPC parties must execute a protocol, whereas with smart contracts parties can directly compute the program independently from the other parties.
Of course, we only presented the fundamental functionalities of these techniques, without the nitty-gritty details. For an example of MPC software, see Taurus' threshold signing software library at https://github.com/taurusgroup/multi-party-sig. For an example of smart contract, see the CMTAT token contract, which we use in tokenization projects, at https://github.com/CMTA/CMTAT.
We hope you enjoyed reading this post !