[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:

• #36167 ([RFC] Enable -Wunused by fanquake)
• #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)
• #28690 (build: Introduce internal kernel library by sedited)
• #27052 (test: rpc: add last block announcement time to getpeerinfo result by LarryRuane)

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 [misspelled word]
• 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 misspellings]
• The node should have snapsotted the set. -> The node should have snapshotted the set. [misspelled word]
• after the snapshop is created -> after the snapshot is created [misspelled word]
• Removing after the snapshop should have no effect on the extension. -> Removing after the snapshot should have no effect on the extension. [misspelled word]
• Allows to infer capacity of a reconciliation sketch based on it's char[] representation, -> Allows inference of the capacity of a reconciliation sketch based on its char[] representation, [“it's” should be “its”; wording is also ungrammatical]
• Re set the peer's phase -> Reset the peer's phase [misspelled word]

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):

• self.generate_txs(self.wallet, 0, 0, 2) 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, 10, 0) in test/functional/p2p_txrecon_responder.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}" -> use assert_equal(self.nodes[0].process.poll(), None)

^{2026-09-04 19:28:07}

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

Addresses @brunoerg comments.

I changed the way we parse recon_result to mimic the check we already have in place for BIP152. Also added a test for it.

Regarding the race, I left a comment so we can address it when addressing general recon connection eviction.

I'd appreciate your input on whether OUTBOUND_FULL_RECONCILIATION should be considered full outbound, and on whether extensions are worth keeping.

534a890...25e545c

Rebased to fix CI, plus slightly decreased MAX_INBOUND_RECONCILIATION_PEERS for now, as some inbounds were being evicted in p2p_sendtxrcncl.py after #36078.

MAX_INBOUND_RECONCILIATION_PEERS is currently a magic number, so we can set it properly (and increase the number of inbounds accordingly) once we decide on how to treat recon connections eviction.

d08f127...0eddbbc

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 At least one of the CI tasks failed. _{Task ASan + LSan + UBSan + integer: https://github.com/bitcoin/bitcoin/actions/runs/33909308334/job/101141694892} _{LLM reason (✨ experimental): CI failed because the fuzz build didn’t compile: connman.cpp calls ConnmanTestMsg::GetExtraFullOutboundCount() which no longer exists (“no member named”).}

<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>

@brunoerg, I've gone ahead and added reconciliation connections as full outbound connections, and dealt with connection eviction in the same way we did for full outbounds.

I'm happy to re-work this is reviewers think this should no be seen as full outbounds, but I thought it may be best to just go ahead with an approach instead of waiting for discussion. These is split in two commits, ab8528650be36714554934946679d69247dbb719 to refactor the current logic into a method that can be reused by reconciliation connections, and a 0ce6c11e2a1c2f583a5e0b4eaed5f019c62c0dba that implements that for them.

With this, I should have also covered your concern about v2->v1 downgrades, as outbound reconciliations now have eviction logic.

On top of that, I've changed the logic for when a peer does not accept our reconciliation connection. Before, we will keep that node connected, acting as a regular outbound but taking a reconciliation slot. This is dangerous as it can lead to 12 full outbound connections, which may make us create even more redundant announcements. Now, those connections are dropped, and we look for another peer.

This can create some issues during the deployment phase, if not enough slots are available for all the new connections. I think we can mitigate this by deploying the feature in two phases. Phase 1 deploys the code, but only makes nodes accept incoming reconciliation connections, not start them, that is gated over a flag that is disabled by default (or even just disabled in general). Once enough deployment is reached, we can flip that feature and allow nodes to proactively initiate those. I have currently not gated this, as it makes it easier for testing, but I think it is worth mentioning.

0eddbbc...37912ec