Boletín de Bitcoin Optech # 117This week’s newsletter describes a compiler bug that casts doubt on the safety of secure systems and explains a technique that can be used to more efficiently verify ECDSA signatures in Bitcoin. Also included are our regular sections with popular questions and answers from the Bitcoin StackExchange, announcements of releases and release candidates, and summaries of notable changes to popular Bitcoin infrastructure software.
US Patent 7,110,538 has expired: Bitcoin transactions are secured using ECDSA (the Elliptic Curve Digital Signature Algorithm). Verifying signatures involves multiplying points on the elliptic curve by scalars. Typically, each transaction input requires one or more signature verifications, meaning that syncing the Bitcoin block chain can require many millions of these elliptic curve point multiplications. Any technique to make point multiplications more efficient therefore has the potential to significantly speed up Bitcoin Core’s initial sync.
In a 2011 bitcointalk post, Hal Finney described a method by Gallant, Lambert and Vanstone (GLV) to efficiently compute elliptic curve point multiplications using an endomorphism on the curve (a mapping from the curve to itself which preserves all relationships between points). By using this GLV endomorphism, the multiplication can be broken into two parts, which are calculated simultaneously to arrive at the solution. Doing this can reduce the number of expensive computations by up to 33%. Finney wrote a proof-of-concept implementation of the GLV endomorphism, which he claimed sped up signature verification by around 25%.
Pieter Wuille separately implemented the GLV endomorphism algorithm in the libsecp256k1 library, which is used to verify signatures in Bitcoin Core. However, the algorithm was encumbered by U.S. Patent 7,110,538 and so to avoid any legal uncertainty, the implementation has not previously been distributed to users. On September 25, the patent expired, removing that legal uncertainty. A PR has been opened in the libsecp256k1 repo to always use the GLV endomorphism algorithm, which is expected to decrease Bitcoin Core’s initial sync time significantly.
https://bitcoinops.org/en/newsletters/2020/09/30/