Today we are pleased to release our paper presenting a new ECDSA threshold signature scheme that is particularly well-suited for securing Bitcoin wallets. We teamed up with cryptographer Rosario Gennaro to build this scheme. Threshold signatures can be thought of as “stealth multi-signatures.”
Previously, I motivated the need for threshold signatures to increase Bitcoin wallet security. For individuals, threshold signatures allow for two-factor security, or the ability to split signing control between two devices so that a single compromised device won’t put your money at risk. For businesses, threshold signatures allow for the realization of access control policies that prevent both insiders and outsiders from stealing corporate funds. As I mentioned previously, and as discussed at length in our paper, Bitcoin’s built in multisignatures are insufficient as they have serious anonymity and confidentiality drawbacks.
I also discussed why building a threshold signature scheme that is compatible with the ECDSA signature scheme used by Bitcoin is so difficult. Our previous work presented a toolbox of options, none of which is perfect but which we believed were a useful starting point. Since that post, we had discussions with businesses that want to implement our techniques, and it turned out that they wanted the best-of-both-worlds properties from the crypto. In particular, they wanted a scheme that required no trusted precomputation, and in which they could realize a t-of-n access control for any t <= n.
These discussions motivated us to go back to the drawing board and see if we could build a scheme that fit the need of these businesses. We realized that we could generalize a well-known 2-out-of-2 signature scheme of Mackenzie and Reiter to an n-of-n threshold signature scheme. Once we have an n-of-n scheme, we could combinatorially build an t-of-n scheme. We present the entire scheme in our paper together with applications, and we demonstrate how this scheme meets the security needs of Bitcoin based businesses and exchanges.
We are confident that threshold signatures are an essential component to improving Bitcoin security without compromising on confidentiality and anonymity. To jumpstart the process of bringing our techniques to use, we have also built a prototype implementation of a two-factor secure wallet. We built a desktop client by modifying Multibit as well as an Android app. A user initiates a transaction on the computer, and the computer then begins the threshold signing protocol with the phone. The phone will show the user the transaction details and will only proceed with the transaction with the user’s explicit approval. The computer and phone use QR codes to initially pair and for all subsequent sessions they communicate over the local Wifi network. This video shows how it all works:
We have released the code for our two-factor implementation, and we welcome community involvement to bring our prototype implementation to production quality as well as to build a reference implementation of our multiparty protocol.
So each participant holds multiple shares, one for each possible subset. Do they have to identify which other signers are in the subset before signing in order to choose the correct share? And, back to my original question, how can this be set up with no dealer so that all subsets achieve the same G-DSA value?
For the t-out-of-n threshold scheme, using a dealer-less protocol to distribute share of the private key to each subset of signers, how does each subset end up with the same G-DSA key?
sorry, think I might have misunderstood what you were proposing, but if you do use a dealer-less protocol are there restrictions? i.e. you need n=2t+1
No, none of our protocols require n = 2t + 1.
ok, but I still can’t understand how each and every subset of t signers in the t of n case can produce the same G-DSA key when it is a multiplicative shared secret derived from the product of their individual secrets? How are you doing this? I can’t really understand how you do it with a dealer let alone without one?
For each subset of t, you will have a separate multiplicative share.
Non-technical person here. Is there a backup method or recovery path should the phone get lost, stolen, or fail?
See section 6.8 of the paper. The recommended backup method is to store a copy of each share separately in cold storage. This method will allow for recovery if either–or even both– the phone and computer is lost.
One could also use a 2-of-3 signature and store the third share separately. This single backup share will allow for recovery if either the computer or phone is lost (but not both).
How many signers can there be and if it can hold 100,000 signers, what would the side effects be (eg; slow transaction building, 1 hour to write the entire transaction?)?.
I remember reading an article suggesting this method could be used to allow for a decentralized network of thousands of nodes to agree upon the split of revenue throughout the entire network. I hope that can be achieved.
The number of possible signers ‘n’ can be as large as you like, but the number constructing any individual signature ‘t’ has to be relatively small.
So our particular signature scheme doesn’t allow the application of voting-via-signing by a decentralized network, but that’s because we were needed compatibility with Bitcoin’s signature verification. If you’re building a new application, you’d pick a signature scheme that supports efficient threshold signatures with large t and n, and those exist.
Funnily enough, this was the original question that motivated our inquiry, but at some point we realized that security is a burning problem in Bitcoin and threshold signatures can help, so we pivoted.
Is this a robust threshold scheme?
Robustness was not a goal here, and in many of our applications it doesn’t make sense. Consider the 2-of-2 case for example. There are only 2 players and we require the participation of both of them, so clearly if one of them is malicious, the signature will fail. Our t-of-n protocol is built using t-of-t combinatorially, so again each t-of-t is not robust as you need the participation of every player. But for the t-of-n case, with a small t, you can isolate a malicious player by choosing a subset without them.
Can you provide better test vectors ? I am interested into building that in NBitcoin, but I will never do it if there is almost no test vectors.