Understanding MPC: Secure Multi-party Computation for Crypto Wallets

There are always new headlines about the latest and greatest technology, but oftentimes the greatest innovations come from concepts that have been around for many years that are contributing to new use cases.

Multiparty computation (MPC) is exactly that.

What is MPC?

Secure multiparty computation has been a general topic in cryptography (not cryptocurrencies but actual cryptography) since it was introduced by Andrew Yao in 1982, and has been studied extensively since its introduction. Yao’s theory became the basis for what is today a very established principle that we see being employed across many use cases.

Yao’s research introduced protocols for “secure computation” that allow mutually distrustful parties to jointly compute a function over their private data without revealing the data to one another (aside from the output of the computation).

That may sound like a mouthful, so let’s break down what that means.

Example

Let’s use a simple example to explain what multi-party computation is and why it is important.

Let’s say there are 3 friends: Alice, Bob and Carol. They are having a conversation and want to figure out the average amount of money they have in their bank accounts between the three of them. Of course doing this requires a very simple calculation of taking all 3 of their individual balances and then dividing them by 3 to find the average.

However, all three of them have different jobs and make different amounts of money, and they feel uncomfortable sharing with each other how much they have. In order to keep their balances anonymous and their friendship jealousy-free, they discuss their options:

1. They can recruit their friend Dan to help. They would each privately tell Dan how much money they have in their accounts and Dan would complete the calculation. The group would have to trust that Dan would calculate properly, not share their private information with anyone else, or make his own judgements about their financial situation.
2. They all tell each other how much money they have and do the calculation publicly. This is the exact situation they are trying to avoid.
3. They use a secure multiparty computation protocol.

Seeing as the group of friends were familiar with cryptography, they decide to use option 3.

But how would this work? Let’s say that the following are the amounts that each friend has in their account.

In order to keep everyone’s balances anonymous, each friend takes the amount in the bank account and comes up with a mathematical equation where the result would equal the amount in their account. Since Alice has $1000, she decides to use the equation 7235 + 3 — 6238 = 1000. She writes each of the 3 new numbers she has chosen onto 3 different pieces of paper and puts them in a bowl, so now there are 3 pieces of paper in the bowl with the numbers 7235, 3, -6238 on them. Bob and Carol do the same exact thing and the following is the breakdown of those numbers.

Now, with 9 numbers in the bowl, the friends shake them up to make sure they remain anonymous. They pull them out, add them up, and divide the total by 3 (because there are 3 friends) to find the average.

And voila! The 3 friends have successfully used a (very simple) multiparty computation protocol to find out that on average, they have $4,000 dollars in their bank accounts.

Why is MPC important

MPC protocols allows for mutually distrustful parties (the group of friends) to jointly compute a function (average their bank account balances) over their private data without revealing the data to one another.

When it comes to crypto wallets, this combination of efficiency and security provide a new backdrop for crypto operations, especially for organizations that require multiple people to have access to accounts and funds.

Above is an oversimplified example that shows how MPC technology can be used to complete just about any task. The structure can get extremely complex depending on the use case, but the ability to accurately and securely complete functions without sacrificing privacy is a massive shift in the way financial infrastructure has been previously built.

The alternatives in many software and financial solutions rely heavily on trusting third parties or put all of the weight directly onto individual users. MPC protocols open the door to replace the trusted third-party with a cryptographic protocol that has been proven secure.

Not all MPCs are created equal

It is important that whenever engaging with any protocol, MPC or otherwise, it is vital to perform due diligence to ensure your funds and your organization are safe.

At the base level, a protocol like this should guarantee the following two properties:

• Correctness: The output must be identical as if a trusted party had computed the function for them.
• Privacy: Parties should not learn anything beyond the output. This means that all the messages that the parties send or receive during the protocol interaction could have been computed from the inputs or outputs of the corrupted parties.

Any MPC protocol, at the very least, should satisfy the above requirements, and there are many organizations that now claim to have built their own secure versions of this. But, as any MPC protocol is designed to act as a trustless partner, it is important to note that they are not regulated and there is no broad standard for how they should be constructed or maintained.

With that said, the cryptography research community has established an understanding on where MPC is usable (surprisingly, for almost every task!), and most importantly, developed mathematical modeling for proving and analyzing the security of protocols.

Utila’s MPC

The foundation for Utila’s wallet platform is a state-of-the-art MPC that brings all of these properties together. Our MPC protocol has been expertly designed with the help of our world-class cryptography team, who has had their work referenced by some of the leading crypto brands around the world.

Built on a sound mathematical foundation, we have been able to add a premier layer of usability that gives organizations a sense of calm, while empowers them to interact with their wallets numerous times a day.

Utila’s proprietary MPC protocol is designed to allow end users the flexibility to sign transactions and complete necessary operations as soon as they need to. By building UI across both desktop and mobile devices, users can operate when and where they need to.

Utila’s MPC protocol is built to accomplish 3 main tasks:

1. Key Generation
2. Transaction Signing
3. Key Refreshing

Key Generation

Utila uses its state-of-the-art MPC protocol to generate the secret key (often referred to as a ‘private key’), which is used for signing transactions. If you are new to crypto, check out this video on public and private keys.

Using Utila, when a wallet is created, a single virtual secret key is implicitly generated and immediately split up into shares and distributed among the predetermined devices. This means that the secret key never exists in its entirety in one place at any point in its lifetime.

As the protocol runs, a secret key is generated, while no party gains access to it. Each party will receive a share of the secret key, similar to what Alice, Bob or Carol did to calculate their average of balance. For instance, let’s say that the secret key is 1000. Alice learns her share is 7235, Bob learns his is 2, and Carol learns hers is -6237.

When added together, the shares are able to reconstruct the secret key (7235 + 2–6237 = 1000). No single party knows the secret (1000), and even when 2 out of the three parties combine their shares, they can not learn anything about the secret key.

Just like the equations that the friends came up with in the previous example, the shares look completely random and reveal no information about the key itself.

Transaction Signing

Every transaction initiated within a crypto wallet needs to be signed by the wallet owner for it to complete. So how does a transaction get signed when the secret key is split amongst many different parties?

The MPC protocol must communicate the public input, which in this case is the transaction, to every party that holds a share of the secret key. The protocol virtually reconstructs the secret key from the distributed shares, and signs on the public transaction. This can only happen is each party agrees to the output (signing the transaction).

Again, the secret key never exists in its entirely in one place at any point of time and during this process the parties learn nothing, except for the output — which here is the signed transaction.

Key Refreshing

Periodically, the parties will run a “refresh” process in which they generate new shares of the secret key. In this task, the secret key does not change, since it is still the same wallet with the same public and private keys. The shares of the secret key will change, but they will still match the same secret key.

This type of task is an added security measure to an already secure process. A key refresh might be necessary if one or more of the devices containing shares have been compromised and the shares contained on those devices have been exposed. Once a refresh has completed, those compromised shares are no longer useful to the adversary and they must again start from zero. This provides a very robust security protocol for the key, because in order for an adversary to gain control of a secret key, they must compromise each device simultaneously within a very limited time window.

This type of proactive security makes it virtually impossible for malicious actors to successfully gain access to your secret key.

Conclusion

MPC technology can be complicated to understand and it has lent itself to being a buzzword in the crypto industry. But, with diligent research and expert construction, it is a tool that will be a staple piece of infrastructure for a long time.