path: root/73/0facd96b5245072f08b3cfccdefcf6cdb78d2c

Return-Path: <lloyd.fourn@gmail.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 13B6CC004D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 13 Aug 2020 05:32:30 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by silver.osuosl.org (Postfix) with ESMTP id D7932204E2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 13 Aug 2020 05:32:29 +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 gcRd+ygsNtl7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 13 Aug 2020 05:32:26 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-io1-f51.google.com (mail-io1-f51.google.com
 [209.85.166.51])
 by silver.osuosl.org (Postfix) with ESMTPS id AF6EC203EA
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 13 Aug 2020 05:32:26 +0000 (UTC)
Received: by mail-io1-f51.google.com with SMTP id u126so6008027iod.12
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 12 Aug 2020 22:32:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=46hoe0owBJJjcQuYRJ8Z3029w6U2hvtGovjq1/5fYvg=;
 b=d8nGniHCCKYWyS72eUy6IY7QUO7AZAdqXQSjPbcMAV+QY/f7NexBZ1IcpI7oyAtTWS
 NUym4pKZpryKx5JSuAqTeOOqySBDq1s8FyafUvuWZCZlIgke2dJgRlsrhhQp5Ct9JNX0
 YcPhiP7JiNe/UBk8VYG+GPFvkm0abJjflmff42Hq190T9A5fug+oQkfu64uQzWBkXYjo
 kklSZKUrjeAYStBO94g6XkBU1imR4sRKz/0dAYcou9mLULrylGewZFKA9mAocwP587Ni
 M3FxeUc9afxPqJFFCTUMRHL0EuWey0+pu7AdHlQwy1LcA2cWlSyPcBbtLpmeSZa5ejSg
 ze3g==
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:cc;
 bh=46hoe0owBJJjcQuYRJ8Z3029w6U2hvtGovjq1/5fYvg=;
 b=rClQaFe5wVgvI/rkviA3WMBJvvM40YPQh4pxW/EEQ83nZcKxAT1KczivgHRm4P/ZHn
 PHlHdAxdNanbQW055CuHcOSRQia6M8tALhGX3I3YHKuUY+10afQ8dkAs8ikYioPeYCfp
 O75sAUM6CbPMvBtUBSEC1Kuc2LiNdGAG+rd3IIWhzXnPzY6vnwcveyGW7IsNIIYB+uZP
 8WF500qqk/XWR52dqLNxg6OJsA0H+zDiCJq/pq/+yhr4M8hw9RdnSBLvtHF/alxLq/c1
 Ig0+E9bqREP09va4G3Ju/7Qkm8T0+qVnQkZ5qq0nEo6yPC0nsHU8SD6X/5CZ3SNUvdZz
 +aYA==
X-Gm-Message-State: AOAM531muQ17AaWo7OSpbM8xtz8DSQye2ieOYfXc2hGh+4sv4fTgELNo
 NlnqBrDbDJDlAbZ216Y1wAQYSuQLvvKjXgjotRw=
X-Google-Smtp-Source: ABdhPJyrm1avqMOhCC7ATfSIJct+3LLtdg/dK8u6P91FotkJ71qOtVCkflIptrhEnExQ4A0UIaAB2jZsbBPdeFE28O0=
X-Received: by 2002:a02:6a6b:: with SMTP id m43mr3266726jaf.79.1597296745628; 
 Wed, 12 Aug 2020 22:32:25 -0700 (PDT)
MIME-Version: 1.0
References: <g7VgKBKlUmgMkNo6Nq1OkyilwW6Z4WbqeSZHXfvh_LDYmry5R7uGbavyEHtv2xr_0KBevL057TxSdlo_tS0_ucBXYNm8MuTu_jgyrGO9jpo=@wuille.net>
 <CALGTLwOStbj6j4p2FFf+mw+88=W7cbNDhoCbpLL9zR9XmrS4Sg@mail.gmail.com>
In-Reply-To: <CALGTLwOStbj6j4p2FFf+mw+88=W7cbNDhoCbpLL9zR9XmrS4Sg@mail.gmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Thu, 13 Aug 2020 15:31:58 +1000
Message-ID: <CAH5Bsr16LN=4d4ns0t5fYE11aw2FfnkBzBJionUUxF+76t+Dfg@mail.gmail.com>
To: Nadav Kohen <nadav@suredbits.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000001fc68c05acbba123"
X-Mailman-Approved-At: Thu, 13 Aug 2020 06:49:10 +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: Thu, 13 Aug 2020 05:32:30 -0000

--0000000000001fc68c05acbba123
Content-Type: text/plain; charset="UTF-8"

Thanks for bringing this discovery up and a big thanks to Peter Dettman for
working on this.

I second what Nadav said. Removing pointless complexity is worth it even at
this stage. I also maintain a non-libsecp implementation of BIP340 etc.
Having two ways to convert an xonly to a point is a pain if you are trying
to maintain type safe apis. If there is no performance penalty (or even a
small one in the short term) to unifying xonly -> point conversion it's
worth it from my perspective.

