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
|
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 A7A5640B
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 5 Aug 2018 14:34:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f169.google.com (mail-io0-f169.google.com
[209.85.223.169])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E3479623
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 5 Aug 2018 14:34:13 +0000 (UTC)
Received: by mail-io0-f169.google.com with SMTP id v26-v6so8874178iog.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 05 Aug 2018 07:34:13 -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=d5Wv3HlM0hfmTDeeVNp2K15eCZwciOP9rFyEYfXTDwE=;
b=YmaQJtQ3cSOZptKKoJf4vaa8MLY0pMaUxc7az+8sn9leEMWcwtjl3FPVoVQ57FTPlT
UFtP7kz6cx6kSLSDAqhn44mCIQMmav64tbdkc7WsT81s9MI6qT6Fl5iM9DZWdZ7jzqmy
Me10FHvNbmwYp9D4CTNXLiSN+67Ax7YMud9oU=
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=d5Wv3HlM0hfmTDeeVNp2K15eCZwciOP9rFyEYfXTDwE=;
b=UunR5JOt5aXZinn+AWhfH8js0O8N2mN3ZMow2G6anraVVd3KMdwm90ycrVQgRUFohX
vvuCebw+jOix4Ig/dnlE0j3Ajl/fidksQdYzOFcRdx3QYqh9unFV3RnGKqiAp8hzXSX4
aUVwu1edLMicWzfaJtZ2kIObxE8si9G7n9ixX2/b5iS2eU/Z+HyUThZawxBiJxUeawV0
YGSM+v0iLIz8cs0zE4QcDdBnKLzx+KVJcFHEh9HfNyoD3b9gEqby+1FwAMBn2sEFVjKT
ZBxs5wFzh7cy+Uc6UGc8pVWT2TaXeoy9TFY9b0uBwA0PWFfLpu3pw/PyllDDBq61bvzx
OxXw==
X-Gm-Message-State: AOUpUlGWSNGtfEUO9e/Jc2YlK0y4cicL267ci9HqipWTrNtw3AlBK/Ie
EyI05ZPzsLu9ixl0pkvCD4SnhXDwWccJ5nbx3vj5hg==
X-Google-Smtp-Source: AA+uWPxlZV74dQhr+lTUP9hnRB6aea1Mea/S6hsf+OpZQaYuW4e+txJUOekoAkfm5fm2HwKFnzBLSBfhMga3gVXxc2w=
X-Received: by 2002:a6b:5208:: with SMTP id
g8-v6mr12831311iob.60.1533479653169;
Sun, 05 Aug 2018 07:34:13 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a02:6949:0:0:0:0:0 with HTTP;
Sun, 5 Aug 2018 07:33:52 -0700 (PDT)
In-Reply-To: <CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
<A899D97B-5D47-4AB0-8A7F-57F91C58ADE1@sprovoost.nl>
<CAPg+sBg1WuG1MihC3zBHJpxVqC2Sys7Y52iWs6JXEMmnL_tE_w@mail.gmail.com>
<CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sun, 5 Aug 2018 10:33:52 -0400
Message-ID: <CAMZUoKm_ij4Ffzx5Wpipa5RAFA=5F06jhiTCMJhp3vAj1q+2jA@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ff7b700572b10d19"
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: Sun, 05 Aug 2018 14:34:14 -0000
--000000000000ff7b700572b10d19
Content-Type: text/plain; charset="UTF-8"
Over chat it has been pointed out to me that computing the non-quadratic
residue is not the same cost as computing a quadratic residue. As pointed
out in footnote 7 of the the proposed BIP, c^((p+1)/4) is always a
quadratic residue and must be negated to find the non-quadratic residue.
In light of this, I revise my proposed change to make the verification
equation
R + sG + eP = 0.
(by 0 in the equation above I mean the identity element for the (+)
operation, which is the point at infinity.)
This equation is suitable for batch verification. This equation is clearly
written as a linear combination that doesn't use negation. In most
implementations, equality comparison tests are implemented by subtraction
and a comparison with zero. By writing the verification equation this way,
we clearly see that only the comparison with zero test is needed.
For single signature verification the check becomes, compute Q := sG + eP.
Verify that Q isn't the point at infinity and Q.x = r. Verify that Q.y is
*not* a quadratic residue. (While I was incorrect earlier about the costs
of computing a non-residue, it is the case the *verifying* a value is a
quadratic residue is the same cost as verifying a value is a non-residue.)
Effectively in my first email I was suggesting that the 'e' value in a
signature be negated from the current BIP proposal. In this revision I am
effectively suggesting that the 's' value in a signature should be the one
that is negated instead.
On Sat, Aug 4, 2018 at 8:22 AM, Russell O'Connor <roconnor@blockstream.io>
wrote:
> I propose changing the verification equation from "Let *R = sG - eP*" to
>
> Let *R = sG + eP*
>
> This allows faster verification by avoiding negating a point (or a
> coefficient).
>
>
> If, instead of directly following the literal verification specification,
> one is instead reconstructing R from r by finding a y coordinate that is a
> quadratic residue, under the existing scheme one would verify
>
>
> *sG - eP = R*
>
> which is effectively verifying
>
> 0 = *sG - eP* - R or 0 = R - *sG + eP*
>
> Either way one needs to negate at least one point (or one coefficient)
> because of the opposite signs between sG and eP.
>
>
> Under my proposed revised verification scheme, one would instead verify
>
> 0 = sG + eP + (-R).
>
> While it seems that this requires negating R, it does not. Rather (-R)
> can be directly constructed from r by finding a y coordinate that is *not*
> a quadratic residue, which is precisely the same amount of work that
> construction R from r was.
>
> In either verification procedure, changing the verification equation to my
> proposal removes one negation operation from the cost of doing verification.
>
>
>
--000000000000ff7b700572b10d19
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Over chat it has been pointed out to me that computin=
g the non-quadratic residue is not the same cost as computing a quadratic r=
esidue.=C2=A0 As pointed out in footnote 7 of the the proposed BIP, c^((p+1=
)/4) is always a quadratic residue and must be negated to find the non-quad=
ratic residue.</div><div><br></div><div>In light of this, I revise my propo=
sed change to make the verification equation</div><div><br></div><div>R + s=
G + eP =3D 0.</div><div><br></div><div> (by 0 in the equation above I mean =
the identity element for the (+) operation, which is the point at infinity.=
)<br></div><div><br></div><div>This equation is suitable for batch verifica=
tion.=C2=A0 This equation is clearly written as a linear combination that d=
oesn't use negation.=C2=A0 In most implementations, equality comparison=
tests are implemented by subtraction and a comparison with zero. By writin=
g the verification equation this way, we clearly see that only the comparis=
on with zero test is needed.<br></div><div><br></div><div>For single signat=
ure verification the check becomes, compute Q :=3D sG + eP.=C2=A0 Verify th=
at Q isn't the point at infinity and Q.x =3D r.=C2=A0 Verify that Q.y i=
s *not* a quadratic residue. (While I was incorrect earlier about the costs=
of computing a non-residue, it is the case the *verifying* a value is a qu=
adratic residue is the same cost as verifying a value is a non-residue.) <b=
r></div><div><br></div><div>Effectively in my first email I was suggesting =
that the 'e' value in a signature be negated from the current BIP p=
roposal.=C2=A0 In this revision I am effectively suggesting that the 's=
' value in a signature should be the one that is negated instead.<br></=
div><div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Sat, =
Aug 4, 2018 at 8:22 AM, Russell O'Connor <span dir=3D"ltr"><<a href=
=3D"mailto:roconnor@blockstream.io" target=3D"_blank">roconnor@blockstream.=
io</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"marg=
in:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"=
><div>I propose changing the verification equation from "Let <i>R =3D =
sG - eP</i>" to</div><div><br></div><div>=C2=A0=C2=A0=C2=A0 Let <i>R =
=3D sG + eP</i><br></div><div><br></div><div>This allows faster verificatio=
n by avoiding negating a point (or a coefficient).</div><div><br></div><div=
><br></div><div>If, instead of directly following the literal verification =
specification, one is instead reconstructing R from r by finding a y coordi=
nate that is a quadratic residue, under the existing scheme one would verif=
y</div><div><br></div><div>=C2=A0=C2=A0 <i>sG - eP =3D R<br></i></div><div>=
<br></div><div>which is effectively verifying</div><div><br></div><div>=C2=
=A0 0 =3D <i>sG - eP</i> - R=C2=A0 or 0 =3D R - <i>sG + eP</i><br></div><di=
v><br></div><div>Either way one needs to negate at least one point (or one =
coefficient) because of the opposite signs between sG and eP.<br></div><div=
><br></div><div><br></div><div>Under my proposed revised verification schem=
e, one would instead verify</div><div><br></div><div>=C2=A0 0 =3D sG + eP +=
(-R).</div><div><br></div><div>While it seems that this requires negating =
R, it does not.=C2=A0 Rather (-R) can be directly constructed from r by fin=
ding a y coordinate that is *not* a quadratic residue, which is precisely t=
he same amount of work that construction R from r was.<br></div><div><br></=
div><div>In either verification procedure, changing the verification equati=
on to my proposal removes one negation operation from the cost of doing ver=
ification.</div><div class=3D"gmail_extra"><br><br></div></div>
</blockquote></div><br></div></div></div>
--000000000000ff7b700572b10d19--
|
