Use cluster linearization for transaction relay sort order
What the developer wrote
Authored by Suhas Daftuar
Use cluster linearization for transaction relay sort order
Previously, transaction batches were first sorted by ancestor count and then
feerate, to ensure transactions are announced in a topologically valid order,
while prioritizing higher feerate transactions. Ancestor count is a crude
topological sort criteria, so replace this with linearization order so that the
highest feerate transactions (as would be observed by the mining algorithm) are
relayed before lower feerate ones, in a topologically valid way.
This also fixes a test that only worked due to the ancestor-count-based sort
order.
What changed, and why it matters
This commit changes the order in which Bitcoin nodes announce pending transactions to peers. Previously, transactions were announced based on how many ancestor transactions they had, then by fee rate. Now they are announced using the same 'cluster linearization' order the mining code uses, so higher-fee transactions are relayed first while still respecting dependency order. The change also updates a test that depended on the old ordering. There is no indication this fixes a security vulnerability; it is a behavior refinement.
No security action required. Treat as a normal protocol/behavior optimization. Reviewers may want to confirm that CompareMainOrder is deterministic and that the relay comparator remains transitive under all mempool states.
Security signals we found
No security-relevant signals in commit message or diff
Behavior change in P2P relay ordering only
No memory safety, cryptographic, consensus, or authorization changes
Evidence from the diff
Replaces CTxMemPool::CompareDepthAndScore with CompareMiningScoreWithTopology in net_processing’s transaction relay priority comparator. The old logic sorted by ancestor count, then by mempool score. The new logic delegates to m_txgraph->CompareMainOrder, which uses the cluster linearization total order (chunk feerate and topology). A functional test is adjusted because its assertions relied on the ancestor-count sort order to predict which descendants would be relayed under the descendant limit.
Changed components
src/net_processing.cppsrc/txmempool.cppsrc/txmempool.htest/functional/mempool_packages.pyInspect captured patch +21 / −29
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 37778322..f60ab27b 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -5425,8 +5425,8 @@ public:
bool operator()(std::set<Wtxid>::iterator a, std::set<Wtxid>::iterator b)
{
/* As std::make_heap produces a max-heap, we want the entries with the
- * fewest ancestors/highest fee to sort later. */
- return m_mempool->CompareDepthAndScore(*b, *a);
+ * higher mining score to sort later. */
+ return m_mempool->CompareMiningScoreWithTopology(*b, *a);
}
};
} // namespace
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index f2a63c26..fa7da083 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -803,24 +803,20 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
assert(innerUsage == cachedInnerUsage);
}
-bool CTxMemPool::CompareDepthAndScore(const Wtxid& hasha, const Wtxid& hashb) const
+bool CTxMemPool::CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const
{
- /* Return `true` if hasha should be considered sooner than hashb. Namely when:
- * a is not in the mempool, but b is
- * both are in the mempool and a has fewer ancestors than b
- * both are in the mempool and a has a higher score than b
+ /* Return `true` if hasha should be considered sooner than hashb, namely when:
+ * a is not in the mempool but b is, or
+ * both are in the mempool but a is sorted before b in the total mempool ordering
+ * (which takes dependencies and (chunk) feerates into account).
*/
LOCK(cs);
auto j{GetIter(hashb)};
if (!j.has_value()) return false;
auto i{GetIter(hasha)};
if (!i.has_value()) return true;
- uint64_t counta = i.value()->GetCountWithAncestors();
- uint64_t countb = j.value()->GetCountWithAncestors();
- if (counta == countb) {
- return CompareTxMemPoolEntryByScore()(*i.value(), *j.value());
- }
- return counta < countb;
+
+ return m_txgraph->CompareMainOrder(*i.value(), *j.value()) < 0;
}
namespace {
diff --git a/src/txmempool.h b/src/txmempool.h
index 5834cd00..232538ae 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -379,7 +379,7 @@ public:
void removeConflicts(const CTransaction& tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
- bool CompareDepthAndScore(const Wtxid& hasha, const Wtxid& hashb) const;
+ bool CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const;
bool isSpent(const COutPoint& outpoint) const;
unsigned int GetTransactionsUpdated() const;
void AddTransactionsUpdated(unsigned int n);
diff --git a/test/functional/mempool_packages.py b/test/functional/mempool_packages.py
index b5f994e8..8f53d913 100755
--- a/test/functional/mempool_packages.py
+++ b/test/functional/mempool_packages.py
@@ -245,21 +245,17 @@ class MempoolPackagesTest(BitcoinTestFramework):
mempool1 = self.nodes[1].getrawmempool(False)
assert set(mempool1).issubset(set(mempool0))
assert parent_transaction in mempool1
- # Note: this test is brittle, because it relies on the relay sort order
- # of node0 to be based on ancestor count (so that the first 10
- # descendants of parent_transaction relay before the later ones).
- for tx in chain[:CUSTOM_DESCENDANT_LIMIT-1]:
- assert tx in mempool1
- for tx in chain[CUSTOM_DESCENDANT_LIMIT:]:
- assert tx not in mempool1
- for tx in mempool1:
- entry0 = self.nodes[0].getmempoolentry(tx)
- entry1 = self.nodes[1].getmempoolentry(tx)
- assert not entry0['unbroadcast']
- assert not entry1['unbroadcast']
- assert_equal(entry1['fees']['base'], entry0['fees']['base'])
- assert_equal(entry1['vsize'], entry0['vsize'])
- assert_equal(entry1['depends'], entry0['depends'])
+ for tx in chain:
+ if tx in mempool1:
+ entry0 = self.nodes[0].getmempoolentry(tx)
+ entry1 = self.nodes[1].getmempoolentry(tx)
+ assert not entry0['unbroadcast']
+ assert not entry1['unbroadcast']
+ assert entry1["descendantcount"] <= CUSTOM_DESCENDANT_LIMIT
+ assert_equal(entry1['fees']['base'], entry0['fees']['base'])
+ assert_equal(entry1['vsize'], entry0['vsize'])
+ assert_equal(entry1['depends'], entry0['depends'])
+
# Test reorg handling
# First, the basics:
self.generate(self.nodes[0], 1)
Why this scored 19/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.