This 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 Stack Exchange, announcements of releases and release candidates, and summaries of notable changes to popular Bitcoin infrastructure software.
None this week.
● Discussion about compiler bugs: a test written last week by Russell O’Connor for libsecp256k1 failed due to a bug in the GNU Compiler Collection’s (GCC’s) built-in version of the standard C library’s
memcmp(memory compare) function. This function takes two regions of memory, interprets them as integer values, and returns whether the first region is less than, equal to, or greater than the second region. This is a commonly used low-level function. Programs are almost never designed to verify such fundamental operations were performed correctly, so bugs of this type can easily result in a program producing incorrect results. Those incorrect results are possible even if the program’s code was well reviewed, strongly tested, formally verified, and otherwise built with the utmost care. A single incorrect result in the execution of cryptographic or consensus code could result in serious consequences for the users of that code—or anyone who depends on remaining in consensus with users of that code.
The potential issues affect not only software written in C and compiled with GCC, but any software or library that depends on software or libraries compiled with the affected versions of GCC. It also includes programs written in other languages whose compilers or interpreters were built using GCC. Although the full extent of the issue is still unknown, Russell O’Connor has run an analysis of an entire Linux system and found only a handful of instances where this bug causes a miscompilation, suggesting that it’s fairly rare for code to be miscompiled due to the bug.
As of this writing, developers have tested Bitcoin Core 0.20.1 and not found any direct problems. If any noteworthy problems are found in other software, we’ll provide an update in a future newsletter.
● 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.
Selected Q&A from Bitcoin Stack Exchange
Bitcoin Stack Exchange is one of the first places Optech contributors look for answers to their questions—or when we have a few spare moments to help curious or confused users. In this monthly feature, we highlight some of the top-voted questions and answers posted since our last update.
● What is the history of nLockTime in Bitcoin Core? Reviewing older versions of Bitcoin Core’s source code, Martin Harrigan asks for clarification on whether height-based or time-based nLockTime features were added first and what fork implications that had. Pieter Wuille and David A. Harding confirm height-based logic came first and give some interesting historical insights.
● Is there any other P2P protocol in use besides a “Gossip protocol”? Murch outlines the different communication protocols used in the Bitcoin ecosystem including Bitcoin’s P2P protocol, mining protocols like FIBRE and stratum, LN-related protocols, as well as multiparty coordination protocols like payjoin.
● Why do Anchor Outputs need to enforce an nSequence of 1? Dalit Sairio asks about anchor outputs and the necessity of the
OP_CHECKSEQUENCEVERIFY(CSV) addition to LN scripts. User darosior describes the concerns around CPFP carve-out and why the delay of 1 block is needed.
Releases and release candidates
New releases and release candidates for popular Bitcoin infrastructure projects. Please consider upgrading to new releases or helping to test release candidates.
- ● LND 0.11.1-beta.rc4 is the release candidate for a minor version. Its release notes summarize the changes as “a number of reliability improvements, some macaroon [authentication token] upgrades, and a change to make our version of anchor commitments spec compliant.”
Notable code and documentation changes
● Bitcoin Core #18267 and #19993 add support for signet. If Bitcoin Core is started with
-chain=signet), it’ll connect to either the default signet or the signet defined by the
● Bitcoin Core #19572 adds a new “sequence” ZMQ topic that notifies subscribers when blocks are connected/disconnected and when transactions are added/removed from the mempool. Transaction addition/removal notification messages include a “mempool sequence number” that subscribers can use to determine the order in which these additions/removals occurred and to cross-reference with
getrawmempoolRPC results, which now also include this new field.
● Eclair #1501 adds support for unilateral closes of channels using anchor outputs, completing Eclair’s basic implementation of this new LN protocol feature. According to the PR, Eclair still needs to add the features necessary to fee bump commitment transactions and HTLCs, but this is coming next.
● LND #4576 is the first in a planned series of PRs adding support for anchor outputs to LND’s watchtower implementation. This PR, in particular, adds a flag indicating that anchor outputs were used in the channel being closed so that the watchtower can respond appropriately. The PR notes, “[the] changes require no modification of the encrypted payload format. The anchor payloads are equal size and contain exactly the same witness info as the legacy payloads, only requiring light modifications to the reconstruction logic.”
● BIPs #907 updates the BIP155 specification of version 2
addrmessages to allow addresses up to 512 bytes and adds a new
sendaddrv2message that nodes can use to signal that they want to receive