From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id A68F5C004D for ; Wed, 12 Aug 2020 18:57:43 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 9CECD883B1 for ; Wed, 12 Aug 2020 18:57:43 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HT50n0dtuAFY for ; Wed, 12 Aug 2020 18:57:41 +0000 (UTC) X-Greylist: delayed 00:07:31 by SQLgrey-1.7.6 Received: from mail-40133.protonmail.ch (mail-40133.protonmail.ch [185.70.40.133]) by whitealder.osuosl.org (Postfix) with ESMTPS id 3F5A083683 for ; Wed, 12 Aug 2020 18:57:41 +0000 (UTC) Date: Wed, 12 Aug 2020 18:49:56 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wuille.net; s=protonmail; t=1597258207; bh=9lC+xWJQ9Kw93VaCY3w+VICqh9i+8beMTCJ2nWiwjAc=; h=Date:To:From:Reply-To:Subject:From; b=F06hCAwbLDTv72c6m9RabLHw8XNwJX9ooYZNqYEvSbOc1/AgHJBp8QlDmaZWtWVxU xlzh6veryfy7MFQ5INPz3IBHZESIvkNfZFnRt8jwQ5n1o2BuTsVXMCGOKPpaPzI+9r ZyxcQYHWaXA5PBb7KGcMpbc1nSYykmm9owgX/oPY= To: Bitcoin dev list From: Pieter Wuille Reply-To: Pieter Wuille Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Wed, 12 Aug 2020 19:04:05 +0000 Subject: [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: Wed, 12 Aug 2020 18:57:43 -0000 Hello all, 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 really ex= ist. As it comes with other trade-offs (it slows down signing, and is a les= s 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 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) - 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 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 spee= d, 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 re= sulting 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 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 [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/822311ca230a48d2c373f3e48b91= b2a59e1371d6 [9] https://github.com/bitcoin/bitcoin/pull/17977 Cheers, -- Pieter