An overview of Multi-Party Computation (MPC), Threshold Signatures (TSS) and MPC-TSS wallets

15 min readJun 21, 2023

I. Introduction

Conventional wallets use a seed phrase and hierarchical deterministic (HD) structure to generate private keys, public keys, and on-chain addresses for signing transactions. This allows for easy key recovery using the seed phrase, but also means that the loss of a private key can result in permanent loss of funds or exposure to malicious third-party actors. As such, protecting private keys is crucial for safeguarding one’s cryptocurrency holdings, as traditional crypto wallets are typically owned and controlled by one individual.

To ensure the protection and accessibility of cryptocurrency holdings, a viable solution is to distribute key responsibilities across multiple parties or resources. This approach can significantly enhance the security of private keys, as it minimises the risk of permanent loss due to the misplacement or corruption of a single key. Additionally, in the event of an emergency, a multi-party key management system can improve the ability to recover lost keys. However, implementing such a system may also introduce added complexity, potentially making it more challenging to access keys when needed.

This article explores the fascinating world of digital asset security and examines the different techniques for distributing key responsibilities across multiple parties or resources, including the MultiSig and Secret Sharing Scheme. However, we’ll be focusing on cutting-edge solutions like Multi-Party Computation (MPC), Threshold Signature Scheme (TSS), and how they have given birth to secure MPC based TSS wallets that tackle the challenges of digital asset management. We’ll also take a closer look at ZenGo, a leading provider of MPC wallet solutions in the cryptocurrency industry, and analyse how it works.

II. Collaborative Security: A New Era of Shared Responsibility

Think of a private key as a key and a wallet as a vault. The vault typically has only one key that can unlock it. If attackers gain access to that key, they can steal the victim’s money and belongings. If the key is lost, the safe and its contents will remain locked forever. To lessen the risk of loss, the user of the vault may opt to make a duplicate key, but this elevates the risk of theft, or to share the responsibility of holding a single key to unlock the vault, but it is evident that in this case, some changes need to be made, either with the key, the lock, or both.

Classic Vault: One Key, One Lock / Source

Instead of worrying about duplicating the key, let’s shift our focus to changing it! Sharing the responsibility of private keys among multiple parties is a crucial step towards improving security.

With this approach, the risk of theft and loss is mitigated since attackers would need to steal multiple independent keys, and only a certain subset of the keys are needed to unlock the vault. In the upcoming sections, we will explore the evolution of solutions designed to distribute private key responsibilities among multiple parties.

III. MultiSig

MultiSig (multi-signature) creates a vault with multiple locks and keys, sharing the responsibility for its security. It can create a mechanism that requires only some keys to open the vault, making it more secure against key duplication. However, this requires a new type of vault, which can be more easily tracked, and incurs higher fees due to additional signatures needed for transactions.

MultiSig Vault: Two Keys, Two Locks. The vault is “heavier” and looks different‍ / Source

Pros: Better security, as the keys are never stored in the same place (if properly constructed).

Cons: Higher fees, less privacy, not universally supported.

IV. Secret Sharing Scheme

The Secret Sharing Scheme (SSS) shares the responsibility for the vault’s security by breaking the key into multiple pieces. This can be done in a redundant manner such that only a certain amount of key pieces can be reassembled into a functioning key. The key pieces can be assigned to multiple parties.

When using a Secret Sharing Scheme, the vault looks the same as a regular vault and therefore the disadvantages of MultiSig described above are resolved. However, SSS has a major drawback: When the key is generated initially or reassembled to unlock the vault, it is again stored (even if briefly) in its full form. This weakness provides a golden opportunity for attackers to get a hold of the key.

SSS Vault: One Key Split in Two, One Lock. The vault looks the same as Classic Vault / Source

Pros: Similar fees, privacy, and universal support as a regular transaction. When not in use, the key parts reside in different places.

Cons: When created and used, the key is present in its complete form and thus susceptible to stealing from a single place.

V. ✨ Let the magic happen! ✨

Can we code a solution that delivers the rewards without incurring the risks?

Can we get a system of true multiple keys in which the keys are ALWAYS separated and NEVER meet each other, but the vault still has only one lock so it looks the same as a regular vault?

