TxGraph::Trim(): avoidable removals caused by implicit linearization dependencies #36656

Tested at a773e1e33b34 (src/txgraph.cpp was unchanged in the tree used for the tests). All sizes below are in weight units (WU).

Context

PR #31553 describes Trim() as best-effort. Its review discussed an example from instagibbs (TxA..TxE) where Trim() evicts a transaction that could have remained. That example came from the earlier stop-at-first-failure version; the current skip-and-continue code handles it. sipa also asked for "ideas for tests that exercise the improved quality UF brings".

This report covers two mechanisms that still produce avoidable removals. Both involve implicit edges between consecutive transactions in an existing cluster linearization. They require a pre-existing cluster of at least three transactions; with two transactions, the implicit edge coincides with the real dependency.

These implicit edges affect both deps_left and the union-find partitions:

1. Over-count: the algorithm builds a candidate's would-be cluster by joining partitions connected through implicit edges. It can therefore reject a candidate even though its real connected component would fit within the limits.
2. Cascade: when a candidate is skipped, its implicit successor never reaches deps_left == 0 and is removed as well, even when none of its real ancestors was removed.

Over-count: implicit edge among block transactions (count limit 3, all sizes 100)

T0 (fee 20), T1 (10) and T2 (30, spends T0 and T1) are transactions from the disconnected block, re-added to the mempool by the reorg. Their linearization is T0, T1, T2. C1 (40) and C2 (50) are mempool transactions spending T0.

Trim() keeps {T0,C1,C2} and removes {T1,T2}. T1 has no ancestors. It is removed only because the implicit edge T0 -> T1 makes it part of T0's would-be cluster.

Removing only T2 is valid: the real clusters would be {T0,C1,C2} (n=3) and {T1} (n=1).

Processing order: T0, C2, C1, then T1, which is rejected because the implicit edge makes the candidate cluster exceed the count limit (3+1 > 3). T2 is never considered.

The same effect can be reproduced with a weight limit of 300 WU using four transactions:

• T0 (fee 20, size 100), T1 (10, size 100) and T2 (30, size 100, spends T0 and T1) are in the block.
• T3 (fee 80, size 200) is in the mempool and spends T0.

Trim() keeps {T0,T3} and removes {T1,T2}. Removing only T2 is valid.

Over-count: implicit edge among mempool transactions (count limit 3, all sizes 100)

R is a block transaction (fee 10). A (20) and D (50) spend R. B (30) has no in-mempool parent. X (40) spends A and B.

Before the reorg, {A,B,X} is linearized as B, A, X. Trim() keeps {R,B,D} and removes {A,X}.

Removing only X is valid: the real clusters would be {R,A,D} (n=3) and {B} (n=1).

Processing order: B, R, D, then A. A is rejected because the implicit edge B -> A joins {R,D}, {B} and A into a would-be cluster of four transactions. X is never considered.

Cascade (count limit 3, all sizes 100)

R is a block transaction (fee 10). P (20) has no in-mempool parent. Y (40) spends R and P. Z (30) spends P. D (50) spends R.

Before the reorg, {P,Y,Z} is linearized as P, Y, Z; D is a separate cluster.

D is included before Y. Rejecting Y is correct at that point: adding it would join {R,D} and {P} into a real cluster of four transactions. But Z's only real parent is P, which remains in the mempool. Z is never considered because its implicit predecessor, Y, was skipped.

Trim() keeps {R,P,D} and removes {Y,Z}. Removing only Y is valid: the real clusters would be {R,D} (n=2) and {P,Z} (n=2).

Processing order: P, R, D, then Y, which is rejected. Z is never considered.

Reproduced on the real reorg path

Functional tests using adaptations of both over-count examples reproduce the effect with the default limits (64 transactions / 404,000 WU, or 101 kvB), both with invalidateblock and with a competing chain:

• Block side: T0 plus 63 mempool children are kept (64 total). T1, which has no ancestors, is removed. sendrawtransaction accepts T1 back as a singleton.
• Mempool side: R's real cluster has 63 transactions. A, a child of R, is evicted even though adding it back would bring the cluster to 64. sendrawtransaction accepts A afterwards.

The cascade example is currently reproduced only in TxGraph unit tests.

Exhaustive search over small graphs

For each reported avoidable removal, I rebuilt a fresh TxGraph from the kept set plus the candidate, using only real dependencies and not calling Trim() again. A candidate counts as re-admissible only if all its real ancestors are kept and the kept set plus the candidate fits within the limits.

Candidates with removed real ancestors are not counted, so these figures are a lower bound. I used a reference trace to classify the mechanism; it matched the production outcome in every case. The graphs were uniformly enumerated. These counts are not estimates of how often the behavior occurs on the network.

The columns count scenarios with at least one avoidable removal, not individual transactions. Each scenario is counted once, and the two classes are mutually exclusive.

No cases were found at smaller n. A separate random search at n=5..8 under the weight limit found cases involving both mechanisms.

Impact and existing tests

The effect is on mempool policy and relay, not consensus. The reproductions do not show funds at risk. They show transactions being removed even though retaining them would satisfy the real cluster limits. This may require rebroadcast and delay propagation.

At the tested commit, the general Trim() check in the txgraph fuzz target verifies that Trim() removes something if and only if a cluster is oversized, that removals are descendant-closed, that every oversized cluster is touched and no other cluster is touched, and that the result fits within the limits. The separate cycle-free Trim() scenario also checks 1 <= removed <= max_removed.

The examples above satisfy these checks: each removes two transactions where removing one would suffice. None of these checks requires the removal set to be minimal.

None of the existing Trim() unit tests (zigzag, flower, huge, big_singletons) or mempool_updatefromblock.py exercises purely implicit edges. A change limited to how these edges are handled should therefore leave those tests unaffected.

Question

Is this acceptable for a best-effort trim? If not, would a change be welcome that unions partitions only across real dependencies and, when a transaction is skipped, still releases successors that are not its real descendants?

Trim() currently receives the implicit chain plus the newly added dependencies, so implementing this would also require providing the real intra-cluster dependencies.

Unit tests, functional tests and exhaustive-search code: https://gist.github.com/javierpmateos/a1a4b947d67aea60fd50897f1c37b1f0

Trimming only happens during reorg. I wouldn't spend a lot of time making this hyper-optimized, unless it's not resulting in correctly sized clusters.