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 ohsogreat 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 cosigners to cooperatively sign a common message without the need to trust each other, or prove KnowledgeofSecretKey (KOSK).
There are currently three iterations of MuSig:
 InsecureMuSig  An outdated and insecure 2round version
 MuSig1  The secure 3round variant
 MuSig2  The faster but slightly less secure 2round variant
* _{The term rounds means the number of communication roundtrips required for a signing session.}
This post covers MuSig1: the secure 3round multisignature variant. My goal is to make the atfirst trickylooking 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 basepoint of the secp256k1 curve.  
The message we’re trying to sign (a byte array).  
The SHA256 hash function.  
The order of the secp256k1 curve. There are 

Sampling 

Concatenation of the byte arrays 
MuSig relies on namespaced hash functions, which are denoted
Rogue Keys
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
The first and most obvious dragon we need to slay is the Rogue Key Attack, which I also introduced in my Schnorr Signatures article.
Option 1: KOSK
Rogue Keys can be avoided naively by requiring that each cosigner to prove she knows the private key for her public key. Such an affirmation is called KnowledgeofSecretKey (KOSK).
why does that work?
Carol picked
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 cosigners to prove KnowledgeofSecretKey, 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 cosigners to compute their public keys based on the keys of their peers. So what’s a cypherpunk to do?
Option 2: Key Commitments
A slightlylessobtuse solution would be to require each cosigner 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 cosigners 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 inadvance to a public key, and then verifying the commitments of others, the cosigners 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 keycommitment scheme would be to require each cosigner to provide a namespaced hash of their public key before seeing anyone else’s pubkey.
To lock each cosigner into their choice of pubkey, cosigners would each send this hash (AKA a commitment) to oneanother before revealing their pubkeys. Once each cosigner 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
This format prevents the “whogoesfirst” 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 cosigning 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 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 keycommitment solution: Once Alice has exposed her public key to anyone, she can only ever use it to cosign 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 cosigners, 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 cosigners’ keys to scramble the final aggregated key. Let’s say
Each cosigner could compute a namespaced hash of
Some of the pubkeys in
Each cosigner can easily compute the key coefficients of their peers and determine
If
Note that each key coefficient must be distinct persigner. A global key coefficient, such as
Nonces would be computed as they were in the naive aggregation example.
After sharing their public nonces with oneanother, cosigners could each compute the aggregated nonce
Recall from the previous article that a Schnorr signature
To make aggregated signatures valid for those equations, the signature must be aggregated in a way that allows
This mirrors the way in which the aggregated pubkey
The final signature
To better visualize the structure here, group all the nonces and keys separately, and factor out
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 cosigners 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 cosigners to first reveal their nonces
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 cosigner must provide a KnowledgeofSecretKey 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
Rather than having each cosigner 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 cosigners, cosigners can expose their real public nonces. Once everyone has shared commitments and then nonces, all can verify and rejoice, confident that nobody in the cosigning 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 cosigner (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
They share
Alice for example is not at risk, provided she receives
Signatures would then be computed and aggregated as discussed in the last section.
The Real MuSig1 Protocol
We’ve finally arrived at the fullyjustified MuSig1 protocol. Let’s give Alice, Bob and Carol one more try at signing cooperatively.
1. Key Aggregation
Cosigners share their public keys with oneanother. Everyone can now compute each other’s key coefficients, and thereby compute the aggregated pubkey.
The pseudorandom key coefficients
2. Nonce Commitments
Each cosigner samples a random secret nonce and privately computes the corresponding public nonce. They hash the public nonce into a commitment.
The nonce commitments
3. Message Choice
The message to sign
It is important that
4. The Big Nonce Reveal
Cosigners reveal their nonces
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 cosigner possesses the public nonces of their peers, they can compute the aggregated public nonce
5. Challenge Hashing
The nonce
Each cosigner can compute
6. Partial Signing
Cosigners compute their partial signatures
7. Signature Aggregation
The partial signatures can be shared with other participants at will.
Once each cosigner has
Cosigners already learned the aggregated nonce
Note that there is a “whogoesfirst” 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
This is commonly called a free option problem, and unfortunately there is no way around it: Someone is going to learn
8. Signature Verification
Verifying this signature is exactly the same as verifying any normal Schnorr Signature
This will be correct for the aggregated signature.
If the final signature is not valid, one of the cosigners 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 softspot for MuSig1 over MuSig2, because it is dumbsimple compared to the magic of MuSig2.
MuSig2 has some fancy sauce that helps it avoid the whole noncecommitment issue, without leaving it vulnerable to Wagner’s Attack. Perhaps another day I’ll discuss MuSig2.