MuSig1 - A Reasonably Secure Multisig Scheme

Conduition

2023-06-29

cryptography

Introduction

In my last post I droned on about how well Schnorr Signatures kick ECDSA in the teeth. I left off with a cliffhanger: Schnorr’s oh-so-great linear signature aggregation seems to be vulnerable to whomever shares their public key last.

Thus I felt it would be appropriate to drone on today over the elegant solution offered by MuSig. MuSig is a protocol proposed by Maxwell, Poelstra, Seurin and Wuille which allows co-signers to cooperatively sign a common message without the need to trust each other, or prove Knowledge-of-Secret-Key (KOSK).

There are currently three iterations of MuSig:

* _{The term rounds means the number of communication round-trips required for a signing session.}

This post covers MuSig1: the secure 3-round multisignature variant. My goal is to make the at-first tricky-looking math behind MuSig1 feel more intuitive and approachable. To that end, you’re in luck: MuSig1 is much simpler compared to MuSig2, which will make my job easier. MuSig2 is more arcane and will require a deal more work to firmly grasp. That’s a task for another day though.

We will start from the naive example of signature aggregation which I illustrated in the last article, and solve one problem at a time to arrive at MuSig1.

Notation

Just so we’re all on the same page:

Notation	Meaning
	The base-point of the secp256k1 curve.
	The message we’re trying to sign (a byte array).
	The SHA-256 hash function.
	The order of the secp256k1 curve. There are possible valid non-zero points on the curve, plus the ‘infinity’ point (AKA zero).
	Sampling randomly from the set of integers modulo . Note that we exclude zero when sampling.
	Concatenation of the byte arrays and .

MuSig relies on namespaced hash functions, which are denoted where is the namespace of the hash. A namespaced hash function is a normal cryptographic hash function, but with some constant bits added to every hashed message which ensure that the output of the namespaced hash function can’t be reused for other namespaces. One could define a namespaced hash function like so.

Rogue Keys

The first and most obvious dragon we need to slay is the Rogue Key Attack, which I also introduced in my Schnorr Signatures article.

Let’s return to Alice, Bob, and Carol in my example from the Schnorr article.

Our alphabet friends all anticipate signing the same messages but they do not yet know each other’s public keys. They don’t trust each other to give their honest public keys. Nobody is willing to share their public key yet, because others might collude to contribute a rogue key which gives the malicious parties sole ownership of the final aggregated pubkey.

Name	Public Key	Private Key
Alice
Bob
Carol

For example, Carol could wait for Alice and Bob to expose their public keys, and then declare hers as . After summing up all the public keys, Alice and Bob would compute an aggregated public key , which gives sole signing power to Carol.

Option 1: KOSK

Rogue Keys can be avoided naively by requiring that each co-signer to prove she knows the private key for her public key. Such an affirmation is called Knowledge-of-Secret-Key (KOSK).

why does that work?

Carol picked based on Alice and Bob’s pubkeys, but the point she happened to choose is effectively a randomly sampled point on the curve, whose secret key Carol does not know. Forcing Carol to prove KOSK would prevent Alice and Bob from accepting such a maliciously-computed rogue key.

The Problem

This is flawed because not every key I want to aggregate with is going to be fully under my control all the time. Perhaps I want to aggregate a public key right now, but I can only expect to learn its secret key next week (e.g. in a Discreet Log Contract). Perhaps I want to aggregate a public key which is itself an aggregated key, whose component secret keys are owned by 3rd parties who are not online right now.

Ideally, we’d like to avoid forcing co-signers to prove Knowledge-of-Secret-Key, because their keys may not wholly belong to them but they still want to be able to sign cooperatively with those keys. Yet at the same time, we cannot allow co-signers to compute their public keys based on the keys of their peers. So what’s a cypherpunk to do?

Option 2: Key Commitments

A slightly-less-obtuse solution would be to require each co-signer to commit to their public key ahead of time. Everyone shares their public keys only after everyone else in the cohort has already committed to theirs.