LL

On Thu, Aug 13, 2020 at 6:29 AM Nadav Kohen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello Pieter and all,
>
> I am one of the maintainers of Bitcoin-S[1] and I maintain our secp256k1
> bindings (via JNI) as well as our (inefficient) bouncy castle fallback
> implementations of all secp256k1 functionality we depend on including
> Schnorr signatures. In light of this new information that there is no real
> downside to using evenness as the nonce tie-breaker, I am personally very
> in favor of this change as it strictly simplifies things as well as making
> types consistent between nonces and persistent signing keys (I can get rid
> of our SchnorrNonce type :). An additional minor benefit not already
> mentioned is that in places in our codebase where deserialized data is just
> being passed around and not used, we currently require a computation to go
> from a (x-only) SchnorrNonce to an ECPublicKey whereas going from a
> SchnorrPublicKey simply requires pre-pending a 0x02 byte.
>
> I am likely not aware of the entire impact that changing the BIP at this
> stage would have but from my view (of having to update bindings and test
> vectors and my fallback implementation, as well as wanting to get a stable
> branch on secp256k1-zkp containing both ECDSA adaptor signatures and
> Schnorr signatures for use in Discreet Log Contracts), I think this change
> is totally worth it and it will only become harder to make this
> simplification in the future. The schnorrsig branch has not yet been merged
> into secp256k1 (and is nearing this stage I think) and so long as making
> this change doesn't set us back more than a month (which seems unlikely) I
> am personally in favor of making this change. Glad to hear other's thoughts
> on this of course but I figured I'd voice my support :)
>
> Best,
> Nadav
>
> [1] https://github.com/bitcoin-s/bitcoin-s/
>
>
>
> On Wed, Aug 12, 2020 at 2:04 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
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--0000000000001fc68c05acbba123
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Thanks for bringing this discovery up and a big thank=
s to Peter Dettman for working on this.<br></div><div><br></div><div>I seco=
nd what Nadav said. Removing pointless complexity is worth it even at this =
stage. I also maintain a non-libsecp implementation of BIP340 etc. Having t=
wo ways to convert an xonly to a point is a pain if you are trying to maint=
ain type safe apis. If there is no performance penalty (or even a small one=
 in the short term) to unifying xonly -&gt; point conversion it&#39;s worth=
 it from my perspective.</div><div><br><div>LL</div></div></div><br><div cl=
ass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Aug 13, 2=
020 at 6:29 AM Nadav Kohen via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-de=
v@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfound=
ation.org</a>&gt; wrote:<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"><div dir=3D"ltr">Hello Pieter and all,<div><br></div><div>I am o=
ne of the maintainers of Bitcoin-S[1] and I maintain our secp256k1 bindings=
 (via JNI) as well as our (inefficient) bouncy castle fallback implementati=
ons of all secp256k1 functionality we depend on including Schnorr signature=
s. In light of this new information that there is no real downside to using=
 evenness as the nonce tie-breaker, I am personally very in favor of this c=
hange as it strictly simplifies things as well as making types consistent b=
etween nonces and persistent signing keys (I can get rid of our SchnorrNonc=
e type :). An additional minor benefit not already mentioned is that in pla=
ces in our codebase where deserialized data is just being passed around and=
 not used, we currently require a computation to go from a (x-only) Schnorr=
Nonce to an ECPublicKey whereas=C2=A0going from a SchnorrPublicKey simply r=
equires pre-pending a 0x02 byte.</div><div><br></div><div>I am likely not a=
ware of the entire impact that changing the BIP at this stage would have bu=
t from my view (of having to update bindings and test vectors and my fallba=
ck implementation, as well as wanting to get a stable branch on secp256k1-z=
kp containing both ECDSA adaptor signatures and Schnorr signatures for use =
in Discreet Log Contracts), I think this change is totally worth it and it =
will only become harder to make this simplification in the future. The schn=
orrsig=C2=A0branch has not yet been merged into secp256k1 (and is nearing t=
his stage I think) and so long as making this change doesn&#39;t set us bac=
k more than a month (which seems unlikely) I am personally in favor of maki=
ng this change. Glad to hear other&#39;s thoughts on this of course but I f=
igured I&#39;d voice my support :)</div><div><br></div><div>Best,</div><div=
>Nadav</div><div><br></div><div>[1]=C2=A0<a href=3D"https://github.com/bitc=
oin-s/bitcoin-s/" target=3D"_blank">https://github.com/bitcoin-s/bitcoin-s/=
</a></div><div><br></div><div><br></div></div><br><div class=3D"gmail_quote=
"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, Aug 12, 2020 at 2:04 PM Pie=
ter Wuille via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfou=
ndation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt=
; wrote:<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 a=
ll,<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&#39;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&#39;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>
_______________________________________________<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>

--0000000000001fc68c05acbba123--