Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 13B6CC004D for ; 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 ; 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 ; 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 ; Thu, 13 Aug 2020 05:32:26 +0000 (UTC) Received: by mail-io1-f51.google.com with SMTP id u126so6008027iod.12 for ; 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: In-Reply-To: From: Lloyd Fournier Date: Thu, 13 Aug 2020 15:31:58 +1000 Message-ID: To: Nadav Kohen , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Thanks for bringing this discovery up and a big thank= s to Peter Dettman for working on this.

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 -> point conversion it's worth= it from my perspective.

LL

On Thu, Aug 13, 2= 020 at 6:29 AM Nadav Kohen via bitcoin-dev <bitcoin-dev@lists.linuxfound= ation.org> wrote:
Hello Pieter and all,

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.

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'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's thoughts on this of course but I f= igured I'd voice my support :)

Best,
Nadav




On Wed, Aug 12, 2020 at 2:04 PM Pie= ter Wuille via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>= ; wrote:
Hello a= ll,

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.

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.

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).
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.


# 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 base= d on:

* 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.

* 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.


# 2. What is the actual impact of picking evenness instead?

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.

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.

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.

* i7-7820HQ: (verify) (sign)
=C2=A0 - master-nogmp: -0.3% +16.1%
=C2=A0 - safegcd-nogmp: +6.7% +17.1%
=C2=A0 - master-gmp: +0.6% +7.7%
=C2=A0 - safegcd-gmp: +1.6% +8.6%

* Cortex-A53: (verify) (sign)
=C2=A0 - master-nogmp: -0.3% +15.7%
=C2=A0 - safegcd-nogmp: +7.5% +16.9%
=C2=A0 - master-gmp: +0.3% +4.1%
=C2=A0 - safegcd-gmp: 0.0% +3.5%

* EPYC 7742: (verify) (sign)
=C2=A0 - master-nogmp: -0.3% +16.8%
=C2=A0 - safegcd-nogmp: +8.6% +18.4%
=C2=A0 - master-gmp: 0.0% +7.4%
=C2=A0 - 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 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.


# 3. How big a change is it

* In the BIP:
=C2=A0 - Changing both invocations of `has_square_y` to `has_even_y`.
=C2=A0 - Changing the `lift_x_square_y` invocation to `lift_x_even_y`.
=C2=A0 - Applying the same change to the test vector generation code, and t= he resulting test vectors.
* In the libsecp256k1:
=C2=A0 - An 8-line patch to the proposed BIP340 implementation[7]: see [8]<= br> * In Bitcoin Core:
=C2=A0 - 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 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.

Thoughts?


# 5. References

=C2=A0 [1] https://github.com/b= itcoin/bips/blob/master/bip-0340.mediawiki#design
=C2=A0 [2] https://= lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017639.html
=C2=A0 [3] https://en.wikipedia.org/wiki/E= xtended_Euclidean_algorithm
=C2=A0 [4] https://gcd.cr.yp.to/safegcd-20190413.pdf =C2=A0 [5] https://github.com/bitcoin-core/secp256= k1/pull/767
=C2=A0 [6] https://github.com/bitcoin-core/secp256= k1/pull/797
=C2=A0 [7] https://github.com/bitcoin-core/secp256= k1/pull/558
=C2=A0 [8] https://= github.com/sipa/secp256k1/commit/822311ca230a48d2c373f3e48b91b2a59e1371d6
=C2=A0 [9] https://github.com/bitcoin/bitcoin/pull/1797= 7


Cheers,

--
Pieter

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000001fc68c05acbba123--