Multi-Party Computation (MPC)

What Is Multi-Party Computation?

Multi-party computation (MPC) is a subfield of cryptography that enables a group of parties to jointly evaluate a function over their private inputs while keeping those inputs secret from each other. Each participant learns the output of the computation but gains no information about any other participant's input beyond what the output itself reveals.

The concept was introduced by Andrew Yao in 1982 through the "Millionaires' Problem": two millionaires want to determine who is richer without revealing their actual net worth to each other. This seemingly impossible task is solvable with MPC. Yao showed that any function computable by a circuit can be securely evaluated by two parties using a technique called garbled circuits. Subsequent work by Oded Goldreich, Silvio Micali, and Avi Wigderson generalized the approach to any number of parties.

In cryptocurrency and blockchain systems, MPC has become foundational to modern key management. Rather than entrusting a single device with a complete private key, MPC distributes key material across multiple parties so that they can jointly produce digital signatures without ever reconstructing the full key. This eliminates the single point of failure that makes traditional wallets vulnerable to theft, loss, and insider attacks.

How It Works

MPC protocols vary widely in design, but they share a common goal: enabling collaborative computation while preserving input privacy. Three foundational techniques underpin most practical MPC systems.

Secret Sharing

Shamir's Secret Sharing (SSS), introduced by Adi Shamir in 1979, is the most widely used secret sharing scheme in MPC. It splits a secret into n shares using a random polynomial of degree k-1, where k is the threshold. Any k shares can reconstruct the secret via Lagrange interpolation, but fewer than k shares reveal absolutely nothing about it. This property is information-theoretic: it holds regardless of the attacker's computational power.

In MPC protocols, secret sharing serves as both a data distribution mechanism and a computation tool. Parties can perform addition on shared values without communication (each party simply adds its local shares), while multiplication requires an interactive protocol. By decomposing any function into additions and multiplications over a finite field, secret sharing enables general-purpose MPC.

// Shamir's Secret Sharing: 2-of-3 example
// Secret s = 42, polynomial f(x) = 42 + 17x (mod 97)

share_1 = f(1) = 42 + 17 = 59
share_2 = f(2) = 42 + 34 = 76
share_3 = f(3) = 42 + 51 = 93

// Any 2 shares reconstruct f(0) = 42
// 1 share alone reveals nothing about 42

Garbled Circuits

Yao's garbled circuits protocol enables two-party computation by encoding a Boolean circuit as an encrypted truth table. One party (the "garbler") encrypts the circuit so that each wire carries a random cryptographic label rather than a plaintext bit. The other party (the "evaluator") decrypts the circuit gate by gate using the labels corresponding to both parties' inputs, learning only the final output.

Garbled circuits are particularly efficient for functions that can be expressed as compact Boolean circuits. They require only constant rounds of communication (typically just one after setup), which is advantageous when network latency is a concern. However, the circuit must be constructed and transmitted in its entirety, which can be expensive for large computations.

Oblivious Transfer

Oblivious transfer (OT) is a cryptographic primitive where a sender holds multiple values and a receiver selects one without the sender learning which value was chosen, and without the receiver learning the other values. In a 1-out-of-2 OT, the sender has two messages (m₀, m₁), the receiver has a choice bit b, and the receiver learns only m_b while the sender learns nothing about b.

OT serves as a fundamental building block for garbled circuits (the evaluator obtains input labels via OT) and for many other MPC protocols. Research has shown that oblivious transfer is both necessary and sufficient for general secure computation: any MPC protocol can be built from OT as a primitive, and any protocol that achieves MPC can be used to construct OT.

MPC for Digital Signatures

The most impactful application of MPC in cryptocurrency is distributed key generation and threshold signing. Rather than one entity holding a private key, the key is split into shares distributed across multiple parties. When a transaction needs signing, a threshold number of parties execute an MPC protocol to produce a valid signature without any party ever possessing the complete key.

Threshold Signature Schemes

