Threshold signatures and Bitcoin wallet security: A menu of options

Before Bitcoin can mature as a currency, the security of wallets must be improved. Previously, I motivated the need for sharing Bitcoin wallets using threshold signatures as a means to greatly increase their resilience to theft. For corporate users, threshold signatures enable cryptographically secure access control. For individuals, threshold signatures can be used to build two-factor secure wallets.

Our work was predicated on the assumption that there exist threshold signature schemes that are compatible with Bitcoin. Indeed, there are various threshold signature schemes that meet this requirement. But it turns out that there are a number of desirable properties of such schemes, and each alternative satisfies some subset of them. In this technical post, I’ll examine the desirable properties and how each available solution fares. While no scheme is suited to all possible applications, it appears that almost every use case can be satisfied by one of the schemes I describe.

Bitcoin uses ECDSA signatures to validate transactions. Aside from the private key, x, every ECDSA signature has an associated nonce, k. Computing the signature requires knowledge of the x, k, as well as k^-1, the modular multiplicative inverse of k. It is imperative that the signer does not reveal k or k^-1, as knowledge of either of these together with the signature in which k is used allows one to derive the private key. It is similarly crucial that a new nonce is chosen for each signature as one can learn the private key from two signatures that share a nonce.

For the threshold version of ECDSA, we must ensure then that k is not known to any of the signing parties. As knowledge of k implies knowledge of the private key, we must apply the same secret sharing techniques to k and k^-1as we do to the private key itself. Moreover, the requirement that a nonce must not be reused means that for each signature, participants will have to obtain shares of a fresh k as well as shares of k^-1.

Generating ECDSA signatures in a threshold manner has two difficulties. Firstly, as a new k is needed for each signature, we would ideally want participants to be able to generate shares of k themselves without a dealer. While generating shares of a random nonce is not very difficult, recall that parties must also obtain shares of k^-1, the nonce’s modular multiplicative inverse, and this of course must be done without reconstructing k. Obtaining shares of both k and k^-1 without a trusted dealer is one of the central difficulties in generating ECDSA signatures in a threshold manner. The second difficulty for creating a threshold version of ECDSA is that generating the signature requires obtaining shares of k^-1·x, the product of two secret shared values.

These difficulties are not unique to ECDSA; they apply to generic DSA over any other group, such as a multiplicative group of integers mod p as used in traditional DSA (DSS). While the literature is rather sparse on the topic of ECDSA signatures, it is quite rich on DSA, and most of the techniques presented can be modified to work for ECDSA as well. Today, I will discuss four such proposals and discuss the drawbacks of each one.

It is important to put the ensuing discussion into the proper context. ECDSA, the digital signature scheme used in Bitcoin, comes from the DSA family of digital signature schemes for which building threshold signature schemes is difficult. We will discuss various options for threshold ECDSA, and discuss their applicability to Bitcoin. Fundamentally, there is no reason that the Bitcoin protocol cannot also recognize other signature schemes that lend themselves to building more ideal threshold versions. In fact, we plan to introduce a Bitcoin Improvement Proposal (BIP) suggesting that Bitcoin include an option for a more threshold-friendly scheme.

Before discussing the four schemes, I will introduce some notation that will ease our analysis. Any threshold signature will have a security parameter t, which is the minimum number of participants that can jointly reconstruct (or even learn any information about) the key. By t’ we will refer to the minimum number of participants required to generate a signature. Clearly t’ will always be at least t, and ideally, we’d like t’ to equal t. We denote by the total number of players (participants) by n. In an ideal scheme, t will be able to assume any positive integer value less than or equal to n. Note that if t’ > t, then this latter property will be impossible to realize as n ≥ t’ > t.

The easiest way around the difficulties above is to introduce a trusted dealer. In this scheme, presented by Susan Langford in the context of threshold DSA, the dealer deals to each player shares of k^-1,  k^-1·x, and k·G (this is the only part of the signature that k is used, and it can be precomputed and shared as it does not require knowledge of the message). A trusted dealer will initialize the signers and deal them shares for many k. Once they are dealt these values, the parties can generate signatures in a threshold manner without further help from the dealer.

