The term Multi-Party Computation (MPC) has been growing steadily in prominence within the Web3 sphere, and it's playing an integral role in new wallet technologies that are paving the way for widespread Web3 adoption.

Regular web users often find managing client-side key-pairs for web platform interactions to be a complex task. This complexity can be better understood by examining two common web interactions: login and payment.

The former swaps traditional username and password protocols with a blockchain account managed by dedicated software, while the latter pivots from standard credit/debit card payment to using an alternative currency. These significant shifts can potentially pose barriers to adoption, making it more difficult for new users to transition to Web3 platforms.

Therefore, the introduction of innovative wallet solutions has become pivotal to navigate these obstacles. The goal here is to emulate the familiar user journey of Web 2.0 while maintaining the independence characteristic of Web3.

This is where MPC enters the picture. At its most fundamental level, MPC involves a diverse group of entities participating in a protocol to achieve a shared objective.

For an in-depth explanation of MPC, please refer to this article. However, to summarize, there are three crucial elements we need to understand:

1. The diversity of the involved parties and their differing interests is critical to ensure the security of the computation. Many MPC protocols, depending on the specific use case, are resilient against potential malicious activity by a portion of the participants. Thus, it's crucial that a majority of the participants in an MPC remain honest and refrain from colluding with any ill-intentioned parties.

2. The protocol, or distributed algorithm, outlines a series of operations that each party must adhere to in order to achieve the collective objective. Such protocols typically derive from scholarly research, with their properties rigorously tested and peer-reviewed by experts in cryptography and distributed algorithm disciplines.

3. The common purpose is the expected outcome of the protocol. This might be the generation of a key-pair, the reconstruction of a private key, the production of a random value, and so on.

The usage and implementation of these elements can vary widely, not only based on the intended purpose but also according to the specific circumstances and trust assumptions concerning the interacting entities. A significant portion of MPC protocol implementations are designed specifically for distributed and decentralized key-pair management. Hence, we'll explore a few concrete examples of these MPC implementations to better illustrate the points discussed above.

Key Backup

The case of key backup is rather straightforward and isn't typically classified as an MPC solution. However, it utilizes the essential mechanism of partitioning a secret across a diverse group of parties, making it worthy of consideration.

Here, a user who already owns a key pair desires to create a backup to safeguard against potential loss of the private key. Considering the possible high value of key pairs, the user is understandably reluctant to entrust a single service with a duplicate of their key. Instead, the user deploys a secret sharing algorithm to divide the private key into several parts — let's say n parts. Out of these, a subset — let's call it t — is needed for reconstruction.

Should the user decide to rebuild the secret, they must identify themselves to at least t parties, secure the corresponding secret shares, and the private key can then be pieced together using the reconstruction algorithm.

Even though multiple parties are jointly involved towards a shared objective, there isn't a distributed algorithm in place that the entities collectively execute to achieve this goal. In reality, the user is the sole active participant in this setup, acting as both the dealer and the assembler of the secret. This approach leaves the shareholders with no responsibilities beyond simple share custody.

Distributed Key Generation

It's essential to generate a key pair in a cryptographically secure manner to guarantee the safety of the wallet. Even when a single machine is involved in the process, different mechanisms may be put in place to ensure private keys are effectively generated at random and immediately put under custody.

Such requirements become even more important when multiple entities are involved in the generation process. In contrast to the key backup situation, the presence of a pre-generated secret supplied by a dealer is untenable. The reasoning behind this could be manifold, such as the need to generate a public key for encrypting data that should only be decrypted after a mutual agreement is established, or ensuring a private key exists but cannot be used without collective approval.

Several projects have already provided working, usable examples for this use case:

• Zcash is a privacy-focused cryptocurrency built on zkSNARKs. A critical aspect of preserving the chain's anonymity and privacy features involves generating a public key for which no entity holds the corresponding private key. In order to accomplish this, the Zcash team initiated what they referred to as Ceremony. This involves 90 different entities and facilitates the decentralized generation of this key pair, producing the public key while ensuring the corresponding private key was never even computed.

