Add BIP MuSig2 #1372

jonasnick commented at 8:35 PM on October 3, 2022: contributor

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

kanzure cross-referenced this on Oct 3, 2022 from issue October topics by justinmoon

NicolasDorier commented at 9:48 AM on October 4, 2022: contributor

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 this as a draft on Oct 6, 2022

jonasnick commented at 8:33 PM on October 6, 2022: contributor

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

apoelstra cross-referenced this on Oct 8, 2022 from issue Is there a way of having aggregate signature in first Tr descriptor parameter? by dr-orlovsky

jonasnick commented at 1:48 PM on October 12, 2022: contributor

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

bitcoin deleted a comment on Oct 12, 2022

jonasnick force-pushed on Nov 3, 2022

jonasnick commented at 2:52 PM on November 3, 2022: contributor

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

jonasnick marked this as ready for review on Nov 3, 2022

in bip-musig2.mediawiki:597 in e615cea4a3 outdated

 542 | +With this modification, the secret signing key ''sk'' of the signer generating the nonce is '''not''' an optional argument and must be provided to ''NonceGen''.
 543 | +The security of the resulting scheme is then depending on the requirement that reading the counter must never yield the same counter value in two ''NonceGen'' invocations with the same ''sk''.
 544 | +
 545 | +Second, if there is a unique signer who is supposed to send the ''pubnonce'' last, it is possible to modify nonce generation for this single signer to not require high-quality randomness.
 546 | +Such a nonce generation algorithm ''DeterministicSign'' is specified below.
 547 | +Note that the only optional argument is ''rand'', which can be omitted if randomness is entirely unavailable.

brandonblack commented at 10:30 PM on November 21, 2022:

if randomness is entirely unavailable.

also useful if the secret key is stored in multiple locations and it is not feasible to ensure that both signing rounds execute in the same location.

real-or-random commented at 1:52 PM on January 5, 2023:

I can't follow, can you elaborate?

brandonblack commented at 6:02 PM on January 5, 2023:

Sure. If I have 2 copies of my secret key in separate physical locations, I may have cause to generate a nonce when near one copy, but create my partial signature when near the other copy. In that case I have no mechanism to ensure against nonce reuse unless I use 2-stage DeterministicSign (as described by Jonas).