Imagine everyone putting their pubkeys into envelopes and placing those envelopes on a table for all to see. Once everyone has put their envelopes on the table (e.g. everyone is fully committed), the co-signers can start tearing them open and revealing pubkeys. Any pubkeys which weren’t committed to (by placing them on the table) cannot be trusted.

why does that work?

By committing in-advance to a public key, and then verifying the commitments of others, the co-signers ensure that nobody in their signing cohort has computed their public keys as a function of each other’s public keys - i.e. every public key is chosen independently of each other.

Example

A simple way to implement a key-commitment scheme would be to require each co-signer to provide a namespaced hash of their public key before seeing anyone else’s pubkey.

To lock each co-signer into their choice of pubkey, co-signers would each send this hash (AKA a commitment) to one-another before revealing their pubkeys. Once each co-signer receives commitments from everyone else, they can confidently share their pubkey with the rest of their peers. Upon receiving public keys from their peers, they verify all the commitments to make sure everyone behaved honestly in selecting their pubkeys.

From Alice’s perspective, she shares and receives from Bob and Carol. Once Alice has Bob and Carol’s commitments she shares and receives . She then check that and that . If or do not match their respective commitments, Alice won’t accept them.

This format prevents the “who-goes-first” problem: It no longer matters who exposes their commitments or keys first, as long as each participant has everyone else’s commitments in hand before sharing their pubkey. The output of a namespaced hash function can’t be used to compute a rogue pubkey. The namespacing also makes the commitments useless for anything except verifying key commitments. At the same time, it locks Alice, Bob, and Carol into their choice of pubkeys, which they committed to before seeing each other’s pubkeys.

The Problem

This does work on paper, but not so well on silicon. It has a glaring gotcha: Public keys cannot be reused between signing sessions.

Let’s say Alice, Bob and Carol want to add a new signer, Dave, to their group. If Alice reveals her pubkey with Bob and Carol, then she can no longer safely use that key with Dave. Dave comes into the co-signing cohort fresh, so Alice doesn’t know his public key yet. Dave now has an opportunity to collude with Bob or Carol.

If Dave can convince Bob or Carol to give him Alice’s pubkey , Dave can compute a rogue public key to exclude Alice from the new aggregated key.

Dave is able to do this before ever communicating with Alice, because he can learn her pubkey from Bob or Carol. Thus, we must now confront the practical problem of the key-commitment solution: Once Alice has exposed her public key to anyone, she can only ever use it to co-sign with pubkeys which were committed to before she revealed hers. Any other new pubkeys could be rogue.

Key Coefficients

Instead of committing to public keys ahead of time, what if the final aggregated key couldn’t be predicted by a malicious party? This way, even if rogue keys can be selected by some co-signers, the resulting aggregated key would not be usable. This would be the same result as if the malicious party had instead been a foolish party, having selected a random pubkey for which they knew of no existing secret key.

Example

To arrange this, we might use namespaced hashes of the co-signers’ keys to scramble the final aggregated key. Let’s say is a determinstic (e.g. lexically-sorted) encoding of Alice, Bob and Carol’s public keys.

Each co-signer could compute a namespaced hash of once all parties have shared their pubkeys. They also commit the hash to their own pubkey, so that each hash is unique per signer. We call these hashes key coefficients and denote them with the greek letter _(alpha).

Some of the pubkeys in might be rogue, but that won’t matter because of the next step. When computing the aggregated key, all parties multiply their pubkeys by their respective key coefficients. This forms the final aggregated key .

Each co-signer can easily compute the key coefficients of their peers and determine independently, provided they have a full list of the cohort’s pubkeys. In fact, they must do this, because otherwise they cannot tell the difference between an honestly scrambled key and a maliciously computed rogue key .

If is a cryptographically secure hash function, it will be preimage resistant. Carol will not be able to find a rogue key which would result in a compromised aggregated key, because she cannot predict the output of . Even if Carol has a large set of keys which she controls, the best Carol can do is simply guess and check random rogue keys until she finds one which produces a compromised aggregated key .

