By Jonas Nick, Tim Ruffing

With the Taproot update to Bitcoin getting closer to potential activation, there has been considerable interest in the MuSig multisignature scheme. MuSig allows a group to collectively own some bitcoin and create a single signature to authorize a payment. Due to MuSig’s innovative key-aggregation feature, this signature is a regular Schnorr signature that can be processed by Bitcoin once Taproot is activated. When used to create multisig wallets, MuSig reduces transaction fees and increases privacy compared to the traditional way of using the CHECKMULTISIG opcode for n-of-n signatures, which needs n public keys and n ECDSA signatures on the blockchain.

In 2018, we published the first version of the MuSig scheme, which we will refer to as MuSig1 in this post. As we will discuss below, deploying MuSig1 in practice can be difficult due to the amount of communication required between the signers. We are delighted that it is possible to improve upon MuSig1 such that the signing process becomes significantly easier. We call our novel scheme MuSig2 to emphasize that it requires only two communication rounds and we consider it the successor of MuSig1. Together with cryptographer Yannick Seurin from the French National Cybersecurity Agency (ANSSI), we published a preprint that proves MuSig2 secure and is currently undergoing peer review. In January we will present MuSig2 at the Real World Crypto 2021 conference.

Interactivity of MuSig1 is a significant issue in practice

The most significant drawback of MuSig1, compared to CHECKMULTISIG based wallets, is that MuSig1 requires interaction between signers. More precisely, creating a signature requires three communication rounds, each consisting of messages being passed back and forth. The figure below shows this process for the case of two signers. You can imagine that one signer is a desktop wallet and the other is the Blockstream Green cosigner or that the signers share a Lightning channel that they’re trying to close.

In contrast, wallets using CHECKMULTISIG require only a single communication round: they receive a transaction and return a signature. For example, if MuSig1 were used to forward payments in the Lightning Network, privacy would be improved but the payment would take noticeably longer. This problem gets worse as communication latency increases. A MuSig1 signing device stored in a safety deposit box requires two visits from its owner before it can create a signature.

MuSig2 allows for non-interactive signing

The MuSig2 multisignature scheme is our proposal to overcome these issues. As the name suggests, MuSig2 is intended to be the successor of MuSig1. It offers the same functionality and security as MuSig1 but makes it possible to eliminate almost all interaction between signers. With MuSig2, signers need only two rounds of communication to create a signature, and crucially, one of these rounds can be preprocessed before signers know the message that they want to be signed. As soon as there is some message to be signed, e.g., a Bitcoin transaction, the process is the same as with today’s CHECKMULTISIG-based wallets: transfer the transaction to the signer and receive a signature in return. MuSig2 retains the simplicity and efficiency of MuSig1, and only adds a small amount of additional computation.

The MuSig family

A few weeks ago, we discussed MuSig-DN, which is also a two-round protocol but uses zero-knowledge proofs that are very complex compared to the simplicity of MuSig2. The advantage of MuSig-DN is its support for deterministic nonces, which avoids the need to keep state between signing sessions and rounds.

This raises the question of which scheme to use in a given application. The table above demonstrates that there is no reason to prefer MuSig1 over MuSig2. In practice, we expect that most applications will choose MuSig2 over MuSig-DN because simplicity is a dominant factor for adoption. This is especially true when creating interoperable implementations since all signers must agree on using the same protocol. Moreover, support for non-interactive signing increases usability significantly.

On the other hand, if open signing sessions need to be stored on a persistent medium, the statelessness property of MuSig-DN is beneficial. To demonstrate the risk with MuSig2 in that scenario, imagine we perform the following sequence of events:

1. Start a MuSig2 signing session.
2. Save the session to a hard drive.
3. Perform a hard drive backup.
4. Finish the signing session.
5. Restore the backup.
6. Complete the session again.

The result is that we create two signatures with the same nonce, which can be used to steal our secret key. Therefore, implementers of MuSig2 must be careful and make sure that the above scenario can not occur. In contrast, MuSig-DN is robust against this attack.

The challenge of constructing two-round multi-signatures

Constructing a simple Schnorr multisignature scheme that needs only two rounds and is still secure under concurrent sessions (i.e., if some signer is involved in multiple signing sessions simultaneously) was an unsolved research problem. All previous attempts (including an early version of the MuSig1 paper) suffered from a subtle attack discovered by Drijvers et al. in which an attacker opens many sessions with a victim signer and is able to obtain a signature on a message that the victim did not intend to sign.

Let us quickly look at what makes MuSig2 secure under concurrent sessions. Where in MuSig1, each signer i creates a single nonce, in MuSig2, each signer creates two nonces R_i,1, R_i,2, sends them to the other signers in the first round and effectively uses a random linear combination R_i = R_i,1 + b*R_i,2 of those nonces in lieu of the former single nonce R_i. The coefficient b is the output of a hash function applied to all signers’ nonces, the aggregated public key, and the message. As in MuSig1, the aggregate nonce is then R = R_1 + … + R_n. If any signer changes any of their nonces, every other signer will use a different, random linear combination of their two nonces. This prevents the attacks that were discovered for other two-round multisignature schemes. You can find all the nitty-gritty details in our paper.

Next steps

We’re eager to replace the MuSig1 implementation in the secp256k1-zkp library with MuSig2, which will be simpler and, most importantly, easier to use. With MuSig2 in the toolbox, a few protocols will benefit substantially, such as “scriptless script Lightning” and threshold signatures. If the Bitcoin community chooses to adopt the Taproot softfork, MuSig2 is applicable to a range of Blockstream’s products, such as Blockstream Green and c-lightning, as well as to the Liquid peg mechanism. Indeed, the Liquid Network may activate Taproot before Bitcoin does, letting us use MuSig2 in production even earlier!

Note: This blog was originally posted at https://medium.com/p/bf9582e99295