* Re: [bitcoin-dev] MuSig2 BIP @ 2022-04-28 15:33 Brandon Black 0 siblings, 0 replies; 15+ messages in thread From: Brandon Black @ 2022-04-28 15:33 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1924 bytes --] Hi Laolu, > Finally, can you elaborate a bit on this fragment of the BIP that describes > a "short cut" when a specific signers is meant to send their nonces last: > > > 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 > > My reading here is that if there's a signer that will always send their > nonce last (possibly the responder to an LN funding attempt or a server for > a non-custodial service like Loop), then they don't actually need to > generate real randomness, and can just fully specify all the new optional > arguments? If so then this may end up really simplifying the implementation > of certain protocols since that last party doesn't (?) need to worry about > their nonces as long as all the other (?) parties are using strong > randomness? I believe this was added in response to an email that a co-worker and I sent to Jonas. The idea originated because one of our signers would have a difficult time tracking, restoring, and securely deleting secret nonces across a signing session, so what was important was that the signer not have to retain state, rather than that they not have to provide their own randomness. The result is that the signer also doesn't need to provide randomness though. The important property of the last signer's nonce is that any variation in any other party's nonce, or other values that contribute to the challenge, must uniformly randomize the last signer's nonce. The sentences following the one you quote describe exactly how achieve this, particularly: * Optional arguments become required * extra_in argument must be composed of all other parties' nonces These modifications ensure that if and only if the partial signature will be exactly equal will the same nonce be used in a subsequent signing session. Best, --Brandon [-- Attachment #2: Type: text/html, Size: 2257 bytes --] ^ permalink raw reply [flat|nested] 15+ messages in thread
* [bitcoin-dev] MuSig2 BIP
@ 2022-04-05 22:57 Jonas Nick
2022-04-28 1:47 ` Olaoluwa Osuntokun
` (2 more replies)
0 siblings, 3 replies; 15+ messages in thread
From: Jonas Nick @ 2022-04-05 22:57 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
Tim Ruffing, Elliott Jin, and I are working on a MuSig2 BIP that we would like
to propose to the community for discussion. The BIP is compatible with BIP340
public keys and signatures. It supports tweaking, which allows deriving BIP32
child keys from aggregate keys and creating BIP341 Taproot outputs with key and
script paths. You can find the BIP draft at:
https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki
The draft is in a state where it should be possible to write an implementation
based on the BIP that passes the basic test vectors (as, e.g., demonstrated by
[0]). The draft BIP also contains a reference implementation in python. Please
be aware that this is only a draft and that it may still be necessary to make
small tweaks to the algorithms and test vectors.
[0] https://github.com/btcsuite/btcd/pull/1820
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [bitcoin-dev] MuSig2 BIP 2022-04-05 22:57 Jonas Nick @ 2022-04-28 1:47 ` Olaoluwa Osuntokun 2022-04-28 3:53 ` Olaoluwa Osuntokun 2022-05-22 22:26 ` AdamISZ 2022-10-03 20:41 ` Jonas Nick 2 siblings, 1 reply; 15+ messages in thread From: Olaoluwa Osuntokun @ 2022-04-28 1:47 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5581 bytes --] Hi Jonas, Great work on this BIP! Props to you and the other co-authors for putting together such an excellent technical specification. I'm sure I'm not the only developer stoked to see the much anticipated musig2 BIP published! I made a PR earlier today to add some JSON test vectors [1], which'll make it easier for other implementations to integrate the existing vectors and more easily update implementations to account for any updates to the vectors. I've been following the BIP for a few months now, and have been updating my implementation for `btcsuite/btcd` (mostly) in lock step. Admittedly, I miss the earlier iterations of the BIP that were a bit simpler, but also commend y'all's approach re specifying more performant (removal of that O(n^2) loop), safe (the added aux input to nonce generation), and generalized (support for both normal and x-only tweaks) algorithms. We've also been integrating my implementation into lnd [2] as well in order to get more familiar with my proposed API, as well as hands-on experience crafting real transactions that use musig2 in the wild. There may, or may not be a few musig2 spends in the main chain today created using our PR ;). We hope to cut a release next month (lnd v0.15.0) that includes an experimental API intended to give developers safe access to musig2 signing and key aggregation. I've also concurrently started working on a proposal for a new taproot native (taprooty level 1, so step 1 here [6]) LN channel type that natively uses musig2 where applicable. While exercising all the different signing combinations on regtest, we realized that in order to support signing for a key that uses BIP 86 derivation (so commit to an empty root, and only the serialized internal) or an external key that commits to a tapscript root, an implementation must make the _pre tweaked_ combined key available to the caller. Without this key a valid control block proof (in the script path spend case) can't be constructed. Similarly, for the BIP 86 case, the pre-tweak combined key needs to be used to apply the top-level taproot tweak. As is the BIP doesn't touch on this case, which is something any implementation will need to account for if they wish to support the two signing modes I mentioned above. In practice, what we do now is compute the aggregated key, stash that away, _then_ compute the tweaked key, making both available to the caller [3]. We also add a special case for BIP 86 [5], since in that case no real tweak needs to be specified, instead an implementation should compute the BIP 340 tagged hash (tap tweak) of the pre-tweaked aggregated key and use that as the main tweak. In both of these cases, we use a special taproot specific options to make the operations explicit [4] from the caller's PoV. This _does_ mean that an implementation needs to know how to compute the BIP 341 taproot tweak fwiw. So ideally any changes to the BIP in this direction can just link out to BIP 341 in place. Finally, can you elaborate a bit on this fragment of the BIP that describes a "short cut" when a specific signers is meant to send their nonces last: > 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 My reading here is that if there's a signer that will always send their nonce last (possibly the responder to an LN funding attempt or a server for a non-custodial service like Loop), then they don't actually need to generate real randomness, and can just fully specify all the new optional arguments? If so then this may end up really simplifying the implementation of certain protocols since that last party doesn't (?) need to worry about their nonces as long as all the other (?) parties are using strong randomness? -- Laolu [1]: https://github.com/jonasnick/bips/pull/10 [2]: https://github.com/lightningnetwork/lnd/pull/6361 [3]: https://github.com/Roasbeef/btcd/blob/afbf14a3a061b961c7fe0d21dcbbc6c941a33027/btcec/schnorr/musig2/keys.go#L320-L331 [4]: https://github.com/Roasbeef/btcd/blob/afbf14a3a061b961c7fe0d21dcbbc6c941a33027/btcec/schnorr/musig2/keys.go#L211-L248 [5]: https://github.com/Roasbeef/btcd/blob/afbf14a3a061b961c7fe0d21dcbbc6c941a33027/btcec/schnorr/musig2/keys.go#L406-L414 [6]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-November/003336.html On Tue, Apr 5, 2022 at 4:04 PM Jonas Nick via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Tim Ruffing, Elliott Jin, and I are working on a MuSig2 BIP that we would > like > to propose to the community for discussion. The BIP is compatible with > BIP340 > public keys and signatures. It supports tweaking, which allows deriving > BIP32 > child keys from aggregate keys and creating BIP341 Taproot outputs with > key and > script paths. You can find the BIP draft at: > https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki > > The draft is in a state where it should be possible to write an > implementation > based on the BIP that passes the basic test vectors (as, e.g., > demonstrated by > [0]). The draft BIP also contains a reference implementation in python. > Please > be aware that this is only a draft and that it may still be necessary to > make > small tweaks to the algorithms and test vectors. > > [0] https://github.com/btcsuite/btcd/pull/1820 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 7244 bytes --] ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-04-28 1:47 ` Olaoluwa Osuntokun @ 2022-04-28 3:53 ` Olaoluwa Osuntokun 2022-04-28 19:18 ` Jonas Nick 0 siblings, 1 reply; 15+ messages in thread From: Olaoluwa Osuntokun @ 2022-04-28 3:53 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 323 bytes --] Stating the taproot interaction more plainly: the taproot tweak is defined as a function of the internal key itself h_tapTeak(internalKey || rootHash), which means that the full tweak can't be known ahead of time. Instead, one must aggregate the keys to obtain the internal key _then_ apply the tweaks as normal. -- Laolu [-- Attachment #2: Type: text/html, Size: 374 bytes --] ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-04-28 3:53 ` Olaoluwa Osuntokun @ 2022-04-28 19:18 ` Jonas Nick 0 siblings, 0 replies; 15+ messages in thread From: Jonas Nick @ 2022-04-28 19:18 UTC (permalink / raw) To: Olaoluwa Osuntokun, Bitcoin Protocol Discussion Happy to hear that the BIP draft is already useful and thank you, Laolu, for extracting the test vectors. > an implementation must make the _pre tweaked_ combined key available to the caller To apply the Taproot tweak with the key aggregation algorithm as specified you would have to do the following (slightly simplified): P := KeyAgg(pk_1, ..., pk_n, tweaks = []) t := hash_TapTweak(P, root) Q := KeyAgg(pk_1, ..., pk_n, tweaks = [t]) This unnecessarily recomputes the pre-tweaked key aggregate. In the BIP, there are more places where the specified algorithms unnecessarily recompute certain values. I believe this is justified if it makes the spec significantly easier to understand. In this case, however, it's clear that calling KeyAgg multiple times for the same set of public keys is not intuitive at all. This is something I had not fully considered before. Thanks for bringing it up. The approach you're taking in btcd makes a lot of sense to me. But in the specification, we want to avoid specifying how exactly the tweaks are derived. In the libsecp256k1-zkp implementation, key aggregation and tweaking are separated into different functions. But this requires keeping state between key aggregation and tweaking, which is why we had not chosen this approach for the BIP. I will investigate how in the BIP, we can also split key aggregation and tweaking and minimize complexity. > My reading here is that [...] last party doesn't (?) need to worry about their > nonces Your reading is mostly right. Brandon describes correctly how and why to modify the nonce generation algorithm. I opened a PR that replaces the description of this signing mode with a precise specification. Indeed, the result is that the last party doesn't need to worry about their nonce (even if the other parties use bad randomness). [0] https://github.com/jonasnick/bips/pull/11 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-04-05 22:57 Jonas Nick 2022-04-28 1:47 ` Olaoluwa Osuntokun @ 2022-05-22 22:26 ` AdamISZ 2022-05-23 15:56 ` Jonas Nick 2022-10-03 20:41 ` Jonas Nick 2 siblings, 1 reply; 15+ messages in thread From: AdamISZ @ 2022-05-22 22:26 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion Jonas, Many thanks for getting the BIP draft out. Particularly appreciate the reference code! I have a question about identical pubkeys (including how it relates to MuSig2* optimization): What is the purpose of allowing this? Isn't it always the case that N equal keys combined with M non-equal keys is logically equivalent to 1+M keys? It non trivially complicates certain aspects of the algorithm to allow it and I guess I must be missing something in my previous statement because, otherwise, isn't it pointless (and pretty unwise, considering how likely it is to come from an error)? The whole 'second key' thing in MuSig2 is a sorty of icky side effect. A valid point about this is already made in the BIP and enunciated clearly and in detail: that MuSig2 is designed to discover lying at the partial sig verify stage, so it's not really that I'm saying that what's in the BIP is logically or mathematically wrong; it just seems unwise and needlessly complex. The case of 2 keys being identical does not imply an attacker; it is far more likely to be a busted implementation by counterparties where they're accidentally using P1, P1 instead of their intended P1, P2. I suppose the key word is 'needlessly' - is there a need for this that I'm overlooking? Cheers, waxwing/AdamISZ Sent with ProtonMail secure email. ------- Original Message ------- On Tuesday, April 5th, 2022 at 17:57, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Tim Ruffing, Elliott Jin, and I are working on a MuSig2 BIP that we would like > to propose to the community for discussion. The BIP is compatible with BIP340 > public keys and signatures. It supports tweaking, which allows deriving BIP32 > child keys from aggregate keys and creating BIP341 Taproot outputs with key and > script paths. You can find the BIP draft at: > https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki > > The draft is in a state where it should be possible to write an implementation > based on the BIP that passes the basic test vectors (as, e.g., demonstrated by > [0]). The draft BIP also contains a reference implementation in python. Please > be aware that this is only a draft and that it may still be necessary to make > small tweaks to the algorithms and test vectors. > > [0] https://github.com/btcsuite/btcd/pull/1820 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-22 22:26 ` AdamISZ @ 2022-05-23 15:56 ` Jonas Nick 2022-05-23 22:09 ` AdamISZ 0 siblings, 1 reply; 15+ messages in thread From: Jonas Nick @ 2022-05-23 15:56 UTC (permalink / raw) To: AdamISZ, Bitcoin Protocol Discussion Thank you for taking the time to look at the BIP and reference code, waxwing. I don't know if you're overlooking anything, so let me try to restate the paragraph in the BIP draft that attempts to cover this topic [0]. Suppose signers would just abort in the presence of identical public keys. In that case, a disruptive signer can permanently DoS-attack a session by simply copying the public key of some other signer. Therefore, the BIP is much more useful if it can deal with identical public keys. The MuSig2 BIP draft requires some added complexity to handle identical public keys (because of the MuSig2* optimization). But this solution naturally allows identifying and removing disruptive signers, which ultimately reduces the complexity for MuSig2 users. [0] https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki#public-key-aggregation ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-23 15:56 ` Jonas Nick @ 2022-05-23 22:09 ` AdamISZ 2022-05-24 19:06 ` AdamISZ 0 siblings, 1 reply; 15+ messages in thread From: AdamISZ @ 2022-05-23 22:09 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion Jonas, all,: So I do want to ask a couple further clarifying questions on this point, but I got rather majorly sidetracked :) I wonder can you (and other list readers!) take a look at my attempt here to summarize what is described in Footnote 2 of the draft BIP (as it's related to this discussion and also .. it's pretty interesting generally!): https://gist.github.com/AdamISZ/ca974ed67889cedc738c4a1f65ff620b (btw github gists have equation rendering now which is nice!) Thanks, waxwing/AdamISZ Sent with ProtonMail secure email. ------- Original Message ------- On Monday, May 23rd, 2022 at 10:56, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Thank you for taking the time to look at the BIP and reference code, waxwing. I > don't know if you're overlooking anything, so let me try to restate the > paragraph in the BIP draft that attempts to cover this topic [0]. > > Suppose signers would just abort in the presence of identical public keys. In > that case, a disruptive signer can permanently DoS-attack a session by simply > copying the public key of some other signer. Therefore, the BIP is much more > useful if it can deal with identical public keys. > > The MuSig2 BIP draft requires some added complexity to handle identical public > keys (because of the MuSig2* optimization). But this solution naturally allows > identifying and removing disruptive signers, which ultimately reduces the > complexity for MuSig2 users. > > [0] https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki#public-key-aggregation > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-23 22:09 ` AdamISZ @ 2022-05-24 19:06 ` AdamISZ 2022-05-26 15:32 ` Jonas Nick 0 siblings, 1 reply; 15+ messages in thread From: AdamISZ @ 2022-05-24 19:06 UTC (permalink / raw) To: Bitcoin Protocol Discussion, Jonas Nick ------- Original Message ------- On Monday, May 23rd, 2022 at 17:09, AdamISZ via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Jonas, all,: > > So I do want to ask a couple further clarifying questions on this point, but I got rather majorly sidetracked :) > I wonder can you (and other list readers!) take a look at my attempt here to summarize what is described in Footnote 2 of the draft BIP (as it's related to this discussion and also .. it's pretty interesting generally!): > > https://gist.github.com/AdamISZ/ca974ed67889cedc738c4a1f65ff620b > > (btw github gists have equation rendering now which is nice!) > > Thanks, > waxwing/AdamISZ > Jonas, list, So given that that's basically correct (see the comments), continuing on this point of how to handle duplicate keys: In https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki#identifiying-disruptive-signers we have: "If partial signatures are received over authenticated channels, this method can be used to identify disruptive signers and hold them accountable. Note that partial signatures are not signatures. An adversary can forge a partial signature, i.e., create a partial signature without knowing the secret key for the claimed public key." (the gist in the previous message was just fleshing out what's stated there and in Footnote 2: if you get a "valid" partial sig at index i, it doesn't mean that the signer at index i knows the key for index i, *if* they also control index j; it just means they won't be able to produce "valid" partial sigs for both indices i and j). (scare quotes "valid" - there is no notion in MuSig2 of a partial signature as a signature, only the aggregate signature in toto is valid or invalid or forged). So we see in the above quote, that the concept of 'authenticated channels' is rather important. Consider 2 scenarios: 1. "Persistent": Every signer has a persistent identity across many signing sessions, and their communications are authenticated against that identity. 2. "Spontaneous": Signers join the protocol in some ad hoc way, but authenticate specifically inasmuch as they set up temporary nyms and use e.g. diffie hellman to establish a confidential and authenticated channel for the period of this signing session. An example of "Spontaneous" might be: a variant of a multiparty channel construction with anonymous participants on LN or LN* in which participants set up such constructions ad hoc e.g. via liquidity markets .. in contrast, e.g. a hardware wallet multisig setup with a known provider might be a "Persistent" case. Not sure, but ... are we mainly talking about the "Spontaneous" case? Because the "Persistent" case doesn't seem interesting: If I "know" the counterparty that I'm engaging in this protocol with, first, a Sybil at two indices is kinda weird, so the occurrence of a duplicated key from them tells me something is wrong and manual intervention is needed (or equivalently some sanity check in the meta-protocol). Often (e.g. cold storage, devices) there'd be a way to know in advance what the keys *should* be. It's very likely a bug. (I suppose you could argue waiting till the second signing round helps, because it helps us isolate the bug (except it might not, if in certain protocols, both signers have access to some shared keys, but, meh) ... but that doesn't seem convincing ... executing more of a protocol when you already know the implementation is broken seems unwise). So, to the "Spontaneous" case: if we see two identical pubkeys from two pseud/anonymous counterparties, I can see the argument for waiting until partial sig sending occurs, before establishing misbehaviour. The main substance of the argument seems to be something like: we can't actually deduce adversarial behaviour at key exchange time, so we *have* to wait for the partial signature step. I'm objecting to this on two fronts: * A general principle of security should be 'abort early'. It's to me just sensibly conservative to not continue given the substantial risk of bugs (esp. in systems exposed to nonce-fragility!) * The claim that the protocol laid out in the BIP identifies misbehaviour seems to be at best partially correct, it cannot be true in the general case. Jonas has already countered my first bullet point by stating that this abort-early (at key exchange) strategy opens up an unlimited DOS vector. My counter here is that that, because of the second bullet oint, the DOS vector remains, in the "Spontaneous" case, anyway; and that the only way to close it is to use either identities (switch to "Persistent": see e.g. Coinshuffle which registers identities via inputs), or cost. (Why does the DOS vector remain? Because of the partial sig "validation" issue as per my gist and Footnote2: if key 3 and key 4 are identical in a set of 5, we can wait, and then find that partial sig 3 verifies, and partial sig 4 *also* verifies, and only at index 5 do we see an 'invalid' partial sig. If the adversary (as seems extremely likely.. I can't imagine it being otherwise) has used two *different* nyms for his two adversarial indices 4 and 5, then ejecting 5 doesn't really seem to close the DOS potential? If we then restart and 'grab another anonymous nym' for the 5th index, can't it be the adversary again? And haven't we let the adversary stay, at index 4? (though I'm not sure the implications)). Another way to look at it, I'm saying that this claim: "In contrast, MuSig2 is designed to identify disruptive signers at signing time: any signer who prevents a signing session from completing successfully by sending incorrect contributions in the session can be identified and held accountable (see below)." isn't *fully* correct. That is, for sure the algorithm will identify a disruptive signer who simply operates one key, but it doesn't (as current) always identify every key owned by a disruptive signer. So it doesn't close the DOS vector. (To be clear the whole 'fake partial sig' adversarial behaviour is *not* specific to having duplicate public keys; I'm just discussing whether the protocol should continue if duplicates are seen). So overall I have the feeling that allowing duplicate keys at setup makes the implementation messier (and this protocol is complex, so that matters a bit more), and it strikes me as risky in the inevitable presence of implementation errors. Cheers, waxwing/AdamISZ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-24 19:06 ` AdamISZ @ 2022-05-26 15:32 ` Jonas Nick 2022-05-26 17:34 ` AdamISZ 0 siblings, 1 reply; 15+ messages in thread From: Jonas Nick @ 2022-05-26 15:32 UTC (permalink / raw) To: AdamISZ, Bitcoin Protocol Discussion Thanks for the detailed feedback. Let me try to summarize your argument: Key aggregation should fail if there are duplicate keys because this is likely a bug and continuing might be dangerous. If it is not a bug but a dishonest signer trying to disrupt, then resuming the protocol and trying to identify the dishonest signer does not work because partial signatures are not real signatures. I disagree that identifying dishonest signers is useless. But if I try hard, I can see your point that honest signers should not continue in order to protect terribly broken implementations. Broken could mean that signers reuse nonces, output their secret key instead of a partial signature, etc. However, terribly broken implementations are terribly broken. It seems very unlikely that they're nice enough to truthfully indicate their brokenness by copying someone elses public key. Perhaps they use the sum of every other key, actually create a proper public key, or do something entirely different. So I think in practice, it is implausible to find a single instance of an implementation that doesn't survive partial signature creation by looking at duplicate public keys. However, your suggestion to abort in KeyAgg when encountering duplicate public keys is compatible with the MuSig2 BIP draft. No one can force a signer to accept an arbitrary set of public keys for the multi-signature, so signers are always fine to abort at the key aggregation stage to try to protect terribly broken co-signers. In that sense, the BIP draft takes a more general and flexible approach. I doubt that identifying duplicate public keys is less complex. The only consequence of allowing duplicate public keys is that the `GetSecondKey` is required to loop over the public keys. Aborting when encountering duplicate public keys also has the added complexity of giving users the unspecific instruction to "debug signers X and Y" versus "there's something definitely wrong with signer Z". As mentioned above, I don't follow your argument that identifying signers claiming the public key of other signers is useless. I do think the "persistent" case is interesting. It's easy to imagine persistent identities not tied to secp256k1 curve points. Only for creating BIP-340 multi-signatures do they use secp256k1 public keys. These keys can be fresh, or if they are persistent, the participants may want to rotate them from time to time. So there are plenty of opportunities for an attacker to overtake a participant and try to disrupt the protocol. You mention that duplicating keys would require "a Sybil at two indices", but actually a single malicious signer that copies some public key is sufficient. Your analysis of the "spontaneous" case misses that partial signature verification identifies at least one of the dishonest signers and therefore allows to make progress. This closes the DoS vector as far as the MuSig protocol is concerned. If there are multiple disruptive signers, they may not all be identified in a single round but require multiple signing attempts. Of course, applications that use MuSig and replace disruptive signers with just some other arbitrary nym may be so unlucky that it always has disruptive signers. But that's a problem of the application layer, and it's easy to conceive smarter peer selection. I agree that the claim "any signer who prevents a signing session from completing successfully by sending incorrect contributions in the session can be identified" is incorrect. We can identify at least one, and that means applications can make progress. I opened a PR to fix the wording [0]. [0] https://github.com/jonasnick/bips/pull/25 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-26 15:32 ` Jonas Nick @ 2022-05-26 17:34 ` AdamISZ 2022-06-12 23:07 ` AdamISZ 0 siblings, 1 reply; 15+ messages in thread From: AdamISZ @ 2022-05-26 17:34 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion Hi Jonas, list, responses inline Sent with Proton Mail secure email. ------- Original Message ------- On Thursday, May 26th, 2022 at 10:32, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Thanks for the detailed feedback. Let me try to summarize your argument: Key > aggregation should fail if there are duplicate keys because this is likely a bug > and continuing might be dangerous. If it is not a bug but a dishonest signer > trying to disrupt, then resuming the protocol and trying to identify the > dishonest signer does not work because partial signatures are not real > signatures. > > I disagree that identifying dishonest signers is useless. Oh but that wasn't the claim - that it's useless. I'd characterize it more like: the benefit of identifying one disruptor index is less than claimed (but PR now to fix that), and in certain (see 'spontaneous' case) does not allow a guarantee of progress (but see below .. you have convinced me that this is kind of a false conclusion to draw). That combined with the risk potential from implementation errors weighted my opinion in favour of the abort early option. > It seems very unlikely that they're > nice enough to truthfully indicate their brokenness by copying someone elses > public key. I don't really buy that. My thinking was, there are of course an infinite number of ways an implementation can be broken, but this is not a vanishingly unlikely case, especially when you consider how often there might be ex-protocol cooperative interactions between signers. The obvious case that crops up is when one agent actually stands behind multiple different signing keys; in that scenario it's not that unlikely, and if that agent is co-signing with *other* agents something very bad might happen. > > However, your suggestion to abort in KeyAgg when encountering duplicate public > keys is compatible with the MuSig2 BIP draft. No one can force a signer to > accept an arbitrary set of public keys for the multi-signature, so signers are > always fine to abort at the key aggregation stage to try to protect terribly > broken co-signers. In that sense, the BIP draft takes a more general and > flexible approach. That's a very fair point, and good to mention. The BIP strongly justifies no abort early, though. I doubt that identifying duplicate public keys is less > complex. The only consequence of allowing duplicate public keys is that the > `GetSecondKey` is required to loop over the public keys. Aborting when > encountering duplicate public keys also has the added complexity of giving users > the unspecific instruction to "debug signers X and Y" versus "there's something > definitely wrong with signer Z". Yeah, this is the 'we can identify the disruptor' point which has been discussed in the previous mail and below, re: spontaneous. It's true except when it, partially, isn't :) > > As mentioned above, I don't follow your argument that identifying signers > claiming the public key of other signers is useless. I do think the "persistent" > case is interesting. It's easy to imagine persistent identities not tied to > secp256k1 curve points. Only for creating BIP-340 multi-signatures do they use > secp256k1 public keys. These keys can be fresh, or if they are persistent, the > participants may want to rotate them from time to time. So there are plenty of > opportunities for an attacker to overtake a participant and try to disrupt the > protocol. You mention that duplicating keys would require "a Sybil at two > indices", but actually a single malicious signer that copies some public key is > sufficient. > > Your analysis of the "spontaneous" case misses that partial signature > verification identifies at least one of the dishonest signers and therefore > allows to make progress. This closes the DoS vector as far as the MuSig protocol > is concerned. Well but I didn't miss that point, I addressed it in the section "Why does the DOS vector remain?". I see that where we've diverged here is only that you consider the case 'the same adversary keeps joining the group' to be out of scope as something that higher level protocols would have to address. On reflection I guess I agree: such a protocol needs to address this point, regardless of the quirk of repeated keys, and regardless of forged partial sigs; if participant 5 is a disruptor and you replace him with another, you have to have a mechanism to handle that it might be the same guy, and it's outside the scope of this doc. The fact that the disruptor may still stay at another index modulates that argument a little bit, but doesn't invalidate it, I believe. So from that perspective, my point here was more a 'quibble' than an actual critique: because the document kind of implies that you can do a bit more than you can, and didn't let the reader know that such an attacker, in this specific case, might 'still be around' in some sense, as you agree below: > > I agree that the claim "any signer who prevents a signing session from > completing successfully by sending incorrect contributions in the session can be > identified" is incorrect. We can identify at least one, and that means > applications can make progress. I opened a PR to fix the wording [0]. > > [0] https://github.com/jonasnick/bips/pull/25 Right, thanks, will follow up. Honestly, as an implementor, I would still abort early *in most usage scenarios* ... So many more coins were lost to screw ups in implementations than super genius attackers. Cheers, waxwing/AdamISZ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-05-26 17:34 ` AdamISZ @ 2022-06-12 23:07 ` AdamISZ 0 siblings, 0 replies; 15+ messages in thread From: AdamISZ @ 2022-06-12 23:07 UTC (permalink / raw) To: Bitcoin Protocol Discussion Sent with Proton Mail secure email. ------- Original Message ------- On Thursday, May 26th, 2022 at 12:34, AdamISZ via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Hi Jonas, list, > responses inline > <snip> > > > > [0] https://github.com/jonasnick/bips/pull/25 > > > Right, thanks, will follow up. > Just to drop a note to the thread that as per the contents of that now merged PR, I'm much more comfortable with the contents of the draft on that sticky point re: pubkeys being repeated (and the peripheral points that got raised in that PR discussion). Thanks, waxwing/AdamISZ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-04-05 22:57 Jonas Nick 2022-04-28 1:47 ` Olaoluwa Osuntokun 2022-05-22 22:26 ` AdamISZ @ 2022-10-03 20:41 ` Jonas Nick 2022-10-11 15:34 ` Jonas Nick 2 siblings, 1 reply; 15+ messages in thread From: Jonas Nick @ 2022-10-03 20:41 UTC (permalink / raw) To: Bitcoin Protocol Discussion Since the initial publication of the BIP draft, we incorporated feedback from this mailing list and the development git repository and made significant improvements compared to the initial version. There are multiple implementations today, and there have been no requests for major changes or features in the past weeks. This indicates that now is a good time to proceed with the next step of the BIP process. We opened a pull request with the MuSig2 BIP in the git repository: https://github.com/bitcoin/bips/pull/1372 Special thanks goes to my co-authors Tim Ruffing and Elliott Jin as well as Adam Gibson, Anthony Towns, arik-so, Bastien Teinturier, Brandon Black, Greg Sanders, Jesse Posner, Lloyd Fournier, mplsgrant, nickfarrow, niftynei, Olaoluwa Osuntokun, Pieter Wuille, Riccardo Casatta, Russell O'Connor and Rusty Russell for their valuable feedback. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-10-03 20:41 ` Jonas Nick @ 2022-10-11 15:34 ` Jonas Nick 2022-11-03 14:43 ` Jonas Nick 0 siblings, 1 reply; 15+ messages in thread From: Jonas Nick @ 2022-10-11 15:34 UTC (permalink / raw) To: Bitcoin Protocol Discussion It is still true that cryptography is hard, unfortunately. Yannick Seurin, Tim Ruffing, Elliott Jin, and I discovered an attack against the latest version of BIP MuSig2 in the case that a signer's individual key A = a*G is tweaked before giving it as input to key aggregation. In more detail, a signer may be vulnerable if _all_ of the following conditions are true: 1. The signer supports signing with a tweaked individual key (as provided to key aggregation) and the tweak is known to the attacker (e.g., as in BIP 32 unhardened derivation). 2. The signer's public key appears at least two times with different tweaks in the set of public keys that are aggregated. This would, for example, be the case if a signer with public key A=a*G creates partial signatures for an aggregate key corresponding to public key set {A, A+t*G} where t is some tweak. Note that an attacker could make this condition true by using the key B = A+t*G after having seen A. 3. The signer uses "concurrent signing", i.e., the signer stores secnonces for multiple signing sessions. 4. The secret key provided to the Sign algorithm is not yet fully determined when the NonceGen algorithm is called. This would, for example, be the case if the attacker, after having seen the nonce of the signer, can influence whether a or a+t will be provided as a secret key to Sign. In this scenario, an attacker may forge a signature for any message and any aggregate public key that contains the signer's individual public key A (with any attacker-chosen tweak). In particular, the attacker may forge a signature for any message and the public key A itself. Condition 4 should only apply in relatively rare cases unless the signer is tricked into such a situation. Fix: Note that if the optional secret key argument is provided to the NonceGen algorithm and matches the secret key provided to the Sign algorithm, then Condition 4 will not hold. Thus, one definite fix is to make the secret key argument to the NonceGen algorithm mandatory. We are investigating other options and will follow up shortly with a concrete fix of the BIP draft. This discovery does not invalidate the security proof of the scheme as presented in the MuSig2 paper because the security model in the paper does not support tweaking a signer's key. If you've implemented the BIP draft in your library or are already using it in production don't hesitate to reach out to clarify the implications of this discovery. Tim Ruffing, Elliott Jin, Jonas Nick ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [bitcoin-dev] MuSig2 BIP 2022-10-11 15:34 ` Jonas Nick @ 2022-11-03 14:43 ` Jonas Nick 0 siblings, 0 replies; 15+ messages in thread From: Jonas Nick @ 2022-11-03 14:43 UTC (permalink / raw) To: Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2022-11-03 14:43 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-04-28 15:33 [bitcoin-dev] MuSig2 BIP Brandon Black -- strict thread matches above, loose matches on Subject: below -- 2022-04-05 22:57 Jonas Nick 2022-04-28 1:47 ` Olaoluwa Osuntokun 2022-04-28 3:53 ` Olaoluwa Osuntokun 2022-04-28 19:18 ` Jonas Nick 2022-05-22 22:26 ` AdamISZ 2022-05-23 15:56 ` Jonas Nick 2022-05-23 22:09 ` AdamISZ 2022-05-24 19:06 ` AdamISZ 2022-05-26 15:32 ` Jonas Nick 2022-05-26 17:34 ` AdamISZ 2022-06-12 23:07 ` AdamISZ 2022-10-03 20:41 ` Jonas Nick 2022-10-11 15:34 ` Jonas Nick 2022-11-03 14:43 ` Jonas Nick
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox