MIME-Version: 1.0
References: <CAJvkSsc_rKneeVrLkTqXJDKcr+VQNBHVJyXVe=7PkkTZ+SruFQ@mail.gmail.com>
 <ca674cee-6fe9-f325-7e09-f3efda082b6b@gmail.com>
 <YwMiFAEImHAJfAHHU7WbN1C1JuHjh0vC18Hn61QplFOlY5mEgKmjsAlj2geV1-28E36_wgfL9_QHTRJsbtOLt73o9C4JfoVt8scvYGzKHOI=@protonmail.com>
 <CAJowKgJ61nWBHMfNVx7J+C1QwZZMQ9zUaFQnAw1roXiPfi5O6A@mail.gmail.com>
 <CAJvkSsdAVFf44XXXXhXqV7JcnmV796vttHEtNEp=v-zxehUofw@mail.gmail.com>
In-Reply-To: <CAJvkSsdAVFf44XXXXhXqV7JcnmV796vttHEtNEp=v-zxehUofw@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Wed, 26 Jul 2023 00:09:41 -0400
Message-ID: <CAJowKgJFHzXEtJij4K0SR_KvatTZMDfUEU40noMzR2ubj8OSvA@mail.gmail.com>
To: Tom Trevethan <tom@commerceblock.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000049f08706016464cb"
Subject: Re: [bitcoin-dev] Blinded 2-party Musig2
Precedence: list

--00000000000049f08706016464cb
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=E2=80=AFPM Tom Trevethan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Thanks for the replies. As I understand it, the v=3D2 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 invers=
e
> 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, whic=
h
> 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 =3D x1.G and sends X1 t=
o
> user (party 2)
> User generates private key x2 and public key X2 =3D x2.G and (random)
> blinding nonce z and computes the aggregate public key X =3D z.(X1 + X2)
> (server never learns of X, X2 or z).
>
> Signing:
>
> Server generates nonces r11 and r12 and R11 =3D r11.G and R12 =3D r12.G a=
nd
> sends R11 and R12 to the user.
> User generates nonces r21 and r22 and R21 =3D r21.G and R22 =3D r22.G
> User computes R1 =3D R11 + R21 and R2 =3D R12 + R22 and b =3D H(X,(R1,R2)=
,m) and
> R =3D R1 + b.R2 and c =3D (X,R,m)
> User sends the values y =3D cz and b to the server.
> Server computes s1 =3D yx1 + r11 + br12 and sends it to the user.
> User computes s2 =3D yx2 + r21 + br22 and s =3D 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 =3D 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 X=
3
> 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 =3D e + x2
> Client sends t1 and z to the reciever as part of transfer_msg (encrypted
> with the receiver public key X3 =3D x3.G).
> Receiver client decrypts t1 and then subtracts their private key x3: t2 =
=3D
> e + x2 - x3.
> Receiver client sends t2 to the server as part of transfer_receiver.
> Server the updates the private key share x1_2 =3D x1 + t2 - e =3D x1 + e =
+ x2
> - x3 - e =3D 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=E2=80=AFPM Erik Aronesty <erik@q32.com> wrot=
e:
>
>> posk is "proof of secret key".   so you cannot use wagner to select R
>>
>> On Mon, Jul 24, 2023 at 1:59=E2=80=AFPM 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. th=
e
>>> 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 =3D c * a1 * x1 + r1, you expressed the idea that the challenge c
>>> could be given to the server, to construct s1, but since a1 =3D H(L, X1=
) and
>>> L is the serialization of all (in this case, 2) keys, that wouldn't wor=
k
>>> 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 a1=
X1 +
>>> 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 serv=
er
>>> sees?
>>>
>>> But I agree with Jonas that this is just the start, i.e. the fundamenta=
l
>>> 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 p=
roof
>>> 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 t=
he
>>> 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" (i=
irc
>>> 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] :=3D R1[i] + R2[i] for all i <=3D K-1
>>> > R[K] :=3D R1[0] + ... + R1[K-1]
>>> > c[i] :=3D H(X, R[i], m[i]) for all i <=3D K.
>>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
>>> > c[0] + ... + c[K-1] =3D c[K].
>>> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].
>>> > - Let
>>> > s[K] =3D s[0] + ... + s[K-1].
>>> > Then (s[K], R[K]) is a valid signature from the server, since
>>> > s[K]G =3D 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 =3D k1G
>>> > - Client sends c to the server and proves in zero knowledge that c =
=3D
>>> > SHA256(X1 + X2, R1 + R2, m).
>>> > - Server replies with s1 =3D 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
>