Yes, We Can. That is exactly what Threshold Signatures do. Threshold Signatures are based on the cryptography field of Multi-Party Computation (MPC). In a way, we can think of Threshold Signatures as the child of SSS and MultiSig, inheriting the best qualities of its parents.

1. Intro to MPC

In essence, MPC is a software solution that facilitates collaboration between multiple parties to achieve a common goal, without the need for any party to disclose their data to the others.

Secure multi-party computation (MPC) enables a group of independent data owners who do not trust each other or any common third party to jointly compute a function that depends on all of their private inputs.
- Secure Computation, Wei Jiang

Deeper, MPC (Multi-party computation) is a cryptography technology utilised for key management on the blockchain. 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.

The simplest use case of MPC is allowing two (or more) parties to jointly compute a function output without revealing their inputs. For example: Using MPC, a group of friends can securely calculate their average salary (“output”), without revealing how much each of them gets (“inputs”).

There are three main properties of multi-party computation :

1. Correctness: the parties involved in multi-party computing initiate computation tasks and perform collaborative computation through an agreed secure multi-party computation function. The output produced by and algorithm is correct (as expected).

2. Privacy: each party must ensure that their secret inputs are independent and that no local data is disclosed during the computation.

3. Decentralisation: a decentralised computing model is offered with total equal of each participant, and no privilege for any participant or third party.

2. Intro to TSS

Threshold Signatures (TSS) allows parties to share the capability of digitally signing messages.

Threshold Signature Scheme (TSS) is a cryptographic primitive for distributed key generation and signing. The use of TSS in blockchain clients is a new paradigm that can provide numerous benefits, especially in terms of security. In the broader sense, TSS can influence the design of key management systems (such as crypto wallets) and lead the way for native support in DeFi use cases. Having said that, TSS is still a new technology, so the risks and limitations should also be considered.

Threshold signatures require a subset of parties authorised to produce signatures on behalf of the group. The message is only considered signed if a threshold (t out of n, t = threshold of signers, n = number of total signers) of signers sign off on the message.

3. MPC based Threshold Signatures

The MPC-based threshold signature scheme divides the private key into many “fragments” in some way, and these fragments are held by multiple parties. When a signature is needed, the multi-party computation ensures that these fragments can directly generate a legitimate signature without putting them together. “No need to put it all together” means that the real private key is never and does not need to appear.

With Threshold Signatures, each of the parties creates a key independently. Then they forge the vault’s lock together, in a modular way, in which each party shapes a part of the lock that corresponds to its key. Eventually, at the end of this process, a vault with a single modular lock is created that corresponds to each of the keys.

The vault is indistinguishable from a regular, single-lock vault. The modular nature of the lock cannot be detected by an external observer.

Threshold Signatures Vault: Two Keys, One Lock. The vault looks the same as Classic Vault / Source

Pros: The different keys never meet each other, the Threshold Signatures vault is indistinguishable from a regular vault and hence universal, and it has the same privacy and cost (fees) as a regular vault.

Cons: The interactive nature of the processes of shaping the modular lock and the unlocking process requires that all of the parties be present during the action (as opposed to MultiSig in which each of the parties can sign asynchronously). The shaping process is harder on performance, but due to recent advancements in this field very much feasible.

VI. MPC based TSS Wallets

MPC wallets remove the single point of failure by using a Threshold Signature Scheme (TSS). Under this paradigm, we create and distribute shares of a private key such that no one single person or machine controls the private key entirely — this process is called Distributed Key Generation (DKG).

“A MPC-powered wallet can support anything and everything a normal self-custody wallet can. Not just sending, receiving and trading, but also using dApps, DEXes, storing and trading NFTs, voting in governance, yield farming, web3 games, etc.”
Pete kim — Coinbase

None of the parties ever hold a complete private key. Instead, they each hold a piece. The parties must always work together to create a public key (which is cryptographically derived from all shares of the private key) and signatures of transactions.

MPC wallets enable parties to share the responsibility of signing and encrypting data without any single party holding a complete private key. Cryptographic applications use multi-party computation (MPC) to generate digital signatures or decrypt data without sharing private inputs.

TSS-based wallets, also have a nice security feature, which is enabling of private key rotation without changing the corresponding public key and blockchain address. Private key rotation, also known as proactive secret sharing, is yet another MPC protocol that takes the secret shares as input, and outputs a new set of secret shares. The old secret shares can be deleted and the new ones can be used in the same way.

