An overview of Multi-Signature and Multi-Party Computation

Introduction

Traditionally, crypto wallets were associated with one owner who controls one public/private key pair. Public-key cryptography, in turn, depends on keeping the private key actually private. This creates a significant burden on the key holder, who often has to keep the key safe, accessible and retrievable. Hence, the criticism follows that the average user is potentially not the best guardian of their private keys.

‍

To tackle such criticism, an alternative would be to share the responsibility of the keys between multiple parties, a process that can increase safety and retrievability, but risks harming accessibility. Across crypto, two primary approaches have risen to handle such an option while holding accessibility nearly constant - multi-sig and multi-party computation.

‍

Multi-signature, on the one hand, creates multiple locks and requires all or a quorum of the parties to approve a transaction. The number of keys and how they are distributed can be customized based on the security requirements of the wallet — a savings account may require a larger majority than a checking account. Conversely, to hack the wallet and steal the funds, the attacker would need to obtain multiple independent keys, which is a much harder task.

‍

Multi-Party Computation (MPC), on the other hand, breaks a single key into shards, distributing them across locations and requiring a ceremony to put them back together using advanced math and zero-knowledge proofs. A new generation of wallets that leverage MPC has become popular due to its distributed key generation and malleable key management.

‍

In this blog post, we cover the basics behind multi-signature setup and math, from MultiSig designs to the current generation of MPC wallets, and their impact on the market.

‍

Multi-Signature wallets

In the second installment of our Wallet Wars trilogy blog posts, we briefly mentioned multi-signature wallets such as Safe or Armory. MultiSig wallets were natively supported during the early bitcoin development and are probably the earliest example of multi-party key management.

MultiSig shares the responsibility for the vault’s security by multiplying the locks. Instead of a single key that locks the vault, MultiSig creates a vault with multiple locks and keys and assigns the keys to multiple parties.

‍

Key generation

Multiple keys are generated for a corresponding vault with multiple locks.

‍

Signing

All or some of the keys are inserted into the locks

‍Pros:

• Highly secure since each lock is independent

Cons:‍

• Higher fees as the transactions need to be encoded with more bytes for the additional signatures.
• Changing the number of keys or the voting rule after wallet creation is difficult. Wallet owners have to construct a new wallet, redistribute the keys and enforce that no parties direct funds towards the old wallet — a tedious process.
• Because the wallet has to be bigger with a distinct design, it may attract unwanted attention.

‍

Multi-party Computation

MPC stands for multi-party computation. It refers to a set of cryptographic techniques that allows multiple parties – each holding their own private data – to evaluate a computation without ever revealing any of the private data held by each party.

‍

MPC enables key management in a distributed fashion by “breaking the key” into multiple parts – rather than a single owner having to be responsible for a private key, multiple parties can hold partitions of the private key, and some subset of them can come together to sign transactions.

‍

Shamir’s Secret Sharing Scheme (SSSS)

Adi Shamir, an MIT cryptographer, published a paper in 1979 called 'How to Share a Secret.’ The author outlined a method to split hidden data into n pieces where at least k pieces were necessary to reveal the original secret (where k is greater than n/2). This method was known as Shamir's Secret Sharing Scheme (SSSS). The mathematical intuition behind SSSS is that for a given k point, we can find a polynomial equation with degree (k-1). For example:  

• For the given two points, (x1, y1) and (x2, y2) we can find a linear polynomial ax + by = c.
• Similarly, for the given three points, we can find a quadratic polynomial ax2 + bx + cy = d.

‍

The idea is to build a polynomial with degree (K – 1) such that the constant term is the secret code and the remaining numbers are random. The constant term can then be found by using any K out of N points generated from this polynomial by using Lagrange’s Basis Polynomial. 

For example: Let the secret code S = 65, N = 4, K = 2. 

1. Initially, in order to encrypt the secret code, we build a polynomial of degree (K – 1).
2. Therefore, let the polynomial be y = a + bx. Here, the constant part ‘a’ is our secret code.
3. Let b be any random number, say b = 15.
4. Therefore, for this polynomial y = 65 + 15x, we generate N = 4 points from it.
5. Let those 4 points be (1, 80), (2, 95), (3, 110), (4, 125). Clearly, we can generate the initial polynomial from any two of these 4 points and in the resulting polynomial, the constant term a is the required secret code.

This protocol maps very cleanly for public key encryption. The private key is the constant term. Each party receives one of the four points. When a signature is needed, any two parties/points suffice to reconstruct the polynomial and deliver the constant term/secret code. In other words, the key is “broken into multiple pieces” and the pieces are sufficiently redundant that you don’t need all four to reassemble a functioning key. 

