[UPDATE (April 3, 2014): We’ve found an error in our paper. In the threshold signature scheme that we used, there are restrictions on the threshold value. In particular if the key is shared over a degree t polynomial, then 2t+1 players (not t+1) are required to to construct a signature. We thought that this could be reduced to t+1, but our technique was flawed. We are exploring various modifications, and we will post further details when we have an update.]
The Bitcoin ecosystem has been plagued by thefts and losses that have affected both businesses and individuals. The security of a Bitcoin wallet rests entirely on the security of its associated private keys which can digitally sign transactions to irreversibly spend the coins in the wallet. In a new paper, we show how to use the cryptographic technique of threshold signatures to increase the security of both corporate and individual wallets.
Perhaps Bitcoin’s toughest security challenge is protecting Internet-connected wallets from insider threats. Such hot wallets cannot be kept in highly secure, offline cold storage. One good way for businesses to mitigate this vulnerability is to have hot wallets jointly controlled by multiple parties. This way, no party can independently steal corporate funds. In our paper, we show how to achieve joint control of wallets using threshold signatures.
The problem of implementing joint control is more important and more difficult for a Bitcoin wallet than it is for a traditional bank account. Whereas regular bank transactions have recovery mechanisms if fraud is detected, Bitcoin transactions are irreversible and their pseudonymity makes it difficult to identify thieves and attempt to recover stolen funds. Moreover, while large bank transactions typically require human action to complete, Bitcoin transactions–no matter how large–require only a cryptographic signature to authorize.
The threshold signature approach to joint control works like this: the private key controlling the wallet is split between devices belonging to n different participants such that any m of them can jointly produce a digital signature, while a group of less than m participants cannot. Crucially, in the process of producing a signature, the key is never reconstructed. As long as an attacker has compromised fewer than m devices, the key remains secure.
Our method for achieving joint control has significant benefits over Bitcoin’s “multi-signature” transactions. With multi-signatures, each party’s signature is published to the block chain, whereas threshold signatures allow participants to privately create a single signature which is indistinguishable from ordinary Bitcoin signatures. You can think of our solution as “stealth multi-signatures.” This improves anonymity and confidentiality while keeping transactions a constant size, reducing fees and providing flexibility to scale to an arbitrary number of parties.
We implemented a threshold signature protocol and have used it to demonstrate joint control over a Bitcoin wallet. We produced this transaction using a 9-of-12 threshold signature. If you click on the link to see the transaction details, you won’t see anything special; it looks like any regular transaction. That’s exactly the point!
Joint control is one of several security measures that can be built using threshold signatures. In our paper, we show that threshold signatures can be used as a primitive to build schemes for secure bookkeeping and secure delegation. One application that we’re particularly excited about is using threshold signatures to achieve two-factor security for personal wallets. In a follow-up post, we will elaborate on this application and discuss our ongoing efforts to build a two-factor secure wallet.
The main lesson from our work is that a spectrum of traditional internal financial controls can be translated to the Bitcoin world by novel application of cryptography. We hope that the security measures we’ve proposed will become standard in Bitcoin usage, and we are looking forward to working with developers and others who want to adopt our solutions.
We’d like to thank Greg Maxwell and Andrew Miller for providing useful feedback.
About “threshold deterministic address derivation” in section 3.3:
1) Maybe an advantage of multi-signature over your threshold signatures proposal is whether a single party has full knowledge of the salt, or as you put it, “it is important that the salt be secret”. For example in page 12 of a talk that I gave (http://www.cs.technion.ac.il/~idddo/detwal.pdf), consider the two-factor scenario where the user derives one sequence of pubkeys on her laptop, the other sequence of pubkeys on her smartphone, and creates P2SH addresses by combining each pair of pubkeys into a multi-signature script. In this scenario, the salt that’s need to create the subsequent pubkeys (i.e. scripts) isn’t known to a single party (=device), only the two parties together can generate the scripts. You haven’t elaborated much on the issue of keeping the salt secret, it’d be a pain for the parties to run secure-MPC that computes SHA512 to generate each newly derived pubkey… It’s good to keep the salt secret both for privacy as you mention in this section, but also for security, because if a single secret keys leaks and the salts aren’t secret then the other secret keys leak too (discussed at https://bitcointalk.org/index.php?topic=19137.0;all). Related to this, if the parties wish to do private-derivations (a.k.a. type-1) instead of homomorphic-derivations (a.k.a. type-2) as you do in this section, then secure-MPC would be needed there too.
2) You say in footnote 3 that hierarchical derivation is irrelevant to you, but if that’s the case then you don’t need to have a fresh salt (T_R as the reader may infer?) for each extended keypair, it’d be enough to have only a single master salt if hierarchical derivation isn’t used, i.e. there’s no need for extended keypairs.
1) In the design we had in mind, the salt is kept secret to the outside world, but it is known to each device. So each party can independently derive the public keys/addresses. No MPC is needed for this.
If the salt leaks but no key leaks (say the attacker compromised just one device), then the attacker can link the addresses (privacy breach), but still does not learn the keys (security).
In regards to the benefits of using secret sharing to distribute shares of the salt as opposed to having each device know it: Secret sharing would definitely improve privacy since an attacker who compromised one device would not learn the salt, and thus not be able to link the addresses. But, would it improve security? If we assume that the only way that an attacker learns the private key is by compromising t devices, then this same attacker would learn the salt too. So whenever a key is leaked, we assume that the salt too is leaked.
2) We only refer to the extended key-pair with regards to the master key. We said that it could be used to derive regular (non-extended) child keys, and we never actually use T_R. You are correct though that considering that we are only using a master salt, it would be clearer not to introduce extended keys at all and not to mention T_R. We’ll make that clearer. Thanks for the feedback!
1) Before the section on deterministic wallets, you have the section “Generating in advance”. If you use that, and a single secret key leaks (example: via side-channel attack when you’re signing with it), then all the other secret keys that you generated in advance remain secure. However, if you use deterministic wallets and the attacker managed to obtain the salt and a single secret key, then this attacker will gain access to all of the secret keys in your wallet because you use homomorphic-derivations (if you could have used private-derivations then the attacker will gain access only to all the secret keys derived after the leaked key, but private-derivations would require secure-MPC). Therefore, letting all the devices have access to the salt implies that the security (and privacy) guarantees are weaker. Because you’re using homomorphic-derivations, it’s probably a good idea not to give the users a false sense of confidence when they derive new addresses on devices that don’t even have access to the secret keys (i.e. the users might be too cavalier with exposing the salt), therefore two good practices are (i) not having full knowledge of the salt on a single device, and (ii) using private-derivation in the root of a particular hierarchical wallet branch, so that leakage won’t affect other (high-value) branches of the wallet. There’s a slide on “How to mitigate the risks of homomorphic derivations” in page 10 of the above detwal.pdf file. If you agree then you might wish to mention some of this in your paragraph on “Advantages of multi-signatures”.
2) Having a master salt means that there’s a single highly-sensitive piece of data that needs to be protected. Are you sure that hierarchical wallets are irrelevant to your interests?
3) About the “Flexibility” advantage in sections 3.2 and 4.5, could you please elaborate a little on revocation schemes and their practicality in this context? Is your reference on revocation schemes the most relevant one? (there’s also a line of work starting with “Efficient Trace and Revoke Schemes” by Naor and Pinkas).
Do you plan on publishing the code?
Absolutely. We’re cleaning up/reviewing our modifications to bitcoinj and we’ll release those soon. We hope to work together with the community instead of developing the code on our own.
From a skim, the scheme appears to require a trusted ‘dealer’ to split up the initial private key… and the dealer, retaining the key, would always have unilateral signing authority. Section 4.4 mentions “a protocol to deal shares without a dedicated dealer” – assuming interactive cooperation among authentic participants. Is this described anywhere? (Does a single bad-faith participant in that process obtain unilateral signing authority?)
Ah, yes, that’s an important point. We’ll revise the paper to make this clearer.
In short, if you want to convert an existing wallet to joint control, you do need the owner of the wallet to act as the dealer (naturally).
But if n participants want to create a new threshold-shared wallet, it’s straightforward to do this without a dealer. Players execute a “joint random secret sharing protocol” (same as step 2 of the threshold signing protocol in Section 2.3) to end up with shares of a random number which is the private key. Computing the public key from shares of the private key is another simple step.
To see why a single bad-faith participant cannot subvert the process, we need to consider the system design. I’ll explain w.r.t. a two-factor secure wallet for an individual. If Alice creates a 2-factor secure wallet this way, she’d have to look at the public key displayed by her computer and her phone, verify that the two match, and only then give it out as her address. If she does this, she can be sure that one of her devices could have been compromised the whole time and yet the bitcoins she receives at her new address are safe.