• EthDKG, funded by the Ethereum foundation, was set up to exhibit the applicability of elliptic curve addition, multiplication, and pairing within the Ethereum Virtual Machine. Given a heterogeneous set of parties, EthDKG provides a general way to generate a key-pair in a decentralized way assuming that any party can cheat and deviate from the protocol at any time. Both the total number of the parties n and the threshold to reach to reconstruct the secret t have no particular restrictions, except that n > t. The codebase includes reusable Solidity smart contracts, benchmarks and scripts to leverage the work in different projects.

• OKX threshold-lib, which underwent an audit process with CertiK, incorporates elements from the more comprehensive tss-lib of the BNB chain. It allows for the distributed generation of a key pair, easing the stringent constraints of EthDKG. Indeed, both libraries are custom-fit for user wallets and operate under the assumption of an implicit benign behavior from the involved parties. However, this doesn't imply that a deviation from the prescribed behavior by any entity would be able to influence the final outcome or violate the t-out-of-n rule. Every operation and piece of transmitted information can be cryptographically validated for legitimacy, and any malicious attempt would merely lead to the termination of the process, which could then restart with a new set of entities.

Distributed Signature Computation

Beyond key generation, there exists the necessity to utilize the created secrets. For wallets, the most critical application for a key pair lies in computing signatures. There are several kinds of signature schemes, and different blockchains may adopt different ones.

ECDSA

ECDSA is the signature used, among many others, in Bitcoin and Ethereum, which is why it's the first scheme to consider. The main challenge in distributing the computation of an ECDSA signature across multiple parties lies in the secure generation of a random number, which appears directly in the signature algorithm. A brief overview of such an algorithm can be found here. As the issue is not directly resolved by the signature properties, creative solutions were necessary.

The most commonly adopted solution for crypto wallets with distributed key pairs adheres to the Lidell17 design, which is specifically tailored for the simplified case of 2 out of 2 parties signing. In practical terms, given a secret shared between two parties (for which Lindell also offers a practical generation protocol), a valid ECDSA signature can be computed if both parties adhere to the protocol with respect to the same message to be signed.

The Lindell17 protocol can be broadened to a 2-out-of-n configuration by employing a different protocol for the distributed key generation, as exemplified in OKX threshold-lib and BNB tss-lib.

However, some practical limitations exist:

1. The threshold constraint, which is fixed to 2 actors of the set, remains.

2. Lindell17 relies on the Pailler homomorphic encryption scheme, which is based on pairs of prime numbers and can be costly to generate and use.

3. Costly zero-knowledge proofs are needed after the key generation and before initiating a signature session.

This is why alternative enhancements over such protocols emerged, like GG18 or updated works from Lindell and colleagues. However, to our knowledge, practical open-source implementations of these improvements are not yet publicly available.

EdDSA and BLS

These signature schemes are also fairly popular: EdDSA, in its ed25519 implementation, is used for Solana transactions, while BLS serves as the signature scheme for the Ethereum Beacon Chain.

Regarding threshold signatures, their implementation is quite straightforward due to the underlying mathematics and the absence of a discardable random value in their signature output. In practice, based on the equations that define the signatures in these schemes and given the local shares of each participant, a valid signature, with a few minor adjustments, is essentially the sum of at least t-out-of-n signatures computed using the shares of the parties as private keys.

Consequently, each participant computes a partial signature and the final, valid one is the aggregated result of these.

Conclusion

The algorithms detailed in this overview can be directly incorporated into dedicated browser extensions, or even securely embedded in web pages. This allows applications to guide users throughout their experience.

The threshold mechanism offers a layer of security: a compromise on the user's side or any other party's side rarely results in loss of funds or unauthorized operations.

Nevertheless, the accessibility and usability of such MPC protocols by users depend on the providers that implement them. However, they offer a strong foundation for making Web3 more accessible to the public.