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
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
|
Return-Path: <john@johnnewbery.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 7C64AC0051
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 09:14:18 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by silver.osuosl.org (Postfix) with ESMTP id 77FEF204CF
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 09:14:18 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id VO0M0CbH6bPp
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 09:14:16 +0000 (UTC)
X-Greylist: delayed 00:23:11 by SQLgrey-1.7.6
Received: from mail-lj1-f179.google.com (mail-lj1-f179.google.com
[209.85.208.179])
by silver.osuosl.org (Postfix) with ESMTPS id 79F4E20479
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 09:14:15 +0000 (UTC)
Received: by mail-lj1-f179.google.com with SMTP id w14so1083377ljj.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 02:14:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=johnnewbery-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=5LPKEqZI4Jk9WsvMcyiBMGYUyfrsU9ELamXjw8csqVw=;
b=s1lGKpLKOmo/SNbOegGUER1K7XI/YwoG48fIqR1iVGwKKH/VBd6b6VFb/nd9+6soKj
VdLW2v7o/2GchIJtOGCcnGfl6Wurt7f65QskCH7gAHM9ECXEJ3kucFLk5xPE9vIimIVZ
gY7Eb6mWtGSMMSubQbSQSxPNMjINvMbcfAk8RvB/k/3XAVZk+K8drwGN/9vT5/MX5H/R
19IO6cZXitfeoab9zKc2NoWSBunnzxP+QlwiBT6cBbq0jCxzHo+1WLsPyYho4GrGuF5B
GrRjTW7LYMPZaxL0ukP0x89ZjEiqL9JLawC+DoeAWzlYUlMMJ/dzOpqeIobQVS8Pxokr
rjIA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=5LPKEqZI4Jk9WsvMcyiBMGYUyfrsU9ELamXjw8csqVw=;
b=YBtXiEaZPjkVWO2r1xWyHqLvp0EqqjKisQKFqwAF/2/CNjIMx9GeaEmfu4xbsUvv2Y
GIIzEoL/b67StarzHJwPTMfApXNKCVDaDpIqvreroNt8oWuGvBnaZYdnsHSoxrnvFgku
MWdLlXqj2aUAoOEXY4SnfNzXerWvKM/m1bp5YKkQ9uit1KUPxJdD5C0+xD2a4UkjUK+/
hbea7mdgUVkUfCPc7LFLu6nH1W5zZQczHT4FG7BIfh6nzO3SluN27rV2rMk4LkNBrzcg
3PgbMkrY3BfjZcB62wYkL4EDF8PmVie4aO0qABqUEQZNDuKuPlCiSLaqeVxYXFyTxQk6
1LSw==
X-Gm-Message-State: AOAM53112u1XJZFQZGpFhGvaViCc5t4MpiEjscPg19qRMQHFI/afZXgR
ykZnsdpUGxc6DCT9E1FdQNKWXNCtpwWDmZRtsko=
X-Google-Smtp-Source: ABdhPJxwMBr6yQ0qLH/LozP+WGyaUzeB7SwEusgvJFEIZr4jX1wFCn8vnBs2MYtHi/poRDsiwc1PUA==
X-Received: by 2002:a2e:3207:: with SMTP id y7mr1077237ljy.302.1597999861910;
Fri, 21 Aug 2020 01:51:01 -0700 (PDT)
Received: from mail-lj1-f169.google.com (mail-lj1-f169.google.com.
[209.85.208.169])
by smtp.gmail.com with ESMTPSA id b28sm171530lff.85.2020.08.21.01.51.00
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Fri, 21 Aug 2020 01:51:00 -0700 (PDT)
Received: by mail-lj1-f169.google.com with SMTP id t6so998842ljk.9
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 21 Aug 2020 01:51:00 -0700 (PDT)
X-Received: by 2002:a2e:b0d2:: with SMTP id g18mr979119ljl.136.1597999860202;
Fri, 21 Aug 2020 01:51:00 -0700 (PDT)
MIME-Version: 1.0
References: <g7VgKBKlUmgMkNo6Nq1OkyilwW6Z4WbqeSZHXfvh_LDYmry5R7uGbavyEHtv2xr_0KBevL057TxSdlo_tS0_ucBXYNm8MuTu_jgyrGO9jpo=@wuille.net>
In-Reply-To: <g7VgKBKlUmgMkNo6Nq1OkyilwW6Z4WbqeSZHXfvh_LDYmry5R7uGbavyEHtv2xr_0KBevL057TxSdlo_tS0_ucBXYNm8MuTu_jgyrGO9jpo=@wuille.net>
From: John Newbery <john@johnnewbery.com>
Date: Fri, 21 Aug 2020 09:50:49 +0100
X-Gmail-Original-Message-ID: <CAFmfg2uL-gCV+1e1rf8+ywSUcEGTA01PP4jm+8kYub7R9E9hNw@mail.gmail.com>
Message-ID: <CAFmfg2uL-gCV+1e1rf8+ywSUcEGTA01PP4jm+8kYub7R9E9hNw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000004c1b205ad5f56b1"
X-Mailman-Approved-At: Fri, 21 Aug 2020 09:34:44 +0000
Subject: Re: [bitcoin-dev] Revisiting squaredness tiebreaker for R point in
BIP340
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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, 21 Aug 2020 09:14:18 -0000
--00000000000004c1b205ad5f56b1
Content-Type: text/plain; charset="UTF-8"
Pieter,
Thanks for the illuminating write-up. There seem to be two questions here,
one technical and one process:
1. Is changing to even tie-breaker for R the correct choice technically? I
can't comment on the performance characteristics of using a square/even
tie-breaker and I'll assume the numbers you give are correct. An enormous
benefit that you don't mention (but Nadav and Lloyd do) is that
standardizing to a single tie-breaker for R points and public keys is much
simpler to explain and much easier for implementers and developers to
understand. I've explained the taproot proposals to many people through the
optech workshops and bitdevs meetups, and people are invariably confused by
which type of tie-breaker to use where. Absent a large performance benefit
for having different tiebreakers, I think this alone is good reason to
standardize to one tie-breaker.
2. Is it too late in the process to change? No. We're building things to
last years, hopefully decades. We should measure a hundred times and cut
once. A benefit of the long lead time of taproot is that as we get more
information, we can improve the proposal. Let's do that here. Nadav and
Lloyd have both written alternative implementations of taproot and are
happy to make this change. Presumably if this was going to cause serious
pain for any other implementer/developer they would have raised objections
by now.
Summary: We should change the proposal and implementation to use even
tie-breakers everywhere.
John #notoquadraticresiduetiebreakers Newbery
On Wed, Aug 12, 2020 at 7:49 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hello all,
>
> The current BIP340 draft[1] uses two different tiebreakers for conveying
> the Y coordinate of points: for the R point inside signatures squaredness
> is used, while for public keys evenness is used. Originally both used
> squaredness, but it was changed[2] for public keys after observing this
> results in additional complexity for compatibility with existing systems.
>
> The reason for choosing squaredness as tiebreaker was performance: in
> non-batch signature validation, the recomputed R point must be verified to
> have the correct sign, to guarantee consistency with batch validation.
> Whether the Y coordinate is square can be computed directly in Jacobian
> coordinates, while determining evenness requires a conversion to affine
> coordinates first.
>
> This argument of course relies on the assumption that determining whether
> the Y coordinate is square can be done more efficiently than a conversion
> to affine coordinates. It appears now that this assumption is incorrect,
> and the justification for picking the squaredness tiebreaking doesn't
> really exist. As it comes with other trade-offs (it slows down signing, and
> is a less conventional choice), it would seem that we should reconsider the
> option of having the R point use the evenness tiebreaker (like public keys).
>
> It is late in the process, but I feel I owe this explanation so that at
> least the possibility of changing can be discussed with all information. On
> the upside, this was discovered in the context of looking into a cool
> improvement to libsecp256k1[5], which makes things faster in general, but
> specifically benefits the evenness variant.
>
>
> # 1. What happened?
>
> Computing squaredness is done through the Jacobi symbol (same inventor,
> but unrelated to Jacobian coordinates). Computing evenness requires
> converting points to affine coordinates first, and that needs a modular
> inverse. The assumption that Jacobi symbols are faster to compute than
> inverses was based on:
>
> * A (possibly) mistaken belief about the theory: fast algorithms for both
> Jacobi symbols and inverses are internally based on variants of the same
> extended GCD algorithm[3]. Since an inverse needs to extract a full big
> integer out of the transition steps made in the extgcd algorithm, while the
> Jacobi symbol just extracts a single bit, it had seemed that any advances
> applicable to one would be applicable to the other, but inverses would
> always need additional work on top. It appears however that a class of
> extgcd algorithms exists (LSB based ones) that cannot be used for Jacobi
> calculations without losing efficiency. Recent developments[4] and a
> proposed implementation in libsecp256k1[5] by Peter Dettman show that using
> this, inverses in some cases can in fact be faster than Jacobi symbols.
>
> * A broken benchmark. This belief was incorrectly confirmed by a broken
> benchmark[6] in libsecp256k1 for the libgmp-based Jacobi symbol calculation
> and modular inverse. The benchmark was repeatedly testing the same constant
> input, which apparently was around 2.5x faster than the average speed. It
> is a variable-time algorithm, so a good variation of inputs matters. This
> mistake had me (and probably others) convinced for years that Jacobi
> symbols were amazingly fast, while in reality they were always very close
> in performance to inverses.
>
>
> # 2. What is the actual impact of picking evenness instead?
>
> It is hard to make very generic statements here, as BIP340 will hopefully
> be used for a long time, and hardware advancements and algorithmic
> improvements may change the balance. That said, performance on current
> hardware with optimized algorithms is the best approximation we have.
>
> The numbers below give the expected performance change from squareness to
> evenness, for single BIP340 validation, and for signing. Positive numbers
> mean evenness is faster. Batch validation is not impacted at all.
>
> In the short term, for block validation in Bitcoin Core, the numbers for
> master-nogmp are probably the most relevant (as Bitcoin Core uses
> libsecp256k1 without libgmp, to reduce consensus-critical dependencies).
> If/when [5] gets merged, safegcd-nogmp will be what matters. On a longer
> time scale, the gmp numbers may be more relevant, as the Jacobi
> implementation there is certainly closer to the state of the art.
>
> * i7-7820HQ: (verify) (sign)
> - master-nogmp: -0.3% +16.1%
> - safegcd-nogmp: +6.7% +17.1%
> - master-gmp: +0.6% +7.7%
> - safegcd-gmp: +1.6% +8.6%
>
> * Cortex-A53: (verify) (sign)
> - master-nogmp: -0.3% +15.7%
> - safegcd-nogmp: +7.5% +16.9%
> - master-gmp: +0.3% +4.1%
> - safegcd-gmp: 0.0% +3.5%
>
> * EPYC 7742: (verify) (sign)
> - master-nogmp: -0.3% +16.8%
> - safegcd-nogmp: +8.6% +18.4%
> - master-gmp: 0.0% +7.4%
> - safegcd-gmp: +2.3% +7.8%
>
> In well optimized cryptographic code speedups as large as a couple percent
> are difficult to come by, so we would usually consider changes of this
> magnitude relevant. Note however that while the percentages for signing
> speed are larger, they are not what is unexpected here. The choice for the
> square tiebreaker was intended to improve verification speed at the cost of
> signing speed. As it turns out that it doesn't actually benefit
> verification speed, this is a bad trade-off.
>
>
> # 3. How big a change is it
>
> * In the BIP:
> - Changing both invocations of `has_square_y` to `has_even_y`.
> - Changing the `lift_x_square_y` invocation to `lift_x_even_y`.
> - Applying the same change to the test vector generation code, and the
> resulting test vectors.
> * In the libsecp256k1:
> - An 8-line patch to the proposed BIP340 implementation[7]: see [8]
> * In Bitcoin Core:
> - Similarly small changes to the Python test reimplementation[9]
> * Duplicating these changes in other draft implementations that may
> already exist.
> * Review for all the above.
>
>
> # 4. Conclusion
>
> We discovered that the justification for using squaredness tiebreakers in
> BIP340 is based on a misunderstanding, and recent developments show that it
> may in fact be a somewhat worse choice than the alternative. It is a
> relatively simple change to address this, but that has be weighed against
> the impact of changing the standard at this stage.
>
> Thoughts?
>
>
> # 5. References
>
> [1]
> https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#design
> [2]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017639.html
> [3] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
> [4] https://gcd.cr.yp.to/safegcd-20190413.pdf
> [5] https://github.com/bitcoin-core/secp256k1/pull/767
> [6] https://github.com/bitcoin-core/secp256k1/pull/797
> [7] https://github.com/bitcoin-core/secp256k1/pull/558
> [8]
> https://github.com/sipa/secp256k1/commit/822311ca230a48d2c373f3e48b91b2a59e1371d6
> [9] https://github.com/bitcoin/bitcoin/pull/17977
>
>
> Cheers,
>
> --
> Pieter
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--00000000000004c1b205ad5f56b1
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Pieter,<div><br></div><div>Thanks for the illuminating wri=
te-up. There seem to be two questions here, one technical and one process:<=
/div><div><br></div><div>1. Is changing to even tie-breaker for R the corre=
ct choice technically? I can't comment on the performance=C2=A0characte=
ristics of using a square/even tie-breaker and I'll assume the numbers =
you give are correct. An enormous benefit that you don't mention (but N=
adav and Lloyd do) is that standardizing to a single tie-breaker for R poin=
ts and public keys is much simpler to explain and much easier for implement=
ers and developers to understand. I've explained the taproot proposals =
to many people through the optech workshops and bitdevs meetups, and people=
are invariably confused by which type of tie-breaker to use where. Absent =
a large performance benefit for having different tiebreakers, I think this =
alone is good reason to standardize to one tie-breaker.</div><div><br></div=
><div>2. Is it too late in the process to change? No. We're building th=
ings to last years, hopefully decades. We should measure a hundred times an=
d cut once. A benefit of the long lead time of taproot is that as we get mo=
re information, we can improve the proposal. Let's do that here. Nadav =
and Lloyd have both written alternative implementations of taproot and are =
happy to make this change. Presumably if this was going to cause serious pa=
in for any other implementer/developer they would have raised objections by=
now.</div><div><br></div><div>Summary: We should change the proposal and i=
mplementation to use even tie-breakers everywhere.</div><div><br></div><div=
>John #notoquadraticresiduetiebreakers Newbery</div></div><br><div class=3D=
"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, Aug 12, 2020 at=
7:49 PM Pieter Wuille via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@li=
sts.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> wrot=
e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0=
.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hello all,<br=
>
<br>
The current BIP340 draft[1] uses two different tiebreakers for conveying th=
e Y coordinate of points: for the R point inside signatures squaredness is =
used, while for public keys evenness is used. Originally both used squaredn=
ess, but it was changed[2] for public keys after observing this results in =
additional complexity for compatibility with existing systems.<br>
<br>
The reason for choosing squaredness as tiebreaker was performance: in non-b=
atch signature validation, the recomputed R point must be verified to have =
the correct sign, to guarantee consistency with batch validation. Whether t=
he Y coordinate is square can be computed directly in Jacobian coordinates,=
while determining evenness requires a conversion to affine coordinates fir=
st.<br>
<br>
This argument of course relies on the assumption that determining whether t=
he Y coordinate is square can be done more efficiently than a conversion to=
affine coordinates. It appears now that this assumption is incorrect, and =
the justification for picking the squaredness tiebreaking doesn't reall=
y exist. As it comes with other trade-offs (it slows down signing, and is a=
less conventional choice), it would seem that we should reconsider the opt=
ion of having the R point use the evenness tiebreaker (like public keys).<b=
r>
<br>
It is late in the process, but I feel I owe this explanation so that at lea=
st the possibility of changing can be discussed with all information. On th=
e upside, this was discovered in the context of looking into a cool improve=
ment to libsecp256k1[5], which makes things faster in general, but specific=
ally benefits the evenness variant.<br>
<br>
<br>
# 1. What happened?<br>
<br>
Computing squaredness is done through the Jacobi symbol (same inventor, but=
unrelated to Jacobian coordinates). Computing evenness requires converting=
points to affine coordinates first, and that needs a modular inverse. The =
assumption that Jacobi symbols are faster to compute than inverses was base=
d on:<br>
<br>
* A (possibly) mistaken belief about the theory: fast algorithms for both J=
acobi symbols and inverses are internally based on variants of the same ext=
ended GCD algorithm[3]. Since an inverse needs to extract a full big intege=
r out of the transition steps made in the extgcd algorithm, while the Jacob=
i symbol just extracts a single bit, it had seemed that any advances applic=
able to one would be applicable to the other, but inverses would always nee=
d additional work on top. It appears however that a class of extgcd algorit=
hms exists (LSB based ones) that cannot be used for Jacobi calculations wit=
hout losing efficiency. Recent developments[4] and a proposed implementatio=
n in libsecp256k1[5] by Peter Dettman show that using this, inverses in som=
e cases can in fact be faster than Jacobi symbols.<br>
<br>
* A broken benchmark. This belief was incorrectly confirmed by a broken ben=
chmark[6] in libsecp256k1 for the libgmp-based Jacobi symbol calculation an=
d modular inverse. The benchmark was repeatedly testing the same constant i=
nput, which apparently was around 2.5x faster than the average speed. It is=
a variable-time algorithm, so a good variation of inputs matters. This mis=
take had me (and probably others) convinced for years that Jacobi symbols w=
ere amazingly fast, while in reality they were always very close in perform=
ance to inverses.<br>
<br>
<br>
# 2. What is the actual impact of picking evenness instead?<br>
<br>
It is hard to make very generic statements here, as BIP340 will hopefully b=
e used for a long time, and hardware advancements and algorithmic improveme=
nts may change the balance. That said, performance on current hardware with=
optimized algorithms is the best approximation we have.<br>
<br>
The numbers below give the expected performance change from squareness to e=
venness, for single BIP340 validation, and for signing. Positive numbers me=
an evenness is faster. Batch validation is not impacted at all.<br>
<br>
In the short term, for block validation in Bitcoin Core, the numbers for ma=
ster-nogmp are probably the most relevant (as Bitcoin Core uses libsecp256k=
1 without libgmp, to reduce consensus-critical dependencies). If/when [5] g=
ets merged, safegcd-nogmp will be what matters. On a longer time scale, the=
gmp numbers may be more relevant, as the Jacobi implementation there is ce=
rtainly closer to the state of the art.<br>
<br>
* i7-7820HQ: (verify) (sign)<br>
=C2=A0 - master-nogmp: -0.3% +16.1%<br>
=C2=A0 - safegcd-nogmp: +6.7% +17.1%<br>
=C2=A0 - master-gmp: +0.6% +7.7%<br>
=C2=A0 - safegcd-gmp: +1.6% +8.6%<br>
<br>
* Cortex-A53: (verify) (sign)<br>
=C2=A0 - master-nogmp: -0.3% +15.7%<br>
=C2=A0 - safegcd-nogmp: +7.5% +16.9%<br>
=C2=A0 - master-gmp: +0.3% +4.1%<br>
=C2=A0 - safegcd-gmp: 0.0% +3.5%<br>
<br>
* EPYC 7742: (verify) (sign)<br>
=C2=A0 - master-nogmp: -0.3% +16.8%<br>
=C2=A0 - safegcd-nogmp: +8.6% +18.4%<br>
=C2=A0 - master-gmp: 0.0% +7.4%<br>
=C2=A0 - safegcd-gmp: +2.3% +7.8%<br>
<br>
In well optimized cryptographic code speedups as large as a couple percent =
are difficult to come by, so we would usually consider changes of this magn=
itude relevant. Note however that while the percentages for signing speed a=
re larger, they are not what is unexpected here. The choice for the square =
tiebreaker was intended to improve verification speed at the cost of signin=
g speed. As it turns out that it doesn't actually benefit verification =
speed, this is a bad trade-off.<br>
<br>
<br>
# 3. How big a change is it<br>
<br>
* In the BIP:<br>
=C2=A0 - Changing both invocations of `has_square_y` to `has_even_y`.<br>
=C2=A0 - Changing the `lift_x_square_y` invocation to `lift_x_even_y`.<br>
=C2=A0 - Applying the same change to the test vector generation code, and t=
he resulting test vectors.<br>
* In the libsecp256k1:<br>
=C2=A0 - An 8-line patch to the proposed BIP340 implementation[7]: see [8]<=
br>
* In Bitcoin Core:<br>
=C2=A0 - Similarly small changes to the Python test reimplementation[9]<br>
* Duplicating these changes in other draft implementations that may already=
exist.<br>
* Review for all the above.<br>
<br>
<br>
# 4. Conclusion<br>
<br>
We discovered that the justification for using squaredness tiebreakers in B=
IP340 is based on a misunderstanding, and recent developments show that it =
may in fact be a somewhat worse choice than the alternative. It is a relati=
vely simple change to address this, but that has be weighed against the imp=
act of changing the standard at this stage.<br>
<br>
Thoughts?<br>
<br>
<br>
# 5. References<br>
<br>
=C2=A0 [1] <a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0340.=
mediawiki#design" rel=3D"noreferrer" target=3D"_blank">https://github.com/b=
itcoin/bips/blob/master/bip-0340.mediawiki#design</a><br>
=C2=A0 [2] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-d=
ev/2020-February/017639.html" rel=3D"noreferrer" target=3D"_blank">https://=
lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017639.html</=
a><br>
=C2=A0 [3] <a href=3D"https://en.wikipedia.org/wiki/Extended_Euclidean_algo=
rithm" rel=3D"noreferrer" target=3D"_blank">https://en.wikipedia.org/wiki/E=
xtended_Euclidean_algorithm</a><br>
=C2=A0 [4] <a href=3D"https://gcd.cr.yp.to/safegcd-20190413.pdf" rel=3D"nor=
eferrer" target=3D"_blank">https://gcd.cr.yp.to/safegcd-20190413.pdf</a><br=
>
=C2=A0 [5] <a href=3D"https://github.com/bitcoin-core/secp256k1/pull/767" r=
el=3D"noreferrer" target=3D"_blank">https://github.com/bitcoin-core/secp256=
k1/pull/767</a><br>
=C2=A0 [6] <a href=3D"https://github.com/bitcoin-core/secp256k1/pull/797" r=
el=3D"noreferrer" target=3D"_blank">https://github.com/bitcoin-core/secp256=
k1/pull/797</a><br>
=C2=A0 [7] <a href=3D"https://github.com/bitcoin-core/secp256k1/pull/558" r=
el=3D"noreferrer" target=3D"_blank">https://github.com/bitcoin-core/secp256=
k1/pull/558</a><br>
=C2=A0 [8] <a href=3D"https://github.com/sipa/secp256k1/commit/822311ca230a=
48d2c373f3e48b91b2a59e1371d6" rel=3D"noreferrer" target=3D"_blank">https://=
github.com/sipa/secp256k1/commit/822311ca230a48d2c373f3e48b91b2a59e1371d6</=
a><br>
=C2=A0 [9] <a href=3D"https://github.com/bitcoin/bitcoin/pull/17977" rel=3D=
"noreferrer" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/1797=
7</a><br>
<br>
<br>
Cheers,<br>
<br>
--<br>
Pieter<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--00000000000004c1b205ad5f56b1--
|