Add BIP MuSig2

[jonasnick]

This PR adds a BIP for the MuSig2 protocol. We, the BIP authors, posted an initial draft version to the bitcoin-dev mailing list in April. Since then, we have addressed feedback from the mailing list and the development git repository (to the best of our knowledge, we didn't leave feedback unaddressed). We kept the resulting change log in the BIP draft. In the past weeks, we received no requests for major changes or features, which indicates that it is a good time to stabilize the BIP draft. The development git repo is archived at https://github.com/jonasnick/bips.

There are already multiple (experimental) implementations of the draft, such as:

• the reference python implementation included in this PR (supports BIP version 1.0.0)
• a libsecp256k1-zkp module (currently supports BIP version 0.1.0)
• btcec (currently supports BIP version 0.4.0)
• secp256kfun (supports BIP version 1.0.0)
• nbitcoin (supports BIP version 1.0.0)

TODO:

• resolve https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html
• after BIP number is assigned, replace alias bip-musig2 with bip-<number>

CC @real-or-random @robot-dreams

[NicolasDorier]

ACK, I spent lot's of time to implement MuSig2 through the several iterations of the specs.
Even if I'm not well versed into cryptography, for the 1.0, I used this BIP + the python reference implementation as a guide, as well as passed through all the tests vectors, and could implement Musig2 without facing any issue.
Congratulation for the quality of this BIP.

[jonasnick]

Marked as draft since there's still work to be done (BIP number) but it's ready to review.

[jonasnick]

Also, this PR is staying a draft until https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html is addressed.

[jonasnick]

Also, this PR is staying a draft until https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html is addressed.

I pushed a version of the BIP draft that addresses this and therefore this PR is ready for review again. Note that we retroactively renamed the version 1.0.0 in our change log to 1.0.0-rc.1 (not great, but with this little cheat we have a coherent change log again).

As for the specific changes let me copy the post that I just send to bitcoin-dev:

We updated the MuSig2 BIP draft to fix the vulnerability published in an earlier
post [0].

We also wrote an article [1] that contains a description of
1. the vulnerable scheme (remember that the original MuSig2 scheme is not
   vulnerable because it doesn't allow tweaking)
2. an attack against the vulnerable scheme using Wagner's algorithm
3. a fixed scheme that permits tweaking

Moreover, we implemented the "BLLOR" attack mentioned in the article which
works against the reference python implementation of the previous version of the
MuSig2 BIP draft (takes about 7 minutes on my machine) [2].

The fix of the MuSig2 BIP is equivalent to the fix of the scheme in the article
[1]: before calling ''NonceGen'', the signer must determine the (potentially
tweaked) secret key it will use for this signature. BIP MuSig2 now ensures that
users can not accidentally violate this requirement by adding a mandatory public
key argument to ''NonceGen'', appending the public key to the ''secnonce'' array
and checking the public key against the secret key in ''Sign'' (see the pull
request for the detailed changes [3]).

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html
[1] https://github.com/jonasnick/musig2-tweaking
[2] https://gist.github.com/robot-dreams/89ce8c3ff16f70cb2c55ba4fe9fd1b31 (must
    be copied into the bip-musig2 directory)
[3] https://github.com/jonasnick/bips/pull/74 

[brandonblack]

Thanks for all of your work on this!

I'm about half-way through updating my TypeScript implementation to match the latest spec, and have a few comments. Possibly more to come as I finish.

The new vectors are very helpful for me as an implementer. One comment on those is that it can take a careful reading of the reference implementation to find the right things to assert.

[luke-jr]

Needs a backwards compatibility section

[jonasnick]

From BIP 2:

All BIPs that introduce backwards incompatibilities must include a section describing these incompatibilities

@luke-jr BIP MuSig2 describes a new standard. I have no idea which proposal it could be considered incompatible with.

[apoelstra]

@jonasnick I think it's common to have a "Backward Compatibility" section that just says exactly what you said. "BIP MuSig2 describes a new standard. There is nothing for it to be backward compatible with."

You could also maybe say that people are able to use other multisig schemes (e.g. CHECKMULTISIG) alongside it, or even in the same script, but you have to choose one or the other for each key that you're signing with.

[real-or-random]

@jonasnick I think it's common to have a "Backward Compatibility" section that just says exactly what you said. "BIP MuSig2 describes a new standard. There is nothing for it to be backward compatible with."

It's also common not to have it, see BIP340 and BIP342.

But anyway, I agree with @jonasnick here. BIP2 mandates this section only for BIPs that introduce backwards incompatibilities.

[ajtowns]

But anyway, I agree with @jonasnick here. BIP2 mandates this section only for BIPs that introduce backwards incompatibilities.

Sounds like that reading of bip2 doesn't match current policy, #1421 (comment)

[michaelfolkson]

In my book, it is perfectly fine (if it applies) to say that there are no backwards compatibility issues, especially if it is stated why that is the case (e.g. "because the op-codes in question are OP_SUCCESSes"). Not having a backwards compatibility section means the reader has to determine whether there are any, by themselves.

This seems reasonable to me. Both BIP editors seem pretty keen on having a backwards compatibility section regardless with a one liner if it doesn't apply. I'll open a PR for a revised BIP 2 (BIP 3) relatively soon but for now the one liner seems good to me and this certainly shouldn't hold up this BIP getting a BIP number.

@jonasnick I think it's common to have a "Backward Compatibility" section that just says exactly what you said. "BIP MuSig2 describes a new standard. There is nothing for it to be backward compatible with."

You could also maybe say that people are able to use other multisig schemes (e.g. CHECKMULTISIG) alongside it, or even in the same script, but you have to choose one or the other for each key that you're signing with.

In this case perhaps more than a one liner might be useful as @apoelstra says. MuSig2 isn't compatible with SegWit version 0 (v0) outputs as it requires Schnorr signatures that are only available in SegWit version 1 (v1). It also can't be used in the same script as OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY as these have been deprecated in SegWit v1. It can be used in the same script as OP_CHECKSIGADD that was introduced in SegWit v1.

[jonasnick]

I just pushed version 1.0.0-rc.3 of the BIP. This version contains minor improvements to the test vectors and addresses feedback (including @brandonblack's above). Change Log:

** Improve ''NonceGen'' test vectors by not using an all-zero hex string as ''rand_'' values. This change addresses potential issues in some implementations that interpret this as a special value indicating uninitialized memory or a broken random number generator and therefore return an error.
** Fix invalid length of a ''pubnonce'' in the ''PartialSigVerify'' test vectors.
** Improve ''KeySort'' test vector.
** Add explicit ''IndividualPubkey'' algorithm.
** Rename KeyGen Context to KeyAgg Context.

The commit history can be followed in this branch.

@luke-jr @kallewoof At this time we're not planning to make further changes to the BIP. We would like to request a BIP number.

Would be interesting to hear from the maintainers if this BIP needs a backwards-compatibility section and why.

[michaelfolkson]

I think we're going to be in a transitional period for a while in this repo until we can get an update to BIP 2 (BIP 3) finalized that both BIP editors are happy with and ideally the broader community is happy with too. There are a number of things that may need to be updated and clarified since BIP 2 was finalized a number of years ago.

In my book, it is perfectly fine (if it applies) to say that there are no backwards compatibility issues, especially if it is stated why that is the case (e.g. "because the op-codes in question are OP_SUCCESSes"). Not having a backwards compatibility section means the reader has to determine whether there are any, by themselves. (@kallewoof)

@luke-jr: Do you agree with Kalle on the above? The authors of this draft BIP just want some clarity on whether this is needed or not. If you do agree that a one liner is needed we should also include this requirement in the update to BIP 2 (BIP 3).

A draft of this BIP has been discussed and scrutinized for a while now on the mailing list and seems to me to be in a sufficient state to get a BIP number.

[real-or-random]

I think we're going to be in a transitional period for a while in this repo until we can get an update to BIP 2 (BIP 3) finalized that both BIP editors are happy with and ideally the broader community is happy with too. There are a number of things that may need to be updated and clarified since BIP 2 was finalized a number of years ago.

I'm not entirely sure what you mean by "transitional period", but if you suggest that there's something that hinders this PR from being moved forward, then I strongly disagree. We have established and agreed upon procedures, which are written down in BIP 2. I don't see how the fact that changes to BIP2 have been proposed, or will be proposed, would suspend the validity or applicability of the current procedures in BIP2.

Personally, I'm also not entirely happy with every aspect of BIP2, and perhaps I'll propose changes, but again, that doesn't render the current rules obsolete. The current rules will be obsolete only once other rules have been agreed upon and merged here.

---

A draft of this BIP has been discussed and scrutinized for a while now on the mailing list and seems to me to be in a sufficient state to get a BIP number.

Agreed, though I'm obviously biased here.

[michaelfolkson]

@real-or-random: Sorry if I wasn't clear. The "transitional period" is referring to this repo generally and whether we are following the BIP 2 process to the word. Things like the 3 year rejection rule we already aren't following despite it being in BIP 2.

"BIPs should be changed from Draft or Proposed status, to Rejected status, upon request by any person, if they have not made progress in three years."

if you suggest that there's something that hinders this PR from being moved forward, then I strongly disagree.

This isn't what I'm suggesting. Just that the BIP process has a few open questions currently hence there's some confusion on a number of things. As I say at the end I don't think this should hold up a BIP number being allocated for this particular draft BIP.

[real-or-random]

@michaelfolkson Okay, makes sense, I agree!

[luke-jr]

I see how BIP 2 could be read to imply backwards compatibility is optional, but IMO it is almost always applicable, if only to say there are no compatibility issues.

In particular for this BIP, I agree with @michaelfolkson on the need for more than a "no issues" section:

In this case perhaps more than a one liner might be useful as @apoelstra says. MuSig2 isn't compatible with SegWit version 0 (v0) outputs as it requires Schnorr signatures that are only available in SegWit version 1 (v1). It also can't be used in the same script as OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY as these have been deprecated in SegWit v1. It can be used in the same script as OP_CHECKSIGADD that was introduced in SegWit v1.

[jonasnick]

I pushed version 1.0.0-rc.4 which contains a small update to the test vectors:

* '''1.0.0-rc.4''' (2023-03-02):
** Add expected value of ''pubnonce'' to ''NonceGen'' test vectors.

and added a backwards compatibility section that restates compatibility with BIP 340 and mentions incompatibility with ECDSA.

[real-or-random]

@kallewoof @luke-jr Could we get a BIP number here?

[luke-jr]

BIP 327 seems good

[luke-jr]

Something more here might be nice

[real-or-random]

Just clarifying: You're saying that the title could be more elaborate?

[luke-jr]

Yes, with just this, nobody knows what it is

[real-or-random]

updated

[real-or-random]

BIP 327 seems good

Thanks!

[real-or-random]

Forced-pushed to update the title, and make changes necessary after the number was assigned.

Please let us know if further changes are necessary.

[kallewoof]

bip-0327.mediawiki has too-long TItle (45 > 44 char max) at scripts/buildtable.pl line 128, <$F> line 3.

It's one letter over the limit, so I'll just merge this.