MIME-Version: 1.0
In-Reply-To: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Fri, 6 Jul 2018 17:05:03 -0400
Message-ID: <CAMZUoKks9of0oWdn8J=601cY2PMf+EV4e=PeWpDAXPcGPNFkRw@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000beb71905705b0518"
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Precedence: list

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

Some quick comments:

Signing
>
> To sign:
>
>    - Let *k =3D int(hash(bytes(d) || m)) mod n*[8
>    <https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#c=
ite_note-8>
>    ].
>    - Let *R =3D kG*.
>    - If *jacobi(y(R)) =E2=89=A0 1*, let *k =3D n - k*.
>    - Let *e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>    - The signature is *bytes(x(R)) || bytes(k + ex mod n)*.
>
> Can we avoid mutable variables in these specification?  I know this is
commonly done in RFCs, but I think it is fairly confusing to have `k`
defined in two different ways within a single specification.
Let's let k' =3D k when jacobi(y(R)) =3D 1 and let k' =3D n - k when jacobi=
(y(R))
=3D -1.  Note that this ensures that jacobi(y(k'G)) =3D 1.

Also you've sort of left it undefined what to do when k =3D 0.  According t=
o
the current specification, you will produce an invalid signature.  The
expected result is that you should win a 1000 BTC prize.

One solution is to let k =3D *1 + int(hash(bytes(d) || m)) mod (n-1)*.
Alternatively you could let k' =3D 1 when k =3D 0.  Or you could just make =
a
note that signature generation fails with this message and private key pair
when this happens.

Let *e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>

P =3D dG should probably be noted somewhere in the text.  I.e. this signatu=
re
is generated for the public key P =3D dG.

If the inputs to hash were reordered as *hash(bytes(dG) || bytes(x(R)) ||
m)* then there is an opportunity for SHA256 expander to be partially
prefilled for a fixed public key.  This could provide a little benefit,
especially when multiple signatures for a single public key need to be
generated and/or verified.  If all things are otherwise equal, perhaps this
alternate order is better.

 The signature is *bytes(x(R)) || bytes(k + ex mod n)*.


You haven't defined `x`.  I'm guessing you mean `d` instead.

> Optimizations
>
> *Jacobian coordinates*
>
>    - *oncurve(P)* can be implemented as *y2 =3D x3 + 7z6 mod p*.
>
> oncurve(P) requires that `P` be on the curve and not infinity.  You need
another condition here to ensure that `P` is not infinity.


On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be useful
> in other contexts to have a common Schnorr scheme available, it is its
> own informational BIP.
>
> If accepted, we'll work on more production-ready reference
> implementations and tests.
>
> This is joint work with several people listed in the document.
>
> Cheers,
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Some quick comments:<br><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">Signing<br><br>To sign:






<ul><li>Let <i>k =3D int(hash(bytes(d) || m)) mod n</i><sup id=3D"gmail-use=
r-content-cite_ref-8-0">[<a href=3D"https://github.com/sipa/bips/blob/bip-s=
chnorr/bip-schnorr.mediawiki#cite_note-8">8</a>]</sup>.</li><li>Let <i>R =
=3D kG</i>.</li><li>If <i>jacobi(y(R)) =E2=89=A0 1</i>, let <i>k =3D n - k<=
/i>.</li><li>Let <i>e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod n</i=
>.</li><li>The signature is <i>bytes(x(R)) || bytes(k + ex mod n)</i>.</li>=
</ul></blockquote><div>Can we avoid mutable variables in these specificatio=
n?=C2=A0 I know this is commonly done in RFCs, but I think it is fairly con=
fusing to have `k` defined in two different ways within a single specificat=
ion.<br></div><div>Let&#39;s let k&#39; =3D k when jacobi(y(R)) =3D 1 and l=
et k&#39; =3D n - k when jacobi(y(R)) =3D -1.=C2=A0 Note that this ensures =
that jacobi(y(k&#39;G)) =3D 1.<br><br></div><div>Also you&#39;ve sort of le=
ft it undefined what to do when k =3D 0.=C2=A0 According to the current spe=
cification, you will produce an invalid signature.=C2=A0 The expected resul=
t is that you should win a 1000 BTC prize.<br><br></div><div>One solution i=
s to let k =3D <i>1 + int(hash(bytes(d) || m)) mod (n-1)</i>.=C2=A0 Alterna=
tively you could let k&#39; =3D 1 when k =3D 0.=C2=A0 Or you could just mak=
e a note that signature generation fails with this message and private key =
pair when this happens.<br></div><div><br><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex">Let <i>e =3D int(hash(bytes(x(R)) || bytes(dG) || m)) mod =
n</i>.<br></blockquote><div><br></div><div>P =3D dG should probably be note=
d somewhere in the text.=C2=A0 I.e. this signature is generated for the pub=
lic key P =3D dG.<br><br></div><div>If the inputs to hash were reordered as=
 <i>hash(bytes(dG) || <i>bytes(x(R)) || </i>m)</i> then there is an opportu=
nity for SHA256 expander to be partially prefilled for a fixed public key.=
=C2=A0 This could provide a little benefit, especially when multiple signat=
ures for a single public key need to be generated and/or verified.=C2=A0 If=
 all things are otherwise equal, perhaps this alternate order is better.<br=
></div><br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.=
8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=C2=A0The sign=
ature is <i>bytes(x(R)) || bytes(k + ex mod n)</i>.</blockquote><div><br></=
div><div>You haven&#39;t defined `x`.=C2=A0 I&#39;m guessing you mean `d` i=
nstead.<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.=
8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><h3>Optimizati=
ons</h3><p><b>Jacobian coordinates</b> <br></p><ul><li><i>oncurve(P)</i> ca=
n be implemented as <i>y<sup>2</sup> =3D x<sup>3</sup> + 7z<sup>6</sup> mod=
 p</i>.</li></ul></blockquote><div>oncurve(P) requires that `P` be on the c=
urve and not infinity.=C2=A0 You need another condition here to ensure that=
 `P` is not infinity.<br></div><div>=C2=A0</div></div></div></div><div clas=
s=3D"gmail_extra"><br><div class=3D"gmail_quote">On Fri, Jul 6, 2018 at 2:0=
8 PM, Pieter Wuille via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto=
:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists=
.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex=
">Hello everyone,<br>
<br>
Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,<br>
over the same curve as is currently used in ECDSA:<br>
<a href=3D"https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediaw=
iki" rel=3D"noreferrer" target=3D"_blank">https://github.com/sipa/bips/<wbr=
>blob/bip-schnorr/bip-schnorr.<wbr>mediawiki</a><br>
<br>
It is simply a draft specification of the signature scheme itself. It<br>
does not concern consensus rules, aggregation, or any other<br>
integration into Bitcoin - those things are left for other proposals,<br>
which can refer to this scheme if desirable. Standardizing the<br>
signature scheme is a first step towards that, and as it may be useful<br>
in other contexts to have a common Schnorr scheme available, it is its<br>
own informational BIP.<br>
<br>
If accepted, we&#39;ll work on more production-ready reference<br>
implementations and tests.<br>
<br>
This is joint work with several people listed in the document.<br>
<br>
Cheers,<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
-- <br>
Pieter<br>
______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
</font></span></blockquote></div><br></div>

--000000000000beb71905705b0518--