--00000000000049f08706016464cb
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">personally, i think *any* time a public key is transmitted=
, it should come with a &quot;proof of secret key&quot;.=C2=A0 =C2=A0it sho=
uld be baked-in to low level protocols so that people don&#39;t accidentall=
y create vulns.=C2=A0 alt discussion link:=C2=A0 <a href=3D"https://gist.gi=
thub.com/RubenSomsen/be7a4760dd4596d06963d67baf140406">https://gist.github.=
com/RubenSomsen/be7a4760dd4596d06963d67baf140406</a></div><br><div class=3D=
"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Jul 25, 2023 at=
 5:18=E2=80=AFPM Tom Trevethan via bitcoin-dev &lt;<a href=3D"mailto:bitcoi=
n-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&=
gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div =
dir=3D"ltr">Thanks for the replies. As I understand it, the v=3D2 nonces si=
gning protocol of musig2 prevents the Wagner attack. Also, that the challen=
ge value c must be blinded from the server to prevent the server from being=
 able to determine the signature from the on-chain state. <br><br>In additi=
on, in order to update the server (party 1) keyshare when a statecoin is tr=
ansferred between users, the key aggregation coefficient must be set to 1 f=
or each key. The purpose of this coefficient in the Musig2 protocol is to p=
revent &#39;rogue key attacks&#39; where one party can choose a public key =
derived from both their own secret key and the inverse of the other party&#=
39;s public key giving them the ability to unilaterally produce a valid sig=
nature over the aggregate key. However this can be prevented by the party p=
roducing a proof of knowledge of the private key corresponding to their sup=
plied 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 pubk=
ey combines with the sender pubkey to get the coin address) which proves th=
at the server is required to co-sign to generate any signature for this add=
ress. <br><br>Here is a modified protocol:<br><br>Keygen:<br><br>Server gen=
erates private key x1 and public key X1 =3D x1.G and sends X1 to user (part=
y 2)<br>User generates private key x2 and public key X2 =3D x2.G and (rando=
m) blinding nonce z and computes the aggregate public key X =3D z.(X1 + X2)=
 (server never learns of X, X2 or z). <br><br>Signing:<br><br>Server genera=
tes nonces r11 and r12 and R11 =3D r11.G and R12 =3D r12.G and sends R11 an=
d R12 to the user. <br>User generates nonces r21 and r22 and R21 =3D r21.G =
and R22 =3D r22.G<br>User computes R1 =3D R11 + R21 and R2 =3D R12 + R22 an=
d b =3D H(X,(R1,R2),m) and R =3D R1 + b.R2 and c =3D (X,R,m)<br>User sends =
the values y =3D cz and b to the server. <br>Server computes s1 =3D yx1 + r=
11 + br12 and sends it to the user. <br>User computes s2 =3D yx2 + r21 + br=
22 and s =3D s1 + s2 and signature (s,R)<br><br>Transfer:<br><br>In a state=
coin transfer, when receiving a statecoin, in order to verify that the coin=
 address (i.e. aggregate public key) is shared correctly between the previo=
us owner and the server, the client must verify the following:<br><br>Retri=
eve the CURRENT public key from the server for this coin X1.<br>Retrieve th=
e public key X2 and the blinding nonce z from the sender. <br>Verify that z=
.X1 + X2 =3D P the address of the statecoin.<br>Verify that the sender has =
the private key used to generate X2: this is done by verifying the statecha=
in signature over the receiver public key X3 from X2.<br>This proves that t=
he address P was generated (aggregated) with the server and can only be sig=
ned with cooperation with the server, i.e. no previous owner can hold the f=
ull key.<br><br>In order to update the key shares on transfer, the followin=
g protocol can be used:<br><br>Server (party 1) generates a random blinding=
 nonce e and sends it to user.<br>User adds their private key to the nonce:=
 t1 =3D e + x2<br>Client sends t1 and z to the reciever as part of transfer=
_msg (encrypted with the receiver public key X3 =3D x3.G).<br>Receiver clie=
nt decrypts t1 and then subtracts their private key x3: t2 =3D e + x2 - x3.=
<br>Receiver client sends t2 to the server as part of transfer_receiver.<br=
>Server the updates the private key share x1_2 =3D x1 + t2 - e =3D x1 + e +=
 x2 - x3 - e =3D x1 + x2 - x3<br>So now, x1_2 + x3 (the aggregation of the =
new server key share with the new client key share) is equal to x1 + x2 (th=
e aggregation of the old server key share with the old client key share).<b=
r>The server deletes x1.<br></div><br><div class=3D"gmail_quote"><div dir=
=3D"ltr" class=3D"gmail_attr">On Tue, Jul 25, 2023 at 3:12=E2=80=AFPM Erik =
Aronesty &lt;<a href=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com=
</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=
<div dir=3D"ltr">posk is &quot;proof of secret key&quot;.=C2=A0 =C2=A0so yo=
u cannot use wagner to select R</div><br><div class=3D"gmail_quote"><div di=
r=3D"ltr" class=3D"gmail_attr">On Mon, Jul 24, 2023 at 1:59=E2=80=AFPM Adam=
ISZ via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation=
.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote=
:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.=
8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">@ZmnSCPxj:<br>
<br>
yes, Wagner is the attack you were thinking of.<br>
<br>
And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the R =
commitments.<br>
<br>
@Tom:<br>
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.<br>
<br>
Jonas&#39; reply clearly has covered a lot of what matters here, but I want=
ed to mention (using your notation):<br>
<br>
in s1 =3D c * a1 * x1 + r1, you expressed the idea that the challenge c cou=
ld be given to the server, to construct s1, but since a1 =3D H(L, X1) and L=
 is the serialization of all (in this case, 2) keys, that wouldn&#39;t work=
 for blinding the final key, right?<br>