Such a structure adds a time dimension to the security, which means an attacker must be at multiple locations at the same time to attack a threshold wallet. Combining secret shares before rotation and after the rotation will give the attacker no extra power if they want to forge a signature.

MPC based TSS wallets have the ability to implement multiple recovery techniques to enable users to regain access to their wallets in the event of a loss. The specific combination of recovery techniques implemented in a wallet is dependent on the wallet’s design and security needs. In this article, we will explore the backup model utilised by the ZenGo wallet.

Pros:

Improved Security: An MPC-based TSS wallet provides improved security as private keys are never fully exposed or stored on a single device, reducing the risk of theft or hacks.
Increased Privacy: With MPC-based TSS wallets, the private key is never reconstructed on any one device, which provides enhanced privacy and anonymity.
User-Friendly: MPC-based TSS wallets can be more user-friendly and accessible than other types of secure wallets, as users do not have to manage their private keys themselves.
Distributed Trust: As MPC-based TSS wallets use multiple parties to sign transactions, they promote distributed trust, reducing the reliance on a single trusted entity or third-party.

Cons:

Technical Complexity: MPC-based TSS wallets can be technically complex and may require a higher level of technical knowledge to use and understand.
Limited Choice: MPC-based TSS wallets may have limited cryptocurrency support compared to other wallets, making them less flexible for users.
Network Dependence: As MPC-based TSS wallets require multiple parties to sign transactions, they are dependent on a reliable network connection and may be slower than other types of wallets.
Limited Adoption: Due to their technical complexity and limited support, MPC-based TSS wallets have not yet been widely adopted, making them less accessible to most users.

VII. ZenGo — An MPC based TSS wallet

Not Your Keys Not Your Crypto? Outdated.

The ZenGo (white paper) wallet is non-custodial (meaning ZenGo do not have any access or control of your funds) and keyless. Using threshold signatures, ZenGo have replaced the traditional private key with two independently created “mathematical secret shares” that never meet each other removing the one single point of failure. One share is stored on the customer’s mobile device and the other on the ZenGo server. Therefore, even if one of the shares gets compromised, the attacker won’t know the other one and your assets will still be safe.

The ZenGo system is a “two out of two” party ECDSA (the signature algorithm used by Bitcoin, Ethereum and others) threshold signatures system. The two parties are the secure ZenGo server and the ZenGo user’s mobile device that can jointly perform all needed cryptographic functions (like key generation, transaction signatures and transaction verification) while neither of the parties reveal their respective secrets.

We use a distributed key generation protocol to generate each secret key separately. That way, no party has access to the other’s secret. We also created a distributed signing protocol so that both shares are always required to sign transactions on the blockchain. These shares never leave the device that created them. Both protocols are based on the well-known Lindell protocol, which we modified for ZenGo. One of the modifications we made was to ensure that only the mobile device could initiate a transaction. That way, we can never access or move our customers’ funds. You can check and audit our open source implementation on GitHub.
To bolster the security of the system, we store the shares using the strongest native security technology available for both the server and the device (e.g. KeyChain and Secure Enclave for iOS devices). To make sure the customer’s share never gets lost, we encrypt it with a key generated on their mobile device. The encrypted share is sent to the ZenGo servers and the decryption key is synced to the customer’s personal cloud service (e.g. iCloud, Google drive). This prevents the ZenGo server from ever being able to access the client share.

As a fresh face in the ZenGo wallet world, you might be thinking, “Holy moly, these features are cooler than a snowman’s shades!” But don’t get too carried away, because losing one of the shares (client share or server share) is a real possibility if you accidentally delete the ZenGo app or misplace your phone, resulting in the client share going MIA. And let’s not even think about the nightmare scenario of ZenGo disappearing like a magician’s assistant, which would leave the server share Houdini-ing into thin air.

💡 Fear not! ZenGo has got your back with an epic backup system for both shares.

A. How ZenGo backups work: user side

The share stored on the customer’s device (the “Client Share”) can get lost. Your phone might get lost, stolen, or broken and if we didn’t have a proper solution then you could potentially lose access to your funds. ZenGo realised that the client share can’t exist solely on the customer’s device.

