A Guide to Multi-Party Computation (MPC)

In 2022, almost $4 billion were lost due to Web3 hacks, representing a 47% increase from 2021. Even worse, hacks have only continued to increase in 2023. In this environment, innovative solutions for security and privacy are needed for the continued success of the industry.

Multi-Party Computation (MPC) is one such innovation. MPC is a cryptographic protocol that enables multiple parties to jointly compute a function over their inputs while keeping these inputs private. It has applications in privacy-preserving data analysis, secure voting systems, and blockchain technology, among others.

MPC originated from the work of Andrew Yao all the way back in the 1980s. He presented the concept as a solution to the Millionaire's Problem, where two parties want to know who is richer without revealing their actual wealth. This foundation has led to numerous applications and advancements in MPC.

MPC is witnessing a surge in popularity with the rise of MPC wallets. These wallets utilize MPC to enhance security by ensuring that no single party has access to the private keys. There are several such wallets for popular blockchains like Ethereum, but a limited number for smaller blockchains. Martian Wallet, for instance, is pioneering the integration of MPC in the Aptos and Sui blockchains.

While Aptos and Sui are relatively new blockchains designed for scalability and accessibility, they have not yet developed native MPC wallets. Martian, led by co-founders Utkarsh Sinha and Siddharth Jain, is addressing this gap. Sinha writes that their focus on “technical excellence” helped them to “raise more than $3 million in funding and reach over 1.5 million installs.” Jain explains that they’re working on “Multi-Party Computation to make the Martian experience smoother and more secure.”

In this guide, we will look into the workings of MPC. We will implement a basic version of MPC using Python to provide a practical illustration of how it works.

Understanding the Mechanics of MPC

There are two key building blocks to MPC: Homomorphic encryption and zero-knowledge proofs.

Homomorphic encryption is a type of encryption that allows computations to be performed on ciphertexts, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. Later in this guide, we look at a code example where Paillier encryption is used, which is an example of homomorphic encryption. The encrypted inputs are added together without revealing their actual values.

Another concept used in MPC is Zero-Knowledge Proofs (ZKP). ZKP enables one party to prove to another that a statement is true, without conveying any information apart from the fact that the statement is indeed true. For example, in the Millionaire's Problem, a party can prove that their wealth is greater than a certain amount without revealing the exact amount.

An intuitive analogy

Imagine three friends who want to know the average of their salaries without revealing their individual salaries to each other. They can use MPC through secret sharing in the following way:

1. The first friend adds a large random number to her salary, which acts as her secret share, and tells the sum to the second friend.
2. The second friend adds his salary and another random number (his secret share) to the sum he received, and tells the new sum to the third friend.
3. The third friend adds her salary to the sum and tells the final sum back to the first friend.
4. The first friend subtracts the random number she initially added and tells the new sum to the second friend.
5. The second friend does the same, and now, the sum of their salaries is with the third friend.
6. The third friend can calculate the average by dividing the sum by three.

For example, friend 1’s salary is 100K. They add a random number 33K (secret share 1), so friend 2 gets told 133K. Friend 2’s salary is 40K. They add a random number 37K (secret share 2), and add that 77K to the previous sum of 133K for a total of 210K. Friend 3 adds their salary, 55K, for a total of 265K, and tells it to friend 1.

Friend 1 subtracts their random number 33K, to get 232K. Friend 2 takes 232K and subtracts their random number of 37K to get 195K. Friend 3 divides 195K by 3 to get 65K, which is the correct average of the 3 salaries (100K, 40K, and 55K).

At no point did any friend learn about the other friends’ salaries, and yet they were able to compute the average. The parties in an MPC protocol engage in rounds of communication, exchanging shares and using cryptographic methods to ensure the correctness and privacy of the computation.

The security of MPC protocols depends on assumptions about the computational power and behavior of the parties (honest, malicious). There are different flavors of MPC depending on the security model (e.g., semi-honest, malicious) and the underlying cryptographic assumptions (e.g., computational, information-theoretic).

In a semi-honest model, the parties follow the protocol but may try to learn additional information from the messages they receive. In the malicious model, parties may arbitrarily deviate from the protocol.

Robustness and fairness are also crucial properties for MPC. Robustness ensures that if the protocol is correctly executed, the output is correct. Fairness ensures that if any party learns the output, then all honest parties can learn it.

Practical Considerations and Applications

In practical applications, the number of parties, the complexity of the function to be computed, and the security requirements will dictate the choice of MPC protocol. Some protocols are more communication-efficient but require more rounds, while others may have higher computation costs but fewer rounds.

This technique has many applications, beyond Web3 wallets, such as:

• Privacy-Preserving Data Analysis: MPC can be used for securely computing statistics on combined datasets from different organizations without revealing individual data entries.
• Secure Voting: MPC can ensure that votes are accurately counted without revealing who voted for whom.
• Secure Auctions: Bidders can submit bids such that the highest bid is determined without revealing individual bids.
• Private Set Intersection: Two parties can find the intersection of their datasets without revealing any additional information about the sets.

Implementing MPC Using Python

Let’s consider a barebones example of implementing MPC with Python. If you haven’t already, you’ll want to install Python from the official website and set up a virtual environment to keep your project dependencies isolated.

Then, run the following code.

/# Sample Python code for implementing a basic MPC protocol using the phe library.
/# Note: This is a conceptual example and not intended for production use.
pip install phe
from phe import paillier /# Generating public and private keys
public_key, private_key = paillier.generate_paillier_keypair()
/# Two parties with their private inputs
input_party1 = 5 input_party2 = 10
/# Encrypting the inputs
encrypted_input1 = public_key.encrypt(input_party1) encrypted_input2 = public_key.encrypt(input_party2)
/# Sum of encrypted inputs (without knowing the actual values)
encrypted_sum = encrypted_input1 + encrypted_input2
/# Decrypting the result
decrypted_sum = private_key.decrypt(encrypted_sum) print(f"The sum of inputs is: {decrypted_sum}")’’’ 

This Python code snippet demonstrates a basic example of an MPC protocol. It uses the phe library to encrypt inputs from two parties, performs computation on the encrypted data, and decrypts the result without revealing the original inputs.

Takeaways

MPC has evolved as a fundamental cryptographic protocol for ensuring data privacy and security. With the rise of MPC wallets, users can achieve enhanced security for their digital assets. As blockchain technology continues to evolve, integrating MPC into new platforms like Aptos and Sui via Martian Wallet is a testament to the ongoing innovation in this space.

Please note that the code provided in this guide is for educational purposes and should not be used in production without proper security assessments.