A threshold signature scheme implements a t-of-n signing policy: any t parties from a group of n can jointly produce a valid signature, but fewer than t cannot. The resulting signature is indistinguishable from one produced by a single signer. Two major families of threshold signature schemes are used in practice:

• ECDSA-based MPC: required for legacy Bitcoin address types and most non-Bitcoin blockchains. Protocols such as GG18 and GG20 (by Gennaro and Goldfeder) enable threshold ECDSA but require complex cryptographic machinery including Paillier encryption and zero-knowledge proofs. Signing typically takes 4 to 8 rounds of communication.
• Schnorr-based threshold signing: enabled on Bitcoin by the Taproot upgrade. FROST (Flexible Round-Optimized Schnorr Threshold) and MuSig2 leverage the linear structure of Schnorr signatures to achieve threshold signing in just two rounds, with simpler security proofs and no need for homomorphic encryption.

The practical difference is significant: ECDSA-based MPC signing can take hundreds of milliseconds per signature due to the overhead of zero-knowledge proofs and encrypted multiplications, while Schnorr-based schemes like FROST complete in a few milliseconds under normal network conditions.

Distributed Key Generation

Before threshold signing can begin, the group must perform a distributed key generation (DKG) ceremony that produces key shares without any party ever seeing the complete key. Each participant generates a random polynomial and distributes evaluations to every other participant. The group's public key emerges from combining all contributions, but the corresponding private key exists only as distributed shares.

// Distributed Key Generation (conceptual)
// Each party i generates polynomial: f_i(x) = a_i0 + a_i1*x + ...

// Party i sends f_i(j) to party j over secure channel
// Party j verifies shares against published commitments
// Party j's final key share: s_j = Σ f_i(j) for all i

// Group public key: P = (Σ a_i0) * G
// Group secret key s = Σ a_i0 (never computed anywhere)

DKG is the most operationally complex phase of any MPC wallet setup. All n participants must be online simultaneously, exchange data over authenticated channels, and correctly verify each other's commitments. A failed DKG requires restarting from scratch.

MPC Wallets vs. Multisig

Both MPC wallets and multisig wallets distribute signing authority across multiple parties, but they achieve this through fundamentally different mechanisms. The choice between them involves tradeoffs across privacy, cost, flexibility, and trust assumptions.

The core tradeoff: multisig provides on-chain enforcement and auditability at the cost of higher fees and reduced privacy, while MPC provides efficiency and privacy at the cost of moving trust to the software layer. For a detailed analysis, see the research article on MPC vs. multisig custody.

Use Cases

MPC Wallets

MPC wallets are the most visible application of MPC in cryptocurrency. Key shares are typically distributed in a 2-of-3 configuration between the user's device, the wallet provider's server, and a recovery backup. This enables familiar authentication flows (biometrics, passwords) while ensuring that neither the user nor the provider can unilaterally move funds. If the user loses their device, the provider and recovery shares cooperate to restore access.

Major custodians and wallet-as-a-service providers use MPC architectures, including Fireblocks, Coinbase, and Fordefi. The approach has become the dominant model for institutional custody, where key shares are distributed across geographically separated hardware security modules (HSMs).

Threshold Signatures in Layer 2 Protocols

Layer 2 protocols use MPC-based threshold signatures to distribute trust across operator sets. Spark, for example, uses FROST threshold signing so that operators collectively manage on-chain UTXOs: one key is held by the user and the other is managed collectively by Spark Operators via FROST. No single operator has unilateral spending authority, and the resulting transactions appear as standard Taproot spends on-chain. For details, see the Spark Layer 2 overview.

Private Auctions and Sealed-Bid Protocols

MPC enables sealed-bid auctions where bids remain encrypted until all participants have committed. The auction outcome (the winner and winning price) is computed without revealing losing bids to anyone. This has applications in NFT auctions, on-chain governance votes, and MEV mitigation through encrypted transaction ordering.

