* [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 [bitcoin-dev] MuSig2 BIP 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 [bitcoin-dev] MuSig2 BIP 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 [bitcoin-dev] MuSig2 BIP 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
* 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
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-05 22:57 [bitcoin-dev] MuSig2 BIP 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
2022-04-28 15:33 Brandon Black
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox