Publicly Verifiable Backup of Signing Keys

This is the seventh blog in a series aimed at explaining the growing use of MPC and threshold signing to protect cryptocurrencies.

Check out the rest of the blog posts in this series:

Brief Recap

In the previous blog posts in this series, I described the use of MPC and threshold signing for protecting cryptocurrencies, along with its main features and properties. In this post, I talk about an additional crucial feature needed – secure backup.

The Importance of Backup and the Challenge with Threshold Signing Schemes

We have all seen news of people losing their cryptocurrency after losing their private signing keys. Unlike other financial scenarios, there is no redress and no one to go to in order to retrieve funds in case private signing keys are lost. As such, money should only ever be transferred to an address (associated with a signing key) after the signing key has been securely backed up. In the standard case, where the entire key is held by a single machine, that machine can simply back up the key (e.g., by encrypting it under a public encryption key, where the associated decryption key is stored in a physically secure location). However, what happens if the machine writes garbage to the backup? In such a case, funds will be transferred to the address at great risk. One could argue that this doesn’t really matter since if the machine is corrupted, then the key could be used to steal all of the funds anyway, and backup is the least of our problems.

However, in the setting of threshold signing, this is a serious issue. Recall that in this setting, the key is generated in MPC, each machine holds only a share of the private key, and some of the machines may be malicious. If the key is generated between two machines, and one is corrupted, then the key cannot be used for any unauthorized operation (since the honest machine would not cooperate) but the backup can be completely ruined by the single corrupted machine encrypting garbage instead of the valid key share. Likewise, consider a key that is generated with a 3-out-of-4 threshold quorum. If two out of the four parties are corrupted, then they cannot use the key since they do not constitute a quorum. However, destroying two parts of the key will make the key impossible to recover.

How is it possible to backup a key in this setting, ensuring that the backup is valid, without revealing the key?

Zero-Knowledge Proofs

A zero-knowledge proof is a fascinating protocol that enables a prover to convince a verifier of the truthfulness of a statement, without revealing anything beyond that fact. Zero-knowledge proofs have been studied since the mid 1980s and have a rich and beautiful theory. One area of interest where zero knowledge has been applied is that of anonymous credentials: in this setting, a user can prove that it has the right to use a service, without revealing anything about her identity and without linking that use to other services that she uses. Lately, there has been renewed interest in zero knowledge and its applications in the blockchain space.

Publicly-Verifiable ZK for Signing Keys

Given the existence of zero-knowledge proofs, the solution to the backup problem is simple. After the signing key has been generated, each participating party encrypts its share of the key (with an externally supplied public encryption key) and proves in zero knowledge that it encrypted the correct share. (I admit that it’s not really that simple. First, this has to be coupled with the key generation MPC protocol itself. Second, the proof has to be efficient enough to not significantly slow down key generation. Nevertheless, good solutions to this problem exist.)

It is important to note that the fact that the proof is zero knowledge ensures that nothing about the private signing key is revealed in the process. In addition, the private key for decrypting the backup can be stored offline in a physically secure location, since it is only needed in the case of a disaster where the signing key is lost. Finally, different key shares can be encrypted under different backup keys, if desired.

According to this, the flow of transferring funds (or opening a “wallet”) should be as follows. First, a new signing key pair is generated in MPC. Then, a backup is generated, and the validity of this backup is proven in zero knowledge. After the backup has been validated and stored (in multiple locations), the address associated with the public key is defined to be “active”, and funds can be transferred. This methodology provides strong guarantees against the threat of key loss. (Note that the private key/s for the backup encryption key/s need to be stored securely as well. However, this needs to be done once, and the same encryption key/s can later be used for backing up many signing keys generated via MPC.)

Another important point to note is that zero-knowledge proofs are typically interactive. This is problematic in this setting, since multiple parties may wish to verify the validity of the backup, and this verification may take place at different times as well. This is solved using the Fiat-Shamir heuristic, which yields publicly verifiable non-interactive zero-knowledge proofs.

Summary

Backup of private signing keys for cryptocurrencies is absolutely essential. When signing keys are generated in MPC, the generation of this backup when some of the parties may be corrupted is challenging. Fortunately, this can be solved using zero-knowledge proofs, that are both efficient to compute and verify, and publicly verifiable.