[DO NOT MERGE] Erlay: bandwidth-efficient transaction relay protocol (Full implementation) #35591

Erlay Project Tracking: #30249 Conceptual Discussion: #34542

---

This is a full implementation of Erlay. Its purpose is to check the integrity and correctness of the implementation against changes/additions that may originate from the review process and/or rebases on top of newer functionality.

This is not to be merged. Functionality will be spread across multiple smaller PRs to ease the review process.

---

Approach

This approach uses Erlay as a fallback mechanism for transaction propagation. Instead of mixing fanout and reconciliation into a single connection type, the current approach leaves the existing connections as they are, and adds additional low-bandwidth connections to be used in case the node is being eclipsed. This connections should have minimal cost under normal circumstances, and only undergo real traffic in case other 8 full-outbound connections are being captured.

outbound-full-reconciliation connections

For now, we are adding 4 additional reconciliation-only connections to the node while we test it's impact on real node running the approach. Further analysis may be needed to pick a meaningful value for this. The number of inbound connections should also be scaled based on how many connections we are adding.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/35591.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline and AI policy for information on the review process. A summary of reviews will appear here.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #35561 (net: move some CNodeState fields to Peer by Crypt-iQ)
• #35522 (refactor: Extract per-message helpers from SendMessages() (move-only) by pablomartin4btc)
• #34743 (p2p: don't disconnect manual peers for block stalling by willcl-ark)
• #32554 (bench: replace embedded raw block with configurable block generator by l0rinc)
• #31260 (scripted-diff: Type-safe settings retrieval by ryanofsky)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

LLM Linter (✨ experimental)

Possible typos and grammar issues:

• Giving it a 6x marging to prevent flakiness -> Giving it a 6x margin to prevent flakiness [“marging” is misspelled]
• peer1 only has one one tx in the set, which matches out sketch som no diff -> peer1 only has one tx in the set, which matches our sketch so no diff [multiple typos/broken words: “one one”, “out”, “som”]

Possible places where named args for integral literals may be used (e.g. func(x, /*named_arg=*/0) in C++, and func(x, named_arg=0) in Python):

• AddTxsToReconSet(tracker, peer_id2, 5) in src/test/txreconciliation_tests.cpp
• AddTxsToReconSet(tracker, peer_id0, 5) in src/test/txreconciliation_tests.cpp
• AddTxsToReconSet(tracker, peer_id0, 10) in src/test/txreconciliation_tests.cpp
• AddTxsToReconSet(tracker, peer_id1, 10) in src/test/txreconciliation_tests.cpp
• AddTxsToReconSet(tracker, peer_id2, 10) in src/test/txreconciliation_tests.cpp
• self.generate_txs(self.wallet, 0, 10, 0) in test/functional/p2p_txrecon_initiator.py
• self.test_reconciliation_initiator_no_extension(3, 3, 20) in test/functional/p2p_txrecon_initiator.py
• self.generate_txs(self.wallet, 0, 1, 0) in test/functional/p2p_txrecon_responder.py
• self.generate_txs(self.wallet, 0, 5, 0) in test/functional/p2p_txrecon_responder.py
• self.test_reconciliation_responder_flow_no_extension(3, 3, 20) in test/functional/p2p_txrecon_responder.py

Possible places where comparison-specific test macros should replace generic comparisons:

• [test/functional/p2p_txrecon_disabled.py] assert self.nodes[0].process.poll() is None, f"node crashed handling {msgname}" -> assert_equal(self.nodes[0].process.poll(), None)

^{2026-08-24 11:30:00}

Rebased on master.

Opening this so it can be tested against CI and to make sure nothing obvious is missing. Next step will be testing with real nodes (most likely in Warnet).

Things to consider/add:

• This is currently using sendtxrcncl as a way, for outbound nodes, to signal they want to establish a full-reconciliation connection, plus adding a limit on the number of full-reconcilition inbounds that will be accepted by a node. This is not the originally intended way of using sendtxrcncl. It may be worth considering an approach based on BIP-434.
• The extension phase was designed so peers with an ongoing reconciliation that had underpredicted the sketch capacity could still reconcile without having to directly fallback to fanout. Given reconciliation is now used as fallback, and the extra bandwidth may not be as problematic, it may be worth considering overshooting the initial sketch capacity and getting rid of the extension phase.
• Fuzz tests are missing

