Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 > wrote: > >> >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 > 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 >>> 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.
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 >> 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 > 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 >> wrote: >> >>> >>> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick 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
Re: [bitcoin-dev] Blinded 2-party Musig2
@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 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 > wrote: > >> >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 wrote: > >> On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 wrote: > > On Thu, Jul 27, 2023 at 9:08 AM Jonas Nick 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 adam...@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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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 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 > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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
Re: [bitcoin-dev] Blinded 2-party Musig2
correct. you cannot select R if it is shipped with a POP On Wed, Jul 26, 2023, 4:35 PM Tom Trevethan 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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
[bitcoin-dev] Blinded 2-party Musig2
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 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
[bitcoin-dev] Blinded 2-party Musig2
@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). ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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 signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
[bitcoin-dev] Blinded 2-party Musig2
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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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
Re: [bitcoin-dev] Blinded 2-party Musig2
@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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 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
>>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
Not sure what "posk" is or how it relates to the attack. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
> 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
Re: [bitcoin-dev] Blinded 2-party Musig2
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 > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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
Re: [bitcoin-dev] Blinded 2-party Musig2
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
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
[bitcoin-dev] Blinded 2-party Musig2
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
