What is Multi-Party Computation (MPC)?

by Brian Spector, Chief Product and Technology Officer at Qredo

Published Jul 2, 2021 3:38:08 PM


Multi-party computation (MPC) is a cryptographic tool that allows multiple parties to make calculations using their combined data, without revealing their individual input.


Invented by Chinese computer scientist Andrew Yao, MPC works by using complex encryption to distribute computation between multiple parties.

In the context of digital assets, MPC can be used to replace individual private keys for the signing of transactions.  MPC distributes the signing process between multiple computers. Each computer possesses a piece of private data representing a share of the key, and together they cooperate to sign transactions in a distributed way.

Qredo is the first to combine MPC with a L2 blockchain, creating a  secure environment for flexible management and instant transfer of digital assets.

In the sections below, we explore MPC in a little more detail:  

  1. The evolution of cryptography

  2. Andrew Yao and the birth of MPC 

  3. Multi-party computation use cases 

  4. How does MPC protect private keys? 

  5. Qredo's consensus-driven MPC

  6. MPC FAQ 

  7. Is multi-party computation secure? 

  8. MPC vs Multisig

  9. MPC vs Shamir's Secret Sharing Scheme


The evolution of cryptography

Cryptography has historically been used to conceal information. All the way back to the Greek tyrant Histiaeus, who hid tattooed messages on the scalps of his slaves to prevent adversaries from intercepting wartime communications. 

Since then, encryption has evolved to serve ever more use cases. New cryptographic technologies like public key cryptography have emerged, enabling the modern web and providing even more complex ways to keep data secret.

Andrew Yao and the birth of MPC

The cryptographic breakthrough known as multi-party computation was born In the economic boom of the eighties, and has been in development for the last few decades; taking the protocol all the way from an intellectual curiosity to a powerful tool for building real systems:

  • 1982 – Pioneering Chinese cryptographer and computer scientist Andrew Yao introduces MPC with the Garbled Circuits Protocol, allowing two parties to jointly compute data without revealing inputs.

    Later that year, Yao sets ‘The Millionaire’s Problem’ to illustrate the importance of MPC:

    Frame 60Two secretive millionaires having lunch decide that the richest one should pay the bill. However, neither wants to reveal how much money they have. How can they work out who is richer and who will pay for lunch?

    Solving this problem requires a two party protocol . Add another millionaire to the mix and you need a multi-party protocol. 

  • 1987 – Computer scientists Oded Goldreich, Silvio Micali, and Avi Wigderson introduce the Goldreich-Micali-Wigderson (GMW) protocol, adapting two-party computation to multi-party.
  • 2008 - MPC goes live! The first large-scale commercial application of the technology is  used to  preserve privacy in sealed-bid sugar beet auctions in Denmark. In this type of auction, the highest bidder wins, but pays the price proposed by the second-highest bidder. MPC enabled the sugar beet farmers to place bids, without revealing what they were willing to pay to Danisco, the only Danish sugar beet processor at the time.
  • 2015 - Following an explosion of hacks and thefts of digital assets from hot and cold wallets, early crypto pioneers begin using MPC to secure private keys.
  • 2018 -  Qredo conceptualizes consensus-driven MPC, coupling multi-party computation with a decentralized Layer 2 network to securely manage digital assets— with no single point of failure.


Multi-party computation use cases: from auctions to genetic testing

As MPC has evolved over time, accelerating digitization has caused technology to spew out sensitive information at ever-faster rates. This has created the perfect storm, with MPC increasingly being used to protect sensitive data by acting as a digital non-disclosure agreement that controls which information is disclosed to whom. Examples include:

In genetic testing, MPC can be used to let people check their own genetic profile, without inadvertently revealing to governments or insurers how fast they metabolize caffeine, or how likely they are to develop diabetes.

In sealed-bid auctions, MPC can be used to ensure that each simultaneously submitted bid is kept completely private.

In sensitive research, MPC can be used to securely collect and analyze personal data—like financial and medical details—without forcing individuals to reveal sensitive information to a third party. 

As Boston University illustrates in the video below, rival rideshare organizations can use MPC to work together on issues of the collective good—without ever needing to share their confidential user data:

 


How does MPC protect private keys?

Unlike the use cases above where the goal is to prevent the sensitive data of multiple parties from being revealed, MPC can also be used to protect a single piece of sensitive data owned by one entity — like the private keys controlling digital assets. 

Without MPC,  private keys are typically stored in one place; either in a hot wallet (connected to the internet) or in cold storage (offline). In the terminology of system design, this creates a “single point of failure” that is an irresistible target for hackers. 

MPC can eliminate this Achilles' heel.  

