This week’s newsletter describes research around using binary fuse filters as an alternative to the GCS used in compact block filters. Also included are our regular sections summarizing proposals and discussion about changing Bitcoin’s consensus rules, announcing new releases and release candidates, and describing notable changes to popular Bitcoin infrastructure software.

News

  • ● Binary fuse filters as an alternative to BIP158’s GCS: Csaba Purszki posted to Delving Bitcoin his research on finding a better alternative to Golomb-Rice Coded Sets (GCS) used for compact block filters as defined in BIP158.

    According to Purszki, a suitable alternative can be found in binary fuse filters, a family of probabilistic data structures for approximate set membership, and specifically the 16-bit variant, called Fuse16. The main characteristic of this type of algorithm is the ability to give O(1) query time (for reference, GCS gives O(N)), which reduces the CPU power required to query the filters. Moreover, these filters guarantee zero false negatives, with a rate of false positives equal to 1/2^k, with k being the number of bits.

    Purszki provided the preliminary results of his research, which compare the current GCS performance against binary fuse filters. Tests were performed on 10 different wallet use cases (from 24 scripts up to 480), running filters on 50,000 mainnet blocks, on two different CPUs, a desktop x86_64, and an ARM. Binary fuse filters were able to obtain a 6x-45x speedup on ARM, according to the different wallet use cases, and 9x-80x on desktop at the cost of a slight increase in bandwidth, 0%-3%. For a full write up on the methodology and full results, the reader can refer to Purszki’s website.

    Kyoto developer Robert Netzke commented on the differences in false positive rates with respect to GCS and possible failures that could occur in the algorithm.

Changing consensus

A monthly section summarizing proposals and discussion about changing Bitcoin’s consensus rules.

  • ● Post-quantum HD wallets with fallback SPHINCS keys: In a post on the Bitcoin-Dev mailing list, Conduition described a design for post-quantum BIP32 congruent hierarchical deterministic wallets with fallback SPHINCS keys. The design replaces the child key derivation functions of BIP32 to generate SPHINCS keys alongside secp256k1 keys. Due to the lack of an algebraic relationship within SPHINCS keys, non-hardened child keys share the same SPHINCS keys as their parents and siblings. This requires wallets to insert a nonce (or the secp256k1 key) into scripts spent using the SPHINCS key to retain privacy equivalent to BIP32 wallets. A benefit of this design choice is that the expensive full SPHINCS key derivation can be deferred to the first non-hardened derivation step and then cached for all non-hardened keys below that step. This wallet design is intended to be combined with BIP360 P2MR outputs and a future OP_CHECKSPHINCS (or similar) to enable migration to quantum-resistant wallets. Conduition suggests that such a wallet structure might also be combined with future lower-cost post-quantum signature algorithms with SPHINCS providing a dependable fallback in case they are proven insecure.

  • ● Discussion of a post-quantum output type: Antoine Poinsot wrote to the Bitcoin-Dev mailing list defending a plain post-quantum output type (as opposed to a P2TR-like output type which allows quantum-vulnerable key spending to be disabled by a later soft fork). The crux of the argument is that the decision of whether or when it makes sense to disable quantum-vulnerable spends should be separated from enabling users to migrate to post-quantum cryptography at their discretion. In the subsequent conversation, the participants agreed on both adding post-quantum signing to tapscript and adding a plain post-quantum output type. Several open questions remain, including whether and to what degree to incentivize migration and when / whether to disable quantum-vulnerable signatures.

  • ● Proposal to embed post-quantum keys in tapscript without consensus changes: Daniel Buchner sent a proposal to the Bitcoin-Dev mailing list which describes a potential path to enabling flexible post-quantum wallet designs without fully describing the signature validation parameters. Because BIP342 signature checking opcodes treat all non-32-byte keys as unknown key types which are valid with any non-empty signature, other key lengths (in this case with an initial tag byte) can be used in scripts today as long as either the scripts are kept secret or they also require a secure BIP340 signature in addition to the unknown key or keys. If Buchner’s proposal were to be standardized, wallets could start building scripts with various post-quantum key types now while continuing to spend using quantum-vulnerable keys until such time as a soft fork enables secure spending with the post-quantum keys. Like many quantum migration proposals, this proposal only retains security in the face of a quantum adversary if key reuse is strictly prevented. Buchner is seeking feedback on the proposal.

  • ● BIP54 demonstration of slow blocks on signet: On Delving Bitcoin, Antoine Poinsot wrote about a demonstration of the types of slow-to-validate blocks that BIP54 (consensus cleanup) prevents. Repeated three times over the course of a day, batches of slow-to-validate blocks were signed on the most popular Bitcoin signet and then reorged away to enable testing of propagation and validation behavior of these blocks without forever slowing signet initial block download. Many around the world watched the slow blocks hit their nodes and logged the validation and propagation behavior. As expected, the slow-to-validate blocks propagated much more slowly through the network and required significantly more time to be fully validated on individual nodes compared to typical blocks. It should be noted that these demonstration blocks were far from the worst case that is prevented by BIP54.

  • ● Post-quantum BIP86 recovery using zk-STARK proofs of BIP32 seeds: Olaoluwa Osuntokun (roasbeef) posted on the Bitcoin-Dev mailing list his project to demonstrate zk-STARK recovery of quantum-vulnerable coins secured by keys derived using BIP32. This possible mechanism for coin recovery in the event that secp256k1 is disabled in the face of a cryptographically relevant quantum computer has long been discussed, but never fully demonstrated. Osuntokun produced a fully working implementation of the required prover and verifier and provided benchmarks showing that recovery using this method is, at least, possible. The original implementation was intentionally not optimized and several developers offered optimizations that make the recovery less costly both to prove and to verify.

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.

  • ● Core Lightning 26.04.1 is a maintenance release that includes gossip protocol fixes, as well as build system fixes for environments that experienced problems immediately after the major release.

  • ● BTCPay Server 2.3.8 is a minor release of this self-hosted payment solution that includes subscription and point-of-sale updates, LUD21 LNURL-pay support, an additional API surface for managing subscription offerings, and other fixes and improvements.

  • ● BTCPay Server 2.3.9 is a maintenance release that addresses server recovery after a plugin crash and fixes an xpub parsing issue that was introduced in v2.3.8.

