txgraph: use fallback order when linearizing (feature)
What the developer wrote
Authored by Pieter Wuille
txgraph: use fallback order when linearizing (feature)
Add glue to make TxGraph use the fallback order provided to it, in the
fallback comparator it provides to the cluster linearization code.
The order of chunks within a cluster becomes:
1. Topology (chunks after their dependencies)
2. Feerate (high to low)
3. Weight (small to large)
4. Max-txid (chunk with lowest maximum-txid first)
The order of transactions within a chunk becomes:
1. Topology (parents before children)
2. Individual transaction feerate (high to low)
3. Weight (small to large)
4. Txid (low to high txid)
This makes optimal cluster linearization, both the order of chunks
within a chunk, and the order of transactions within those chunks,
completely deterministic.
What changed, and why it matters
This change makes Bitcoin Core's transaction-graph cluster linearization use a deterministic fallback ordering when the optimal algorithm ties or cannot fully decide. Previously the fallback relied on internal index numbers, which could leak information about how transactions are stored internally. The new fallback uses actual transaction properties (feerate, weight, txid) and an externally supplied order, making behavior predictable and less dependent on internal memory layout. It is a hardening/feature improvement rather than a fix for an active exploit.
No urgent action required. Treat as normal code review/hardening. Verify that m_fallback_order is itself deterministic and does not introduce new sources of non-determinism or side channels in consensus-critical paths.
Security signals we found
Removal of internal DepGraphIndex-based fallback ordering, reducing potential information leakage about internal cluster indexes
Introduction of deterministic, externally-defined fallback ordering for cluster linearization
Comment explicitly noted the old fallback could leak information about DepGraphIndexes
Evidence from the diff
The patch modifies GenericClusterImpl::Relinearize in src/txgraph.cpp. It replaces the IndexTxOrder{} fallback comparator passed to Linearize() with a closure that invokes graph.m_fallback_order on the actual transaction references (ref_a, ref_b). The fallback order now sorts by topology, feerate, weight, and max-txid for chunks, and by topology, individual feerate, weight, and txid for transactions within chunks. The comment about reducing information leakage from DepGraphIndexes is removed because the fallback no longer uses internal indexes.
Changed components
src/txgraph.cppGenericClusterImpl::RelinearizeTxGraph cluster linearization fallback orderingInspect captured patch +8 / −5
diff --git a/src/txgraph.cpp b/src/txgraph.cpp
index 2c024c96..176ef613 100644
--- a/src/txgraph.cpp
+++ b/src/txgraph.cpp
@@ -2140,11 +2140,14 @@ std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph, in
if (IsOptimal()) return {0, false};
// Invoke the actual linearization algorithm (passing in the existing one).
uint64_t rng_seed = graph.m_rng.rand64();
- auto [linearization, optimal, cost] = Linearize(m_depgraph, max_iters, rng_seed, IndexTxOrder{}, m_linearization, /*is_topological=*/IsTopological());
- // Postlinearize to improve the linearization (if optimal, only the sub-chunk order), and
- // reduce the amount of information the IndexTxOrder-based fallback order leaks about
- // DepGraphIndexes in the cluster. This also guarantees that all chunks are connected (even
- // when non-optimal).
+ const auto fallback_order = [&](DepGraphIndex a, DepGraphIndex b) noexcept {
+ const auto ref_a = graph.m_entries[m_mapping[a]].m_ref;
+ const auto ref_b = graph.m_entries[m_mapping[b]].m_ref;
+ return graph.m_fallback_order(*ref_a, *ref_b);
+ };
+ auto [linearization, optimal, cost] = Linearize(m_depgraph, max_iters, rng_seed, fallback_order, m_linearization, /*is_topological=*/IsTopological());
+ // Postlinearize to improve the linearization (if optimal, only the sub-chunk order).
+ // This also guarantees that all chunks are connected (even when non-optimal).
PostLinearize(m_depgraph, linearization);
// Update the linearization.
m_linearization = std::move(linearization);
Why this scored 18/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.