Note that each key coefficient must be distinct per-signer. A global key coefficient, such as could be factored out from each key, allowing Carol to execute a rogue key attack as before, except she multiplies her private key by the common key coefficient . Thus, the key coefficients must be unique per signer.

Nonces would be computed as they were in the naive aggregation example.

After sharing their public nonces with one-another, co-signers could each compute the aggregated nonce .

Recall from the previous article that a Schnorr signature on a message from public key can be verified with the following assertions.

To make aggregated signatures valid for those equations, the signature must be aggregated in a way that allows to be factored out of the keys. To achieve this, partial signatures on a message could be computed as follows.

This mirrors the way in which the aggregated pubkey was computed.

The final signature can then be aggregated like so.

To better visualize the structure here, group all the nonces and keys separately, and factor out from the keys.

Recall the definition of the aggregated nonce and aggregated public key.

Therefore:

Huzzah, the signature is valid!

We’ve really gotten somewhere with this idea. Rogue key attacks are no longer feasible against our fledgling multisignature protocol, because an attacker must play guess and check to figure out which rogue public key to declare to influence the resulting aggregated key, all while the attacker’s peers are waiting impatiently for her response.

A Subtler Attack

Guessing and checking isn’t that great of an option, and so Carol can’t practically trick Alice and Bob into using a key she fully controls. This seems like it should accomplish all our goals, but beware!

Carol still has a chance to manipulate Alice and Bob into signing something they didn’t intend to. When we’re talking signatures with Bitcoin, a forgery is tantamount to the complete loss of one or more UTXOs. This attack is harder to understand than a Rogue Key attack, but don’t let its obscurity fool you: The threat is very real. It is called Wagner’s Generalized Birthday Attack.

This attack’s inner workings are sophisticated, and it took me a deal of effort to fully comprehend them. I’ll summarize here, but if you’re interested, I wrote a full article on the subject which goes into more far detail on how the math behind the attack works.

At first, Wagner’s Attack seems similar to a Rogue Key Attack in that it requires the attacker to wait for other co-signers to reveal something first, and compute a response based on the revealed information.

After opening a number of concurrent signing sessions with Alice and Bob, Carol waits for her co-signers to first reveal their nonces in each session. Carol gives Alice and Bob a phony nonce in each session. Alice and Bob, none-the-wiser, sign a number of apparently benign messages using various values of .

If executed correctly, Carol can aggregate the signatures on those benign messages into a forged signature on an evil message which Alice and Bob never saw. This attack does require some heavy computation, but luckily for Carol’s CPU, the more concurrent signing sessions she can open, the less work she must do.

The fact that this works seems quite magical, but it’s nothing more than some very eloquent analytical math working in tandem with an elegant search algorithm (Wagner’s algorithm, to be exact). See this paper for a full description of this attack applied to the CoSi algorithm, which is similar to MuSig1 but built on the assumption that each co-signer must provide a Knowledge-of-Secret-Key proof to avoid Rogue Key Attacks.

In the interest of brevity, I’ve omitted a full accounting of how this attack works, but know the important part is this: Wagner’s attack depends on the attacker learning his victims’ public nonces before revealing his own. If the attacker cannot choose his nonce as a function of his victims’ nonces, all the work he did will be wasted.

Nonce Commitments

To prevent Carol from computing as a function of , we can reuse the concept of commitments from option 2, but applied to nonces instead of pubkeys.

Rather than having each co-signer share their public nonce directly, they must first hash their nonce and send the hash output as a commitment to their peers. Upon receiving commitments from all of their co-signers, co-signers can expose their real public nonces. Once everyone has shared commitments and then nonces, all can verify and rejoice, confident that nobody in the co-signing cohort attempted to change their nonce.

