Re: [bitcoin-dev] Blinded 2-party Musig2

From: Erik Aronesty <erik@q32•com>
To: Tom Trevethan <tom@commerceblock•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Blinded 2-party Musig2
Date: Wed, 26 Jul 2023 00:09:41 -0400	[thread overview]
Message-ID: <CAJowKgJFHzXEtJij4K0SR_KvatTZMDfUEU40noMzR2ubj8OSvA@mail.gmail.com> (raw)
In-Reply-To: <CAJvkSsdAVFf44XXXXhXqV7JcnmV796vttHEtNEp=v-zxehUofw@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 9060 bytes --]

personally, i think *any* time a public key is transmitted, it should come
with a "proof of secret key".   it should be baked-in to low level
protocols so that people don't accidentally create vulns.  alt discussion
link:  https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406

On Tue, Jul 25, 2023 at 5:18 PM Tom Trevethan via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> Thanks for the replies. As I understand it, the v=2 nonces signing
> protocol of musig2 prevents the Wagner attack. Also, that the challenge
> value c must be blinded from the server to prevent the server from being
> able to determine the signature from the on-chain state.
>
> In addition, in order to update the server (party 1) keyshare when a
> statecoin is transferred between users, the key aggregation coefficient
> must be set to 1 for each key. The purpose of this coefficient in the
> Musig2 protocol is to prevent 'rogue key attacks' where one party can
> choose a public key derived from both their own secret key and the inverse
> of the other party's public key giving them the ability to unilaterally
> produce a valid signature over the aggregate key. However this can be
> prevented by the party producing a proof of knowledge of the private key
> corresponding to their supplied public key. This can be a signature, which
> is produced in any case by signing the statechain state in the mercury
> protocol. This signature must be verified by the receiver of a coin (who
> must also verify the server pubkey combines with the sender pubkey to get
> the coin address) which proves that the server is required to co-sign to
> generate any signature for this address.
>
> Here is a modified protocol:
>
> Keygen:
>
> Server generates private key x1 and public key X1 = x1.G and sends X1 to
> user (party 2)
> User generates private key x2 and public key X2 = x2.G and (random)
> blinding nonce z and computes the aggregate public key X = z.(X1 + X2)
> (server never learns of X, X2 or z).
>
> Signing:
>
> Server generates nonces r11 and r12 and R11 = r11.G and R12 = r12.G and
> sends R11 and R12 to the user.
> User generates nonces r21 and r22 and R21 = r21.G and R22 = r22.G
> User computes R1 = R11 + R21 and R2 = R12 + R22 and b = H(X,(R1,R2),m) and
> R = R1 + b.R2 and c = (X,R,m)
> User sends the values y = cz and b to the server.
> Server computes s1 = yx1 + r11 + br12 and sends it to the user.
> User computes s2 = yx2 + r21 + br22 and s = s1 + s2 and signature (s,R)
>
> Transfer:
>
> In a statecoin transfer, when receiving a statecoin, in order to verify
> that the coin address (i.e. aggregate public key) is shared correctly
> between the previous owner and the server, the client must verify the
> following:
>
> Retrieve the CURRENT public key from the server for this coin X1.
> Retrieve the public key X2 and the blinding nonce z from the sender.
> Verify that z.X1 + X2 = P the address of the statecoin.
> Verify that the sender has the private key used to generate X2: this is
> done by verifying the statechain signature over the receiver public key X3
> from X2.
> This proves that the address P was generated (aggregated) with the server
> and can only be signed with cooperation with the server, i.e. no previous
> owner can hold the full key.
>
> In order to update the key shares on transfer, the following protocol can
> be used:
>
> Server (party 1) generates a random blinding nonce e and sends it to user.
> User adds their private key to the nonce: t1 = e + x2
> Client sends t1 and z to the reciever as part of transfer_msg (encrypted
> with the receiver public key X3 = x3.G).
> Receiver client decrypts t1 and then subtracts their private key x3: t2 =
> e + x2 - x3.
> Receiver client sends t2 to the server as part of transfer_receiver.
> Server the updates the private key share x1_2 = x1 + t2 - e = x1 + e + x2
> - x3 - e = x1 + x2 - x3
> So now, x1_2 + x3 (the aggregation of the new server key share with the
> new client key share) is equal to x1 + x2 (the aggregation of the old
> server key share with the old client key share).
> The server deletes x1.
>
> On Tue, Jul 25, 2023 at 3:12 PM Erik Aronesty <erik@q32•com> wrote:
>
>> posk is "proof of secret key".   so you cannot use wagner to select R
>>
>> On Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev <
>> bitcoin-dev@lists•linuxfoundation.org> wrote:
>>
>>> @ZmnSCPxj:
>>>
>>> yes, Wagner is the attack you were thinking of.
>>>
>>> And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the
>>> R commitments.
>>>
>>> @Tom:
>>> As per above it seems you were more considering MuSig1 here, not MuSig2.
>>> At least in this version. So you need the initial commitments to R.
>>>
>>> Jonas' reply clearly has covered a lot of what matters here, but I
>>> wanted to mention (using your notation):
>>>
>>> in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c
>>> could be given to the server, to construct s1, but since a1 = H(L, X1) and
>>> L is the serialization of all (in this case, 2) keys, that wouldn't work
>>> for blinding the final key, right?
>>> But, is it possible that this addresses the other problem?
>>> If the server is given c1*a1 instead as the challenge for signing (with
>>> their "pure" key x1), then perhaps it avoids the issue? Given what's on the
>>> blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 +
>>> a2X2, is it the case that you cannot find a1 and therefore you cannot
>>> correlate the transaction with just the quantity 'c1*a1' which the server
>>> sees?
>>>
>>> But I agree with Jonas that this is just the start, i.e. the fundamental
>>> requirement of a blind signing scheme is there has to be some guarantee of
>>> no 'one more forgery' possibility, so presumably there has to be some proof
>>> that the signing request is 'well formed' (Jonas expresses it below as a
>>> ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the
>>> face of it, that is what's needed).
>>>
>>> @Jonas, Erik:
>>> 'posk' is probably meant as 'proof of secret key' which may(?) be a
>>> mixup with what is sometimes referred to in the literature as "KOSK" (iirc
>>> they used it in FROST for example). It isn't clear to me yet how that
>>> factors into this scenario, although ofc it is for sure a potential
>>> building block of these constructions.
>>>
>>> Sent with Proton Mail secure email.
>>>
>>> ------- Original Message -------
>>> On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev <
>>> bitcoin-dev@lists•linuxfoundation.org> wrote:
>>>
>>>
>>> > Hi Tom,
>>> >
>>> > I'm not convinced that this works. As far as I know blind musig is
>>> still an open
>>> > research problem. What the scheme you propose appears to try to
>>> prevent is that
>>> > the server signs K times, but the client ends up with K+1 Schnorr
>>> signatures for
>>> > the aggregate of the server's and the clients key. I think it's
>>> possible to
>>> > apply a variant of the attack that makes MuSig1 insecure if the nonce
>>> commitment
>>> > round was skipped or if the message isn't determined before sending
>>> the nonce.
>>> > Here's how a malicious client would do that:
>>> >
>>> > - Obtain K R-values R1[0], ..., R1[K-1] from the server
>>> > - Let
>>> > R[i] := R1[i] + R2[i] for all i <= K-1
>>> > R[K] := R1[0] + ... + R1[K-1]
>>> > c[i] := H(X, R[i], m[i]) for all i <= K.
>>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
>>> > c[0] + ... + c[K-1] = c[K].
>>> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].
>>> > - Let
>>> > s[K] = s[0] + ... + s[K-1].
>>> > Then (s[K], R[K]) is a valid signature from the server, since
>>> > s[K]G = R[K] + c[K]a1X1,
>>> > which the client can complete to a signature for public key X.
>>> >
>>> > What may work in your case is the following scheme:
>>> > - Client sends commitment to the public key X2, nonce R2 and message m
>>> to the
>>> > server.
>>> > - Server replies with nonce R1 = k1G
>>> > - Client sends c to the server and proves in zero knowledge that c =
>>> > SHA256(X1 + X2, R1 + R2, m).
>>> > - Server replies with s1 = k1 + c*x1
>>> >
>>> > However, this is just some quick intuition and I'm not sure if this
>>> actually
>>> > works, but maybe worth exploring.
>>> > _______________________________________________
>>> > bitcoin-dev mailing list
>>> > bitcoin-dev@lists•linuxfoundation.org
>>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists•linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 10705 bytes --]