Using a Threshold Signature Scheme (TSS) it is possible to create and distribute independently held shares in a private key such that no one single person controls the private key entirely.

These shares in the  private key material are distributed between nodes running a multi-party computation protocol.  As such, we can say that no whole, individual private key ever exists—only the distributed shares controlled by different people, spread across multiple nodes.

When a transaction needs to be signed, rather than invoking a single private key, the MPC process is triggered and each independent node cooperates to sign the transaction in a distributed way — much like a group of people singing in harmony to produce a special musical note which cannot be achieved by one voice alone.

This collective, decentralized digital signature is presented to the underlying blockchain network and authenticates transactions — just as a ‘traditional’ private key would have done. 


Qredo's consensus-driven MPC

MPC is on the verge of becoming a household name.

Big players such as PayPal,  BNY Mellon and Coinbase have invested in the technology, recognizing the significant role that it can play in hardening security by splitting private key material between multiple computers. But...

Distributing sensitive private key material is not enough. 

If the MPC nodes are centralized and under the control of a single organization, the assets remain vulnerable to internal collusion or external hacks. This is even more likely if the policy engines determining asset governance are run in vulnerable databases with private key material housed in hackable hardware enclaves like Intel SGX.

Unless the MPC nodes are truly distributed, the distributed signing process is just decentralization theatre, with all trust placed in a centralized MPC provider that controls the nodes, and could potentially censor transactions or succumb to internal collusion.

To achieve true decentralization and remove this risk, Qredo couples a unique implementation of MPC with a Layer 2 blockchain 

Each MPC node independently generates its own secret key material, and is protected from external attack in a tamper-proof enclosure. These are distributed between data centers in six financial hubs around the world, from London to Chicago and Hong Kong.

The coupled Layer 2 blockchain enables fine-grained control of access, and instant settlement between network participants: Instead of waiting for slow and expensive underlying chains, Qredo Network participants can instantly transfer 'digitized ownership rights' between them—creating instant cross chain and cross platform liquidity.

Discover Consensus-Driven MPC




FAQ: Everything you wanted to know and more about MPC


Is multi-party computation secure?

Even if a hacker somehow managed to break into a single MPC node, they would have no way of knowing the value of the collective output from all the nodes. To gain control of a wallet secured by MPC, they would theoretically need to launch a simultaneous attack on the total number of devices needed to sign a transaction.

For example, If the number of nodes is ten and the threshold needed to sign a transaction is five, then the attackers would need to break into six nodes and steal the key shares. This is made more difficult by proactive security measures  like key rotation that automatically move sensitive private key material between nodes.

Assuming the MPC is implemented on secure hardware, this need to attack simultaneously on multiple fronts makes MPC significantly more secure than other private key storage methods like hot and cold wallets which have a single point of failure. 

Furthermore, the flexible governance enabled by MPC reduces the chances that rogue personnel could access a wallet and run off with the assets.


MPC vs Multisig: What is the difference?

"I believe TSS (threshold signatures scheme) will reshape the landscape for wallets and custodian services. It is far superior to multisig." — CZ, Binance CEO

Frame 57

Frame 58

Multisignature wallets share a similar goal with MPC implemented using a Threshold Signature Scheme (MPC TSS): They both distribute signing power among multiple parties. 

The difference is that multisig wallets are secured by several distinct on-chain signatures generated by different private keys, while MPC relies on a single signature created off-chain.

Signing transactions off-chain with MPC has big benefits:

Speed. Transactions can be signed faster off-chain, because they don't rely on transacting with slow underlying blockchains.

Cost. Signatures computed off-chain do not incur network fees.

Privacy. Off-chain signing cannot be viewed on the public ledger. This prevents the chain of transactions being exposed—something which could reveal sensitive signing schemes and workflows to potential attackers. 

Compatibility. While multisig wallets are tied to a specific blockchain, MPC works on the standardized cryptographic signature algorithm (ECDSA) that can be implemented across 95% of blockchains.

Flexibility.  Offchain distributed signing allows for complex governance schemes that can be more easily configured to fit organizational requirements and comply with regulatory needs.

All considered, MPC offers a number of distinct advantages over other forms of crypto custody layered with multisig technology.


MPC vs Shamir's Secret Sharing Scheme

Shamir's Secret Sharing scheme (SSSS) is a cryptographic scheme that divides sensitive data like private keys into parts. Users can define the total number of parts, and a specific subset of parts required to recreate the whole.

Unlike MPC TSS, where signing is truly distributed and each signer directly signs the transaction, in SSSS the shares need to be reassembled on a single machine, or by a single trusted actor. This introduces a single point of failure.

 

More news and thought leadership from Qredo