Privacy-Preserving Analytics

Beyond wallets and signatures, MPC enables computations over sensitive data without exposing it. Exchanges can jointly compute aggregate trading volume or detect wash trading across platforms without sharing proprietary order book data. Compliance teams can perform KYC/AML checks by comparing customer data against sanctions lists without either party revealing their full dataset.

Performance and Tradeoffs

Communication Rounds

MPC protocols require multiple rounds of message exchange between participants. The number of rounds directly impacts latency and is a key differentiator between protocols:

• Garbled circuits: constant rounds (typically 1 after setup), but large data transfer
• Secret sharing protocols (BGW, SPDZ): rounds proportional to the circuit depth of the function being computed
• FROST threshold signing: 2 rounds for online signing (with nonce preprocessing, the online phase can be reduced to 1 round)
• ECDSA threshold signing (GG20): 4 to 8 rounds depending on the protocol variant

In practice, each additional round adds a network round-trip of latency. For geographically distributed parties (common in institutional custody), this means each round adds 50 to 200 milliseconds. A 2-round FROST signing session completes noticeably faster than a 6-round ECDSA MPC session.

Trust Assumptions

MPC protocols differ in how many parties they can tolerate being corrupt. The two main security models are:

• Honest majority (t < n/2): protocols like BGW achieve information-theoretic security but break down if half or more of the parties collude
• Dishonest majority (t < n): protocols like SPDZ and most practical threshold signing schemes tolerate any number of corrupt parties below the threshold, but require computational assumptions (the hardness of discrete log or factoring)

For cryptocurrency custody, dishonest-majority protocols are preferred because the threat model assumes an attacker could compromise multiple parties. FROST and modern ECDSA-MPC protocols operate in this model.

Preprocessing vs. Online Phase

Many MPC protocols split computation into a preprocessing phase (performed before the inputs are known) and an online phase (performed once inputs are available). Preprocessing generates correlated randomness that accelerates the online phase. For threshold signing, this means nonce commitments can be generated in advance, reducing the time-critical signing step to a single round of communication.

Risks and Considerations

Implementation Complexity

MPC protocols are among the most complex cryptographic systems deployed in production. ECDSA-based MPC requires Paillier encryption, range proofs, and multiple zero-knowledge proof systems. Subtle implementation errors can be catastrophic: in 2023, researchers discovered vulnerabilities in several widely deployed MPC libraries (including implementations of the GG18 and GG20 protocols) where flawed zero-knowledge proofs allowed an attacker to extract a party's key share. Thorough, independent auditing of MPC implementations is essential.

Vendor Lock-In

Most production MPC wallet solutions use proprietary protocols with no standard format for key shares or signing sessions. Key shares generated by one vendor's system typically cannot be imported into another's. This creates concentration risk: if the vendor ceases operations, users may face complex migration procedures. Open protocols like FROST (which has an IETF specification in RFC 9591) and emerging Bitcoin-specific standards like BIP 445 aim to address this problem.

Communication Requirements

MPC signing requires real-time, authenticated communication between the threshold number of parties. Network partitions, server outages, or a user's device going offline can prevent transaction signing entirely. This is a meaningful limitation compared to script-based multisig, where each signer can independently produce their signature offline and share it asynchronously via PSBT.

Off-Chain Policy Enforcement

In multisig, the blockchain enforces the signing policy: a 2-of-3 multisig provably requires two valid signatures. In MPC, the signing policy is enforced by the software, not the consensus layer. If the MPC implementation has a vulnerability, an attacker could potentially produce unauthorized signatures. Users must trust both the correctness of the MPC protocol and the integrity of all participating servers.

Key Share Security

While MPC eliminates the single point of failure of a complete private key, each individual key share still requires careful protection. Compromising one share in a 2-of-3 scheme means only one more share is needed to sign. Key shares should be stored with the same rigor applied to seed phrases: dedicated hardware, geographic distribution, and regular rotation via key refresh protocols.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.