Bitcoin, and related blockchains such as Blockstream’s Liquid, use the ECDSA signature algorithm to verify ownership and transfer of coins stored in the system. This was a technical decision apparently made in 2008 based on the widely-used and unpatented digital signature systems available at the time. However, ECDSA has some serious technical limitations. In particular, multisignatures and threshold signatures – signatures made by a quorum of independent parties rather than a single person – are very difficult to produce with ECDSA. ECDSA signatures have a complex algebraic structure that makes them inflexible and difficult to work with, forcing developers to use Bitcoin Script for applications such as cross-chain atomic swaps or Lightning, which could be implemented more compactly and privately using a more flexible signature scheme.
However, while the state of the art in digital signatures has advanced significantly since 2008, the alternative signature schemes described in the literature overlook many practical requirements for real-world usage. In particular, they often assume signers have complete control over how and when their keys are generated; that they always have access to perfect randomness; that they have persistent, reliable and secure memory. In practice, Bitcoin users often have restricted access to their keys, little control over the precise key generation mechanism, and no control over how external parties use the addresses that they generate. To address these concerns, we started an initiative to design a new signature scheme, and a significant practical engineering effort to implement it in a robust and antifragile way.
Introduction
In the first half of last year, in collaboration with Yannick Seurin and Gregory Maxwell, Blockstream cryptographer Pieter Wuille and I published a new multisignature scheme called MuSig. This multisignature scheme offered provable security, even against colluding subsets of malicious signers, and produces signatures indistinguishable from ordinary single-signer Schnorr signatures.
Since then, we’ve been turning MuSig from an academic paper into usable code, and this week we merged that code into secp256k1-zkp, a fork of secp256k1, the high-assurance cryptographic library used by Bitcoin Core, which we’ve extended to add Confidential Transaction support for Elements and Liquid.
As the Bitcoin community is exploring the use of Schnorr signatures in Bitcoin we hope that our code will eventually be merged into the upstream library secp256k1 used by Bitcoin Core and many other projects.
Our code produces signatures compliant with BIP-schnorr, and can also produce adaptor signatures, which could enable Lightning in scriptless script.
Why MuSig?
As we discussed last year, the cryptographic literature has many existing multisignature schemes, and a reasonable question to ask is why we needed to develop our own. The answer, in short, is that we had two requirements not yet met by any existing schemes:
- Short, constant-size signatures which look the same to verifiers regardless of signer set. In a blockchain system, verification efficiency is the most important consideration, and it doesn’t make sense to burden verifiers with the details of signer composition any more than is necessary to prevent theft. As a further benefit, MuSig signatures improve privacy since they hide the exact signer policy.
- Provable security in the plain public key model. What this means is that signers have full flexibility to contribute to a multisignature using ordinary keypairs, without providing any extra information about the specific way these keys were produced or are controlled. Information about key generation may be hard to provide in a Bitcoin context as individual signers have varied and restrictive key management policies. In addition a dependency on key generation details may interact badly with Taproot, a proposed Bitcoin extension in which public signature keys may have additional invisible semantics encoded in them.
Further, since announcing MuSig, we have learned that many published signature schemes, including an earlier unpublished version of MuSig, are actually insecure! We will explore this further in a future post, but for now it suffices to say that our work was cut out for us developing a multisignature scheme suitable for Bitcoin and Liquid.
Pitfalls and Safe API Development
Like all mathematical descriptions of multisignature protocols, MuSig as published assumes participants who have access to memory throughout the signing process which is persistent, easily updated, and can’t be “reset” to previous states by attackers. It also assumes signers have access to randomness sources that are indistinguishable from uniform. Unfortunately the real world is not so simple, and we spent a lot of effort designing an API which can be used in a wide variety of scenarios without the possibility of limited hardware or unstated assumptions leading to loss of secret key material.
MuSig signatures, just like Schnorr signatures or ECDSA, use in their construction a secret “nonce” which must be produced uniformly randomly. Any deviation from uniform, even by a single bit, can lead to secret key loss and stolen funds.
Our primary design goal was to create a misuse-resistant API without sharp corners, and which doesn’t encourage dangerous usage patterns even in constrained environments.
Uniform Randomness
With individual signatures, the standard approach to achieving uniformly random nonces is simple: take some secret data and the message to be signed, and pass these through a cryptographic hash function to get a uniformly random value that will be independent for every message to be signed.
However, with multisignatures, this straightforward and robust solution becomes a liability. A malicious signer might request two multisignatures on the same message, tweaking her own contribution to the signature on the second iteration. If the first signer chooses his nonce by hashing a secret alongside the message, he’ll end up using the same nonce in two very different signatures – essentially the same failure mode that caused the PS3 to be hacked. Unfortunately unlike the single-signer case, there is no simple solution because individual signers must choose their nonces before knowing all the details of the signature to be produced.
A traditional solution to this problem, and the one used before the hashing became popular, is to use a hardware random number generator. Unfortunately, these are expensive, subject to environmental biases or other external influence, and most importantly, there is no way to verify their correct operation.
The latter point, about verification, has some creative solutions which we will explore in a future post. For now, our choice was to require API users provide a unique “session ID” for every signing session. Nonces are produced by hashing the signer’s secret, the set of signers, the message to be signed, and finally this session-unique input. Users who have access to a random number generator may use it to produce session IDs; those who have access to persistent memory may simply use a counter.
We are not happy about requiring random numbers or persistent memory, and expect our ongoing research will soon be able to produce a truly robust solution.
Replay Attacks
Even with a solid source of randomness, it is still possible to extract secret keys from a participant in a multisignature if it is possible to replay a signing protocol from a point part way through the process. This type of attack is called a “replay attack”, and can be carried out against a signer operating inside a restartable virtual machine, or one which supports interrupting signing and restoring from some serializable state. It can even accidentally occur without an active attacker, for example by running two virtual machines cloned from the same state, or by executing code on a distributed database which has come out of sync.
Specifically, if a signer contributes to a multisignature, and the signing process is restarted at a point after choosing his nonce, it is possible to modify the other signers’ contributions to the signature to execute essentially the same attack as in the previous section.
These sorts of attacks do not arise with single signatures because they are produced in one step, with no intermediate state to restart from. These additional challenges are unique to multi-round cryptographic protocols.
Without new mechanisms, which are a subject we are actively researching, there is nothing we can do to protect users signing in virtual machines. Though we can observe that using virtual machines is already lower security, because a machine an attacker can reset is likely a machine an attacker can directly extract secrets from.
To protect signers who may serialize stale states and restart from them, our API simply does not support serialization of signing sessions.
What this means in practice is that users of our code who want to support signing sessions that can survive across power resets or interruptions – which is a reasonable goal for a hardware wallet – must maintain secure persistent memory. If such wallets want to support multiple signing sessions in parallel, they require additional persistent memory for every parallel session.
Again, this limitation is one we believe we can eliminate using approaches we are actively researching.
Conclusion and More to Come
Implicit in all of the above discussion is the observation that multi-party protocols present new and substantially more difficult challenges than single-party protocols. In terms of mathematical complexity, MuSig is far simpler than, for example, Bulletproofs. But in terms of implementation complexity, MuSig has taken more effort and required more tradeoffs between antifragility and API flexibility.
This post has only described multisignatures – signatures in which n signers collaborate to produce a single signature. In a future post we will describe threshold signatures, a related concept in which any subset of the n signers, provided they are sufficient in quantity, are able to produce signatures without contribution from the entire group.
In future posts we will also discuss some techniques for making nonce randomness safer to produce and more verifiable. In particular, by using a technique called sign-to-contract it is possible for a host computer to eliminate any possibility of bias from an untrustworthy hardware wallet’s random number generator.
Going even further, by leveraging the power of zero knowledge proofs it should be possible to eliminate the risks posed by biased randomness and replay attacks, remove the requirement for persistent memory, and reduce the MuSig protocol from three rounds to two. We are excited about this possibility and look forward to sharing our results as they continue to develop.
Our code is publicly available on GitHub and we encourage people to play with it and provide feedback!