This approach has both pros and cons. The most obvious downside is the requirement of a trusted dealer. In the Bitcoin context, this is sensible when transferring coins from existing non-thresholded address in which some party already knows the entire key and thus can serve as a natural dealer. For organizations which keep funds in cold storage and regularly transfer them to hot storage, the transfer process can include trusted dealing of new shares, protected by a ceremony including physical security measures and HSMs. The major downside of this approach is that participants will not be able to generate a new shared address without a trusted dealer.  This means the dealer must deal many values, one for each signature that will be ever be computed. The participants must also ensure that they are synchronized so that the group never signs two messages using the same k. Despite these downsides, this scheme has some properties that make it quite attractive. Most notably, it is non-interactive. Each participant just publishes their partial signature, and anyone with the threshold number of partial signatures can combine them into a valid signature. Additionally, this scheme has the desired properties that t’ = t  and that t can take on any positive integer value less than or equal to n.

A second scheme, proposed by Gennaro et al., eliminates the need for a trusted dealer. Yet this is accomplished at some cost. Firstly, the scheme is interactive, requiring multiple rounds of exchanged messages among participants. Moreover, t’ = 2t - 1. This has two implications. Firstly, it means that “extra” participants will be required to generate a signature. By “extra” I mean that while we are only achieving security against t malicious participants, we require the active participation of 2t -1 of them in order to generate a signature. Secondly, this means that t ≤ (n + 1) / 2. This scheme will thus be unable to realize a 2-out-of-2 signature. In the Bitcoin context, this means that two-factor security cannot be implemented with this scheme. (The error in the first draft of our paper arose because we didn’t realize that t’ > t in the Gennaro et al. scheme.)

While the 2t - 1 requirement is not ideal, it does have some uses. If t is small relative to n, then the 2t - 1 requirement may not be too burdensome. Moreover, consider the case of a company that wants to use this scheme to share spending authority over a corporate wallet. The company can set up t - 1 hardware devices that store key shares and participate in all requests to sign. Now, t employees can jointly generate a signature. Of course, if a single employee manages to compromise all of the hardware devices, they can learn the key. But, together with physical security and tamper resistant hardware, this can be made quite difficult. Alternatively, the 2t – 1 requirement may be acceptable in some cases. Indeed, one major altcoin has already reached out to us requesting assistance implementing this scheme because they believe 2t - 1 is acceptable for their purposes.

Mackenzie and Reiter proposed a scheme specifically for the 2-out-of-2 case. While this scheme is interactive, it is ideal in that it requires no trusted parties and allows participants to jointly generate keys. We are in the process of adapting this scheme to ECDSA with the goal of offering strong two-factor security for Bitcoin. For the rest of this post, we will assume that MacKenzie and Reiter can be made compatible with ECDSA. While we have partially verified this and believe it likely to be the case, there is still work to be done before we can claim this with certainty.

Lastly, another method is to incorporate generic secure multiparty computation to achieve a threshold signature scheme with ideal properties. For the two party case this will use Yao Garbled Circuits, and similar circuit-based schemes exist for the case when more than two parties are involved. These protocols are all interactive, but more fundamentally, the amount of data that would need to be transferred during this interaction is quite large. We’ve put significant work into writing circuits for the 2-out-of-2 threshold signature, and we will describe this work in detail in our modified paper. At this point, however, we believe that due to the data transfer requirements, the other schemes mentioned are strictly better candidates.

In the table below, I summarize the various schemes that I have discussed:

interactive trusted dealer trusted combiner limited number of signatures constraints on t (minimum that can reconstruct key) t’(minimum that can generate signature) Langford t-of-n no yes no yes ≤ n t Gennaro et al. (2t -1)-of-n yes no no no ≤ (n + 1) / 2 2t - 1 Gennaro with t-1 hardware devices yes no no no ≤ number of non-hardware-device players t non-hardware together with t-1 hardware MacKenzie and Reiter 2-of-2 yes no no external combiner (one party is designated combiner) no 2 2 Using generic MPC (circuit-based) yes and large amounts of data will need to be transferred no no no ≤ n t

In summary, there are good solutions for both corporate wallets and two-factor wallet security for individuals. In the former case, if the “extra participants” requirement is acceptable then the Gennaro et al. scheme is probably the way to go. Otherwise the Langford scheme is a good option as long as a secure setup/dealing process can be established. For two-factor security, Mackenzie & Reiter seems close to ideal; the Langford scheme is also reasonable, but requires that wallet generation be done on a device that can be guaranteed to be secure.