1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
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's let k' =3D k when jacobi(y(R)) =3D 1 and l=
et k' =3D n - k when jacobi(y(R)) =3D -1.=C2=A0 Note that this ensures =
that jacobi(y(k'G)) =3D 1.<br><br></div><div>Also you'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' =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't defined `x`.=C2=A0 I'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"><<a href=3D"mailto=
:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists=
.linuxfoundation.org</a>></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'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--
|