Key Aggregation for Schnorr Signatures

Last Monday we published a paper that introduces MuSig, a multi-signature scheme based on Schnorr signatures. This post will dive into its construction and a few of its applications to Bitcoin.

MuSig is a simple multi-signature scheme that is novel in combining:

1. support for key aggregation
2. security in the plain public-key model

There are two versions of MuSig, which vary based on the number of communication rounds. Both are provably secure, but three-round MuSig only relies on the Discrete Logarithm (DL) assumption, which ECDSA also relies on. Two-round MuSig instead relies on the slightly stronger One-More Discrete Logarithm (OMDL) assumption.

While this work is a result of our research into Schnorr signatures for Bitcoin, MuSig is a cryptographic construction that may be useful for other applications. The paper and this post primarily discuss the cryptographic properties of MuSig, and aren’t directly a proposal for Bitcoin.

A multi-signature scheme is a combination of a signing and verification algorithm, where multiple signers (each with their own private/public key) jointly sign a single message, resulting in a single signature. This single signature can then be verified by anyone who also knows the message and the public keys of the signers. Note that in the context of Bitcoin, the term “multisig” usually refers to a k-of-n policy, where k can be different from n. In the cryptographic literature, multi-signatures really only refers to n-of-n policies, though we can easily construct k-of-n on top of n-of-n.

We’re using the term key aggregation to refer to multi-signatures that look like a single-key signature, but with respect to an aggregated public key that is a function of only the participants’ public keys. This means that verifiers don’t actually need to know the original participants’ public keys anymore - they can just be given the aggregated key instead. In some use cases, this leads to better privacy and performance. MuSig is effectively a key aggregation scheme for Schnorr signatures.

Several multi-signature schemes exist already that effectively give us key aggregation for Schnorr signatures, but they come with some caveats like needing to verify that participants actually have the private key corresponding to the public keys they claim to have. Security in the plain public-key model means that no such caveats exist. All we need from the participants is their public keys.

Applications of multi-signatures in Bitcoin

The most obvious use case for multi-signatures in the context of Bitcoin is as a more efficient replacement for n-of-n multisig scripts, and other policies that permit a number of possible combinations of keys (including k-of-n, using key trees, MAST, or traditional threshold schemes). For these, a native multi-signature scheme means we are left with one signature per transaction input. A key aggregation scheme also lets us reduce the number of public keys per input to one, as a user can send coins to the aggregate of all involved keys, rather than including them all in the script. This leads to smaller on-chain footprint, faster validation, and better privacy. As a result, MuSig is a good choice here.

However, we can go further. Instead of restricting ourselves to one signature per input, we can actually get one signature for the entire transaction. Key aggregation can’t be used across multiple inputs, as the public keys are committed to by the outputs, and those can be spent independently. MuSig can be used here (with key aggregation done by the verifier), but Bellare-Neven (BN), a more widely known plain public-key multi-signature scheme that does not support key aggregation would work just as well. Interestingly, it is possible to use BN multi-signatures where the individual keys are MuSig aggregates.

Technically, in order to combine all the transaction inputs’ signatures into one, we don’t need a multi-signature scheme, but an aggregate signature scheme. The distinction is simply that in an aggregate signature, each signer has their own message, rather than one message shared by all. Aggregate signatures can be classified as interactive or non-interactive: interactive aggregate signatures (IAS) require the signers to cooperate, while non-interactive schemes allow the aggregation to be done by anyone. No non-interactive aggregation schemes are known that only rely on the DL assumption, but interactive ones are trivial to construct: take a multi-signature scheme and have every participant sign the concatenation of all messages. Our paper shows that this is not always a desirable construction, and gives an IAS variant of BN with better properties instead.

Details

Notation:

• x, x₁, x₂, … are private keys with corresponding public keys X, X₁, X₂, … (X_i = x_iG, with G the generator)
• The message being signed is m
• H() is a cryptographic hash function

Schnorr signatures

As a refresher, here are the equations relevant for Schnorr signatures:

• Signatures are (R,s) = (rG, r + H(X,R,m)x) where r is a random nonce chosen by the signer
• Verification requires sG = R + H(X,R,m)X

Naive Schnorr multi-signatures

A straightforward generalization is possible to support multi-signatures:

• Call X the sum of the X_i points
• Each signer chooses a random nonce r_i, and shares R_i = r_iG with the other signers
• Call R the sum of the R_i points
• Each signer computes s_i = r_i + H(X,R,m)x_i
• The final signature is (R,s) where s is the sum of the s_i values
• Verification requires sG = R + H(X,R,m)X, where X is the sum of the individual public keys

Interestingly, this satisfies the definition of a key aggregation scheme above: multiple parties can jointly produce a signature that is a valid single-key signature for the sum of the keys. If it’s so simple, what’s all the fuss about?

The issue is of course that this scheme is not secure. Consider the following scenario. Alice and Bob want to produce a multi-signature together. Alice has a key pair (x_A,X_A) and Bob has (x_B,X_B). However, nothing prevents Bob from that claiming his public key is X_B’ = X_B - X_A. If he does so, others will assume that X_A + X_B’ is the aggregated key that Alice and Bob need to cooperate in order to sign for. Unfortunately, that sum is equal to X_B, and Bob can clearly sign for this by himself. This is called a rogue-key attack, and one way to avoid it is requiring that Alice and Bob prove first that they actually possess the private keys corresponding to their claimed public keys. However, this mitigation is not always possible, and even when it is, it is fragile at best. Ideally we construct a scheme whose security does not rely on out-of-band verification of the keys.

Bellare-Neven

As mentioned above, the BN multi-signature scheme is secure without such assumptions. Here is how it works:

• Call L = H(X₁,X₂,…)
• Each signer chooses a random nonce r_i, and shares R_i = r_iG with the other signers
• Call R the sum of the R_i points
• Each signer computes s_i = r_i + H(L,X_i,R,m)x_i
• The final signature is (R,s) where s is the sum of the s_i values
• Verification requires sG = R + H(L,X₁,R,m)X₁ + H(L,X₂,R,m)X₂ + …

Technically, BN has a precommit round, where the signers first reveal H(R_i) to each other, before revealing the R_i points themselves. This step is necessary to prove security under the DL assumption, but it can be avoided if we instead accept the OMDL assumption. This is also the distinction between two-round and three-round MuSig.

Furthermore, when an IAS is desired (where each signer has their own message), appendix A of our paper suggests using L = H((X₁,m₁),(X₂,m₂),…) instead, and s_i = r_i + H(L,R,i)x_i for signing (and analoguous for verification).

In any case, the resulting signature does not satisfy the normal Schnorr equation anymore, nor any other equation that can be written as a function of a combination of the public keys. In other words, we’ve lost the key aggregation property in order to gain security in the plain public-key model.

MuSig

This is where MuSig comes in. It recovers the key aggregation property without losing security:

• Call L = H(X₁,X₂,…)
• Call X the sum of all H(L,X_i)X_i
• Each signer chooses a random nonce r_i, and shares R_i = r_iG with the other signers
• Call R the sum of the R_i points
• Each signer computes s_i = r_i + H(X,R,m)H(L,X_i)x_i
• The final signature is (R,s) where s is the sum of the s_i values
• Verification again satisfies sG = R + H(X,R,m)X

That’s it! All we had to do was define X not as a simple sum of the individual public keys X_i, but as a sum of multiples of those keys, where the multiplication factor depends on a hash of all participating keys.

Acknowledgements

We’re very grateful to Yannick Seurin for his interest in reviewing MuSig’s security, writing its security proof, as well as coming up with the name.