Fixed some typos and addressed some of the linter suggestions

6554707...e63db1a

Fixed several bugs and added a new test for receiving reconciliation messages when reconciliation is not enabled.

e63db1a...35bcd04

Addressed some issues pointed out by corecheck.

35bcd04...d08f127

**Testing report (LLM/experimental) based on the results of an incremental mutation testing run for this PR - full result is avaliable at: https://bitcoincore.space**

---

The overall result is mixed. The PR already has useful coverage for the happy-path reconciliation flow, basic protocol violations, and some queue/timer behavior. However, the survivors show that the tests still leave several important behaviors only weakly specified, especially where reconciliation falls back, extends, or interacts with INV relay bookkeeping.

What the current tests do well

The existing tests cover the basic handshake and some normal flows reasonably well:

• unit coverage for peer registration, queue rotation, set insertion/removal, and non-extension reconciliation in src/test/txreconciliation_tests.cpp
• functional coverage for initiator/responder happy paths in test/functional/p2p_txrecon_initiator.py and test/functional/p2p_txrecon_responder.py
• protocol-violation checks for clearly invalid message ordering and unsupported peers

That baseline is good enough to kill most straightforward mutations. The survivors are mostly about what happens around the edges of the protocol, not the central flow.

Main gaps exposed by the surviving mutants

1. Extension handling is under-tested

This is the clearest gap. Several survivors change extension behavior without being detected:

• not sending REQSKETCHEXT after an undecodable sketch in net_processing
• not snapshotting state before the extension round
• accepting/rejecting malformed extension sizes incorrectly
• flipping success/failure outcomes of extension decoding
• using the wrong transaction set after extension failure
• not clearing peer state after extension completion

This lines up with the current functional tests: both initiator and responder tests explicitly stop short of extension coverage and even leave TODOs for it in test/functional/p2p_txrecon_initiator.py and test/functional/p2p_txrecon_responder.py.

What should be improved:

• add end-to-end functional tests that force an extension round and assert the exact message sequence: REQTXRCNCL -> SKETCH -> REQSKETCHEXT -> SKETCH -> RECONCILDIFF
• assert both extension success and extension failure behavior
• verify that extension failure falls back to announcing the snapshotted set, not the live set
• verify that state is cleared after extension completion and that a second reconciliation starts cleanly

2. Boundary conditions are not pinned down tightly enough

Several survivors change strict inequalities to inclusive ones and still pass:

• remote_sketch_capacity > MAX_SKETCH_CAPACITY changed to >=
• extended_capacity > MAX_SKETCH_CAPACITY * 2 changed to >=
• peer_q > Q_PRECISION changed to >=

This means the tests exercise invalid-above-limit cases, but not the exact boundary values that should remain valid. There is already a good example of this style for rounded q formatting in src/test/txreconciliation_tests.cpp, but the same precision is missing for protocol acceptance thresholds.

What should be improved:

• add exact-boundary tests for MAX_SKETCH_CAPACITY, 2 * MAX_SKETCH_CAPACITY, and Q_PRECISION
• check both sides of each threshold: limit must pass, limit + 1 must fail

3. INV relay side effects are only partially asserted

Many survivors in PeerManagerImpl::AnnounceTxs() and the send path in SendMessages() remove or alter important side effects without breaking tests:

• skipping heap construction/pop order
• changing continue to break when one candidate should not be sent
• not inserting into m_tx_inventory_known_filter
• not erasing from m_tx_inventory_to_send
• not flushing INV batches at MAX_INV_SZ
• not clearing the batch after sending

The current tests mostly check that transactions eventually arrive. They do not strongly check how they are batched, filtered, or suppressed from future re-announcement. That leaves a lot of bookkeeping mutations alive.

What should be improved:

