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
|
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 66778BAD
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Aug 2018 12:22:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f41.google.com (mail-it0-f41.google.com
[209.85.214.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DCC52713
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 4 Aug 2018 12:22:49 +0000 (UTC)
Received: by mail-it0-f41.google.com with SMTP id g141-v6so12140108ita.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 04 Aug 2018 05:22:49 -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=pvoTSor1XVozFA7+/qfu+PJ9fgI/r3UT7lgHvvU3yqI=;
b=X5lswPSANcCCDYtJWY7ja+ZcabjA57cwh2BWW0cAi7RcBuinfRHB/VwOo5MJOcZei7
6eSZrZ4jzIgEWvJRA8TzXcj89nmhjMkW+Fxb6OtxQ79sCdV3REslqs76TFZLptdIwdbO
dFilHdQVbzWftn+53+06QZUwlfUKyaxuFuXCs=
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=pvoTSor1XVozFA7+/qfu+PJ9fgI/r3UT7lgHvvU3yqI=;
b=gJ2eoOzD/fUwkQWTdsQYiVqZxiE21IOCaWSpAvhCD6fK86L1xZq+UXD8aAeQPqrTlP
5AeXPNBl6mFRAPDVpmYYk3+CbGnx/z/Uv8ktgSUZyROvFms9JR396Fl8Mz9FQifI6Oka
r6EsXwMwNEw2oN07/0gvUIpG5JzZO8QAZ+8msoUQgJay1MxwFaOfQBVKY/I9Ks7EfDq0
NS+r21XLEZJ1j8Q3aS2NNRr2/Wv077iTOY8tvHN+sZlyPO59rKWtl2Ro/4KuCjR4SERQ
CUT4Cd3L+ApEwrnbVdn/c3XPHNimzVvRk67XqvEjF18N7HFrS0aJ3Y6yPSQIPCvcItLc
1a0A==
X-Gm-Message-State: AOUpUlHqJ5etw+Y64JMhCt6xm1NUl8taytEqKvyaNn1NpJ96efJCFsE0
MIFhCyCkM0pyI83BdVtuVSB6AtBAVOOrTj2AMufDJg==
X-Google-Smtp-Source: AAOMgpfhkvfHtVzrfGkj8dxhBldkwI8tGuwa7+DFH9St3rl0f9TO9BjWRt6mscvdGfz1akXxRdx6W5SHA27TOBSPuBQ=
X-Received: by 2002:a02:4ac3:: with SMTP id
s64-v6mr6722380jad.93.1533385369195;
Sat, 04 Aug 2018 05:22:49 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a02:6949:0:0:0:0:0 with HTTP;
Sat, 4 Aug 2018 05:22:28 -0700 (PDT)
In-Reply-To: <CAPg+sBg1WuG1MihC3zBHJpxVqC2Sys7Y52iWs6JXEMmnL_tE_w@mail.gmail.com>
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
<A899D97B-5D47-4AB0-8A7F-57F91C58ADE1@sprovoost.nl>
<CAPg+sBg1WuG1MihC3zBHJpxVqC2Sys7Y52iWs6JXEMmnL_tE_w@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sat, 4 Aug 2018 08:22:28 -0400
Message-ID: <CAMZUoKm4Qs2yAc+WKgN1J2D8MDgbzNnK69kF+hbY2GDyRqdVdg@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000003c309b05729b1a0e"
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: Sat, 04 Aug 2018 12:22:50 -0000
--0000000000003c309b05729b1a0e
Content-Type: text/plain; charset="UTF-8"
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.
--0000000000003c309b05729b1a0e
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>I propose changing the verification equation from &qu=
ot;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 fa=
ster verification by avoiding negating a point (or a coefficient).</div><di=
v><br></div><div><br></div><div>If, instead of directly following the liter=
al verification specification, one is instead reconstructing R from r by fi=
nding a y coordinate that is a quadratic residue, under the existing scheme=
one would verify</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><div><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 ver=
ification scheme, 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 req=
uires negating R, it does not.=C2=A0 Rather (-R) can be directly constructe=
d 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.<br></=
div><div><br></div><div>In either verification procedure, changing the veri=
fication equation to my proposal removes one negation operation from the co=
st of doing verification.</div><div class=3D"gmail_extra"><br><br></div></d=
iv>
--0000000000003c309b05729b1a0e--
|