This avoids Wagner’s Attack because the attacker cannot control the final aggregated nonce used in each concurrent signing session. As long as at least one party in the signing cohort is honest, the final aggregated nonce will be an unbiased random curve point, chosen collaboratively by every co-signer (as it should be).

Example

Alice, Bob and Carol each sample a random secret nonce, and use it to compute their public nonce as before.

Unlike the earlier protocols, they do not share their values with each other immediately. Instead they compute commitments as follows.

They share with one-another, in no particular order. Because each commitment reveals no information about its preimage (the nonce), no party learns anything by waiting to receive the commitments of others first.

Alice for example is not at risk, provided she receives before sharing , and provided upon receiving and that she verifies they match the commitments and . Note that Alice must not expose her nonce until she has both and . Even if she receives from Bob, she cannot send to him, because Bob and Carol might be colluding, or they might be the same person. Giving to Bob before Carol commits to might allow Carol to give a rogue nonce.

Signatures would then be computed and aggregated as discussed in the last section.

The Real MuSig1 Protocol

We’ve finally arrived at the fully-justified MuSig1 protocol. Let’s give Alice, Bob and Carol one more try at signing cooperatively.

1. Key Aggregation

Co-signers share their public keys with one-another. Everyone can now compute each other’s key coefficients, and thereby compute the aggregated pubkey.

The pseudo-random key coefficients prevent any co-signers from executing a Rogue Key Attack, because they cannot analytically determine which rogue public key to offer to bring under their control.

2. Nonce Commitments

Each co-signer samples a random secret nonce and privately computes the corresponding public nonce. They hash the public nonce into a commitment.

The nonce commitments are shared at will amongst co-signers. Note that nonce commitments can be safely cached and pre-shared en masse to improve round-trip performance without endangering security. But the nonces themselves should not be pre-shared until a message for signing is fixed.

3. Message Choice

The message to sign must be agreed upon.

It is important that is fixed before nonces are revealed, otherwise Wagner’s Attack will rear its ugly head once more.

4. The Big Nonce Reveal

Co-signers reveal their nonces to one-another and verify the nonces match their respective commitments .

If anyone’s nonce does not match their commitment, the protocol must enforce that the exposed nonces are discarded and will not be used again. One could also retry from step 2 with fresh nonces.

Once a co-signer possesses the public nonces of their peers, they can compute the aggregated public nonce .

5. Challenge Hashing

The nonce , the aggregated pubkey , and the message are hashed with a namespaced hash function to produce the challenge .

Each co-signer can compute independently once is agreed upon and all nonces are known.

6. Partial Signing

Co-signers compute their partial signatures by multiplying their key coefficient, their private key, and the challenge . They add their secret nonces on top to obscure their private keys.

7. Signature Aggregation

The partial signatures can be shared with other participants at will.

Once each co-signer has , they can aggregate them into the final signature .

Co-signers already learned the aggregated nonce in step 4.

Note that there is a “who-goes-first” problem here. Alice, Bob and Carol cannot all learn each other’s partial signatures simultaneously. Whomever is last to share their signature could “run off with the bag”, so to speak, learning the final aggregated signature secret without letting anyone else compute it.

This is commonly called a free option problem, and unfortunately there is no way around it: Someone is going to learn first, so whatever the cohort is signing had better be set up with the expectation that one party might have the option to use the signature while others cannot.

8. Signature Verification

Verifying this signature is exactly the same as verifying any normal Schnorr Signature with a single public key , provided the verifier knows to use the correct hash function .

This will be correct for the aggregated signature.

If the final signature is not valid, one of the co-signers must have submitted an invalid partial signature. Participants within the group who know each other’s public keys and nonces can determine who is responsible by verifying each partial signature separately.

Conclusion

I have a soft-spot for MuSig1 over MuSig2, because it is dumb-simple compared to the magic of MuSig2.

MuSig2 has some fancy sauce that helps it avoid the whole nonce-commitment issue, without leaving it vulnerable to Wagner’s Attack. Perhaps another day I’ll discuss MuSig2.