Rewrite removeForReorg to avoid using sets
What the developer wrote
Authored by Suhas Daftuar
Rewrite removeForReorg to avoid using sets
Also improve test coverage for removeForReorg by creating a scenario where
there are in-mempool descendants that are only invalidated due to an in-mempool
parent no longer spending a mature coin.
What changed, and why it matters
This Bitcoin Core commit rewrites the mempool cleanup logic that runs during blockchain reorganizations. It replaces an older set-based approach with a newer graph-based method for finding all transactions that must be removed because an ancestor became invalid. The change also adds a test for a tricky edge case where a transaction's child is only invalidated because its parent no longer spends a mature coinbase output. The commit itself does not describe a security bug, but the rewrite touches consensus-adjacent mempool code and improves test coverage for a previously untested scenario.
Treat as a routine refactor with defensive test hardening. Reviewers should verify that GetDescendantsUnion(Level::MAIN) returns exactly the same set as the old CalculateDescendants/RemoveStaged combination, and that lock-point assertions remain valid after the staged-removal path changes. No immediate security response is indicated by the supplied materials.
Security signals we found
Refactor of mempool eviction logic during reorgs
New graph-based descendant union used instead of set-based CalculateDescendants
Added functional test for descendants invalidated via parent's coinbase maturity loss
No explicit bug fix or CVE mentioned in commit message
Evidence from the diff
The patch modifies CTxMemPool::removeForReorg() in src/txmempool.cpp. Previously, the code built a setEntries of transactions failing finality/maturity checks, then called CalculateDescendants() to expand that set, and finally RemoveStaged() to evict them. The new code collects TxGraph::Ref pointers for the same initial transactions, invokes m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN), maps each returned Ref back to a mapTx iterator, and calls removeUnchecked(…, REORG). The functional test mempool_reorg.py is extended to create a deeper descendant chain and exercise reorg-induced removal of coinbase spends whose descendants are only invalidated through an in-mempool parent losing a mature-coinbase input.
Changed components
src/txmempool.cppCTxMemPool::removeForReorgTxGraph::GetDescendantsUniontest/functional/mempool_reorg.pyInspect captured patch +31 / −9
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index fec111fd..5fc1f3e8 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -352,15 +352,19 @@ void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check
AssertLockHeld(::cs_main);
Assume(!m_have_changeset);
- setEntries txToRemove;
- for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
- if (check_final_and_mature(it)) txToRemove.insert(it);
+ std::vector<const TxGraph::Ref*> to_remove;
+ for (txiter it = mapTx.begin(); it != mapTx.end(); it++) {
+ if (check_final_and_mature(it)) {
+ to_remove.emplace_back(&*it);
+ }
}
- setEntries setAllRemoves;
- for (txiter it : txToRemove) {
- CalculateDescendants(it, setAllRemoves);
+
+ auto all_to_remove = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN);
+
+ for (auto ref : all_to_remove) {
+ auto it = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref));
+ removeUnchecked(it, MemPoolRemovalReason::REORG);
}
- RemoveStaged(setAllRemoves, MemPoolRemovalReason::REORG);
for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
assert(TestLockPointValidity(chain, it->GetLockPoints()));
}
diff --git a/test/functional/mempool_reorg.py b/test/functional/mempool_reorg.py
index 818dd2ca..71f34b4a 100755
--- a/test/functional/mempool_reorg.py
+++ b/test/functional/mempool_reorg.py
@@ -146,7 +146,7 @@ class MempoolCoinbaseTest(BitcoinTestFramework):
assert_raises_rpc_error(-26, "non-final", self.nodes[0].sendrawtransaction, timelock_tx)
self.log.info("Broadcast and mine spend_2 and spend_3")
- wallet.sendrawtransaction(from_node=self.nodes[0], tx_hex=spend_2['hex'])
+ spend_2_id = wallet.sendrawtransaction(from_node=self.nodes[0], tx_hex=spend_2['hex'])
wallet.sendrawtransaction(from_node=self.nodes[0], tx_hex=spend_3['hex'])
self.log.info("Generate a block")
self.generate(self.nodes[0], 1)
@@ -154,7 +154,7 @@ class MempoolCoinbaseTest(BitcoinTestFramework):
assert_raises_rpc_error(-26, 'non-final', self.nodes[0].sendrawtransaction, timelock_tx)
self.log.info("Create spend_2_1 and spend_3_1")
- spend_2_1 = wallet.create_self_transfer(utxo_to_spend=spend_2["new_utxo"])
+ spend_2_1 = wallet.create_self_transfer(utxo_to_spend=spend_2["new_utxo"], version=1)
spend_3_1 = wallet.create_self_transfer(utxo_to_spend=spend_3["new_utxo"])
self.log.info("Broadcast and mine spend_3_1")
@@ -181,6 +181,24 @@ class MempoolCoinbaseTest(BitcoinTestFramework):
self.log.info("spend_3_1 has been re-orged out of the chain and is back in the mempool")
assert_equal(set(self.nodes[0].getrawmempool()), {spend_1_id, spend_2_1_id, spend_3_1_id})
+ self.log.info("Reorg out enough blocks to get spend_2 back in the mempool, along with its child")
+
+ while (spend_2_id not in self.nodes[0].getrawmempool()):
+ b = self.nodes[0].getbestblockhash()
+ for node in self.nodes:
+ node.invalidateblock(b)
+
+ assert(spend_2_id in self.nodes[0].getrawmempool())
+ assert(spend_2_1_id in self.nodes[0].getrawmempool())
+
+ # Chain 10 more transactions off of spend_2_1
+ self.log.info("Give spend_2 some more descendants by creating a chain of 10 transactions spending from it")
+ parent_utxo = spend_2_1["new_utxo"]
+ for i in range(10):
+ tx = wallet.create_self_transfer(utxo_to_spend=parent_utxo, version=1)
+ self.nodes[0].sendrawtransaction(tx['hex'])
+ parent_utxo = tx["new_utxo"]
+
self.log.info("Use invalidateblock to re-org back and make all those coinbase spends immature/invalid")
b = self.nodes[0].getblockhash(first_block + 100)
for node in self.nodes:
Why this scored 31/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.