in bip-musig2.mediawiki:51 in e615cea4a3 outdated

  46 | +
  47 | +=== Design ===
  48 | +
  49 | +* '''Compatibility with BIP340''': The aggregate public key created as part of this MuSig2 specification is a BIP340 X-only public key, and the signature output at the end of the protocol is a BIP340 signature that passes BIP340 verification for the aggregate key and a message. The public keys that are input to the key aggregation algorithm are ''plain'' public keys in compressed format.
  50 | +* '''Tweaking for BIP32 derivations and Taproot''': The specification supports tweaking aggregate public keys and signing for tweaked aggregate public keys. We distinguish two modes of tweaking: ''Plain'' tweaking can be used to derive child aggregate public keys per [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP32]. ''X-only'' tweaking, on the other hand, allows creating a [https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki BIP341] tweak to add script paths to a Taproot output. See section [[#tweaking|Tweaking]] below for details.
  51 | +* '''Non-interactive signing with preprocessing''': The first communication round, exchanging the nonces, can happen before the message or even the exact set of signers is determined. Therefore, the signers can view it as a preprocessing step. Later, when the parameters of the signing session are chosen, they can send partial signatures without additional interaction.

brandonblack commented at 11:22 PM on November 21, 2022:

The benefit of this is somewhat restricted with the requirement to know the exact derived public key prior to nonce generation.

jonasnick commented at 2:37 PM on November 30, 2022:

True. Maybe it makes sense to make this clearer in the paragraph.

in bip-musig2.mediawiki:260 in e615cea4a3 outdated

 255 | +* The value ''gacc'' : 1 or -1 mod n
 256 | +
 257 | +We write "Let ''(Q, gacc, tacc) = keygen_ctx''" to assign names to the elements of a KeyGen Context.
 258 | +
 259 | +<div>
 260 | +Algorithm ''GetXonlyPubkey(keygen_ctx)'':

brandonblack commented at 11:46 PM on November 21, 2022:

An additional algorithm GetParity(keygen_ctx) or HasEvenY(keygen_ctx) would make using Taproot x-only tweaked MuSig keys easier (eg. for building the corresponding control blocks).

Alternatively, since this algorithm appears intended for use in that context, it could return implementation dependent structured data of has_even_y(Q), xbytes(Q).

jonasnick commented at 2:37 PM on November 30, 2022:

Your suggestion is very close to what GetPlainPubkey already does. In particular, the control block bit can be obtained with GetPlainPubkey[0] & 1. It seems like we don't explain this, but I think we should.

in bip-musig2.mediawiki:379 in e615cea4a3 outdated

 360 | +* Else:
 361 | +** Let ''rand = rand' ''
 362 | +* If the optional argument ''aggpk'' is not present:
 363 | +** Let ''aggpk = empty_bytestring''
 364 | +* If the optional argument ''m'' is not present:
 365 | +** Let ''m_prefixed = bytes(1, 0)''

brandonblack commented at 7:51 PM on November 22, 2022:

I don't see a justification for differentiating absence from zero-length for m but not for extra_in or aggpk.

jonasnick commented at 2:37 PM on November 30, 2022:

aggpk is always 32 and never 0 bytes. extra_in is supposed to "contain additional contextual data that has a chance of changing between NonceGen runs" which implies that a 0-byte extra_in is not useful. We still allow it to avoid adding complexity to the spec.

in bip-musig2.mediawiki:631 in e615cea4a3 outdated

 576 | +* Let ''pubnonce = cbytes(R<sub>⁎,2</sub>) || cbytes(R<sub>⁎,2</sub>)''
 577 | +* Let ''d = int(sk)''
 578 | +* Fail if ''d = 0'' or ''d &ge; n''
 579 | +* Let ''pk = cbytes(d⋅G)''
 580 | +* Let ''secnonce = bytes(32, k<sub>1</sub>) || bytes(32, k<sub>2</sub>) || pk''
 581 | +* Let ''aggnonce = NonceAgg((pubnonce, aggothernonce))''; fail if that fails and blame nonce aggregator for invalid ''aggothernonce''.

brandonblack commented at 8:19 PM on November 22, 2022:

It seems odd to define DeterministicSign instead of DeterministicNonceGen, given that DeterministicSign converges with Sign at this point.

Is there a reason that it is not safe / allowable to send the generated pubnonce to other signers here, and then have the stateless signer verify their partial signatures before creating its own?

Put another way: is there a modification that can be made to allow the stateless signer require partial signatures from other parties before creating and publishing its partial signature?

jonasnick commented at 2:39 PM on November 30, 2022:

The reason that there's no independent DeterministicNonceGen is that it is extremely fragile. When it is not used correctly, the secret signing key can leak to the public. For example, aggnonce must be the result of calling NonceAgg with the deterministic signers nonce and aggothernonce, which must be input to the nonce hash. If we had an independent DeterministicNonceGen instead of a DeterministicSign algorithm, we'd have to describe all of this in prose, which is susceptible to accidental misuse. DeterministicSign, on the other hand, is safe to use and can be tested using the provided test vectors.

Yes, it's possible to securely modify the stateless signer to require partial signatures from other parties before creating and publishing its partial signature. For example, this would be achieved by the following two algorithms wrapping deterministic_sign.

def deterministic_sign_stage1(sk, aggothernonce, pubkeys, tweaks, is_xonly, msg, rand):
  pubnonce, _ = deterministic_sign(sk, aggothernonce, pubkeys, tweaks, is_xonly, msg, rand)
  return pubnonce

def deterministic_sign_stage2(sk, aggothernonce, pubkeys, tweaks, is_xonly, msg, rand, psigs):
  _, psig = deterministic_sign(sk, aggothernonce, pubkeys, tweaks, is_xonly, msg, rand)
  for i in range(len(pubkeys)):
    if pubkeys[i] == plain_pk_gen(sk):
      continue
    assert partial_sig_verify(psigs[i], pubnonces, pubkeys, tweaks, is_xonly, msg, i)
  return psig

Note that the stage2 requires recomputing a bunch of things that have been computed in stage1 already but this is necessary to keep the signer stateless. Similarly, if the inputs in stage2 differ from stage1, the signer may produce a psig that doesn't match the pubnonce. It's possible in stage1 to call a modified deterministic_sign that aborts as soon as the pubnonce is computed and does not compute a partial signature that is thrown away anyway. This is easy to see since the observable behavior of that stage1 is indistinguishable from the original one.

brandonblack commented at 12:31 AM on November 23, 2022: contributor

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.

manda2020panda approved

jonasnick cross-referenced this on Feb 2, 2023 from issue Address Brandon Blacks comments by jonasnick

luke-jr changes_requested

luke-jr commented at 5:25 PM on February 21, 2023: member

Needs a backwards compatibility section

jonasnick commented at 9:46 PM on February 21, 2023: contributor

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 commented at 3:00 PM on February 22, 2023: contributor

@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 commented at 10:24 AM on February 23, 2023: contributor

@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 commented at 5:41 AM on February 24, 2023: contributor

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 commented at 11:16 AM on February 24, 2023: contributor

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 force-pushed on Mar 1, 2023

jonasnick commented at 3:51 PM on March 1, 2023: contributor

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 commented at 9:46 PM on March 10, 2023: contributor

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 commented at 10:00 PM on March 10, 2023: contributor

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 commented at 10:16 PM on March 10, 2023: contributor

@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 commented at 10:58 PM on March 10, 2023: contributor

@michaelfolkson Okay, makes sense, I agree!

luke-jr commented at 9:05 PM on March 11, 2023: member

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 force-pushed on Mar 13, 2023

jonasnick commented at 12:53 PM on March 13, 2023: contributor

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 commented at 12:20 PM on March 21, 2023: contributor

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

luke-jr commented at 12:58 AM on March 26, 2023: member

BIP 327 seems good

in bip-musig2.mediawiki:3 in 4d996ec7c1 outdated

   0 | @@ -0,0 +1,824 @@
   1 | +<pre>
   2 | +  BIP: ?
   3 | +  Title: MuSig2

luke-jr commented at 12:59 AM on March 26, 2023:

Something more here might be nice

real-or-random commented at 2:49 AM on March 26, 2023:

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

luke-jr commented at 2:52 PM on March 26, 2023:

Yes, with just this, nobody knows what it is

real-or-random commented at 2:50 AM on March 27, 2023:

updated

real-or-random commented at 2:49 AM on March 26, 2023: contributor

BIP 327 seems good

Thanks!

real-or-random force-pushed on Mar 27, 2023

Add BIP327: MuSig2 for BIP340-compatible Multi-Signatures 87394eaeb4

real-or-random force-pushed on Mar 27, 2023

real-or-random commented at 2:57 AM on March 27, 2023: contributor

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 commented at 9:40 AM on March 27, 2023: member

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.

kallewoof merged this on Mar 27, 2023

kallewoof closed this on Mar 27, 2023