To prevent this issue, ZenGo introduced a backup process that basically stores the encrypted “Client Share” on the ZenGo server and the decryption key of the “Client Share” on the user’s personal cloud storage account (iCloud, Google drive, …) under a folder named “DO NOT DELETE ZenGo Backup”.

If a user loses their client share, they can recover their wallet by following these steps:

Re-install the ZenGo app on a new or old device.
Enter the email address associated with the wallet.
Confirm the email address using a magic link sent to the user’s email.
ZenGo detects that the email address is linked to an existing wallet and automatically starts the backup process by extracting the decryption key stored in the cloud service. If the key is not found, the wallet cannot be recovered.
After the key is extracted, the ZenGo app prompts the user to verify their identity using a 3D biometric face map.
Once the user’s identity is verified, the ZenGo app retrieves the encrypted client share from the ZenGo server.
With both the encrypted share and the decryption key, ZenGo application can reconstruct the customer’s share and restore the wallet.

You can easily verify this process — simply create an account on ZenGo, back up your account, deposit a small amount of funds, and delete ZenGo from your phone. Install ZenGo again, restore your account, and “Voila!”, your account is restored and your funds are accessible again.

B. How ZenGo backups work: server side

In response to this scenario, ZenGo designed a solution relatively similar in concept to Client Recovery, but without the need for ZenGo’s server to be operational. To the best of our knowledge, this is the first such solution in our industry. We call it “CHILL STORAGE™”.

ZenGo’s innovative solution involves creating a master encryption and decryption key for the server share, ensuring foolproof security, and every client gets an encrypted version of that server share (encrypted with the master encryption key). The master decryption key is then deposited in an established escrow service provider (EscrowTech), while a trustworthy law office (JRG), is appointed as a trustee. The trustee has a crucial role to play, regularly verifying and reporting on ZenGo’s “proof of life,” which comprises both legal and technical criteria, ensuring that your funds are always in safe hands.

Let’s now delve into the steps for effectively recovering the “server share”:

In the event that the Trustee finds out that ZenGo is non-functional, they have the authority to request the decryption key from the escrow provider.
After receiving the request, the trustee will proceed to post the decryption key to a specialised GitHub account. The process is carried out by actual humans, and various safeguards and checks are put in place to prevent any erroneous signals.
The ZenGo app keeps an eye on this repository, and once a valid decryption key is posted, it automatically enters into the recovery mode.
Once the app enters the recovery mode, the “server share” that corresponds to the “client Share” is revealed thanks to the decryption key and the encrypted version of the “server share” stored in the mobile device and the private keys are then computed. Users can then export these private keys to other wallets, enabling them to have complete control over their funds without relying on ZenGo servers.
When the ZenGo app enters the recovery mode, it decrypts the “server share” using the decryption key retrieved from the dedicated GitHub account and the encrypted “server share” stored on the mobile device. This reveals the corresponding “server share” for the “client share” and the private keys are then computed. Users can then export these private keys to other wallets, allowing them to have full control over their funds and not depend on ZenGo servers.

To ensure a seamless user experience, ZenGo conducted rigorous testing of the solution before its public launch. This involved simulating a key release with the trustee to verify the efficacy of the backup system. You can find comprehensive details of this validation test here.

Conclusion

To sum up, this article discusses the shortcomings of conventional cryptocurrency wallets and the necessity for advanced security mechanisms to safeguard private keys. It delves into Multi-Party Computation (MPC), TSS, and Threshold Signature Scheme (TSS) based wallets as innovative solutions to overcome security challenges for digital asset holders. ZenGo, a prominent provider of MPC wallet solutions in the cryptocurrency industry, is analyzed in detail. Additionally, a comparative summary table is presented that evaluates Conventional, MPC-based TSS, and MultiSig wallets based on several criteria.

Conventional Wallets VS MPC/TSS wallets VS MultiSig / Source

I hope you found this article informative and gained valuable insights into the cutting-edge solutions to the security challenges for digital asset holders. I would like to express my sincere gratitude to the amazing writers of the articles that I used as sources for this piece. Don’t forget to check out the links to the articles used and more in the last section. Lastly, a big thank you to my colleagues who reviewed this article and provided valuable feedback. Keep learning and stay secure!