But, is it possible that this addresses the other problem?<br>
If the server is given c1*a1 instead as the challenge for signing (with the=
ir &quot;pure&quot; key x1), then perhaps it avoids the issue? Given what&#=
39;s on the blockchain ends up allowing calculation of &#39;c&#39; and the =
aggregate key a1X1 + a2X2, is it the case that you cannot find a1 and there=
fore you cannot correlate the transaction with just the quantity &#39;c1*a1=
&#39; which the server sees?<br>
<br>
But I agree with Jonas that this is just the start, i.e. the fundamental re=
quirement of a blind signing scheme is there has to be some guarantee of no=
 &#39;one more forgery&#39; possibility, so presumably there has to be some=
 proof that the signing request is &#39;well formed&#39; (Jonas expresses i=
t 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&#39;s needed).<br>
<br>
@Jonas, Erik:<br>
&#39;posk&#39; is probably meant as &#39;proof of secret key&#39; which may=
(?) be a mixup with what is sometimes referred to in the literature as &quo=
t;KOSK&quot; (iirc they used it in FROST for example). It isn&#39;t clear t=
o me yet how that factors into this scenario, although ofc it is for sure a=
 potential building block of these constructions.<br>
<br>
Sent with Proton Mail secure email.<br>
<br>
------- Original Message -------<br>
On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev &lt;<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin=
-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
<br>
<br>
&gt; Hi Tom,<br>
&gt; <br>
&gt; I&#39;m not convinced that this works. As far as I know blind musig is=
 still an open<br>
&gt; research problem. What the scheme you propose appears to try to preven=
t is that<br>
&gt; the server signs K times, but the client ends up with K+1 Schnorr sign=
atures for<br>
&gt; the aggregate of the server&#39;s and the clients key. I think it&#39;=
s possible to<br>
&gt; apply a variant of the attack that makes MuSig1 insecure if the nonce =
commitment<br>
&gt; round was skipped or if the message isn&#39;t determined before sendin=
g the nonce.<br>
&gt; Here&#39;s how a malicious client would do that:<br>
&gt; <br>
&gt; - Obtain K R-values R1[0], ..., R1[K-1] from the server<br>
&gt; - Let<br>
&gt; R[i] :=3D R1[i] + R2[i] for all i &lt;=3D K-1<br>
&gt; R[K] :=3D R1[0] + ... + R1[K-1]<br>
&gt; c[i] :=3D H(X, R[i], m[i]) for all i &lt;=3D K.<br>
&gt; Using Wagner&#39;s algorithm, choose R2[0], ..., R2[K-1] such that<br>
&gt; c[0] + ... + c[K-1] =3D c[K].<br>
&gt; - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].<br=
>
&gt; - Let<br>
&gt; s[K] =3D s[0] + ... + s[K-1].<br>
&gt; Then (s[K], R[K]) is a valid signature from the server, since<br>
&gt; s[K]G =3D R[K] + c[K]a1X1,<br>
&gt; which the client can complete to a signature for public key X.<br>
&gt; <br>
&gt; What may work in your case is the following scheme:<br>
&gt; - Client sends commitment to the public key X2, nonce R2 and message m=
 to the<br>
&gt; server.<br>
&gt; - Server replies with nonce R1 =3D k1G<br>
&gt; - Client sends c to the server and proves in zero knowledge that c =3D=
<br>
&gt; SHA256(X1 + X2, R1 + R2, m).<br>
&gt; - Server replies with s1 =3D k1 + c*x1<br>
&gt; <br>
&gt; However, this is just some quick intuition and I&#39;m not sure if thi=
s actually<br>
&gt; works, but maybe worth exploring.<br>
&gt; _______________________________________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bl=
ank">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org=
/mailman/listinfo/bitcoin-dev</a><br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</blockquote></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--00000000000049f08706016464cb--