‍

Key generation

A regular-looking vault with a single lock is generated. A single corresponding key is generated, and split into multiple pieces. 

Signing

All or some of the key fragments are assembled into a functional key.

Pros:

• Similar fees to a regular transaction
• Private; doesn’t attract attention
  

Cons:

• There are times (when the key is initially generated, and when it’s reassembled for signature) when the key is in its full, complete functional state. These times, the key is hypothetically vulnerable to attack
• Once the private key is recombined and used for signing, it should be considered exposed and all funds held by the key should be moved, so if any participant who helped in recombining the key walks away with it, they can’t do anything meaningful. This is expensive, and not to mention, requires a lot of coordination of people
• Has to happen synchronously in order to be successful

‍

Threshold Signature Scheme (TSS)

Threshold Signature Scheme (TSS) addresses the shortcomings of both Multi-Sig and SSSS. TSS uses the same methodology as SSSS but distributes the key generation, so there is no single point of failure during key creation and key signing. As a result, each of the parties creates a key independently. They then combine forces to forge a modular lock where each module of the lock corresponds to one of the keys. This modular lock can be shaped so that even if only a subset of the keys is available, the vault can still be unlocked. In the end, the modular lock looks exactly like a regular lock.

To sign, each of the keys is used in turn to unlock the lock part of the way.  

Key generation

A regular-looking vault with a single modular lock is generated. Multiple corresponding keys are handed out to multiple parties.

‍

Signing

Each key is inserted and can turn the lock to some small degree. All or some portions of the keys are needed to fully unlock the modular lock.

Pros:

• There is never a full, functional key that can be targeted by hackers.
• The vault is indistinguishable from a regular, single-lock vault. The modular nature of the lock cannot be detected by an external observer, which means it does not attract extra attention.
• It has the same fees as a regular transaction.
• Wallet owners can change the number of key shares by requesting existing dependents to validate the new key distribution, giving more flexibility than multi-sig. 

Cons:

• Limited battle tested open source libraries on which threshold cryptography solutions can be built (as seen below, most companies in the space tend to be bought up)

‍

MPC growth and acquisitions abound

Over time, MPC and specifically TSS have gained popularity as a promising solution to the single user single key problem. One of the first consumer MPC wallets was pioneered by Israeli company KZen when they launched their self-custodial ZenGo wallet in 2019. ZenGo uses threshold signatures, with the two parties being 1) its own servers, and 2) the client’s phone or cloud storage.

‍

Fireblocks, an enterprise-oriented MPC firm, provides institutions with crypto infrastructure to manage their assets through MPC wallets and participate in the decentralized finance market. They experienced an eightfold increase in the speed and throughput of transactions using their new MPC-CMP algorithm, which preprocessed signatures to reduce signatory processing delays. Earlier this year, Fireblocks raised $550m from investors valuing the company at $8 billion.

‍

Japanese crypto exchange Liquid migrated its wallet infrastructure to use MPC technology after six years of service. The change had minimal disruption to users, only requiring them to start using the new wallet address that the exchange automatically generated. In April 2022, Liquid was bought by FTX for an undisclosed amount. 

‍

Meanwhile, the digital asset company Sepior provided users with a Do It Yourself (DIY) MPC wallet implementation where users and institutions could configure their wallets depending on their transaction latency, throughput, and scalability requirements. In July 2022, blockchain node infrastructure provider Blockdaemon acquired Sepior.

‍

The MPC acquisition spree extended into this year when several established crypto firms acquired MPC wallet providers which had a sizable customer base: PayPal acquired Israel-based start-up Curv, which provided enterprise-grade MPC technology; Gemini purchased MPC technology developer Shard X; Coinbase bought Unbound Security; USD Coin issuer Circle took over crypto infrastructure start-up Cybavo.

‍

The crypto world turns to MPC

MPC solutions are quickly gaining popularity (or are quickly acquired). Since the “vaults” and “keys” in the MPC paradigm are indistinguishable from regular ones, wallet providers can relatively easily switch from non-MPC to MPC protocols. Additionally, wallet providers might want to offer semi-custodial wallets that leverage MPC technology to split key management responsibility between a centralized party such as Coinbase or FTX, and the end user.

‍

That said, multi-sig wallets wallets have continued to remain a strong option for advanced security. With free offerings from Safe, and a growing eco-system on top of it, including companies like Multis, it is far from a won battle. It seems that we’re still in early days of the multi-sig and MPC days, with MPC providing a promising approach as a key method for securing wallets without the need to remember mnemonic phrases or the risk of losing access to one's single key.