* [bitcoin-dev] Blinded 2-party Musig2
@ 2023-07-24 7:46 Tom Trevethan
2023-07-24 10:50 ` ZmnSCPxj
` (2 more replies)
0 siblings, 3 replies; 34+ messages in thread
From: Tom Trevethan @ 2023-07-24 7:46 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 2429 bytes --]
We are implementing a version of 2-of-2 Schnorr Musig2 for statechains
where the server (party 1 in the 2-of-2) will be fully 'blinded' - in that
it can hold a private key that is required to generate an aggregate
signature on an aggregate public key, but that it does not learn either: 1)
The aggregate public key 2) The aggregate signature and 3) The message (m)
being signed.
In the model of blinded statechains, the security rests on the statechain
server being trusted to report the NUMBER of partial signatures it has
generated for a particular key (as opposed to being trusted to enforce
rules on WHAT it has signed in the unblinded case) and the full set of
signatures generated being verified client side
https://github.com/commerceblock/mercury/blob/master/doc/merc_blind.md#blinding-considerations
Given the 2-of-2 musig2 protocol operates as follows (in the following
description, private keys (field elements) are denoted using lower case
letters, and elliptic curve points as uppercase letters. G is the generator
point and point multiplication denoted as X = xG and point addition as A =
G + G):
Party 1 generates private key x1 and public key X1 = x1G. Party 2 generates
private key x2 and public key X2 = x2G. The set of pubkeys is L = {X1,X2}.
The key aggregation coefficient is KeyAggCoef(L,X) = H(L,X). The shared
(aggregate) public key X = a1X1 + a2X2 where a1 = KeyAggCoef(L,X1) and a2 =
KeyAggCoef(L,X2).
To sign a message m, party 1 generates nonce r1 and R1 = r1G. Party 2
generates nonce r2 and R2 = r2G. These are aggregated into R = R1 + R2.
Party 1 then computes 'challenge' c = H(X||R||m) and s1 = c.a1.x1 + r1
Party 2 then computes 'challenge' c = H(X||R||m) and s2 = c.a2.x2 + r2
The final signature is then (R,s1+s2).
In the case of blinding this for party 1:
To prevent party 1 from learning of either the full public key or final
signature seems straightforward, if party 1 doesn't not need to
independently compute and verify c = H(X||R||m) (as they are blinded from
the message in any case).
1) Key aggregation is performed only by party 2. Party 1 just sends X1 to
party 2.
2) Nonce aggregation is performed only by party 2. Party 1 just sends R1 to
party 2.
3) Party 2 computes c = H(X||R||m) and sends it to party 1 in order to
compute s1 = c.a1.x1 + r1
Party 1 never learns the final value of (R,s1+s2) or m.
Any comments on this or potential issues would be appreciated.
Tom
[-- Attachment #2: Type: text/html, Size: 2685 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 7:46 [bitcoin-dev] Blinded 2-party Musig2 Tom Trevethan @ 2023-07-24 10:50 ` ZmnSCPxj 2023-07-24 14:25 ` Erik Aronesty 2023-07-24 15:57 ` Tom Trevethan 2023-07-24 14:12 ` Jonas Nick 2023-07-24 15:39 ` Jonas Nick 2 siblings, 2 replies; 34+ messages in thread From: ZmnSCPxj @ 2023-07-24 10:50 UTC (permalink / raw) To: Tom Trevethan; +Cc: Bitcoin Protocol Discussion Good morning Tom, Would this allow party 2 to itself be composed of N >= 2 parties? MuSig2 (as opposed to MuSig1) requires that signatories provide multiple `R` points, not just one each, which are finally aggregated by first combining them using the MuSig() public key compose function. This prevents party 2 from creating an `R` that may allow it to perform certain attacks whose name escapes me right now but which I used to know. (it is the reason why MuSig1 requires 3 round trips, and why MuSig2 requires at least 2 `R` nonces per signatory) Your scheme has only one `R` per party, would it not be vulnerably to that attack? Regards, ZmnSCPxj Sent with Proton Mail secure email. ------- Original Message ------- On Monday, July 24th, 2023 at 7:46 AM, Tom Trevethan via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > We are implementing a version of 2-of-2 Schnorr Musig2 for statechains where the server (party 1 in the 2-of-2) will be fully 'blinded' - in that it can hold a private key that is required to generate an aggregate signature on an aggregate public key, but that it does not learn either: 1) The aggregate public key 2) The aggregate signature and 3) The message (m) being signed. > > In the model of blinded statechains, the security rests on the statechain server being trusted to report the NUMBER of partial signatures it has generated for a particular key (as opposed to being trusted to enforce rules on WHAT it has signed in the unblinded case) and the full set of signatures generated being verified client side https://github.com/commerceblock/mercury/blob/master/doc/merc_blind.md#blinding-considerations > > Given the 2-of-2 musig2 protocol operates as follows (in the following description, private keys (field elements) are denoted using lower case letters, and elliptic curve points as uppercase letters. G is the generator point and point multiplication denoted as X = xG and point addition as A = G + G): > > Party 1 generates private key x1 and public key X1 = x1G. Party 2 generates private key x2 and public key X2 = x2G. The set of pubkeys is L = {X1,X2}. The key aggregation coefficient is KeyAggCoef(L,X) = H(L,X). The shared (aggregate) public key X = a1X1 + a2X2 where a1 = KeyAggCoef(L,X1) and a2 = KeyAggCoef(L,X2). > > To sign a message m, party 1 generates nonce r1 and R1 = r1G. Party 2 generates nonce r2 and R2 = r2G. These are aggregated into R = R1 + R2. > > Party 1 then computes 'challenge' c = H(X||R||m) and s1 = c.a1.x1 + r1 > Party 2 then computes 'challenge' c = H(X||R||m) and s2 = c.a2.x2 + r2 > > The final signature is then (R,s1+s2). > > In the case of blinding this for party 1: > > To prevent party 1 from learning of either the full public key or final signature seems straightforward, if party 1 doesn't not need to independently compute and verify c = H(X||R||m) (as they are blinded from the message in any case). > > 1) Key aggregation is performed only by party 2. Party 1 just sends X1 to party 2. > 2) Nonce aggregation is performed only by party 2. Party 1 just sends R1 to party 2. > 3) Party 2 computes c = H(X||R||m) and sends it to party 1 in order to compute s1 = c.a1.x1 + r1 > > Party 1 never learns the final value of (R,s1+s2) or m. > > Any comments on this or potential issues would be appreciated. > > Tom ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 10:50 ` ZmnSCPxj @ 2023-07-24 14:25 ` Erik Aronesty 2023-07-24 16:08 ` Tom Trevethan 2023-07-24 15:57 ` Tom Trevethan 1 sibling, 1 reply; 34+ messages in thread From: Erik Aronesty @ 2023-07-24 14:25 UTC (permalink / raw) To: ZmnSCPxj, Bitcoin Protocol Discussion; +Cc: Tom Trevethan [-- Attachment #1: Type: text/plain, Size: 4075 bytes --] as long as all parties provide a proof of secret key along with their public key, that should not be possible or you can do it as a two-step process where all parties provide a commitment to the public key and nobody reveals a public key until that commitment is received or if you want to be paranoid you can do both On Mon, Jul 24, 2023, 7:00 AM ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Good morning Tom, > > Would this allow party 2 to itself be composed of N >= 2 parties? > > MuSig2 (as opposed to MuSig1) requires that signatories provide multiple > `R` points, not just one each, which are finally aggregated by first > combining them using the MuSig() public key compose function. > This prevents party 2 from creating an `R` that may allow it to perform > certain attacks whose name escapes me right now but which I used to know. > (it is the reason why MuSig1 requires 3 round trips, and why MuSig2 > requires at least 2 `R` nonces per signatory) > > Your scheme has only one `R` per party, would it not be vulnerably to that > attack? > > Regards, > ZmnSCPxj > > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Monday, July 24th, 2023 at 7:46 AM, Tom Trevethan via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > > > We are implementing a version of 2-of-2 Schnorr Musig2 for statechains > where the server (party 1 in the 2-of-2) will be fully 'blinded' - in that > it can hold a private key that is required to generate an aggregate > signature on an aggregate public key, but that it does not learn either: 1) > The aggregate public key 2) The aggregate signature and 3) The message (m) > being signed. > > > > In the model of blinded statechains, the security rests on the > statechain server being trusted to report the NUMBER of partial signatures > it has generated for a particular key (as opposed to being trusted to > enforce rules on WHAT it has signed in the unblinded case) and the full set > of signatures generated being verified client side > https://github.com/commerceblock/mercury/blob/master/doc/merc_blind.md#blinding-considerations > > > > Given the 2-of-2 musig2 protocol operates as follows (in the following > description, private keys (field elements) are denoted using lower case > letters, and elliptic curve points as uppercase letters. G is the generator > point and point multiplication denoted as X = xG and point addition as A = > G + G): > > > > Party 1 generates private key x1 and public key X1 = x1G. Party 2 > generates private key x2 and public key X2 = x2G. The set of pubkeys is L = > {X1,X2}. The key aggregation coefficient is KeyAggCoef(L,X) = H(L,X). The > shared (aggregate) public key X = a1X1 + a2X2 where a1 = KeyAggCoef(L,X1) > and a2 = KeyAggCoef(L,X2). > > > > To sign a message m, party 1 generates nonce r1 and R1 = r1G. Party 2 > generates nonce r2 and R2 = r2G. These are aggregated into R = R1 + R2. > > > > Party 1 then computes 'challenge' c = H(X||R||m) and s1 = c.a1.x1 + r1 > > Party 2 then computes 'challenge' c = H(X||R||m) and s2 = c.a2.x2 + r2 > > > > The final signature is then (R,s1+s2). > > > > In the case of blinding this for party 1: > > > > To prevent party 1 from learning of either the full public key or final > signature seems straightforward, if party 1 doesn't not need to > independently compute and verify c = H(X||R||m) (as they are blinded from > the message in any case). > > > > 1) Key aggregation is performed only by party 2. Party 1 just sends X1 > to party 2. > > 2) Nonce aggregation is performed only by party 2. Party 1 just sends R1 > to party 2. > > 3) Party 2 computes c = H(X||R||m) and sends it to party 1 in order to > compute s1 = c.a1.x1 + r1 > > > > Party 1 never learns the final value of (R,s1+s2) or m. > > > > Any comments on this or potential issues would be appreciated. > > > > Tom > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 5136 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 14:25 ` Erik Aronesty @ 2023-07-24 16:08 ` Tom Trevethan 0 siblings, 0 replies; 34+ messages in thread From: Tom Trevethan @ 2023-07-24 16:08 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4836 bytes --] Hi Eric, Yes, this was my thinking. The current statechain protocol requires that the sender of a coin sign the statechain with their public key, which is then verified by the receiver. The receiver also verifies that this (sender) public key aggregated with the current server public key corresponds to the public key (TR address) of the coin. This prevents a 'rogue key' attack by the sender and verifies that this coin cannot be spent without cooperation of the server. On Mon, Jul 24, 2023 at 3:25 PM Erik Aronesty <erik@q32•com> wrote: > as long as all parties provide a proof of secret key along with their > public key, that should not be possible > > or you can do it as a two-step process where all parties provide a > commitment to the public key and nobody reveals a public key until that > commitment is received > > or if you want to be paranoid you can do both > > On Mon, Jul 24, 2023, 7:00 AM ZmnSCPxj via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> Good morning Tom, >> >> Would this allow party 2 to itself be composed of N >= 2 parties? >> >> MuSig2 (as opposed to MuSig1) requires that signatories provide multiple >> `R` points, not just one each, which are finally aggregated by first >> combining them using the MuSig() public key compose function. >> This prevents party 2 from creating an `R` that may allow it to perform >> certain attacks whose name escapes me right now but which I used to know. >> (it is the reason why MuSig1 requires 3 round trips, and why MuSig2 >> requires at least 2 `R` nonces per signatory) >> >> Your scheme has only one `R` per party, would it not be vulnerably to >> that attack? >> >> Regards, >> ZmnSCPxj >> >> >> Sent with Proton Mail secure email. >> >> ------- Original Message ------- >> On Monday, July 24th, 2023 at 7:46 AM, Tom Trevethan via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >> >> > We are implementing a version of 2-of-2 Schnorr Musig2 for statechains >> where the server (party 1 in the 2-of-2) will be fully 'blinded' - in that >> it can hold a private key that is required to generate an aggregate >> signature on an aggregate public key, but that it does not learn either: 1) >> The aggregate public key 2) The aggregate signature and 3) The message (m) >> being signed. >> > >> > In the model of blinded statechains, the security rests on the >> statechain server being trusted to report the NUMBER of partial signatures >> it has generated for a particular key (as opposed to being trusted to >> enforce rules on WHAT it has signed in the unblinded case) and the full set >> of signatures generated being verified client side >> https://github.com/commerceblock/mercury/blob/master/doc/merc_blind.md#blinding-considerations >> > >> > Given the 2-of-2 musig2 protocol operates as follows (in the following >> description, private keys (field elements) are denoted using lower case >> letters, and elliptic curve points as uppercase letters. G is the generator >> point and point multiplication denoted as X = xG and point addition as A = >> G + G): >> > >> > Party 1 generates private key x1 and public key X1 = x1G. Party 2 >> generates private key x2 and public key X2 = x2G. The set of pubkeys is L = >> {X1,X2}. The key aggregation coefficient is KeyAggCoef(L,X) = H(L,X). The >> shared (aggregate) public key X = a1X1 + a2X2 where a1 = KeyAggCoef(L,X1) >> and a2 = KeyAggCoef(L,X2). >> > >> > To sign a message m, party 1 generates nonce r1 and R1 = r1G. Party 2 >> generates nonce r2 and R2 = r2G. These are aggregated into R = R1 + R2. >> > >> > Party 1 then computes 'challenge' c = H(X||R||m) and s1 = c.a1.x1 + r1 >> > Party 2 then computes 'challenge' c = H(X||R||m) and s2 = c.a2.x2 + r2 >> > >> > The final signature is then (R,s1+s2). >> > >> > In the case of blinding this for party 1: >> > >> > To prevent party 1 from learning of either the full public key or final >> signature seems straightforward, if party 1 doesn't not need to >> independently compute and verify c = H(X||R||m) (as they are blinded from >> the message in any case). >> > >> > 1) Key aggregation is performed only by party 2. Party 1 just sends X1 >> to party 2. >> > 2) Nonce aggregation is performed only by party 2. Party 1 just sends >> R1 to party 2. >> > 3) Party 2 computes c = H(X||R||m) and sends it to party 1 in order to >> compute s1 = c.a1.x1 + r1 >> > >> > Party 1 never learns the final value of (R,s1+s2) or m. >> > >> > Any comments on this or potential issues would be appreciated. >> > >> > Tom >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > [-- Attachment #2: Type: text/html, Size: 6025 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 10:50 ` ZmnSCPxj 2023-07-24 14:25 ` Erik Aronesty @ 2023-07-24 15:57 ` Tom Trevethan 1 sibling, 0 replies; 34+ messages in thread From: Tom Trevethan @ 2023-07-24 15:57 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 3844 bytes --] Hi ZmnSCPxj, Yes, you are correct - the full scheme ( https://eprint.iacr.org/2020/1261.pdf) should have two or more nonces (and also compute b). I don't think this changes the approach to blinding however. On Mon, Jul 24, 2023 at 11:50 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote: > Good morning Tom, > > Would this allow party 2 to itself be composed of N >= 2 parties? > > MuSig2 (as opposed to MuSig1) requires that signatories provide multiple > `R` points, not just one each, which are finally aggregated by first > combining them using the MuSig() public key compose function. > This prevents party 2 from creating an `R` that may allow it to perform > certain attacks whose name escapes me right now but which I used to know. > (it is the reason why MuSig1 requires 3 round trips, and why MuSig2 > requires at least 2 `R` nonces per signatory) > > Your scheme has only one `R` per party, would it not be vulnerably to that > attack? > > Regards, > ZmnSCPxj > > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Monday, July 24th, 2023 at 7:46 AM, Tom Trevethan via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > > > We are implementing a version of 2-of-2 Schnorr Musig2 for statechains > where the server (party 1 in the 2-of-2) will be fully 'blinded' - in that > it can hold a private key that is required to generate an aggregate > signature on an aggregate public key, but that it does not learn either: 1) > The aggregate public key 2) The aggregate signature and 3) The message (m) > being signed. > > > > In the model of blinded statechains, the security rests on the > statechain server being trusted to report the NUMBER of partial signatures > it has generated for a particular key (as opposed to being trusted to > enforce rules on WHAT it has signed in the unblinded case) and the full set > of signatures generated being verified client side > https://github.com/commerceblock/mercury/blob/master/doc/merc_blind.md#blinding-considerations > > > > Given the 2-of-2 musig2 protocol operates as follows (in the following > description, private keys (field elements) are denoted using lower case > letters, and elliptic curve points as uppercase letters. G is the generator > point and point multiplication denoted as X = xG and point addition as A = > G + G): > > > > Party 1 generates private key x1 and public key X1 = x1G. Party 2 > generates private key x2 and public key X2 = x2G. The set of pubkeys is L = > {X1,X2}. The key aggregation coefficient is KeyAggCoef(L,X) = H(L,X). The > shared (aggregate) public key X = a1X1 + a2X2 where a1 = KeyAggCoef(L,X1) > and a2 = KeyAggCoef(L,X2). > > > > To sign a message m, party 1 generates nonce r1 and R1 = r1G. Party 2 > generates nonce r2 and R2 = r2G. These are aggregated into R = R1 + R2. > > > > Party 1 then computes 'challenge' c = H(X||R||m) and s1 = c.a1.x1 + r1 > > Party 2 then computes 'challenge' c = H(X||R||m) and s2 = c.a2.x2 + r2 > > > > The final signature is then (R,s1+s2). > > > > In the case of blinding this for party 1: > > > > To prevent party 1 from learning of either the full public key or final > signature seems straightforward, if party 1 doesn't not need to > independently compute and verify c = H(X||R||m) (as they are blinded from > the message in any case). > > > > 1) Key aggregation is performed only by party 2. Party 1 just sends X1 > to party 2. > > 2) Nonce aggregation is performed only by party 2. Party 1 just sends R1 > to party 2. > > 3) Party 2 computes c = H(X||R||m) and sends it to party 1 in order to > compute s1 = c.a1.x1 + r1 > > > > Party 1 never learns the final value of (R,s1+s2) or m. > > > > Any comments on this or potential issues would be appreciated. > > > > Tom > [-- Attachment #2: Type: text/html, Size: 4543 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 7:46 [bitcoin-dev] Blinded 2-party Musig2 Tom Trevethan 2023-07-24 10:50 ` ZmnSCPxj @ 2023-07-24 14:12 ` Jonas Nick 2023-07-24 14:40 ` Erik Aronesty 2023-07-24 16:51 ` AdamISZ 2023-07-24 15:39 ` Jonas Nick 2 siblings, 2 replies; 34+ messages in thread From: Jonas Nick @ 2023-07-24 14:12 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion Hi Tom, I'm not convinced that this works. As far as I know blind musig is still an open research problem. What the scheme you propose appears to try to prevent is that the server signs K times, but the client ends up with K+1 Schnorr signatures for the aggregate of the server's and the clients key. I think it's possible to apply a variant of the attack that makes MuSig1 insecure if the nonce commitment round was skipped or if the message isn't determined before sending the nonce. Here's how a malicious client would do that: - Obtain K R-values R1[0], ..., R1[K-1] from the server - Let R[i] := R1[i] + R2[i] for all i <= K-1 R[K] := R1[0] + ... + R1[K-1] c[i] := H(X, R[i], m[i]) for all i <= K. Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that c[0] + ... + c[K-1] = c[K]. - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. - Let s[K] = s[0] + ... + s[K-1]. Then (s[K], R[K]) is a valid signature from the server, since s[K]*G = R[K] + c[K]*a1*X1, which the client can complete to a signature for public key X. What may work in your case is the following scheme: - Client sends commitment to the public key X2, nonce R2 and message m to the server. - Server replies with nonce R1 = k1*G - Client sends c to the server and proves in zero knowledge that c = SHA256(X1 + X2, R1 + R2, m). - Server replies with s1 = k1 + c*x1 However, this is just some quick intuition and I'm not sure if this actually works, but maybe worth exploring. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 14:12 ` Jonas Nick @ 2023-07-24 14:40 ` Erik Aronesty 2023-07-24 15:40 ` Jonas Nick 2023-07-24 16:51 ` AdamISZ 1 sibling, 1 reply; 34+ messages in thread From: Erik Aronesty @ 2023-07-24 14:40 UTC (permalink / raw) To: Jonas Nick, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1984 bytes --] You can't choose R if you provide posk On Mon, Jul 24, 2023 at 10:31 AM Jonas Nick via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Hi Tom, > > I'm not convinced that this works. As far as I know blind musig is still > an open > research problem. What the scheme you propose appears to try to prevent is > that > the server signs K times, but the client ends up with K+1 Schnorr > signatures for > the aggregate of the server's and the clients key. I think it's possible to > apply a variant of the attack that makes MuSig1 insecure if the nonce > commitment > round was skipped or if the message isn't determined before sending the > nonce. > Here's how a malicious client would do that: > > - Obtain K R-values R1[0], ..., R1[K-1] from the server > - Let > R[i] := R1[i] + R2[i] for all i <= K-1 > R[K] := R1[0] + ... + R1[K-1] > c[i] := H(X, R[i], m[i]) for all i <= K. > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that > c[0] + ... + c[K-1] = c[K]. > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. > - Let > s[K] = s[0] + ... + s[K-1]. > Then (s[K], R[K]) is a valid signature from the server, since > s[K]*G = R[K] + c[K]*a1*X1, > which the client can complete to a signature for public key X. > > What may work in your case is the following scheme: > - Client sends commitment to the public key X2, nonce R2 and message m to > the > server. > - Server replies with nonce R1 = k1*G > - Client sends c to the server and proves in zero knowledge that c = > SHA256(X1 + X2, R1 + R2, m). > - Server replies with s1 = k1 + c*x1 > > However, this is just some quick intuition and I'm not sure if this > actually > works, but maybe worth exploring. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 2582 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 14:40 ` Erik Aronesty @ 2023-07-24 15:40 ` Jonas Nick 0 siblings, 0 replies; 34+ messages in thread From: Jonas Nick @ 2023-07-24 15:40 UTC (permalink / raw) To: Erik Aronesty, Bitcoin Protocol Discussion Not sure what "posk" is or how it relates to the attack. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 14:12 ` Jonas Nick 2023-07-24 14:40 ` Erik Aronesty @ 2023-07-24 16:51 ` AdamISZ 2023-07-25 14:12 ` Erik Aronesty 1 sibling, 1 reply; 34+ messages in thread From: AdamISZ @ 2023-07-24 16:51 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion @ZmnSCPxj: yes, Wagner is the attack you were thinking of. And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the R commitments. @Tom: As per above it seems you were more considering MuSig1 here, not MuSig2. At least in this version. So you need the initial commitments to R. Jonas' reply clearly has covered a lot of what matters here, but I wanted to mention (using your notation): in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c could be given to the server, to construct s1, but since a1 = H(L, X1) and L is the serialization of all (in this case, 2) keys, that wouldn't work for blinding the final key, right? But, is it possible that this addresses the other problem? If the server is given c1*a1 instead as the challenge for signing (with their "pure" key x1), then perhaps it avoids the issue? Given what's on the blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 + a2X2, is it the case that you cannot find a1 and therefore you cannot correlate the transaction with just the quantity 'c1*a1' which the server sees? But I agree with Jonas that this is just the start, i.e. the fundamental requirement of a blind signing scheme is there has to be some guarantee of no 'one more forgery' possibility, so presumably there has to be some proof that the signing request is 'well formed' (Jonas expresses it below as a ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the face of it, that is what's needed). @Jonas, Erik: 'posk' is probably meant as 'proof of secret key' which may(?) be a mixup with what is sometimes referred to in the literature as "KOSK" (iirc they used it in FROST for example). It isn't clear to me yet how that factors into this scenario, although ofc it is for sure a potential building block of these constructions. Sent with Proton Mail secure email. ------- Original Message ------- On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Hi Tom, > > I'm not convinced that this works. As far as I know blind musig is still an open > research problem. What the scheme you propose appears to try to prevent is that > the server signs K times, but the client ends up with K+1 Schnorr signatures for > the aggregate of the server's and the clients key. I think it's possible to > apply a variant of the attack that makes MuSig1 insecure if the nonce commitment > round was skipped or if the message isn't determined before sending the nonce. > Here's how a malicious client would do that: > > - Obtain K R-values R1[0], ..., R1[K-1] from the server > - Let > R[i] := R1[i] + R2[i] for all i <= K-1 > R[K] := R1[0] + ... + R1[K-1] > c[i] := H(X, R[i], m[i]) for all i <= K. > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that > c[0] + ... + c[K-1] = c[K]. > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. > - Let > s[K] = s[0] + ... + s[K-1]. > Then (s[K], R[K]) is a valid signature from the server, since > s[K]G = R[K] + c[K]a1X1, > which the client can complete to a signature for public key X. > > What may work in your case is the following scheme: > - Client sends commitment to the public key X2, nonce R2 and message m to the > server. > - Server replies with nonce R1 = k1G > - Client sends c to the server and proves in zero knowledge that c = > SHA256(X1 + X2, R1 + R2, m). > - Server replies with s1 = k1 + c*x1 > > However, this is just some quick intuition and I'm not sure if this actually > works, but maybe worth exploring. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 16:51 ` AdamISZ @ 2023-07-25 14:12 ` Erik Aronesty 2023-07-25 16:05 ` Tom Trevethan 0 siblings, 1 reply; 34+ messages in thread From: Erik Aronesty @ 2023-07-25 14:12 UTC (permalink / raw) To: AdamISZ, Bitcoin Protocol Discussion; +Cc: Tom Trevethan [-- Attachment #1: Type: text/plain, Size: 4378 bytes --] posk is "proof of secret key". so you cannot use wagner to select R On Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > @ZmnSCPxj: > > yes, Wagner is the attack you were thinking of. > > And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the R > commitments. > > @Tom: > As per above it seems you were more considering MuSig1 here, not MuSig2. > At least in this version. So you need the initial commitments to R. > > Jonas' reply clearly has covered a lot of what matters here, but I wanted > to mention (using your notation): > > in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c > could be given to the server, to construct s1, but since a1 = H(L, X1) and > L is the serialization of all (in this case, 2) keys, that wouldn't work > for blinding the final key, right? > But, is it possible that this addresses the other problem? > If the server is given c1*a1 instead as the challenge for signing (with > their "pure" key x1), then perhaps it avoids the issue? Given what's on the > blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 + > a2X2, is it the case that you cannot find a1 and therefore you cannot > correlate the transaction with just the quantity 'c1*a1' which the server > sees? > > But I agree with Jonas that this is just the start, i.e. the fundamental > requirement of a blind signing scheme is there has to be some guarantee of > no 'one more forgery' possibility, so presumably there has to be some proof > that the signing request is 'well formed' (Jonas expresses it below as a > ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the > face of it, that is what's needed). > > @Jonas, Erik: > 'posk' is probably meant as 'proof of secret key' which may(?) be a mixup > with what is sometimes referred to in the literature as "KOSK" (iirc they > used it in FROST for example). It isn't clear to me yet how that factors > into this scenario, although ofc it is for sure a potential building block > of these constructions. > > Sent with Proton Mail secure email. > > ------- Original Message ------- > On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > > > Hi Tom, > > > > I'm not convinced that this works. As far as I know blind musig is still > an open > > research problem. What the scheme you propose appears to try to prevent > is that > > the server signs K times, but the client ends up with K+1 Schnorr > signatures for > > the aggregate of the server's and the clients key. I think it's possible > to > > apply a variant of the attack that makes MuSig1 insecure if the nonce > commitment > > round was skipped or if the message isn't determined before sending the > nonce. > > Here's how a malicious client would do that: > > > > - Obtain K R-values R1[0], ..., R1[K-1] from the server > > - Let > > R[i] := R1[i] + R2[i] for all i <= K-1 > > R[K] := R1[0] + ... + R1[K-1] > > c[i] := H(X, R[i], m[i]) for all i <= K. > > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that > > c[0] + ... + c[K-1] = c[K]. > > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. > > - Let > > s[K] = s[0] + ... + s[K-1]. > > Then (s[K], R[K]) is a valid signature from the server, since > > s[K]G = R[K] + c[K]a1X1, > > which the client can complete to a signature for public key X. > > > > What may work in your case is the following scheme: > > - Client sends commitment to the public key X2, nonce R2 and message m > to the > > server. > > - Server replies with nonce R1 = k1G > > - Client sends c to the server and proves in zero knowledge that c = > > SHA256(X1 + X2, R1 + R2, m). > > - Server replies with s1 = k1 + c*x1 > > > > However, this is just some quick intuition and I'm not sure if this > actually > > works, but maybe worth exploring. > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists•linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 5428 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-25 14:12 ` Erik Aronesty @ 2023-07-25 16:05 ` Tom Trevethan 2023-07-26 4:09 ` Erik Aronesty 0 siblings, 1 reply; 34+ messages in thread From: Tom Trevethan @ 2023-07-25 16:05 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 8215 bytes --] Thanks for the replies. As I understand it, the v=2 nonces signing protocol of musig2 prevents the Wagner attack. Also, that the challenge value c must be blinded from the server to prevent the server from being able to determine the signature from the on-chain state. In addition, in order to update the server (party 1) keyshare when a statecoin is transferred between users, the key aggregation coefficient must be set to 1 for each key. The purpose of this coefficient in the Musig2 protocol is to prevent 'rogue key attacks' where one party can choose a public key derived from both their own secret key and the inverse of the other party's public key giving them the ability to unilaterally produce a valid signature over the aggregate key. However this can be prevented by the party producing a proof of knowledge of the private key corresponding to their supplied public key. This can be a signature, which is produced in any case by signing the statechain state in the mercury protocol. This signature must be verified by the receiver of a coin (who must also verify the server pubkey combines with the sender pubkey to get the coin address) which proves that the server is required to co-sign to generate any signature for this address. Here is a modified protocol: Keygen: Server generates private key x1 and public key X1 = x1.G and sends X1 to user (party 2) User generates private key x2 and public key X2 = x2.G and (random) blinding nonce z and computes the aggregate public key X = z.(X1 + X2) (server never learns of X, X2 or z). Signing: Server generates nonces r11 and r12 and R11 = r11.G and R12 = r12.G and sends R11 and R12 to the user. User generates nonces r21 and r22 and R21 = r21.G and R22 = r22.G User computes R1 = R11 + R21 and R2 = R12 + R22 and b = H(X,(R1,R2),m) and R = R1 + b.R2 and c = (X,R,m) User sends the values y = cz and b to the server. Server computes s1 = yx1 + r11 + br12 and sends it to the user. User computes s2 = yx2 + r21 + br22 and s = s1 + s2 and signature (s,R) Transfer: In a statecoin transfer, when receiving a statecoin, in order to verify that the coin address (i.e. aggregate public key) is shared correctly between the previous owner and the server, the client must verify the following: Retrieve the CURRENT public key from the server for this coin X1. Retrieve the public key X2 and the blinding nonce z from the sender. Verify that z.X1 + X2 = P the address of the statecoin. Verify that the sender has the private key used to generate X2: this is done by verifying the statechain signature over the receiver public key X3 from X2. This proves that the address P was generated (aggregated) with the server and can only be signed with cooperation with the server, i.e. no previous owner can hold the full key. In order to update the key shares on transfer, the following protocol can be used: Server (party 1) generates a random blinding nonce e and sends it to user. User adds their private key to the nonce: t1 = e + x2 Client sends t1 and z to the reciever as part of transfer_msg (encrypted with the receiver public key X3 = x3.G). Receiver client decrypts t1 and then subtracts their private key x3: t2 = e + x2 - x3. Receiver client sends t2 to the server as part of transfer_receiver. Server the updates the private key share x1_2 = x1 + t2 - e = x1 + e + x2 - x3 - e = x1 + x2 - x3 So now, x1_2 + x3 (the aggregation of the new server key share with the new client key share) is equal to x1 + x2 (the aggregation of the old server key share with the old client key share). The server deletes x1. On Tue, Jul 25, 2023 at 3:12 PM Erik Aronesty <erik@q32•com> wrote: > posk is "proof of secret key". so you cannot use wagner to select R > > On Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> @ZmnSCPxj: >> >> yes, Wagner is the attack you were thinking of. >> >> And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the >> R commitments. >> >> @Tom: >> As per above it seems you were more considering MuSig1 here, not MuSig2. >> At least in this version. So you need the initial commitments to R. >> >> Jonas' reply clearly has covered a lot of what matters here, but I wanted >> to mention (using your notation): >> >> in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c >> could be given to the server, to construct s1, but since a1 = H(L, X1) and >> L is the serialization of all (in this case, 2) keys, that wouldn't work >> for blinding the final key, right? >> But, is it possible that this addresses the other problem? >> If the server is given c1*a1 instead as the challenge for signing (with >> their "pure" key x1), then perhaps it avoids the issue? Given what's on the >> blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 + >> a2X2, is it the case that you cannot find a1 and therefore you cannot >> correlate the transaction with just the quantity 'c1*a1' which the server >> sees? >> >> But I agree with Jonas that this is just the start, i.e. the fundamental >> requirement of a blind signing scheme is there has to be some guarantee of >> no 'one more forgery' possibility, so presumably there has to be some proof >> that the signing request is 'well formed' (Jonas expresses it below as a >> ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the >> face of it, that is what's needed). >> >> @Jonas, Erik: >> 'posk' is probably meant as 'proof of secret key' which may(?) be a mixup >> with what is sometimes referred to in the literature as "KOSK" (iirc they >> used it in FROST for example). It isn't clear to me yet how that factors >> into this scenario, although ofc it is for sure a potential building block >> of these constructions. >> >> Sent with Proton Mail secure email. >> >> ------- Original Message ------- >> On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >> >> > Hi Tom, >> > >> > I'm not convinced that this works. As far as I know blind musig is >> still an open >> > research problem. What the scheme you propose appears to try to prevent >> is that >> > the server signs K times, but the client ends up with K+1 Schnorr >> signatures for >> > the aggregate of the server's and the clients key. I think it's >> possible to >> > apply a variant of the attack that makes MuSig1 insecure if the nonce >> commitment >> > round was skipped or if the message isn't determined before sending the >> nonce. >> > Here's how a malicious client would do that: >> > >> > - Obtain K R-values R1[0], ..., R1[K-1] from the server >> > - Let >> > R[i] := R1[i] + R2[i] for all i <= K-1 >> > R[K] := R1[0] + ... + R1[K-1] >> > c[i] := H(X, R[i], m[i]) for all i <= K. >> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >> > c[0] + ... + c[K-1] = c[K]. >> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. >> > - Let >> > s[K] = s[0] + ... + s[K-1]. >> > Then (s[K], R[K]) is a valid signature from the server, since >> > s[K]G = R[K] + c[K]a1X1, >> > which the client can complete to a signature for public key X. >> > >> > What may work in your case is the following scheme: >> > - Client sends commitment to the public key X2, nonce R2 and message m >> to the >> > server. >> > - Server replies with nonce R1 = k1G >> > - Client sends c to the server and proves in zero knowledge that c = >> > SHA256(X1 + X2, R1 + R2, m). >> > - Server replies with s1 = k1 + c*x1 >> > >> > However, this is just some quick intuition and I'm not sure if this >> actually >> > works, but maybe worth exploring. >> > _______________________________________________ >> > bitcoin-dev mailing list >> > bitcoin-dev@lists•linuxfoundation.org >> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > [-- Attachment #2: Type: text/html, Size: 9507 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-25 16:05 ` Tom Trevethan @ 2023-07-26 4:09 ` Erik Aronesty 2023-07-26 17:40 ` Andrew Poelstra 2023-07-26 19:59 ` Jonas Nick 0 siblings, 2 replies; 34+ messages in thread From: Erik Aronesty @ 2023-07-26 4:09 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 9060 bytes --] personally, i think *any* time a public key is transmitted, it should come with a "proof of secret key". it should be baked-in to low level protocols so that people don't accidentally create vulns. alt discussion link: https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406 On Tue, Jul 25, 2023 at 5:18 PM Tom Trevethan via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Thanks for the replies. As I understand it, the v=2 nonces signing > protocol of musig2 prevents the Wagner attack. Also, that the challenge > value c must be blinded from the server to prevent the server from being > able to determine the signature from the on-chain state. > > In addition, in order to update the server (party 1) keyshare when a > statecoin is transferred between users, the key aggregation coefficient > must be set to 1 for each key. The purpose of this coefficient in the > Musig2 protocol is to prevent 'rogue key attacks' where one party can > choose a public key derived from both their own secret key and the inverse > of the other party's public key giving them the ability to unilaterally > produce a valid signature over the aggregate key. However this can be > prevented by the party producing a proof of knowledge of the private key > corresponding to their supplied public key. This can be a signature, which > is produced in any case by signing the statechain state in the mercury > protocol. This signature must be verified by the receiver of a coin (who > must also verify the server pubkey combines with the sender pubkey to get > the coin address) which proves that the server is required to co-sign to > generate any signature for this address. > > Here is a modified protocol: > > Keygen: > > Server generates private key x1 and public key X1 = x1.G and sends X1 to > user (party 2) > User generates private key x2 and public key X2 = x2.G and (random) > blinding nonce z and computes the aggregate public key X = z.(X1 + X2) > (server never learns of X, X2 or z). > > Signing: > > Server generates nonces r11 and r12 and R11 = r11.G and R12 = r12.G and > sends R11 and R12 to the user. > User generates nonces r21 and r22 and R21 = r21.G and R22 = r22.G > User computes R1 = R11 + R21 and R2 = R12 + R22 and b = H(X,(R1,R2),m) and > R = R1 + b.R2 and c = (X,R,m) > User sends the values y = cz and b to the server. > Server computes s1 = yx1 + r11 + br12 and sends it to the user. > User computes s2 = yx2 + r21 + br22 and s = s1 + s2 and signature (s,R) > > Transfer: > > In a statecoin transfer, when receiving a statecoin, in order to verify > that the coin address (i.e. aggregate public key) is shared correctly > between the previous owner and the server, the client must verify the > following: > > Retrieve the CURRENT public key from the server for this coin X1. > Retrieve the public key X2 and the blinding nonce z from the sender. > Verify that z.X1 + X2 = P the address of the statecoin. > Verify that the sender has the private key used to generate X2: this is > done by verifying the statechain signature over the receiver public key X3 > from X2. > This proves that the address P was generated (aggregated) with the server > and can only be signed with cooperation with the server, i.e. no previous > owner can hold the full key. > > In order to update the key shares on transfer, the following protocol can > be used: > > Server (party 1) generates a random blinding nonce e and sends it to user. > User adds their private key to the nonce: t1 = e + x2 > Client sends t1 and z to the reciever as part of transfer_msg (encrypted > with the receiver public key X3 = x3.G). > Receiver client decrypts t1 and then subtracts their private key x3: t2 = > e + x2 - x3. > Receiver client sends t2 to the server as part of transfer_receiver. > Server the updates the private key share x1_2 = x1 + t2 - e = x1 + e + x2 > - x3 - e = x1 + x2 - x3 > So now, x1_2 + x3 (the aggregation of the new server key share with the > new client key share) is equal to x1 + x2 (the aggregation of the old > server key share with the old client key share). > The server deletes x1. > > On Tue, Jul 25, 2023 at 3:12 PM Erik Aronesty <erik@q32•com> wrote: > >> posk is "proof of secret key". so you cannot use wagner to select R >> >> On Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >>> @ZmnSCPxj: >>> >>> yes, Wagner is the attack you were thinking of. >>> >>> And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the >>> R commitments. >>> >>> @Tom: >>> As per above it seems you were more considering MuSig1 here, not MuSig2. >>> At least in this version. So you need the initial commitments to R. >>> >>> Jonas' reply clearly has covered a lot of what matters here, but I >>> wanted to mention (using your notation): >>> >>> in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c >>> could be given to the server, to construct s1, but since a1 = H(L, X1) and >>> L is the serialization of all (in this case, 2) keys, that wouldn't work >>> for blinding the final key, right? >>> But, is it possible that this addresses the other problem? >>> If the server is given c1*a1 instead as the challenge for signing (with >>> their "pure" key x1), then perhaps it avoids the issue? Given what's on the >>> blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 + >>> a2X2, is it the case that you cannot find a1 and therefore you cannot >>> correlate the transaction with just the quantity 'c1*a1' which the server >>> sees? >>> >>> But I agree with Jonas that this is just the start, i.e. the fundamental >>> requirement of a blind signing scheme is there has to be some guarantee of >>> no 'one more forgery' possibility, so presumably there has to be some proof >>> that the signing request is 'well formed' (Jonas expresses it below as a >>> ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the >>> face of it, that is what's needed). >>> >>> @Jonas, Erik: >>> 'posk' is probably meant as 'proof of secret key' which may(?) be a >>> mixup with what is sometimes referred to in the literature as "KOSK" (iirc >>> they used it in FROST for example). It isn't clear to me yet how that >>> factors into this scenario, although ofc it is for sure a potential >>> building block of these constructions. >>> >>> Sent with Proton Mail secure email. >>> >>> ------- Original Message ------- >>> On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev < >>> bitcoin-dev@lists•linuxfoundation.org> wrote: >>> >>> >>> > Hi Tom, >>> > >>> > I'm not convinced that this works. As far as I know blind musig is >>> still an open >>> > research problem. What the scheme you propose appears to try to >>> prevent is that >>> > the server signs K times, but the client ends up with K+1 Schnorr >>> signatures for >>> > the aggregate of the server's and the clients key. I think it's >>> possible to >>> > apply a variant of the attack that makes MuSig1 insecure if the nonce >>> commitment >>> > round was skipped or if the message isn't determined before sending >>> the nonce. >>> > Here's how a malicious client would do that: >>> > >>> > - Obtain K R-values R1[0], ..., R1[K-1] from the server >>> > - Let >>> > R[i] := R1[i] + R2[i] for all i <= K-1 >>> > R[K] := R1[0] + ... + R1[K-1] >>> > c[i] := H(X, R[i], m[i]) for all i <= K. >>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>> > c[0] + ... + c[K-1] = c[K]. >>> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. >>> > - Let >>> > s[K] = s[0] + ... + s[K-1]. >>> > Then (s[K], R[K]) is a valid signature from the server, since >>> > s[K]G = R[K] + c[K]a1X1, >>> > which the client can complete to a signature for public key X. >>> > >>> > What may work in your case is the following scheme: >>> > - Client sends commitment to the public key X2, nonce R2 and message m >>> to the >>> > server. >>> > - Server replies with nonce R1 = k1G >>> > - Client sends c to the server and proves in zero knowledge that c = >>> > SHA256(X1 + X2, R1 + R2, m). >>> > - Server replies with s1 = k1 + c*x1 >>> > >>> > However, this is just some quick intuition and I'm not sure if this >>> actually >>> > works, but maybe worth exploring. >>> > _______________________________________________ >>> > bitcoin-dev mailing list >>> > bitcoin-dev@lists•linuxfoundation.org >>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists•linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 10705 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 4:09 ` Erik Aronesty @ 2023-07-26 17:40 ` Andrew Poelstra 2023-07-26 19:59 ` Jonas Nick 1 sibling, 0 replies; 34+ messages in thread From: Andrew Poelstra @ 2023-07-26 17:40 UTC (permalink / raw) To: Erik Aronesty, Bitcoin Protocol Discussion; +Cc: Tom Trevethan [-- Attachment #1: Type: text/plain, Size: 2463 bytes --] On Wed, Jul 26, 2023 at 12:09:41AM -0400, Erik Aronesty via bitcoin-dev wrote: > personally, i think *any* time a public key is transmitted, it should come > with a "proof of secret key". it should be baked-in to low level > protocols so that people don't accidentally create vulns. alt discussion > link: https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406 > POSK is not a panacea. For example, if you were to try to eliminate rogue key attacks in MuSig by using POSK rather than by rerandomizing the keys, the last person to contribute a key could add a Taproot commitment to their key, thereby modifying the final key to have a Taproot spending path that other participants don't know about. If they did this, they'd have no problem producing a POSK since Taproot commitments don't affect knowledge of the secret key. POSKs are also logistically difficult to produce in many contexts. They essentially require an interactive challege-response (otherwise somebody could just copy a POSK from some other source), meaning that all participants need to be online and have secret key access at key setup time. In some contexts maybe it's sufficient to have a static POSK. Aside from the complexity of determining this, you then need a key serialization format that includes the POSK. There are standard key formats for all widely used EC keys but none have a facility for this. If you are trying to use already-published keys that do not have a POSK attached, you are out of luck. If your protocol requires POSKs to be provably published, you also run into difficulties because they don't make sense to embed on-chain (since blockchain validators don't care about them, and they're twice as big as the keys themselves) so you need to establish some other publication medium. If you want to support nested multisignatures, you need to jointly produce POSKs, which requires its own protocol complexity. The MuSig and MuSig2 papers say essentially the same thing as the above; it's why we put so much effort into developing a scheme which was provably secure in the plain public key model, which means that POSKs are superfluous and you don't need to deal with all these logistical hurdles. -- Andrew Poelstra Director of Research, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 488 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 4:09 ` Erik Aronesty 2023-07-26 17:40 ` Andrew Poelstra @ 2023-07-26 19:59 ` Jonas Nick 2023-07-26 20:35 ` Tom Trevethan 1 sibling, 1 reply; 34+ messages in thread From: Jonas Nick @ 2023-07-26 19:59 UTC (permalink / raw) To: Erik Aronesty, Bitcoin Protocol Discussion, Tom Trevethan None of the attacks mentioned in this thread so far (ZmnSCPxj mentioned an attack on the nonces, I mentioned an attack on the challenge c) can be prevented by proving knowledge of the signing key (usually known as proof of possession, PoP). ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 19:59 ` Jonas Nick @ 2023-07-26 20:35 ` Tom Trevethan 2023-07-26 22:06 ` Erik Aronesty 2023-07-27 8:07 ` Jonas Nick 0 siblings, 2 replies; 34+ messages in thread From: Tom Trevethan @ 2023-07-26 20:35 UTC (permalink / raw) To: Jonas Nick; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 504 bytes --] Not 'signing' but 'secret' i.e. the r values (ephemeral keys). Proof of knowledge of the r values used to generate each R used prevents the Wagner attack, no? On Wed, Jul 26, 2023 at 8:59 PM Jonas Nick <jonasdnick@gmail•com> wrote: > None of the attacks mentioned in this thread so far (ZmnSCPxj mentioned an > attack on the nonces, I mentioned an attack on the challenge c) can be > prevented > by proving knowledge of the signing key (usually known as proof of > possession, > PoP). > [-- Attachment #2: Type: text/html, Size: 793 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 20:35 ` Tom Trevethan @ 2023-07-26 22:06 ` Erik Aronesty 2023-07-27 2:54 ` Lloyd Fournier 2023-07-27 8:07 ` Jonas Nick 1 sibling, 1 reply; 34+ messages in thread From: Erik Aronesty @ 2023-07-26 22:06 UTC (permalink / raw) To: Tom Trevethan; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 663 bytes --] correct. you cannot select R if it is shipped with a POP On Wed, Jul 26, 2023, 4:35 PM Tom Trevethan <tom@commerceblock•com> wrote: > Not 'signing' but 'secret' i.e. the r values (ephemeral keys). Proof of > knowledge of the r values used to generate each R used prevents the Wagner > attack, no? > > On Wed, Jul 26, 2023 at 8:59 PM Jonas Nick <jonasdnick@gmail•com> wrote: > >> None of the attacks mentioned in this thread so far (ZmnSCPxj mentioned an >> attack on the nonces, I mentioned an attack on the challenge c) can be >> prevented >> by proving knowledge of the signing key (usually known as proof of >> possession, >> PoP). >> > [-- Attachment #2: Type: text/html, Size: 1227 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 22:06 ` Erik Aronesty @ 2023-07-27 2:54 ` Lloyd Fournier 0 siblings, 0 replies; 34+ messages in thread From: Lloyd Fournier @ 2023-07-27 2:54 UTC (permalink / raw) To: Erik Aronesty, Bitcoin Protocol Discussion; +Cc: Tom Trevethan [-- Attachment #1: Type: text/plain, Size: 1870 bytes --] Hello all, 1. No proof of knowledge of each R does *NOT* prevent wagner's attack. 2. In my mind, A generic blind signing service is sufficient for doing blinded MuSig, Muig2, FROST or whatever without the blind signing service knowing. You don't need a specialized MuSig2 blind singing service to extract MuSig2 compatible shares from it. You can just add the MuSig tweak (and/or BIP32 etc) to their key when you do the blind signing request (this seemed to be what the OP was suggesting). Making the server have multiple nonces like in MuSig2 proper doesn't help the server's security at all. I think the problem is simply reduced to creating a secure blind schnorr signing service. Jonas mentioned some papers which show how to do that. The question is mostly about whether you can practically integrate those tricks into your protocol which might be tricky. LL On Thu, 27 Jul 2023 at 08:20, Erik Aronesty via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > correct. you cannot select R if it is shipped with a POP > > On Wed, Jul 26, 2023, 4:35 PM Tom Trevethan <tom@commerceblock•com> wrote: > >> Not 'signing' but 'secret' i.e. the r values (ephemeral keys). Proof of >> knowledge of the r values used to generate each R used prevents the Wagner >> attack, no? >> >> On Wed, Jul 26, 2023 at 8:59 PM Jonas Nick <jonasdnick@gmail•com> wrote: >> >>> None of the attacks mentioned in this thread so far (ZmnSCPxj mentioned >>> an >>> attack on the nonces, I mentioned an attack on the challenge c) can be >>> prevented >>> by proving knowledge of the signing key (usually known as proof of >>> possession, >>> PoP). >>> >> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 3002 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 20:35 ` Tom Trevethan 2023-07-26 22:06 ` Erik Aronesty @ 2023-07-27 8:07 ` Jonas Nick [not found] ` <CAJvkSsfa8rzbwXiatZBpwQ6d4d94yLQifK8gyq3k-rq_1SH4OQ@mail.gmail.com> 1 sibling, 1 reply; 34+ messages in thread From: Jonas Nick @ 2023-07-27 8:07 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion No, proof of knowledge of the r values used to generate each R does not prevent Wagner's attack. I wrote > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that > c[0] + ... + c[K-1] = c[K]. You can think of this as actually choosing scalars r2[0], ..., r2[K-1] and define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't make sense if he didn't. ^ permalink raw reply [flat|nested] 34+ messages in thread
[parent not found: <CAJvkSsfa8rzbwXiatZBpwQ6d4d94yLQifK8gyq3k-rq_1SH4OQ@mail.gmail.com>]
* [bitcoin-dev] Fwd: Blinded 2-party Musig2 [not found] ` <CAJvkSsfa8rzbwXiatZBpwQ6d4d94yLQifK8gyq3k-rq_1SH4OQ@mail.gmail.com> @ 2023-07-27 13:25 ` Tom Trevethan 2023-08-07 0:55 ` [bitcoin-dev] " Tom Trevethan 0 siblings, 1 reply; 34+ messages in thread From: Tom Trevethan @ 2023-07-27 13:25 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1441 bytes --] @Jonas OK, thanks, I get the logic now. I believe this attack can be mitigated (at least in the case of using this scheme for statechains) by the receiver of a coin verifying the construction of all previous challenges. So in this case, the sender of a coin would record R2[K-1] in addition to m (and any c blinding nonce used) for the signature it generates with the server. It would then send this (and all previous R2 values i = 0, ..., K-2) to the receiver. The receiver would then query the server for the full set (i = 0, ..., K-1) of R1[i] values it has generated, and the corresponding (blinded) c[i] values used for each co-signing it has performed on this key. The receiver would then verify that each previous c[i] (i = 0, ... K-1) has been correctly formed and includes the server generated R1[i]. If any of the c values fail to verify against the values of R1 provided by the server, then the coin is invalid. On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: > No, proof of knowledge of the r values used to generate each R does not > prevent > Wagner's attack. I wrote > > > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that > > c[0] + ... + c[K-1] = c[K]. > > You can think of this as actually choosing scalars r2[0], ..., r2[K-1] and > define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't > make > sense if he didn't. > [-- Attachment #2: Type: text/html, Size: 2040 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-27 13:25 ` [bitcoin-dev] Fwd: " Tom Trevethan @ 2023-08-07 0:55 ` Tom Trevethan 2023-08-08 17:44 ` moonsettler 2023-08-30 10:52 ` Tom Trevethan 0 siblings, 2 replies; 34+ messages in thread From: Tom Trevethan @ 2023-08-07 0:55 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2275 bytes --] A follow up to this, I have updated the blinded statechain protocol description to include the mitigation to the Wagner attack by requiring the server to send R1 values only after commitments made to the server of the R2 values used by the user, and that all the previous computed c values are verified by each new statecoin owner. https://github.com/commerceblock/mercury/blob/master/layer/protocol.md Essentially, the attack is possible because the server cannot verify that the blinded challenge (c) value it has been sent by the user has been computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN be verified by each new owner of a statecoin for all the previous signatures. Each time an owner cooperates with the server to generate a signature on a backup tx, the server will require that the owner send a commitment to their R2 value: e.g. SHA256(R2). The server will store this value before responding with it's R1 value. This way, the owner cannot choose the value of R2 (and hence c). When the statecoin is received by a new owner, they will receive ALL previous signed backup txs for that coin from the sender, and all the corresponding R2 values used for each signature. They will then ask the server (for each previous signature), the commitments SHA256(R2) and the corresponding server generated R1 value and c value used. The new owner will then verify that each backup tx is valid, and that each c value was computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals SHA256(R2). This ensures that a previous owner could not have generated more valid signatures than the server has partially signed. On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> wrote: > > On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: > >> No, proof of knowledge of the r values used to generate each R does not >> prevent >> Wagner's attack. I wrote >> >> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >> > c[0] + ... + c[K-1] = c[K]. >> >> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] and >> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't >> make >> sense if he didn't. >> > [-- Attachment #2: Type: text/html, Size: 3110 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-07 0:55 ` [bitcoin-dev] " Tom Trevethan @ 2023-08-08 17:44 ` moonsettler 2023-08-09 15:14 ` Tom Trevethan 2023-08-30 10:52 ` Tom Trevethan 1 sibling, 1 reply; 34+ messages in thread From: moonsettler @ 2023-08-08 17:44 UTC (permalink / raw) To: Tom Trevethan; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2678 bytes --] Very nice! Is there an authentication mechanism to avoid 'breaking the chain' with an unverifiable new state by a previous owner? Can the current owner prove the knowledge of a non-identifying secret he learned as recipient to the server that is related to the statechain tip? BR, moonsettler ------- Original Message ------- On Monday, August 7th, 2023 at 2:55 AM, Tom Trevethan via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > A follow up to this, I have updated the blinded statechain protocol description to include the mitigation to the Wagner attack by requiring the server to send R1 values only after commitments made to the server of the R2 values used by the user, and that all the previous computed c values are verified by each new statecoin owner. > https://github.com/commerceblock/mercury/blob/master/layer/protocol.md > > Essentially, the attack is possible because the server cannot verify that the blinded challenge (c) value it has been sent by the user has been computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN be verified by each new owner of a statecoin for all the previous signatures. > > Each time an owner cooperates with the server to generate a signature on a backup tx, the server will require that the owner send a commitment to their R2 value: e.g. SHA256(R2). The server will store this value before responding with it's R1 value. This way, the owner cannot choose the value of R2 (and hence c). > > When the statecoin is received by a new owner, they will receive ALL previous signed backup txs for that coin from the sender, and all the corresponding R2 values used for each signature. They will then ask the server (for each previous signature), the commitments SHA256(R2) and the corresponding server generated R1 value and c value used. The new owner will then verify that each backup tx is valid, and that each c value was computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals SHA256(R2). This ensures that a previous owner could not have generated more valid signatures than the server has partially signed. > > On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> wrote: > >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: >> >>> No, proof of knowledge of the r values used to generate each R does not prevent >>> Wagner's attack. I wrote >>> >>>> Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>>> c[0] + ... + c[K-1] = c[K]. >>> >>> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] and >>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't make >>> sense if he didn't. [-- Attachment #2: Type: text/html, Size: 4129 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-08 17:44 ` moonsettler @ 2023-08-09 15:14 ` Tom Trevethan 2023-08-10 3:30 ` Lloyd Fournier 0 siblings, 1 reply; 34+ messages in thread From: Tom Trevethan @ 2023-08-09 15:14 UTC (permalink / raw) To: moonsettler, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4231 bytes --] @moonsettler When anyone receives a coin (either as payment or as part of a swap) they need to perform a verification of all previous signatures and corresponding backup txs. If anything is missing, then the verification will fail. So anyone 'breaking the chain' by signing something incorrectly simply cannot then send that coin on. The second point is important. All the 'transfer data' (i.e. new and all previous backup txs, signatures and values) is encrypted with the new owner public key. But the server cannot know this pubkey as this would enable it to compute the full coin pubkey and identify it on-chain. Currently, the server identifies individual coins (shared keys) with a statechain_id identifier (unrelated to the coin outpoint), which is used by the coin receiver to retrieve the transfer data via the API. But this means the receiver must be sent this identifier out-of-band by the sender, and also that if anyone else learns it they can corrupt the server key share/signature chain via the API. One solution to this is to have a second non-identifying key used only for authenticating with the server. This would mean a 'statchain address' would then be composed of 2 separate pubkeys 1) for the shared taproot address and 2) for server authentication. Thanks, Tom On Tue, Aug 8, 2023 at 6:44 PM moonsettler <moonsettler@protonmail•com> wrote: > Very nice! Is there an authentication mechanism to avoid 'breaking the > chain' with an unverifiable new state by a previous owner? Can the current > owner prove the knowledge of a non-identifying secret he learned as > recipient to the server that is related to the statechain tip? > > BR, > moonsettler > > ------- Original Message ------- > On Monday, August 7th, 2023 at 2:55 AM, Tom Trevethan via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > A follow up to this, I have updated the blinded statechain protocol > description to include the mitigation to the Wagner attack by requiring the > server to send R1 values only after commitments made to the server of the > R2 values used by the user, and that all the previous computed c values are > verified by each new statecoin owner. > https://github.com/commerceblock/mercury/blob/master/layer/protocol.md > > Essentially, the attack is possible because the server cannot verify that > the blinded challenge (c) value it has been sent by the user has been > computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN > be verified by each new owner of a statecoin for all the previous > signatures. > > Each time an owner cooperates with the server to generate a signature on a > backup tx, the server will require that the owner send a commitment to > their R2 value: e.g. SHA256(R2). The server will store this value before > responding with it's R1 value. This way, the owner cannot choose the value > of R2 (and hence c). > > When the statecoin is received by a new owner, they will receive ALL > previous signed backup txs for that coin from the sender, and all the > corresponding R2 values used for each signature. They will then ask the > server (for each previous signature), the commitments SHA256(R2) and the > corresponding server generated R1 value and c value used. The new owner > will then verify that each backup tx is valid, and that each c value was > computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals > SHA256(R2). This ensures that a previous owner could not have generated > more valid signatures than the server has partially signed. > > On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> > wrote: > >> >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: >> >>> No, proof of knowledge of the r values used to generate each R does not >>> prevent >>> Wagner's attack. I wrote >>> >>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>> > c[0] + ... + c[K-1] = c[K]. >>> >>> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] >>> and >>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't >>> make >>> sense if he didn't. >>> >> > [-- Attachment #2: Type: text/html, Size: 6092 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-09 15:14 ` Tom Trevethan @ 2023-08-10 3:30 ` Lloyd Fournier 2023-08-10 11:59 ` Tom Trevethan 0 siblings, 1 reply; 34+ messages in thread From: Lloyd Fournier @ 2023-08-10 3:30 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5658 bytes --] Hi Tom, These questions might be wrongheaded since I'm not familiar enough with the statechain protocol. Here goes: Why do you need to use schnorr blind signatures for this? Are the blind signatures being used to produce on-chain tx signatures or are they just for credentials for transferring ownership (or are they for both). If they are for on-chain txs then you won't be able to enforce that the signature used was not generated maliciously so it doesn't seem to me like your trick above would help you here. I can fully verify that the state chain signatures were all produced non-maliciously but then there may be another hidden forged signature that can take the on-chain funds that were produced by malicious signing sessions I was never aware of (or how can you be sure this isn't the case). Following on from that point, is it not possible to enforce sequential blind signing in the statechain protocol under each key. With that you don't have the problem of wagner's attack. LL On Wed, 9 Aug 2023 at 23:34, Tom Trevethan via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > @moonsettler > > When anyone receives a coin (either as payment or as part of a swap) they > need to perform a verification of all previous signatures and > corresponding backup txs. If anything is missing, then the verification > will fail. So anyone 'breaking the chain' by signing something > incorrectly simply cannot then send that coin on. > > The second point is important. All the 'transfer data' (i.e. new and all > previous backup txs, signatures and values) is encrypted with the new owner > public key. But the server cannot know this pubkey as this would enable it > to compute the full coin pubkey and identify it on-chain. Currently, the > server identifies individual coins (shared keys) with a statechain_id > identifier (unrelated to the coin outpoint), which is used by the coin > receiver to retrieve the transfer data via the API. But this means the > receiver must be sent this identifier out-of-band by the sender, and also > that if anyone else learns it they can corrupt the server key > share/signature chain via the API. One solution to this is to have a second > non-identifying key used only for authenticating with the server. This > would mean a 'statchain address' would then be composed of 2 separate > pubkeys 1) for the shared taproot address and 2) for server authentication. > > Thanks, > > Tom > > On Tue, Aug 8, 2023 at 6:44 PM moonsettler <moonsettler@protonmail•com> > wrote: > >> Very nice! Is there an authentication mechanism to avoid 'breaking the >> chain' with an unverifiable new state by a previous owner? Can the current >> owner prove the knowledge of a non-identifying secret he learned as >> recipient to the server that is related to the statechain tip? >> >> BR, >> moonsettler >> >> ------- Original Message ------- >> On Monday, August 7th, 2023 at 2:55 AM, Tom Trevethan via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >> A follow up to this, I have updated the blinded statechain protocol >> description to include the mitigation to the Wagner attack by requiring the >> server to send R1 values only after commitments made to the server of the >> R2 values used by the user, and that all the previous computed c values are >> verified by each new statecoin owner. >> https://github.com/commerceblock/mercury/blob/master/layer/protocol.md >> >> Essentially, the attack is possible because the server cannot verify that >> the blinded challenge (c) value it has been sent by the user has been >> computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN >> be verified by each new owner of a statecoin for all the previous >> signatures. >> >> Each time an owner cooperates with the server to generate a signature on >> a backup tx, the server will require that the owner send a commitment to >> their R2 value: e.g. SHA256(R2). The server will store this value before >> responding with it's R1 value. This way, the owner cannot choose the value >> of R2 (and hence c). >> >> When the statecoin is received by a new owner, they will receive ALL >> previous signed backup txs for that coin from the sender, and all the >> corresponding R2 values used for each signature. They will then ask the >> server (for each previous signature), the commitments SHA256(R2) and the >> corresponding server generated R1 value and c value used. The new owner >> will then verify that each backup tx is valid, and that each c value was >> computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals >> SHA256(R2). This ensures that a previous owner could not have generated >> more valid signatures than the server has partially signed. >> >> On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> >> wrote: >> >>> >>> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: >>> >>>> No, proof of knowledge of the r values used to generate each R does not >>>> prevent >>>> Wagner's attack. I wrote >>>> >>>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>>> > c[0] + ... + c[K-1] = c[K]. >>>> >>>> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] >>>> and >>>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't >>>> make >>>> sense if he didn't. >>>> >>> >> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 8046 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-10 3:30 ` Lloyd Fournier @ 2023-08-10 11:59 ` Tom Trevethan 2023-08-14 6:31 ` Lloyd Fournier 0 siblings, 1 reply; 34+ messages in thread From: Tom Trevethan @ 2023-08-10 11:59 UTC (permalink / raw) To: Lloyd Fournier; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 6887 bytes --] HI Lloyd, Yes, the blind signatures are for bitcoin transactions (these are timelocked 'backup txs' if the server disappears). This is not standard 'Schnorr blind signature' (like https://suredbits.com/schnorr-applications-blind-signatures/) but a 2-of-2 MuSig where two keys are required to generate the full signature, but one of them (the server) does not learn of either the full key, message (tx) or final signature. The server is explicitly trusted to report the total number of partial signatures it has generated for a specific key. If you can verify that ALL the signatures generated for a specific key were generated correctly, and the total number of them matches the number reported by the server, then there can be no other malicious valid signatures in existence. In this statechain protocol, the receiver of a coin must check all previous backup txs are valid, and that the total number of them matches the server reported signature count before accepting it. On Thu, Aug 10, 2023 at 4:30 AM Lloyd Fournier <lloyd.fourn@gmail•com> wrote: > Hi Tom, > > These questions might be wrongheaded since I'm not familiar enough with > the statechain protocol. Here goes: > > Why do you need to use schnorr blind signatures for this? Are the blind > signatures being used to produce on-chain tx signatures or are they just > for credentials for transferring ownership (or are they for both). If they > are for on-chain txs then you won't be able to enforce that the signature > used was not generated maliciously so it doesn't seem to me like your trick > above would help you here. I can fully verify that the state chain > signatures were all produced non-maliciously but then there may be another > hidden forged signature that can take the on-chain funds that were produced > by malicious signing sessions I was never aware of (or how can you be sure > this isn't the case). > > Following on from that point, is it not possible to enforce sequential > blind signing in the statechain protocol under each key. With that you > don't have the problem of wagner's attack. > > LL > > On Wed, 9 Aug 2023 at 23:34, Tom Trevethan via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> @moonsettler >> >> When anyone receives a coin (either as payment or as part of a swap) they >> need to perform a verification of all previous signatures and >> corresponding backup txs. If anything is missing, then the verification >> will fail. So anyone 'breaking the chain' by signing something >> incorrectly simply cannot then send that coin on. >> >> The second point is important. All the 'transfer data' (i.e. new and all >> previous backup txs, signatures and values) is encrypted with the new owner >> public key. But the server cannot know this pubkey as this would enable it >> to compute the full coin pubkey and identify it on-chain. Currently, the >> server identifies individual coins (shared keys) with a statechain_id >> identifier (unrelated to the coin outpoint), which is used by the coin >> receiver to retrieve the transfer data via the API. But this means the >> receiver must be sent this identifier out-of-band by the sender, and also >> that if anyone else learns it they can corrupt the server key >> share/signature chain via the API. One solution to this is to have a second >> non-identifying key used only for authenticating with the server. This >> would mean a 'statchain address' would then be composed of 2 separate >> pubkeys 1) for the shared taproot address and 2) for server authentication. >> >> Thanks, >> >> Tom >> >> On Tue, Aug 8, 2023 at 6:44 PM moonsettler <moonsettler@protonmail•com> >> wrote: >> >>> Very nice! Is there an authentication mechanism to avoid 'breaking the >>> chain' with an unverifiable new state by a previous owner? Can the current >>> owner prove the knowledge of a non-identifying secret he learned as >>> recipient to the server that is related to the statechain tip? >>> >>> BR, >>> moonsettler >>> >>> ------- Original Message ------- >>> On Monday, August 7th, 2023 at 2:55 AM, Tom Trevethan via bitcoin-dev < >>> bitcoin-dev@lists•linuxfoundation.org> wrote: >>> >>> A follow up to this, I have updated the blinded statechain protocol >>> description to include the mitigation to the Wagner attack by requiring the >>> server to send R1 values only after commitments made to the server of the >>> R2 values used by the user, and that all the previous computed c values are >>> verified by each new statecoin owner. >>> https://github.com/commerceblock/mercury/blob/master/layer/protocol.md >>> >>> Essentially, the attack is possible because the server cannot verify >>> that the blinded challenge (c) value it has been sent by the user has been >>> computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN >>> be verified by each new owner of a statecoin for all the previous >>> signatures. >>> >>> Each time an owner cooperates with the server to generate a signature on >>> a backup tx, the server will require that the owner send a commitment to >>> their R2 value: e.g. SHA256(R2). The server will store this value before >>> responding with it's R1 value. This way, the owner cannot choose the value >>> of R2 (and hence c). >>> >>> When the statecoin is received by a new owner, they will receive ALL >>> previous signed backup txs for that coin from the sender, and all the >>> corresponding R2 values used for each signature. They will then ask the >>> server (for each previous signature), the commitments SHA256(R2) and the >>> corresponding server generated R1 value and c value used. The new owner >>> will then verify that each backup tx is valid, and that each c value was >>> computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals >>> SHA256(R2). This ensures that a previous owner could not have generated >>> more valid signatures than the server has partially signed. >>> >>> On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> >>> wrote: >>> >>>> >>>> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> >>>> wrote: >>>> >>>>> No, proof of knowledge of the r values used to generate each R does >>>>> not prevent >>>>> Wagner's attack. I wrote >>>>> >>>>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>>>> > c[0] + ... + c[K-1] = c[K]. >>>>> >>>>> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] >>>>> and >>>>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack >>>>> wouldn't make >>>>> sense if he didn't. >>>>> >>>> >>> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > [-- Attachment #2: Type: text/html, Size: 9581 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-10 11:59 ` Tom Trevethan @ 2023-08-14 6:31 ` Lloyd Fournier 0 siblings, 0 replies; 34+ messages in thread From: Lloyd Fournier @ 2023-08-14 6:31 UTC (permalink / raw) To: Tom Trevethan; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 7474 bytes --] Hi Tom, Thanks for the explanation. There's one remaining thing that isn't clear: do you actually require parallel signing requests under the same key. It seems to me that the protocol is very sequential in that you are passing a utxo from one point to another in sequence. If so then the Schnorr blind sigs problem doesn't apply. LL On Thu, 10 Aug 2023 at 20:00, Tom Trevethan <tom@commerceblock•com> wrote: > HI Lloyd, > > Yes, the blind signatures are for bitcoin transactions (these are > timelocked 'backup txs' if the server disappears). This is not standard > 'Schnorr blind signature' (like > https://suredbits.com/schnorr-applications-blind-signatures/) but a > 2-of-2 MuSig where two keys are required to generate the full signature, > but one of them (the server) does not learn of either the full key, message > (tx) or final signature. > > The server is explicitly trusted to report the total number of partial > signatures it has generated for a specific key. If you can verify that ALL > the signatures generated for a specific key were generated correctly, and > the total number of them matches the number reported by the server, then > there can be no other malicious valid signatures in existence. In this > statechain protocol, the receiver of a coin must check all previous backup > txs are valid, and that the total number of them matches the server > reported signature count before accepting it. > > On Thu, Aug 10, 2023 at 4:30 AM Lloyd Fournier <lloyd.fourn@gmail•com> > wrote: > >> Hi Tom, >> >> These questions might be wrongheaded since I'm not familiar enough with >> the statechain protocol. Here goes: >> >> Why do you need to use schnorr blind signatures for this? Are the blind >> signatures being used to produce on-chain tx signatures or are they just >> for credentials for transferring ownership (or are they for both). If they >> are for on-chain txs then you won't be able to enforce that the signature >> used was not generated maliciously so it doesn't seem to me like your trick >> above would help you here. I can fully verify that the state chain >> signatures were all produced non-maliciously but then there may be another >> hidden forged signature that can take the on-chain funds that were produced >> by malicious signing sessions I was never aware of (or how can you be sure >> this isn't the case). >> >> Following on from that point, is it not possible to enforce sequential >> blind signing in the statechain protocol under each key. With that you >> don't have the problem of wagner's attack. >> >> LL >> >> On Wed, 9 Aug 2023 at 23:34, Tom Trevethan via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >>> @moonsettler >>> >>> When anyone receives a coin (either as payment or as part of a swap) >>> they need to perform a verification of all previous signatures and >>> corresponding backup txs. If anything is missing, then the verification >>> will fail. So anyone 'breaking the chain' by signing something >>> incorrectly simply cannot then send that coin on. >>> >>> The second point is important. All the 'transfer data' (i.e. new and all >>> previous backup txs, signatures and values) is encrypted with the new owner >>> public key. But the server cannot know this pubkey as this would enable it >>> to compute the full coin pubkey and identify it on-chain. Currently, the >>> server identifies individual coins (shared keys) with a statechain_id >>> identifier (unrelated to the coin outpoint), which is used by the coin >>> receiver to retrieve the transfer data via the API. But this means the >>> receiver must be sent this identifier out-of-band by the sender, and also >>> that if anyone else learns it they can corrupt the server key >>> share/signature chain via the API. One solution to this is to have a second >>> non-identifying key used only for authenticating with the server. This >>> would mean a 'statchain address' would then be composed of 2 separate >>> pubkeys 1) for the shared taproot address and 2) for server authentication. >>> >>> Thanks, >>> >>> Tom >>> >>> On Tue, Aug 8, 2023 at 6:44 PM moonsettler <moonsettler@protonmail•com> >>> wrote: >>> >>>> Very nice! Is there an authentication mechanism to avoid 'breaking the >>>> chain' with an unverifiable new state by a previous owner? Can the current >>>> owner prove the knowledge of a non-identifying secret he learned as >>>> recipient to the server that is related to the statechain tip? >>>> >>>> BR, >>>> moonsettler >>>> >>>> ------- Original Message ------- >>>> On Monday, August 7th, 2023 at 2:55 AM, Tom Trevethan via bitcoin-dev < >>>> bitcoin-dev@lists•linuxfoundation.org> wrote: >>>> >>>> A follow up to this, I have updated the blinded statechain protocol >>>> description to include the mitigation to the Wagner attack by requiring the >>>> server to send R1 values only after commitments made to the server of the >>>> R2 values used by the user, and that all the previous computed c values are >>>> verified by each new statecoin owner. >>>> https://github.com/commerceblock/mercury/blob/master/layer/protocol.md >>>> >>>> Essentially, the attack is possible because the server cannot verify >>>> that the blinded challenge (c) value it has been sent by the user has been >>>> computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN >>>> be verified by each new owner of a statecoin for all the previous >>>> signatures. >>>> >>>> Each time an owner cooperates with the server to generate a signature >>>> on a backup tx, the server will require that the owner send a commitment to >>>> their R2 value: e.g. SHA256(R2). The server will store this value before >>>> responding with it's R1 value. This way, the owner cannot choose the value >>>> of R2 (and hence c). >>>> >>>> When the statecoin is received by a new owner, they will receive ALL >>>> previous signed backup txs for that coin from the sender, and all the >>>> corresponding R2 values used for each signature. They will then ask the >>>> server (for each previous signature), the commitments SHA256(R2) and the >>>> corresponding server generated R1 value and c value used. The new owner >>>> will then verify that each backup tx is valid, and that each c value was >>>> computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals >>>> SHA256(R2). This ensures that a previous owner could not have generated >>>> more valid signatures than the server has partially signed. >>>> >>>> On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> >>>> wrote: >>>> >>>>> >>>>> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> >>>>> wrote: >>>>> >>>>>> No, proof of knowledge of the r values used to generate each R does >>>>>> not prevent >>>>>> Wagner's attack. I wrote >>>>>> >>>>>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>>>>> > c[0] + ... + c[K-1] = c[K]. >>>>>> >>>>>> You can think of this as actually choosing scalars r2[0], ..., >>>>>> r2[K-1] and >>>>>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack >>>>>> wouldn't make >>>>>> sense if he didn't. >>>>>> >>>>> >>>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists•linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >> [-- Attachment #2: Type: text/html, Size: 10404 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-08-07 0:55 ` [bitcoin-dev] " Tom Trevethan 2023-08-08 17:44 ` moonsettler @ 2023-08-30 10:52 ` Tom Trevethan 1 sibling, 0 replies; 34+ messages in thread From: Tom Trevethan @ 2023-08-30 10:52 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4197 bytes --] An update on progress on the development of the blinded two-party Schnorr scheme for statechains. As stated previously, we believe that one-more-signature and Wagner attacks are mitigated by the client committing the values of the blinding nonce used (labeled f) and the value of R2 used in a signing session to the server before the server responds with their value of R1. Then each time the generated signature is verified (in our application this is a new statecoin owner), the verifier retrieves the commitments and blinded challenge value from the server (c, SHA256(f) and SHA256(R2)) and f and R2 from the co-signer, and verifies that the blinded challenge value c = f + SHA256(X, R1 + R2 + f.X, m) and the commitments match f,R2. This ensures the signer cannot have chosen the values of f and R2 after the value of R1 is randomly generated by the server. This scheme has been implemented in a forked version of the secp256k1-zkp library: https://github.com/ssantos21/secp256k1-zkp where a new function has been added secp256k1_blinded_musig_nonce_process ( https://github.com/ssantos21/secp256k1-zkp/blob/ed08ad7603f211fdf39b5f6db9d7e99cf048a56c/src/modules/musig/session_impl.h#L580 ) which is required for the client generation of the blinded challenge value. One issue that came up and had to be solved was ensuring the R (curve point) is even (in MuSig2 the secret nonce is negated if R is odd) with the point f.X added (and f committed to). We will add a complete explanation of this to the updated spec. The scheme is implemented in a blind server: https://github.com/ssantos21/blinded-musig-sgx-server And client: https://github.com/ssantos21/blinded-musig2-client Any comments or questions appreciated. On Mon, Aug 7, 2023 at 1:55 AM Tom Trevethan <tom@commerceblock•com> wrote: > A follow up to this, I have updated the blinded statechain protocol > description to include the mitigation to the Wagner attack by requiring the > server to send R1 values only after commitments made to the server of the > R2 values used by the user, and that all the previous computed c values are > verified by each new statecoin owner. > https://github.com/commerceblock/mercury/blob/master/layer/protocol.md > > Essentially, the attack is possible because the server cannot verify that > the blinded challenge (c) value it has been sent by the user has been > computed honestly (i.e. c = SHA256(X1 + X2, R1 + R2, m) ), however this CAN > be verified by each new owner of a statecoin for all the previous > signatures. > > Each time an owner cooperates with the server to generate a signature on a > backup tx, the server will require that the owner send a commitment to > their R2 value: e.g. SHA256(R2). The server will store this value before > responding with it's R1 value. This way, the owner cannot choose the value > of R2 (and hence c). > > When the statecoin is received by a new owner, they will receive ALL > previous signed backup txs for that coin from the sender, and all the > corresponding R2 values used for each signature. They will then ask the > server (for each previous signature), the commitments SHA256(R2) and the > corresponding server generated R1 value and c value used. The new owner > will then verify that each backup tx is valid, and that each c value was > computed c = SHA256(X1 + X2, R1 + R2, m) and each commitment equals > SHA256(R2). This ensures that a previous owner could not have generated > more valid signatures than the server has partially signed. > > On Thu, Jul 27, 2023 at 2:25 PM Tom Trevethan <tom@commerceblock•com> > wrote: > >> >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick <jonasdnick@gmail•com> wrote: >> >>> No, proof of knowledge of the r values used to generate each R does not >>> prevent >>> Wagner's attack. I wrote >>> >>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>> > c[0] + ... + c[K-1] = c[K]. >>> >>> You can think of this as actually choosing scalars r2[0], ..., r2[K-1] >>> and >>> define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't >>> make >>> sense if he didn't. >>> >> [-- Attachment #2: Type: text/html, Size: 5798 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 7:46 [bitcoin-dev] Blinded 2-party Musig2 Tom Trevethan 2023-07-24 10:50 ` ZmnSCPxj 2023-07-24 14:12 ` Jonas Nick @ 2023-07-24 15:39 ` Jonas Nick 2023-07-24 16:22 ` Tom Trevethan 2023-07-26 9:44 ` moonsettler 2 siblings, 2 replies; 34+ messages in thread From: Jonas Nick @ 2023-07-24 15:39 UTC (permalink / raw) To: Tom Trevethan, Bitcoin Protocol Discussion > Party 1 never learns the final value of (R,s1+s2) or m. Actually, it seems like a blinding step is missing. Assume the server (party 1) received some c during the signature protocol. Can't the server scan the blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in signature verification and then check c == c'? If true, then the server has the preimage for the c received from the client, including m. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 15:39 ` Jonas Nick @ 2023-07-24 16:22 ` Tom Trevethan 2023-07-26 9:44 ` moonsettler 1 sibling, 0 replies; 34+ messages in thread From: Tom Trevethan @ 2023-07-24 16:22 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 736 bytes --] Hi Jonas, Seems you are right: for every tx, compute c from the on-chain data, and the server can match the c to the m (tx). So there would need to be a method for blinding the value of c. On Mon, Jul 24, 2023 at 4:39 PM Jonas Nick <jonasdnick@gmail•com> wrote: > > Party 1 never learns the final value of (R,s1+s2) or m. > > Actually, it seems like a blinding step is missing. Assume the server > (party 1) > received some c during the signature protocol. Can't the server scan the > blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as > in > signature verification and then check c == c'? If true, then the server > has the > preimage for the c received from the client, including m. > [-- Attachment #2: Type: text/html, Size: 1053 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* [bitcoin-dev] Blinded 2-party Musig2 2023-07-24 15:39 ` Jonas Nick 2023-07-24 16:22 ` Tom Trevethan @ 2023-07-26 9:44 ` moonsettler 2023-07-26 14:59 ` Jonas Nick 2023-07-26 19:19 ` AdamISZ 1 sibling, 2 replies; 34+ messages in thread From: moonsettler @ 2023-07-26 9:44 UTC (permalink / raw) To: bitcoin-dev Hi All, I believe it's fairly simple to solve the blinding (sorry for the bastard notation!): Signing: X = X1 + X2 K1 = k1G K2 = k2G R = K1 + K2 + bX e = hash(R||X||m) e' = e + b s = (k1 + e'*x1) + (k2 + e'*x2) s = (k1 + k2 + b(x1 + x2)) + e(x1 + x2) sG = (K1 + K2 + bX) + eX sG = R + eX Verification: Rv = sG - eX ev = hash(R||X||m) e ?= ev https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb Been trying to get a review on this for a while, please let me know if I got it wrong! BR, moonsettler ------- Original Message ------- On Monday, July 24th, 2023 at 5:39 PM, Jonas Nick via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > Party 1 never learns the final value of (R,s1+s2) or m. > > > Actually, it seems like a blinding step is missing. Assume the server (party 1) > received some c during the signature protocol. Can't the server scan the > blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in > signature verification and then check c == c'? If true, then the server has the > preimage for the c received from the client, including m. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 9:44 ` moonsettler @ 2023-07-26 14:59 ` Jonas Nick 2023-07-26 19:19 ` AdamISZ 1 sibling, 0 replies; 34+ messages in thread From: Jonas Nick @ 2023-07-26 14:59 UTC (permalink / raw) To: moonsettler, Bitcoin Protocol Discussion While this may solve blinding, I don't see how it solves the problem that the client can forge signatures because the client is in control of challenge e'. This is not special to MuSig(2), but is also the reason why original blind Schnorr signatures are insecure (as demonstrated in David Wagner's "A Generalized Birthday Problem" paper). For some more recent work on blind Schnorr signatures, see: - https://eprint.iacr.org/2019/877.pdf Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Mode - https://eprint.iacr.org/2020/1071.pdf On Pairing-Free Blind Signature Schemes in the Algebraic Group Model In particular, the first paper proposes a less-efficient variant of blind Schnorr signatures that is secure under concurrent signing if the "mROS" problem is hard (which is imho plausible). Another potential approach is using commitments and a ZKP as I mentioned earlier in this thread. This scheme is "folklore", in the sense that it is being discussed from time to time but isn't specified and does not have a security proof as far as I am aware. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 9:44 ` moonsettler 2023-07-26 14:59 ` Jonas Nick @ 2023-07-26 19:19 ` AdamISZ 2023-07-26 19:28 ` moonsettler 1 sibling, 1 reply; 34+ messages in thread From: AdamISZ @ 2023-07-26 19:19 UTC (permalink / raw) To: moonsettler, Bitcoin Protocol Discussion It's an interesting idea for a protocol. If I get it right, your basic idea here is to kind of "shoehorn" in a 2FA authentication, and that the blind-signing server has no other function than to check the 2FA? This makes it different from most uses of blind signing, where *counting* the number of signatures matters (hence 'one more forgery etc). Here, you are just saying "I'll sign whatever the heck you like, as long as you're authorized with this 2FA procedure". Going to ignore the details of practically what that means - though I'm sure that's where most of the discussion would end up - but just looking at your protocol in the gist: It seems you're not checking K values against attacks, so for example this would allow someone to extract the server's key from one signing: 1 Alice, after receiving K2, sets K1 = K1' - K2, where the secret key of K1' is k1'. 2 Chooses b as normal, sends e' as normal. 3 Receiving s2, calculate s = s1 + s2 as normal. So since s = k + ex = (k' + bx) + ex = k' + e'x, and you know s, k' and e', you can derive x. Then x2 = x - x1. (Gist I'm referring to: https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb) Sent with Proton Mail secure email. ------- Original Message ------- On Wednesday, July 26th, 2023 at 03:44, moonsettler via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Hi All, > > I believe it's fairly simple to solve the blinding (sorry for the bastard notation!): > > Signing: > > X = X1 + X2 > K1 = k1G > K2 = k2G > > R = K1 + K2 + bX > e = hash(R||X||m) > > e' = e + b > s = (k1 + e'*x1) + (k2 + e'*x2) > s = (k1 + k2 + b(x1 + x2)) + e(x1 + x2) > > sG = (K1 + K2 + bX) + eX > sG = R + eX > > Verification: > > Rv = sG - eX > ev = hash(R||X||m) > e ?= ev > > https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb > > Been trying to get a review on this for a while, please let me know if I got it wrong! > > BR, > moonsettler > > > ------- Original Message ------- > On Monday, July 24th, 2023 at 5:39 PM, Jonas Nick via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > > > > Party 1 never learns the final value of (R,s1+s2) or m. > > > > Actually, it seems like a blinding step is missing. Assume the server (party 1) > > received some c during the signature protocol. Can't the server scan the > > blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in > > signature verification and then check c == c'? If true, then the server has the > > preimage for the c received from the client, including m. > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists•linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 34+ messages in thread
* [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 19:19 ` AdamISZ @ 2023-07-26 19:28 ` moonsettler 2023-07-27 5:51 ` AdamISZ 0 siblings, 1 reply; 34+ messages in thread From: moonsettler @ 2023-07-26 19:28 UTC (permalink / raw) To: AdamISZ, bitcoin-dev Yes, thank you! There I assume if someone has your private key, and can satisfy the 2FA, he will just steal your coins, and not bother with extracting the co-signers key that is specific to you. I can see, how this assumption is not useful generally. BR, moonsettler Sent with Proton Mail secure email. ------- Original Message ------- On Wednesday, July 26th, 2023 at 9:19 PM, AdamISZ <AdamISZ@protonmail•com> wrote: > It's an interesting idea for a protocol. If I get it right, your basic idea here is to kind of "shoehorn" in a 2FA authentication, and that the blind-signing server has no other function than to check the 2FA? > > This makes it different from most uses of blind signing, where counting the number of signatures matters (hence 'one more forgery etc). Here, you are just saying "I'll sign whatever the heck you like, as long as you're authorized with this 2FA procedure". > > Going to ignore the details of practically what that means - though I'm sure that's where most of the discussion would end up - but just looking at your protocol in the gist: > > It seems you're not checking K values against attacks, so for example this would allow someone to extract the server's key from one signing: > > 1 Alice, after receiving K2, sets K1 = K1' - K2, where the secret key of K1' is k1'. > 2 Chooses b as normal, sends e' as normal. > 3 Receiving s2, calculate s = s1 + s2 as normal. > > So since s = k + ex = (k' + bx) + ex = k' + e'x, and you know s, k' and e', you can derive x. Then x2 = x - x1. > > (Gist I'm referring to: https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb) > > > > > Sent with Proton Mail secure email. > > > ------- Original Message ------- > On Wednesday, July 26th, 2023 at 03:44, moonsettler via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > > > Hi All, > > > > I believe it's fairly simple to solve the blinding (sorry for the bastard notation!): > > > > Signing: > > > > X = X1 + X2 > > K1 = k1G > > K2 = k2G > > > > R = K1 + K2 + bX > > e = hash(R||X||m) > > > > e' = e + b > > s = (k1 + e'*x1) + (k2 + e'*x2) > > s = (k1 + k2 + b(x1 + x2)) + e(x1 + x2) > > > > sG = (K1 + K2 + bX) + eX > > sG = R + eX > > > > Verification: > > > > Rv = sG - eX > > ev = hash(R||X||m) > > e ?= ev > > > > https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb > > > > Been trying to get a review on this for a while, please let me know if I got it wrong! > > > > BR, > > moonsettler > > > > ------- Original Message ------- > > On Monday, July 24th, 2023 at 5:39 PM, Jonas Nick via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > > > > Party 1 never learns the final value of (R,s1+s2) or m. > > > > > > Actually, it seems like a blinding step is missing. Assume the server (party 1) > > > received some c during the signature protocol. Can't the server scan the > > > blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in > > > signature verification and then check c == c'? If true, then the server has the > > > preimage for the c received from the client, including m. > > > _______________________________________________ > > > bitcoin-dev mailing list > > > bitcoin-dev@lists•linuxfoundation.org > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists•linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Blinded 2-party Musig2 2023-07-26 19:28 ` moonsettler @ 2023-07-27 5:51 ` AdamISZ 0 siblings, 0 replies; 34+ messages in thread From: AdamISZ @ 2023-07-27 5:51 UTC (permalink / raw) To: moonsettler, Bitcoin Protocol Discussion A reasonable attack scenario might be: attacker gains control of client machine and its privkey, wants to extract money. It first operates passively, waiting for user to do 2FA on a normal transaction, only modifying the nonce used in order to achieve its goal. Then, after that 1 transaction goes through, it gets the server privkey as above, and so 2FA is no longer needed to steal the remainder of the money. Or did I miss some part of the setup? Sent with Proton Mail secure email. ------- Original Message ------- On Wednesday, July 26th, 2023 at 13:28, moonsettler via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Yes, thank you! > > There I assume if someone has your private key, and can satisfy the 2FA, he will just steal your coins, and not bother with extracting the co-signers key that is specific to you. I can see, how this assumption is not useful generally. > > BR, > moonsettler > > Sent with Proton Mail secure email. > > > ------- Original Message ------- > On Wednesday, July 26th, 2023 at 9:19 PM, AdamISZ AdamISZ@protonmail•com wrote: > > > > > It's an interesting idea for a protocol. If I get it right, your basic idea here is to kind of "shoehorn" in a 2FA authentication, and that the blind-signing server has no other function than to check the 2FA? > > > > This makes it different from most uses of blind signing, where counting the number of signatures matters (hence 'one more forgery etc). Here, you are just saying "I'll sign whatever the heck you like, as long as you're authorized with this 2FA procedure". > > > > Going to ignore the details of practically what that means - though I'm sure that's where most of the discussion would end up - but just looking at your protocol in the gist: > > > > It seems you're not checking K values against attacks, so for example this would allow someone to extract the server's key from one signing: > > > > 1 Alice, after receiving K2, sets K1 = K1' - K2, where the secret key of K1' is k1'. > > 2 Chooses b as normal, sends e' as normal. > > 3 Receiving s2, calculate s = s1 + s2 as normal. > > > > So since s = k + ex = (k' + bx) + ex = k' + e'x, and you know s, k' and e', you can derive x. Then x2 = x - x1. > > > > (Gist I'm referring to: https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb) > > > > Sent with Proton Mail secure email. > > > > ------- Original Message ------- > > On Wednesday, July 26th, 2023 at 03:44, moonsettler via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > > > Hi All, > > > > > > I believe it's fairly simple to solve the blinding (sorry for the bastard notation!): > > > > > > Signing: > > > > > > X = X1 + X2 > > > K1 = k1G > > > K2 = k2G > > > > > > R = K1 + K2 + bX > > > e = hash(R||X||m) > > > > > > e' = e + b > > > s = (k1 + e'*x1) + (k2 + e'*x2) > > > s = (k1 + k2 + b(x1 + x2)) + e(x1 + x2) > > > > > > sG = (K1 + K2 + bX) + eX > > > sG = R + eX > > > > > > Verification: > > > > > > Rv = sG - eX > > > ev = hash(R||X||m) > > > e ?= ev > > > > > > https://gist.github.com/moonsettler/05f5948291ba8dba63a3985b786233bb > > > > > > Been trying to get a review on this for a while, please let me know if I got it wrong! > > > > > > BR, > > > moonsettler > > > > > > ------- Original Message ------- > > > On Monday, July 24th, 2023 at 5:39 PM, Jonas Nick via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > > > > > > Party 1 never learns the final value of (R,s1+s2) or m. > > > > > > > > Actually, it seems like a blinding step is missing. Assume the server (party 1) > > > > received some c during the signature protocol. Can't the server scan the > > > > blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in > > > > signature verification and then check c == c'? If true, then the server has the > > > > preimage for the c received from the client, including m. > > > > _______________________________________________ > > > > bitcoin-dev mailing list > > > > bitcoin-dev@lists•linuxfoundation.org > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > > > > _______________________________________________ > > > bitcoin-dev mailing list > > > bitcoin-dev@lists•linuxfoundation.org > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 34+ messages in thread
[parent not found: <mailman.125690.1690381971.956.bitcoin-dev@lists.linuxfoundation.org>]
* [bitcoin-dev] Blinded 2-party Musig2 [not found] <mailman.125690.1690381971.956.bitcoin-dev@lists.linuxfoundation.org> @ 2023-07-26 16:32 ` Tom Trevethan 0 siblings, 0 replies; 34+ messages in thread From: Tom Trevethan @ 2023-07-26 16:32 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 924 bytes --] @moonsettler Your scheme for blinding the challenge (e in your notation) works as far as I can tell. It is better than the way I suggested as it doesn't require modifying the aggregated pubkey (and the blinding nonce can be different for each signature). @AdamISZ and @Jonas It is not necessarily the server that would need to verify that the challenge is 'well formed', but the receiver of a statecoin. The concept of having a blinded statechain server is that each signature generated for a shared public key must be verified by the receiver of the corresponding coin. So a receiver would retrieve the number of co-signings performed by the server (K) and then verify each of the K signatures, and K transactions that they have received from the sender. They can additionally verify that each of the K R values has been correctly formed with a proof of secret value for creating R2 (along with the R1 from the server). [-- Attachment #2: Type: text/html, Size: 1303 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
end of thread, other threads:[~2023-08-30 10:52 UTC | newest]
Thread overview: 34+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-24 7:46 [bitcoin-dev] Blinded 2-party Musig2 Tom Trevethan
2023-07-24 10:50 ` ZmnSCPxj
2023-07-24 14:25 ` Erik Aronesty
2023-07-24 16:08 ` Tom Trevethan
2023-07-24 15:57 ` Tom Trevethan
2023-07-24 14:12 ` Jonas Nick
2023-07-24 14:40 ` Erik Aronesty
2023-07-24 15:40 ` Jonas Nick
2023-07-24 16:51 ` AdamISZ
2023-07-25 14:12 ` Erik Aronesty
2023-07-25 16:05 ` Tom Trevethan
2023-07-26 4:09 ` Erik Aronesty
2023-07-26 17:40 ` Andrew Poelstra
2023-07-26 19:59 ` Jonas Nick
2023-07-26 20:35 ` Tom Trevethan
2023-07-26 22:06 ` Erik Aronesty
2023-07-27 2:54 ` Lloyd Fournier
2023-07-27 8:07 ` Jonas Nick
[not found] ` <CAJvkSsfa8rzbwXiatZBpwQ6d4d94yLQifK8gyq3k-rq_1SH4OQ@mail.gmail.com>
2023-07-27 13:25 ` [bitcoin-dev] Fwd: " Tom Trevethan
2023-08-07 0:55 ` [bitcoin-dev] " Tom Trevethan
2023-08-08 17:44 ` moonsettler
2023-08-09 15:14 ` Tom Trevethan
2023-08-10 3:30 ` Lloyd Fournier
2023-08-10 11:59 ` Tom Trevethan
2023-08-14 6:31 ` Lloyd Fournier
2023-08-30 10:52 ` Tom Trevethan
2023-07-24 15:39 ` Jonas Nick
2023-07-24 16:22 ` Tom Trevethan
2023-07-26 9:44 ` moonsettler
2023-07-26 14:59 ` Jonas Nick
2023-07-26 19:19 ` AdamISZ
2023-07-26 19:28 ` moonsettler
2023-07-27 5:51 ` AdamISZ
[not found] <mailman.125690.1690381971.956.bitcoin-dev@lists.linuxfoundation.org>
2023-07-26 16:32 ` Tom Trevethan
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox