path: root/18/b9b4ce301f4be159c46d0cc2863b6cbe825013

Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id B9225D90
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  6 Jul 2018 21:05:25 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f53.google.com (mail-it0-f53.google.com
	[209.85.214.53])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0DAB877B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  6 Jul 2018 21:05:24 +0000 (UTC)
Received: by mail-it0-f53.google.com with SMTP id p185-v6so18930096itp.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 06 Jul 2018 14:05:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=blockstream.io; s=google;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=Sip78IMYeRyFDZRoaJs20+v1lNhw21PXMlgt0dquxio=;
	b=hVSF7sWp3LiDcw4vLinlDbIogz5TPsKzx91d7ljUFZ2bhCOsRx6qgN0rb+yu0HAu6g
	ZwiFGbHruYfBhaAHoMLWLcdXSJ3bt7pXSAR0w2+R8S2guQmzo5WK+DXlXksxXxNJwCJi
	lSucImlx4NFWx0DBb9Evu7cNHccefVV5L+KWo=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=Sip78IMYeRyFDZRoaJs20+v1lNhw21PXMlgt0dquxio=;
	b=COhVZtNhQZT8L7Scl+qaBdWzgv8LDmO67CDGKJZUwPc8FBNSYPZqfbDSJA0/wvQzHR
	9fHPnP2+6YPXhlUu2Iv/0/o2ddw/gpxiVGFknHaA01qAQUx1RvQLVj/1c4S8ayLd+432
	Mx84IzUbtvyjcI5b/188FSh+SmjqEkxh+lpHs3e6TsNIAB92Pr8dxfvuJ6xTFIJtVOsw
	zjdGYywqQ9qcFeU/GK2bPSAPZavehp7OczV/71DHnD0AZl5MafeVUBjSkvuEVY+Ryuh8
	8svj52my1XbpM+qwxIXk3xknBKV9Sww0YB14jkzMTQn0CV5aaZ4rEA25366FIPg96vQc
	WmHQ==
X-Gm-Message-State: APt69E0o2nV2KJReo1qeM4OXhI0VimJU3xTQjWyrGs4WY9V9OWxlYy9Z
	ZvRkpD/lmG+BTHbGWjM8vM8dtSygAdvKfAo0ZOTE+w==
X-Google-Smtp-Source: AAOMgpddwVy36TX5CVJJ/w/g1ZZ2B8GKNgeibkZa4TvF980QORzhEzxxFE5qyiopH4L7c07+w/ZOEA0XQCHUlT78bTA=
X-Received: by 2002:a24:7b97:: with SMTP id
	q145-v6mr9325326itc.79.1530911124260; 
	Fri, 06 Jul 2018 14:05:24 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a02:6949:0:0:0:0:0 with HTTP;
	Fri, 6 Jul 2018 14:05:03 -0700 (PDT)
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"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 06 Jul 2018 21:05:25 -0000

--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--