Notable code and documentation changes

Notable recent changes in Bitcoin Core, Core Lightning, Eclair, LDK, LND, libsecp256k1, Hardware Wallet Interface (HWI), Rust Bitcoin, BTCPay Server, BDK, Bitcoin Improvement Proposals (BIPs), Lightning BOLTs, Lightning BLIPs, Bitcoin Inquisition, and BINANAs.

  • ● Bitcoin Core #33671 adds a nonmempool field to the getbalances RPC (see Newsletter #46) for wallet UTXOs spent by transactions that are neither confirmed nor in the node’s mempool, such as unbroadcasted, non-standard, evicted, or transactions that are part of too-long mempool chains. Previously, balance buckets could omit value tied to those in-flight spends even though the wallet still recorded the transactions, so getbalances did not fully reflect how the wallet was accounting for those coins. The PR counts that value in the usual mine buckets where it belongs and applies an offset via nonmempool so the fields sum to the wallet’s overall balance while making the mempool mismatch explicit.

  • ● Bitcoin Core #34885 adds btck_block_tree_entry_get_ancestor() to the libbitcoinkernel C API (see Newsletter #380) for retrieving the ancestor of a block at a specified height on its chain branch. Instead of walking backward one block at a time with repeated calls to btck_block_tree_entry_get_previous(), callers constructing block locators from a stale or forked tip can directly request ancestors at the needed heights.

  • ● Bitcoin Core #33920 adds an exportasmap RPC that exports the node’s ASMap data embedded at build time (see Newsletter #394) to a file. This allows users to inspect, validate, and analyze the data using tools such as contrib/asmap-tool.py.

  • ● Bitcoin Core #34911 removes deprecated RBF-related boolean fields from several mempool RPC responses unless they are explicitly requested using the deprecatedrpc configuration option. The getmempoolinfo RPC no longer returns the fullrbf field by default, as full-RBF behavior has been the default since Bitcoin Core 28.0 and the mempoolfullrbf option was removed in Bitcoin Core 29.0. The getrawmempool, getmempoolentry, getmempoolancestors, and getmempooldescendants RPCs no longer return the deprecated bip125-replaceable field described in BIP125 by default.

  • ● BIPs #1548 adds BIP391, a specification for Binary Output Descriptors (BOD), an efficient container format for output script descriptors based on PSBT-style key-value maps. This BIP has a closed status and lists BIP393 as a proposed replacement, noting that BIP391 was withdrawn after BIP393 proposed an alternative method for handling wallet metadata such as descriptor annotations (see Newsletter #400).

  • ● HWI #831 adds support for the Ledger Nano Gen5 hardware signing device.

  • ● BDK #2188 starts verifying that a transaction returned by an Electrum server matches the requested txid before caching or using it. Previously, a server could respond to a fetch_tx() request with any transaction data and a different txid, and BDK would accept it.

  • ● BDK #2115 adds previous-block-hash awareness to CheckPoint by extending the ToBlockHash trait with an optional prev_blockhash() method. This allows BDK to verify that adjacent checkpoints connect when their payloads contain previous-block-hash information, such as in block headers. This also prevents merge_chains() from treating a conflicting height-0 checkpoint as a normal reorg and replacing it. Now, if two checkpoint chains disagree on genesis, the merge fails. See Newsletters #372 and #390 for previous work on CheckPoint.

Want more?

For more discussion about the topics mentioned in this newsletter, join us for the weekly Bitcoin Optech Recap on Riverside.fm at 16:30 UTC on May 5. The discussion is also recorded and will be available from our podcasts page.