[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
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 serial
Re: [bitcoin-dev] Concern about "Inscriptions".
I understand your point of view. However, inscription represent by far the largest spam attack due to their ability to embed themselves in the witness with a fee reduction. Unlike other methods, such as using the op_return field which could also be used to spam the chain, the associated fees and the standardization rule limiting op_return to 80 bytes have so far prevented similar abuses. Although attempting to stop inscription could lead to more serious issues, not taking action against these inscription could be interpreted by spammers as tacit acceptance of their practice. This could encourage more similar spam attacks in the future, as spammers might perceive that the Bitcoin network tolerates this kind of behavior. I want to emphasize that my proposal does not involve implementing a soft fork in any way. On the contrary, what I am asking is simply to consider adding a standardization option. This option would allow the community to freely decide whether it should be activated or not. > Le 26 juil. 2023 à 07:30, vju...@gazeta.pl a écrit : > >> and I would like to understand why this problem has not been addressed more >> seriously > > Because if nobody has any good solution, then status quo is preserved. If > tomorrow ECDSA would be broken, the default state of the network would be > "just do nothing", and every solution would be backward-compatible with that > approach. Burn old coins, and people will call it "Tether", redistribute > them, and people will call it "BSV". Leave everything untouched, and the > network will split into N parts, and then you pick the strongest chain to > decide, what should be done. > >> However, when it comes to inscriptions, there are no available options >> except for a patch produced by Luke Dashjr. > > Because the real solution should address some different problem, that was > always there, and nobody knows, how to deal with it: the problem of > forever-growing initial blockchain download time, and forever-growing UTXO > set. Some changes with "assume UTXO" are trying to address just that, but > this code is not yet completed. > >> So, I wonder why there are no options to reject inscriptions in the mempool >> of a node. > > Because it will lead you to never ending chase. You will block one > inscriptions, and different ones will be created. Now, they are present even > on chains, where there is no Taproot, or even Segwit. That means, if you try > to kill them, then they will be replaced by N regular indistinguishable > transactions, and then you will go back to those more serious problems under > the hood: IBD time, and UTXO size. > >> Inscriptions are primarily used to sell NFTs or Tokens, concepts that the >> Bitcoin community has consistently rejected. > > The community also rejected things like sidechains, and they are still > present, just in a more centralized form. There are some unstoppable > concepts, for example soft-forks. You cannot stop a soft-fork. What > inscription creators did, is just non-enforced soft-fork. They believe their > rules are followed to the letter, but this is not the case, as you can create > a valid Bitcoin transaction, that will be some invalid Ordinals transaction > (because their additional rules are not enforced by miners and nodes). > > > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Concern about "Inscriptions".
> and I would like to understand why this problem has not been addressed more > seriously Because if nobody has any good solution, then status quo is preserved. If tomorrow ECDSA would be broken, the default state of the network would be "just do nothing", and every solution would be backward-compatible with that approach. Burn old coins, and people will call it "Tether", redistribute them, and people will call it "BSV". Leave everything untouched, and the network will split into N parts, and then you pick the strongest chain to decide, what should be done. > However, when it comes to inscriptions, there are no available options except > for a patch produced by Luke Dashjr. Because the real solution should address some different problem, that was always there, and nobody knows, how to deal with it: the problem of forever-growing initial blockchain download time, and forever-growing UTXO set. Some changes with "assume UTXO" are trying to address just that, but this code is not yet completed. > So, I wonder why there are no options to reject inscriptions in the mempool > of a node. Because it will lead you to never ending chase. You will block one inscriptions, and different ones will be created. Now, they are present even on chains, where there is no Taproot, or even Segwit. That means, if you try to kill them, then they will be replaced by N regular indistinguishable transactions, and then you will go back to those more serious problems under the hood: IBD time, and UTXO size. > Inscriptions are primarily used to sell NFTs or Tokens, concepts that the > Bitcoin community has consistently rejected. The community also rejected things like sidechains, and they are still present, just in a more centralized form. There are some unstoppable concepts, for example soft-forks. You cannot stop a soft-fork. What inscription creators did, is just non-enforced soft-fork. They believe their rules are followed to the letter, but this is not the case, as you can create a valid Bitcoin transaction, that will be some invalid Ordinals transaction (because their additional rules are not enforced by miners and nodes). ___ 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
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
[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
[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
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
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
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
