Abstract: Bitcoin, started in 2009, is a digital currency in which all activity is publicly verifiable. Coins are controlled by spending policies expressed in Bitcoin Script, a simple stack-based programming language which supports hash preimage challenges and digital signatures. Included in Bitcoin Script is a basic form of threshold ECDSA signature: a list of public keys and a threshold is specified; the coins can then be moved if threshold-many valid ECDSA signatures are provided in sequence.

This threshold scheme is inefficient in terms of both signature size and verification time (both linear in the threshold size), which are the two most important considerations for cryptosystems designed for inclusion on blockchains. Being explicitly specified, they also represent a fungibility loss as threshold-controlled coins are visibly distinct from non-threshold-controlled coins. However, they achieve several practical goals which have proved difficult to preserve in more efficient threshold schemes: they are noninteractive; they require no persistent state during signing; they work in the plain public-key model and require no interactive key setup; their security follows immediately from the security of the underlying ECDSA scheme even when signing counterparties are considered to be adversarial.

In this talk we describe our work in developing a multisignature scheme for Bitcoin, called MuSig, which supports an extension to threshold signatures, over the last several years. We describe how consideration of both practical use cases and formal security models guided the evolution of our goals, and the unexpected tradeoffs that we found ourselves forced to make.

(Click the above image to see video on Youtube)