• add tests with a mix of sendable and unsendable transactions and assert that later eligible transactions are still announced
• assert that transactions already known to the peer are not re-announced in the next round
• add a case above MAX_INV_SZ and verify the number and sizes of INV messages
• verify that reconciliation and fanout paths do not duplicate announcements after internal state should have been cleared

4. Some state-management behaviors are observable in principle, but not asserted

Survivors also show weak checking around reconciliation state transitions:

• not clearing m_short_id_mapping
• not clearing peer state after handling a result
• always taking the “removed” branch in TryRemovingFromSet
• not recording m_announced_while_reconciling
• returning success from queue-selection paths that should be false

These are not all equally severe, but together they indicate that the tests often validate the final external effect of a single round without checking the follow-up round that would expose stale state.

What should be improved:

• add two-step tests that perform one reconciliation round and then immediately start another to detect stale snapshots, stale mappings, or stale queue state
• specifically verify the “received while reconciling” behavior across the extension path, not just the non-extension path

Bottom line

The current tests are good at proving that the basic txreconciliation flow works. They are not yet strong enough to fully specify the extension path, the exact protocol boundaries, or the internal bookkeeping that prevents duplicate, truncated, or stale announcements.

If I had to prioritize follow-up work, I would do it in this order:

1. Add full initiator/responder extension-path functional tests.
2. Add exact boundary tests for sketch capacity and q.
3. Add stronger assertions around INV batching, filtering, and duplicate suppression.
4. Add second-round/state-cleanup tests to catch stale reconciliation state.

That would likely eliminate most of the meaningful survivors from this run and materially improve confidence in the PR’s tests.

Rebased to include the latest changes in master, including the changes introduced in https://github.com/bitcoin/bitcoin/pull/34628.

Reworked the transaction announcement logic so most of it can be re-used by the trickle code path and the new post-reconciliation code path.

Also started to killing @brunoerg reported mutants.

d08f127...41de5f9

Finished covering the most relevant mutants. Left out the ones regarding extensions, as I'm still debating whether those will be part of the PR.

41de5f9...816d2cd

Rebased master to cover #35852, and applied the inline const(expr) convention introduced by the PR to cover new definitions.

816d2cd...d34d736

Fixed several uncovered edge cases.

d34d736...b0186aa

Added benches for how long it takes to build and decode sketches based on their capacity. This may affect the max sketch capacity that we may accept to work with.

This results in the following:

• The decode for a typical/realistic round (7 tx/s, 30s, q=0.25) is in the order of tens of microseconds.
• A round between two Core nodes (limiting their set size to MAX_RECONSET_SIZE) takes ~120ms
• A peer that advertises sketches as big as they get (MAX_SKETCH_CAPACITY) can make us take ~2.3s to decode
  • This is amplified to 8.8s in the extension case, as we allow up to double the max capacity

This applies only to outbound peers, as those are the ones that makes us decode. This bears the question, should we limit the maximum sketch size that we accept far bellow MAX_SKETCH_CAPACITY? In the case of Core nodes, sets cannot have more than MAX_RECONSET_SIZE elements. So the maximum sketch sizes are 3001 for the initial sketch, 6002 for an extension.

b0186aa...62bf7d1

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 At least one of the CI tasks failed. _{Task iwyu: https://github.com/bitcoin/bitcoin/actions/runs/32289116534/job/96185584884} _{LLM reason (✨ experimental): CI failed because IWYU detected and rejected incorrect/missing #include ordering/content (generated “Failure generated from IWYU” for src/bench/txreconciliation.cpp).}

<details><summary>Hints</summary>

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

• Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

• A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

• An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

</details>

This should be ready to review at this point, even though some details still need deciding. Happy to split the PR into smaller chunks if it makes it easier.

Open questions (that may arise from reviewing parts of the code):

• Should we negotiate reconciliation using BIP-434?
• Should the new connection type be considered a full-outbound? If so, the eviction logic needs to be patched to include these.
• Are extensions worth if we will be using reconciliation as a fallback, or should we just slightly overestimate the sketch capacity and default to fanout on failure?
• Should we cap the maximum capacity sketch we accept closer to MAX_RECONSET_SIZE than to MAX_SKETCH_CAPACITY?

Rebased e366778...534a890