New research: Better wallet security for Bitcoin
[Let’s welcome to Freedom to Tinker Steven Goldfeder, a first-year Ph.D. student in the Princeton computer security group. Today he will describe an exciting research project on Bitcoin security. — Arvind Narayanan]

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 to 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.

@IP Society