Cluster mempool #33629

In "Add sigops adjusted weight calculator" f2eff17c6c4fc945f6fd761564212802107a1d7d

nit: use snake case.

In "Add new (unused) limits for cluster size/count" 2801e80528a3a1c2949a8fda6338882613a673e5

nit: be specific it is in virtual size

    argsman.AddArg("-limitclustersize=<n>", strprintf("Do not accept transactions whose size with all in-mempool connected transactions exceeds <n> virtual kilobytes (default: %u)", DEFAULT_CLUSTER_SIZE_LIMIT_KVB), ArgsManager::ALLOW_ANY | ArgsManager::DEBUG_ONLY, OptionsCategory::DEBUG_TEST);

It would be nice to expose these through the getmempoolinfo RPC.

diff --git a/src/rpc/mempool.cpp b/src/rpc/mempool.cpp
index 492693c9cef..1b62c74f0b3 100644
--- a/src/rpc/mempool.cpp
+++ b/src/rpc/mempool.cpp
@@ -812,6 +812,8 @@ UniValue MempoolInfoToJSON(const CTxMemPool& pool)
     ret.pushKV("fullrbf", true);
     ret.pushKV("permitbaremultisig", pool.m_opts.permit_bare_multisig);
     ret.pushKV("maxdatacarriersize", pool.m_opts.max_datacarrier_bytes.value_or(0));
+    ret.pushKV("limitclustercount", pool.m_opts.limits.cluster_count);
+    ret.pushKV("limitclustersize", pool.m_opts.limits.cluster_size_vbytes);
     return ret;
 }
 
@@ -836,6 +838,8 @@ static RPCHelpMan getmempoolinfo()
                 {RPCResult::Type::BOOL, "fullrbf", "True if the mempool accepts RBF without replaceability signaling inspection (DEPRECATED)"},
                 {RPCResult::Type::BOOL, "permitbaremultisig", "True if the mempool accepts transactions with bare multisig outputs"},
                 {RPCResult::Type::NUM, "maxdatacarriersize", "Maximum number of bytes that can be used by OP_RETURN outputs in the mempool"},
+                {RPCResult::Type::NUM, "limitclustercount", "Maximum number of transactions that can be in a cluster (configured by -limitclustercount)"},
+                {RPCResult::Type::NUM, "limitclustersize", "Maximum size of a cluster in virtual bytes (configured by -limitclustersize)"},
             }},
         RPCExamples{
             HelpExampleCli("getmempoolinfo", "")

Done, thanks.

Thanks -- I'm going to make it "virtual size with all in-mempool..." rather than "virtual kilobytes", which I think is more legible?

In "test: update feature_rbf.py replacement test" 429bdbecfde93c54374fb3098e357e18556e7e21

nit: This should live in functional/test_framework/mempool_util.py

Done.

In "Do not allow mempool clusters to exceed configured limits" 5a388c0d595b2318fea4b1dce977e2d5ff1abc48

If you define the max cluster count in mempool util it can be reused here.

Done.

In "Do not allow mempool clusters to exceed configured limits" 5a388c0d595b2318fea4b1dce977e2d5ff1abc48

I try to not use the magic number by trimming using

pool.DynamicMemoryUsage() - usage_of_5 - usage_of_7 but test fail because tx 6 is also evicted. However when I subtract only the usage of 5 the test succeed.

I grab the usages by computing the delta in memory usage after insertion of the tx.

This test is further updated in a later commit in this PR -- please let me know what you think of the state it ends up in and if it could use further improvements.

51430680ecb722e1d4ee4a26dac5724050f41c9e

The why of this is unclear to me through 8cdd7bb11adeaeb4709c670bef4b57362cfbebcb , worth reordering or expanding commit message?

Ok it's been a really long time since I've thought about this, but I believe the issue was that I needed epoch markers to be movable so that I could make CTxMemPoolEntry movable.

I don't exactly remember why CTxMemPoolEntry needs to be movable but I believe it has something to do with inheriting from TxGraph::Ref. I guess Ref's can't be copied, but they can be moved?

CTxMemPoolEntry seems to only need to be movable for mempool_entries.emplace_back(ConsumeTxMempoolEntry(...)) in test/fuzz/policy_estimator.cpp.

I'm a bit surprised Ref::operator=(Ref&&) isn't virtual -- moving a Ref that might actually a mempool entry seems dangerous; but otoh, moving by operator= only seems to be used in fuzz/txgraph.cpp, which means we don't actually move anything that's not just a Ref.

@ajtowns I don't think a virtual move assignment would actually help. It's true that there are risks when performing (move) assignments across types, but it doesn't seem like making it virtual affects those much.

With the code, as it exists in this PR, the risk is something like:

TxGraph::Ref ref = ...;
TxMempoolEntry entry = ...;
...
ref = std::move(entry);
// or
entry = std::move(ref);

The first of which will "excise" the ref from the entry, leaving the entry ref-less. The second will move a ref into place inside an entry. These are posssibly undesirable operations, but not necessarily dangerous (e.g., they won't result in an inconsistent state or UB on their own).

We could instead have a

virtual TxGraph::Ref& TxGraph::Ref::operator=(TxGraph::Ref&& other);

but this would only allow overriding as

TxGraph::Ref& TxMempoolEntry::operator=(TxGraph::Ref&& other);

which can't really do anything better than the excising effect offered by the current non-virtual move. Note that this would be independent from a

TxMempoolEntry& TxMempoolEntry::operator=(TxMempoolEntry&& other);

operator for moving between entries.

I don't think a virtual move assignment would actually help

Yeah. What about dropping it entirely? I think if the fuzz test is changed something like this:

--- a/src/test/fuzz/txgraph.cpp
+++ b/src/test/fuzz/txgraph.cpp
@@ -138,14 +138,14 @@ struct SimTxGraph
     }

     /** Add a new transaction to the simulation. */
-    TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
+    TxGraph::Ref* AddTransaction(TxGraph::Ref&& ref, const FeePerWeight& feerate)
     {
         assert(graph.TxCount() < MAX_TRANSACTIONS);
         auto simpos = graph.AddTransaction(feerate);
         real_is_optimal = false;
         MakeModified(simpos);
         assert(graph.Positions()[simpos]);
-        simmap[simpos] = std::make_shared<TxGraph::Ref>();
+        simmap[simpos] = std::make_shared<TxGraph::Ref>(std::move(ref));
         auto ptr = simmap[simpos].get();
         simrevmap[ptr] = simpos;
         // This may invalidate our cached oversized value.
@@ -459,9 +459,7 @@ FUZZ_TARGET(txgraph)
                 // Create a real TxGraph::Ref.
                 auto ref = real->AddTransaction(feerate);
                 // Create a shared_ptr place in the simulation to put the Ref in.
-                auto ref_loc = top_sim.AddTransaction(feerate);
-                // Move it in place.
-                *ref_loc = std::move(ref);
+                top_sim.AddTransaction(std::move(ref), feerate);
                 break;
             } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
                 // AddDependency.

then there's no need for an assignment operator (move or copy), just the move constructor?

Nice, that simplifies the interface, and it can always be added back if needed.

As it touches txgraph too, maybe best left for a follow-up?

EDIT: done in #33862

In "Check cluster limits when using -walletrejectlongchains" 1102ac7f74ac2f48760b46be58c7deb70fa727cf

nit: also state that it should be safe to create a new change set here because we lock mempool cs.

Seems redundant, given that we have an EXCLUSIVE_LOCKS_REQUIRED annotation on GetChangeSet() already? Will leave this as-is.

missed that, yeah, you are right.

6c73e4744837a7dc138a9177df3a48f30a1ba6c1

Had to double-check the claim on space usage, seems to hold

https://www.boost.org/doc/libs/1_73_0/libs/multi_index/doc/performance.html#:~:text=On%20the%20other%20hand%2C%20the,N%2D1)p%2C%20where

Actually, in fairness I think there might be some platforms where the space usage may be different -- I think I ran into that at some point in the history of this PR with one of our CI jobs, but I don't recall the details now. (Even still, I think saving the map lookup is likely worth it.)

5a388c0d595b2318fea4b1dce977e2d5ff1abc48

    // Check if the transactions would exceed the cluster size limit.

Fixed.

Wrote up some tests for cluster count and size limits in RBFs, package RBFs, package submission, at different configs of -limitclustercount and -limitclustersize, etc:

<details>

diff --git a/test/functional/mempool_cluster.py b/test/functional/mempool_cluster.py
index 3da8b477a2f..c75eb22bf9b 100755
--- a/test/functional/mempool_cluster.py
+++ b/test/functional/mempool_cluster.py
@@ -4,59 +4,322 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 """Test cluster mempool accessors and limits"""
 
+from decimal import Decimal
+
+from test_framework.mempool_util import (
+    DEFAULT_CLUSTER_LIMIT,
+    DEFAULT_CLUSTER_SIZE_LIMIT_KVB,
+)
+from test_framework.messages import (
+    COIN,
+)
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.wallet import (
     MiniWallet,
 )
 from test_framework.util import (
+    assert_equal,
+    assert_greater_than,
+    assert_greater_than_or_equal,
     assert_raises_rpc_error,
 )
 
-MAX_CLUSTER_COUNT = 64
+def cleanup(func):
+    def wrapper(self, *args, **kwargs):
+        try:
+            func(self, *args, **kwargs)
+        finally:
+            # Mine blocks to clear the mempool and replenish the wallet's confirmed UTXOs.
+            while (len(self.nodes[0].getrawmempool()) > 0):
+                self.generate(self.nodes[0], 1)
+            self.wallet.rescan_utxos(include_mempool=True)
+    return wrapper
 
 class MempoolClusterTest(BitcoinTestFramework):
     def set_test_params(self):
         self.num_nodes = 1
 
-    def run_test(self):
-        node = self.nodes[0]
-        self.wallet = MiniWallet(node)
-
-        node = self.nodes[0]
-        parent_tx = self.wallet.send_self_transfer(from_node=node)
+    def add_chain_cluster(self, node, cluster_count, target_vsize=None):
+        """Create a cluster of transactions, with the count specified.
+        The topology is a chain: the i'th transaction depends on the (i-1)'th transaction.
+        Optionally provide a target_vsize for each transaction.
+        """
+        parent_tx = self.wallet.send_self_transfer(from_node=node, confirmed_only=True, target_vsize=target_vsize)
         utxo_to_spend = parent_tx["new_utxo"]
-        ancestors = [parent_tx["txid"]]
-        while len(node.getrawmempool()) < MAX_CLUSTER_COUNT:
-            next_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=utxo_to_spend)
+        all_txids = [parent_tx["txid"]]
+        all_results = [parent_tx]
+
+        while len(all_results) < cluster_count:
+            next_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=utxo_to_spend, target_vsize=target_vsize)
+            assert next_tx["txid"] in node.getrawmempool()
+
             # Confirm that each transaction is in the same cluster as the first.
-            assert node.getmempoolcluster(next_tx['txid']) == node.getmempoolcluster(parent_tx['txid'])
+            assert_equal(node.getmempoolcluster(next_tx['txid']), node.getmempoolcluster(parent_tx['txid']))
 
             # Confirm that the ancestors are what we expect
             mempool_ancestors = node.getmempoolancestors(next_tx['txid'])
-            assert sorted(mempool_ancestors) == sorted(ancestors)
+            assert_equal(sorted(mempool_ancestors), sorted(all_txids))
 
             # Confirm that each successive transaction is added as a descendant.
-            assert all([ next_tx["txid"] in node.getmempooldescendants(x) for x in ancestors ])
+            assert all([ next_tx["txid"] in node.getmempooldescendants(x) for x in all_txids ])
 
             # Update for next iteration
-            ancestors.append(next_tx["txid"])
+            all_results.append(next_tx)
+            all_txids.append(next_tx["txid"])
             utxo_to_spend = next_tx["new_utxo"]
 
-        assert node.getmempoolcluster(parent_tx['txid'])['txcount'] == MAX_CLUSTER_COUNT
+        assert node.getmempoolcluster(parent_tx['txid'])['txcount'] == cluster_count
+        return all_results
+
+    def check_feerate_diagram(self, node):
+        """Sanity check the feerate diagram."""
         feeratediagram = node.getmempoolfeeratediagram()
         last_val = [0, 0]
         for x in feeratediagram:
+            # The vsize is always positive, except for the first iteration
             assert x['vsize'] > 0 or x['fee'] == 0
-            assert last_val[0]*x['fee'] >= last_val[1]*x['vsize']
+            # Monotonically decreasing fee per vsize
+            assert_greater_than_or_equal(last_val[0] * x['fee'], last_val[1] * x['vsize'])
             last_val = [x['vsize'], x['fee']]
 
+    def test_limit_enforcement(self, cluster_submitted, target_vsize_per_tx=None):
+        """
+        the cluster may change as a result of these transactions, so cluster_submitted is mutated accordingly
+        """
+        # Cluster has already been submitted and has at least 3 transactions, otherwise this test won't work.
+        assert_greater_than_or_equal(len(cluster_submitted), 3)
+        node = self.nodes[0]
+        last_result = cluster_submitted[-1]
+        # We assume that this is the maximum cluster count
+        cluster_limit = node.getmempoolcluster(cluster_submitted[-1]["txid"])['txcount']
+
         # Test that adding one more transaction to the cluster will fail.
-        bad_tx = self.wallet.create_self_transfer(utxo_to_spend=utxo_to_spend)
+        bad_tx = self.wallet.create_self_transfer(utxo_to_spend=last_result["new_utxo"], target_vsize=target_vsize_per_tx)
         assert_raises_rpc_error(-26, "too-large-cluster", node.sendrawtransaction, bad_tx["hex"])
 
-        # TODO: verify that the size limits are also enforced.
-        # TODO: add tests that exercise rbf, package submission, and package
-        # rbf and verify that cluster limits are enforced.
+        # It should also work during replacement
+        utxo_to_double_spend = self.wallet.get_utxo(confirmed_only=True)
+        fee = Decimal("0.000001")
+        tx_to_replace = self.wallet.create_self_transfer(utxo_to_spend=utxo_to_double_spend, fee=fee)
+        node.sendrawtransaction(tx_to_replace["hex"])
+
+        # Multiply fee by 5, which should easily cover the cost to replace. Otherwise, use the target vsize at 10sat/vB
+        fee_to_use = target_vsize_per_tx * 10 if target_vsize_per_tx is not None else int(fee * COIN * 5)
+        bad_tx_also_replacement = self.wallet.create_self_transfer_multi(
+            utxos_to_spend=[last_result["new_utxo"], utxo_to_double_spend],
+            target_vsize=target_vsize_per_tx,
+            fee_per_output=fee_to_use,
+        )
+        assert_raises_rpc_error(-26, "replacement-failed", node.sendrawtransaction, bad_tx_also_replacement["hex"])
+
+        # Replace the last transaction. We are extending the cluster by one, but also removing one: 64 + 1 - 1 = 64
+        # In the case of vsize, it should similarly cancel out.
+        second_to_last_utxo = cluster_submitted[-2]["new_utxo"]
+        fee_to_beat = cluster_submitted[-1]["fee"]
+        vsize_to_use = cluster_submitted[-1]["tx"].get_vsize() if target_vsize_per_tx is not None else None
+        good_tx_replacement = self.wallet.create_self_transfer(utxo_to_spend=second_to_last_utxo, fee=fee_to_beat * 5, target_vsize=vsize_to_use)
+        node.sendrawtransaction(good_tx_replacement["hex"], maxfeerate=0)
+
+        cluster_submitted[-1] = good_tx_replacement
+
+    def test_limit_enforcement_package(self, cluster_submitted):
+        node = self.nodes[0]
+        # Create a package from the second to last transaction. This shouldn't work because the effect is 64 + 2 - 1 = 65
+        last_utxo = cluster_submitted[-2]["new_utxo"]
+        fee_to_beat = cluster_submitted[-1]["fee"]
+        # We do not use package RBF here because it has additional restrictions on mempool ancestors.
+        parent_tx_bad = self.wallet.create_self_transfer(utxo_to_spend=last_utxo, fee=fee_to_beat * 5)
+        child_tx_bad = self.wallet.create_self_transfer(utxo_to_spend=parent_tx_bad["new_utxo"])
+        package_result = node.submitpackage([parent_tx_bad["hex"], child_tx_bad["hex"]], maxfeerate=0)
+        # The parent should be submitted, but the child rejected.
+        result_parent_only = node.submitpackage([parent_tx_bad["hex"], child_tx_bad["hex"]])
+
+        assert parent_tx_bad["txid"] in node.getrawmempool()
+        assert child_tx_bad["txid"] not in node.getrawmempool()
+        assert_equal(result_parent_only["package_msg"], "transaction failed")
+        assert_equal(result_parent_only["tx-results"][child_tx_bad["wtxid"]]["error"], "too-large-cluster")
+
+        # Now, create a package from the second to last transaction. This should work because the effect is 64 + 2 - 2 = 64
+        third_to_last_utxo = cluster_submitted[-3]["new_utxo"]
+        parent_tx_good = self.wallet.create_self_transfer(utxo_to_spend=third_to_last_utxo)
+        child_tx_good = self.wallet.create_self_transfer(utxo_to_spend=parent_tx_good["new_utxo"], fee=fee_to_beat * 5)
+        result_both_good = node.submitpackage([parent_tx_good["hex"], child_tx_good["hex"]], maxfeerate=0)
+        assert_equal(result_both_good["package_msg"], "success")
+        assert parent_tx_good["txid"] in node.getrawmempool()
+        assert child_tx_good["txid"] in node.getrawmempool()
+
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_cluster_count_limit(self, max_cluster_count):
+        node = self.nodes[0]
+        cluster_submitted = self.add_chain_cluster(node, max_cluster_count)
+        self.check_feerate_diagram(node)
+        for result in cluster_submitted:
+            assert_equal(node.getmempoolcluster(result["txid"])['txcount'], max_cluster_count)
+
+        self.log.info("Test that cluster count limit is enforced")
+        self.test_limit_enforcement(cluster_submitted)
+        self.log.info("Test that the resulting cluster count is correctly calculated in a package")
+        self.test_limit_enforcement_package(cluster_submitted)
+
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_cluster_size_limit(self, max_cluster_size_vbytes):
+        node = self.nodes[0]
+        # This number should be smaller than the cluster count limit.
+        num_txns = 10
+        # Leave some buffer so it is possible to add a reasonably-sized transaction.
+        target_vsize_per_tx = int((max_cluster_size_vbytes - 500) / num_txns)
+        cluster_submitted = self.add_chain_cluster(node, num_txns, target_vsize_per_tx)
+
+        vsize_remaining = max_cluster_size_vbytes - node.getmempoolcluster(cluster_submitted[0]["txid"])['vsize']
+        self.log.info("Test that cluster size limit is enforced")
+        self.test_limit_enforcement(cluster_submitted, target_vsize_per_tx=vsize_remaining + 4)
+
+        # Try another cluster and add a small transaction: it should succeed
+        last_result = cluster_submitted[-1]
+        small_tx = self.wallet.create_self_transfer(utxo_to_spend=last_result["new_utxo"], target_vsize=vsize_remaining)
+        node.sendrawtransaction(small_tx["hex"])
+
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_cluster_merging(self, max_cluster_count):
+        node = self.nodes[0]
+
+        self.log.info(f"Test merging 2 clusters with transaction counts totaling {max_cluster_count}")
+        for num_txns_cluster1 in [1, 5, 10]:
+            # Create a chain of transactions
+            cluster1 = self.add_chain_cluster(node, num_txns_cluster1)
+            for result in cluster1:
+                node.sendrawtransaction(result["hex"])
+            utxo_from_cluster1 = cluster1[-1]["new_utxo"]
+
+            # Make the next cluster, which contains the remaining transactions
+            assert_greater_than(max_cluster_count, num_txns_cluster1)
+            num_txns_cluster2 = max_cluster_count - num_txns_cluster1
+            cluster2 = self.add_chain_cluster(node, num_txns_cluster2)
+            for result in cluster2:
+                node.sendrawtransaction(result["hex"])
+            utxo_from_cluster2 = cluster2[-1]["new_utxo"]
+
+            # Now create a transaction that spends from both clusters, which would merge them.
+            tx_merger = self.wallet.create_self_transfer_multi(utxos_to_spend=[utxo_from_cluster1, utxo_from_cluster2])
+            assert_raises_rpc_error(-26, "too-large-cluster", node.sendrawtransaction, tx_merger["hex"])
+
+            # Spending from the clusters independently should work
+            tx_spending_cluster1 = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=utxo_from_cluster1)
+            tx_spending_cluster2 = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=utxo_from_cluster2)
+            assert tx_spending_cluster1["txid"] in node.getrawmempool()
+            assert tx_spending_cluster2["txid"] in node.getrawmempool()
+
+        self.log.info(f"Test merging {max_cluster_count} clusters with 1 transaction spending from all of them")
+        utxos_to_merge = []
+        for _ in range(max_cluster_count):
+            # Use a confirmed utxo to ensure distinct clusters
+            confirmed_utxo = self.wallet.get_utxo(confirmed_only=True)
+            singleton = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=confirmed_utxo)
+            assert singleton["txid"] in node.getrawmempool()
+            utxos_to_merge.append(singleton["new_utxo"])
+
+        assert_equal(len(utxos_to_merge), max_cluster_count)
+        tx_merger = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_to_merge)
+        assert_raises_rpc_error(-26, "too-large-cluster", node.sendrawtransaction, tx_merger["hex"])
+
+        # Spending from 1 fewer cluster should work
+        tx_merger_all_but_one = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_to_merge[:-1])
+        node.sendrawtransaction(tx_merger_all_but_one["hex"])
+        assert tx_merger_all_but_one["txid"] in node.getrawmempool()
+
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_cluster_merging_size(self, max_cluster_size_vbytes):
+        node = self.nodes[0]
+
+        self.log.info(f"Test merging clusters with sizes totaling {max_cluster_size_vbytes} vB")
+        num_txns = 10
+        # Leave some buffer so it is possible to add a reasonably-sized transaction.
+        target_vsize_per_tx = int((max_cluster_size_vbytes - 500) / num_txns)
+        utxos_to_merge = []
+        vsize_remaining = max_cluster_size_vbytes
+        for _ in range(num_txns):
+            confirmed_utxo = self.wallet.get_utxo(confirmed_only=True)
+            singleton = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=confirmed_utxo)
+            assert singleton["txid"] in node.getrawmempool()
+            utxos_to_merge.append(singleton["new_utxo"])
+            vsize_remaining -= singleton["tx"].get_vsize()
+
+        assert_greater_than_or_equal(vsize_remaining, 500)
+
+        # Create a transaction spending from all clusters that exceeds the cluster size limit.
+        tx_merger_too_big = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_to_merge, target_vsize=vsize_remaining + 4, fee_per_output=10000)
+        assert_raises_rpc_error(-26, "too-large-cluster", node.sendrawtransaction, tx_merger_too_big["hex"])
+
+        # A transaction that is slightly smaller should work.
+        tx_merger_small = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_to_merge[:-1], target_vsize=vsize_remaining - 4, fee_per_output=10000)
+        node.sendrawtransaction(tx_merger_small["hex"])
+        assert tx_merger_small["txid"] in node.getrawmempool()
+
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_cluster_limit_rbf(self, max_cluster_count):
+        node = self.nodes[0]
+
+        # Use min feerate for the to-be-replaced transactions. There are many, so replacement cost can be expensive.
+        min_feerate = node.getmempoolinfo()["mempoolminfee"]
+
+        self.log.info("Test that cluster size calculation takes RBF into account")
+        utxos_created_by_parents = []
+        fees_rbf_sats = 0
+        for _ in range(max_cluster_count - 1):
+            parent_tx = self.wallet.send_self_transfer(from_node=node, confirmed_only=True)
+            utxo_to_replace = parent_tx["new_utxo"]
+            child_tx = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=utxo_to_replace, fee_rate=min_feerate)
+
+            fees_rbf_sats += int(child_tx["fee"] * COIN)
+            utxos_created_by_parents.append(utxo_to_replace)
+
+        # This transaction would create a cluster of size max_cluster_count
+        # Importantly, the node should account for the fact that half of the transactions will be replaced.
+        tx_merger_replacer = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_created_by_parents, fee_per_output=fees_rbf_sats * 2)
+        node.sendrawtransaction(tx_merger_replacer["hex"])
+        assert tx_merger_replacer["txid"] in node.getrawmempool()
+        assert_equal(node.getmempoolcluster(tx_merger_replacer["txid"])['txcount'], max_cluster_count)
+
+        self.log.info("Test that cluster size calculation takes package RBF into account")
+        utxos_to_replace = []
+        fee_rbf_decimal = 0
+        for _ in range(max_cluster_count):
+            confirmed_utxo = self.wallet.get_utxo(confirmed_only=True)
+            tx_to_replace = self.wallet.send_self_transfer(from_node=node, utxo_to_spend=confirmed_utxo, fee_rate=min_feerate)
+            fee_rbf_decimal += tx_to_replace["fee"]
+            utxos_to_replace.append(confirmed_utxo)
+
+        tx_replacer = self.wallet.create_self_transfer_multi(utxos_to_spend=utxos_to_replace)
+        tx_replacer_sponsor = self.wallet.create_self_transfer(utxo_to_spend=tx_replacer["new_utxos"][0], fee=fee_rbf_decimal * 2)
+        node.submitpackage([tx_replacer["hex"], tx_replacer_sponsor["hex"]], maxfeerate=0)
+        assert tx_replacer["txid"] in node.getrawmempool()
+        assert tx_replacer_sponsor["txid"] in node.getrawmempool()
+        assert_equal(node.getmempoolcluster(tx_replacer["txid"])['txcount'], 2)
+
+
+    def run_test(self):
+        node = self.nodes[0]
+        self.wallet = MiniWallet(node)
+        self.generate(self.wallet, 400)
+
+        self.test_cluster_limit_rbf(DEFAULT_CLUSTER_LIMIT)
+
+        for cluster_size_limit_kvb in [10, 20, 33, 100, DEFAULT_CLUSTER_SIZE_LIMIT_KVB]:
+            self.log.info(f"-> Resetting node with -limitclustersize={cluster_size_limit_kvb}")
+            self.restart_node(0, extra_args=[f"-limitclustersize={cluster_size_limit_kvb}"])
+
+            cluster_size_limit = cluster_size_limit_kvb * 1000
+            self.test_cluster_size_limit(cluster_size_limit)
+            self.test_cluster_merging_size(cluster_size_limit)
+
+        for cluster_count_limit in [4, 10, 16, 32, DEFAULT_CLUSTER_LIMIT]:
+            self.log.info(f"-> Resetting node with -limitclustercount={cluster_count_limit}")
+            self.restart_node(0, extra_args=[f"-limitclustercount={cluster_count_limit}"])
+
+            self.test_cluster_count_limit(cluster_count_limit)
+            if cluster_count_limit > 10:
+                self.test_cluster_merging(cluster_count_limit)
+
 
 if __name__ == '__main__':
     MempoolClusterTest(__file__).main()
diff --git a/test/functional/test_framework/mempool_util.py b/test/functional/test_framework/mempool_util.py
index 3c4609c0b44..89e2558307e 100644
--- a/test/functional/test_framework/mempool_util.py
+++ b/test/functional/test_framework/mempool_util.py
@@ -33,6 +33,8 @@ from .wallet import (
 DEFAULT_MIN_RELAY_TX_FEE = 100
 # Default for -incrementalrelayfee in sat/kvB
 DEFAULT_INCREMENTAL_RELAY_FEE = 100
+DEFAULT_CLUSTER_LIMIT = 64
+DEFAULT_CLUSTER_SIZE_LIMIT_KVB = 101
 
 TRUC_MAX_VSIZE = 10000
 TRUC_CHILD_MAX_VSIZE = 1000

</details>

Looks good, will include -- thank you for the test coverage!

I did make a few changes (the linter alerted on a few lines) so please take a look again at what is here.

My bad on the linter, lgtm!

ae1ac5410383e57ed16867580a5fd355a46953de

Seems more self-contained to start/stop the builder inside addChunks

I think the reason I didn't is probably because addChunks() has multiple places where it returns, so it seemed a little messy to have to invoke StopBlockBuilding() within that function. But if you think it's worth it, I can rework the function and push the calls down into it.

sounds reasonable, leave as is

ae1ac5410383e57ed16867580a5fd355a46953de

if we're essentially only using this, why not inline chunk_feerate instead?

In this commit, chunk_feerate.fee is used further down, but this gets cleaned up further in #33591 with the introduction of CFeeRate::GetFeePerVSize, at which point this could be inlined. I'll make that change in #33591.

Oh, actually we need the weight further down for the check to see if the chunk will fit in the block, so I'm inclined to leave this as-is?

oops you're right

ae1ac5410383e57ed16867580a5fd355a46953de

Was getting confused with the two vectors, are they even needed?

diff --git a/src/node/miner.cpp b/src/node/miner.cpp
index 52103bda82..1bfe771444 100644
--- a/src/node/miner.cpp
+++ b/src/node/miner.cpp
@@ -206,8 +206,8 @@ bool BlockAssembler::TestPackage(FeePerWeight package_feerate, int64_t packageSi
 // Perform transaction-level checks before adding to block:
 // - transaction finality (locktime)
-bool BlockAssembler::TestPackageTransactions(const std::vector<const CTxMemPoolEntry *>& txs) const
+bool BlockAssembler::TestPackageTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const
 {
-    for (auto tx : txs) {
-        if (!IsFinalTx(tx->GetTx(), nHeight, m_lock_time_cutoff)) {
+    for (const auto tx : txs) {
+        if (!IsFinalTx(tx.get().GetTx(), nHeight, m_lock_time_cutoff)) {
             return false;
         }
@@ -243,13 +243,11 @@ void BlockAssembler::addChunks()
 
     std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> selected_transactions;
+    selected_transactions.reserve(MAX_CLUSTER_COUNT_LIMIT);
     FeePerWeight chunk_feerate;
 
+    // This fills selected_transactions
     chunk_feerate = m_mempool->GetBlockBuilderChunk(selected_transactions);
     FeePerVSize chunk_feerate_vsize = ToFeePerVSize(chunk_feerate);
 
-    std::vector<const CTxMemPoolEntry*> chunk_txs;
-    // We'll add at most one chunk per iteration below, and chunk count is bounded by
-    // the cluster size limit.
-    chunk_txs.reserve(MAX_CLUSTER_COUNT_LIMIT);
     while (selected_transactions.size() > 0) {
         // Check to see if min fee rate is still respected.
@@ -260,12 +258,10 @@ void BlockAssembler::addChunks()
 
         int64_t package_sig_ops = 0;
-        chunk_txs.clear();
         for (const auto& tx : selected_transactions) {
-            chunk_txs.emplace_back(&tx.get());
             package_sig_ops += tx.get().GetSigOpCost();
         }
 
         // Check to see if this chunk will fit.
-        if (!TestPackage(chunk_feerate, package_sig_ops) || !TestPackageTransactions(chunk_txs)) {
+        if (!TestPackage(chunk_feerate, package_sig_ops) || !TestPackageTransactions(selected_transactions)) {
             m_mempool->SkipBuilderChunk();
             // This chunk won't fit, so we let it be removed from the heap and
@@ -283,6 +279,6 @@ void BlockAssembler::addChunks()
             // This chunk will fit, so add it to the block.
             nConsecutiveFailed = 0;
-            for (const auto& tx : chunk_txs) {
-                AddToBlock(*tx);
+            for (const auto& tx : selected_transactions) {
+                AddToBlock(tx);
             }
             pblocktemplate->m_package_feerates.emplace_back(chunk_feerate_vsize);
diff --git a/src/node/miner.h b/src/node/miner.h
index 58fedcc1af..a42e2e2cb4 100644
--- a/src/node/miner.h
+++ b/src/node/miner.h
@@ -117,5 +117,5 @@ private:
       * These checks should always succeed, and they're here
       * only as an extra check in case of suboptimal node configuration */
-    bool TestPackageTransactions(const std::vector<const CTxMemPoolEntry *>& txs) const;
+    bool TestPackageTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const;
 };

Good point! Taking your change.

Incorporated in a8be743aeb42ec8ab613f822989a11a2f2ce70ac

ae1ac5410383e57ed16867580a5fd355a46953de

nit: I think renaming TestPackage to TestPackageBlockLimits or something might help readability going forward

Done in #33591 (d7109669b54d299e84dfe90d2ebf591ff673f51c)

2aad9f01e514b77538eb780138a8e52484eaf5a8

is this right? If so this warrants a test (note to self and others)

        // If we can't calculate a feerate, it's because the cluster size limits were hit, and we may want to try package RBF.

Will take this doc change in #33591.

Done in 6881d21c57ce122f0c2f5900e6caab7ba806d279.

2aad9f01e514b77538eb780138a8e52484eaf5a8

nit: belt and suspenders

        Assume(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
        return m_txgraph->CountDistinctClusters(entries, TxGraph::Level::MAIN);

Done.

2aad9f01e514b77538eb780138a8e52484eaf5a8

Didn't carefully look at this test case, but we should make sure we are testing the case of package RBF conflicting against clusters of up to count 64

Looks like the test is still only conflicting with size 2

just extended it to clusters of size three and made log more sensible

diff --git a/test/functional/mempool_package_rbf.py b/test/functional/mempool_package_rbf.py
index 759e3cb07d..c54534f6f8 100755
--- a/test/functional/mempool_package_rbf.py
+++ b/test/functional/mempool_package_rbf.py
@@ -94,5 +94,5 @@ class PackageRBFTest(BitcoinTestFramework):
 
     def test_package_rbf_basic(self):
-        self.log.info("Test that a child can pay to replace its parents' conflicts of cluster size 2")
+        self.log.info("Test that a child can pay to replace its parents' conflicts")
         node = self.nodes[0]
         # Reuse the same coins so that the transactions conflict with one another.
@@ -196,10 +196,10 @@ class PackageRBFTest(BitcoinTestFramework):
         del self.coins[:num_coins]
 
-        # Original transactions: 101 transactions with 1 descendants each -> 202 total transactions, 101 clusters
-        size_two_clusters = []
+        # Original transactions: 101 transactions with 2 descendants each -> 303 total transactions, 101 clusters
+        size_three_clusters = []
         for coin in parent_coins:
-            size_two_clusters.append(self.wallet.send_self_transfer_chain(from_node=node, chain_length=2, utxo_to_spend=coin))
-        expected_txns = [txn["tx"] for parent_child_txns in size_two_clusters for txn in parent_child_txns]
-        assert_equal(len(expected_txns), num_coins * 2)
+            size_three_clusters.append(self.wallet.send_self_transfer_chain(from_node=node, chain_length=3, utxo_to_spend=coin))
+        expected_txns = [txn["tx"] for parent_child_txns in size_three_clusters for txn in parent_child_txns]
+        assert_equal(len(expected_txns), num_coins * 3)
         self.assert_mempool_contents(expected=expected_txns)
 
@@ -241,5 +241,5 @@ class PackageRBFTest(BitcoinTestFramework):
         pkg_results = node.submitpackage([package_parent["hex"], package_child["hex"]], maxfeerate=0)
         assert_equal(pkg_results["package_msg"], "success")
-        self.assert_mempool_contents(expected=[singleton_tx["tx"], size_two_clusters[-1][0]["tx"], size_two_clusters[-1][1]["tx"], package_parent["tx"], package_child["tx"]] )
+        self.assert_mempool_contents(expected=[singleton_tx["tx"], size_three_clusters[-1][0]["tx"], size_three_clusters[-1][1]["tx"], size_three_clusters[-1][2]["tx"], package_parent["tx"], package_child["tx"]] )
 
         self.generate(node, 1)

Done in c00612c15592faa094d60c7bba8eb9966f5910d6

In "Select transactions for blocks based on chunk feerate" a8be743aeb42ec8ab613f822989a11a2f2ce70ac

nit: change to helper functions for addChunks since addPackageTxs is now gone.

    // helper functions for addChunks()

Done.

In "Select transactions for blocks based on chunk feerate" a8be743aeb42ec8ab613f822989a11a2f2ce70ac

nit: It will be better for us replace package with chunk here and other places in the miner?

diff --git a/src/node/miner.cpp b/src/node/miner.cpp
index 1bfe7714440..e80d55c1f31 100644
--- a/src/node/miner.cpp
+++ b/src/node/miner.cpp
@@ -192,12 +192,12 @@ std::unique_ptr<CBlockTemplate> BlockAssembler::CreateNewBlock()
     return std::move(pblocktemplate);
 }
 
-bool BlockAssembler::TestPackage(FeePerWeight package_feerate, int64_t packageSigOpsCost) const
+bool BlockAssembler::TestChunk(FeePerWeight chunk_feerate, int64_t chunk_sigops_cost) const
 {
-    if (nBlockWeight + package_feerate.size >= m_options.nBlockMaxWeight) {
+    if (nBlockWeight + chunk_feerate.size >= m_options.nBlockMaxWeight) {
         return false;
     }
-    if (nBlockSigOpsCost + packageSigOpsCost >= MAX_BLOCK_SIGOPS_COST) {
+    if (nBlockSigOpsCost + chunk_sigops_cost >= MAX_BLOCK_SIGOPS_COST) {
         return false;
     }
     return true;
@@ -205,7 +205,7 @@ bool BlockAssembler::TestPackage(FeePerWeight package_feerate, int64_t packageSi
 
 // Perform transaction-level checks before adding to block:
 // - transaction finality (locktime)
-bool BlockAssembler::TestPackageTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const
+bool BlockAssembler::TestChunkTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const
 {
     for (const auto tx : txs) {
         if (!IsFinalTx(tx.get().GetTx(), nHeight, m_lock_time_cutoff)) {
@@ -256,13 +256,13 @@ void BlockAssembler::addChunks()
             return;
         }
 
-        int64_t package_sig_ops = 0;
+        int64_t chunk_sig_ops = 0;
         for (const auto& tx : selected_transactions) {
-            package_sig_ops += tx.get().GetSigOpCost();
+            chunk_sig_ops += tx.get().GetSigOpCost();
         }
 
         // Check to see if this chunk will fit.
-        if (!TestPackage(chunk_feerate, package_sig_ops) || !TestPackageTransactions(selected_transactions)) {
+        if (!TestChunk(chunk_feerate, chunk_sig_ops) || !TestChunkTransactions(selected_transactions)) {
             m_mempool->SkipBuilderChunk();
             // This chunk won't fit, so we let it be removed from the heap and
             // we'll try the next best.
@@ -281,7 +281,7 @@ void BlockAssembler::addChunks()
             for (const auto& tx : selected_transactions) {
                 AddToBlock(tx);
             }
-            pblocktemplate->m_package_feerates.emplace_back(chunk_feerate_vsize);
+            pblocktemplate->m_chunk_feerates.emplace_back(chunk_feerate_vsize);
         }
 
         selected_transactions.clear();
diff --git a/src/node/miner.h b/src/node/miner.h
index a42e2e2cb48..5fee028d9cd 100644
--- a/src/node/miner.h
+++ b/src/node/miner.h
@@ -47,9 +47,9 @@ struct CBlockTemplate
     // Sigops per transaction, not including coinbase transaction (unlike CBlock::vtx).
     std::vector<int64_t> vTxSigOpsCost;
     std::vector<unsigned char> vchCoinbaseCommitment;
-    /* A vector of package fee rates, ordered by the sequence in which
-     * packages are selected for inclusion in the block template.*/
-    std::vector<FeePerVSize> m_package_feerates;
+    /* A vector of chunk fee rates, ordered by the sequence in which
+     * chunks are selected for inclusion in the block template.*/
+    std::vector<FeePerVSize> m_chunk_feerates;
 };
 
 /** Generate a new block, without valid proof-of-work */
@@ -109,14 +109,14 @@ private:
     */
     void addChunks() EXCLUSIVE_LOCKS_REQUIRED(m_mempool->cs);
 
-    // helper functions for addPackageTxs()
-    /** Test if a new package would "fit" in the block */
-    bool TestPackage(FeePerWeight package_feerate, int64_t packageSigOpsCost) const;
-    /** Perform checks on each transaction in a package:
+    // helper functions for addChunkTxs()
+    /** Test if a new chunk would "fit" in the block */
+    bool TestChunk(FeePerWeight chunk_feerate, int64_t chunk_sigops_cost) const;
+    /** Perform checks on each transaction in a chunk:
       * locktime, premature-witness, serialized size (if necessary)
       * These checks should always succeed, and they're here
       * only as an extra check in case of suboptimal node configuration */
-    bool TestPackageTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const;
+    bool TestChunkTransactions(const std::vector<CTxMemPoolEntryRef>& txs) const;
 };
 
 /**

I took this change in #33591.

In "Select transactions for blocks based on chunk feerate" a8be743aeb42ec8ab613f822989a11a2f2ce70ac

nit: maybe reserve again after clear here?

clear() doesn't change the capacity of the vector, so there's no need to reserve() again.

In "test: rewrite PopulateMempool to not violate mempool policy (cluster size) limits" afb9003bc602a77ed15bf4e79277d960937a5c28

nitty-nit: instead of undo, spent outputs might be better?

I think "spent" would be confusing, as the purpose of this object is to store the data needed to undo the removal of a utxo from the unspent_prevouts list, in the event that a transaction spending the prevout fails to get into the mempool.

729cec4f6ddb880210b7e0011fff8b0a5f88c933

micro-nit: readability of format prior to this commit was better, can it remain a multiline ctor for MiniMinerMempoolEntry with annotations?

I think it will even be better to have a struct for this to avoid the repetition of the declaration of the variables and passing the as out params, according to guidelines we prefer returning values https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#coding-style-c-functions-and-methods

After cluster mempool, mini_miner should be modified anyway (and I think this whole MiniMinerMempoolEntry object will disappear, see for example my draft here). So I don't think it's worth re-implementing a new interface in this PR.

In "policy: Remove CPFP carveout rule" 31a045700ee13a6746c4f4de253e64a0b8a61334

In doc/policy/mempool-limits.md, Exemptions section CPFP carveout is now stale and should also be deleted

I think the whole file can be deleted, as ancestor/descendant limits are now also obsolete.

I think we can write a new doc for cluster limits in a followup? And a release note (/me ducks)

Agreed -- I was thinking I'd tackle this in #33591, if that seems reasonable?

In "Implement new RBF logic for cluster mempool" e6315c24326016cfaee5bd046e8b2e4e1088ac6b

Delete the bip125 rule numbers references.

This is a reference to Rule #5 in doc/policy/mempool-replacements.md.

In "Implement new RBF logic for cluster mempool" e6315c24326016cfaee5bd046e8b2e4e1088ac6b

nit: replace transactions with clusters here and other places

        """Replacements that evict too many clusters are rejected"""

Fixed this in a couple of places, should be good now I think.

In "Implement new RBF logic for cluster mempool" e6315c24326016cfaee5bd046e8b2e4e1088ac6b

10872f7ec923803f711cd2c3af93a0e17121330e

You're still looking up ancestors in TRUC prior to knowing how large the resulting graph would be, but you're only doing it once against a single in-mempool parent, so it should be bounded to 64 results total.

Maybe leave a comment to that effect or stick that in the commit message?

Updated the commit message.

This started failing when I added it to other tests, then I realized it's the wrong direction

            assert_greater_than_or_equal(last_val[1] * x['vsize'], last_val[0] * x['fee'])

I ended up writing some feerate diagram tests to check my understanding of how it works. It might be helpful for reviewers and/or if you're interested in taking them:

<details>

diff --git a/test/functional/mempool_cluster.py b/test/functional/mempool_cluster.py
index ee8005a1cd2..c86e6a1b5c0 100755
--- a/test/functional/mempool_cluster.py
+++ b/test/functional/mempool_cluster.py
@@ -7,6 +7,8 @@
 from decimal import Decimal
 
 from test_framework.mempool_util import (
+    assert_equal_feerate_diagram,
+    check_feerate_diagram_monotonically_decreasing,
     DEFAULT_CLUSTER_LIMIT,
     DEFAULT_CLUSTER_SIZE_LIMIT_KVB,
 )
@@ -71,17 +73,6 @@ class MempoolClusterTest(BitcoinTestFramework):
         assert node.getmempoolcluster(parent_tx['txid'])['txcount'] == cluster_count
         return all_results
 
-    def check_feerate_diagram(self, node):
-        """Sanity check the feerate diagram."""
-        feeratediagram = node.getmempoolfeeratediagram()
-        last_val = [0, 0]
-        for x in feeratediagram:
-            # The vsize is always positive, except for the first iteration
-            assert x['vsize'] > 0 or x['fee'] == 0
-            # Monotonically decreasing fee per vsize
-            assert_greater_than_or_equal(last_val[0] * x['fee'], last_val[1] * x['vsize'])
-            last_val = [x['vsize'], x['fee']]
-
     def test_limit_enforcement(self, cluster_submitted, target_vsize_per_tx=None):
         """
         the cluster may change as a result of these transactions, so cluster_submitted is mutated accordingly
@@ -149,7 +140,7 @@ class MempoolClusterTest(BitcoinTestFramework):
     def test_cluster_count_limit(self, max_cluster_count):
         node = self.nodes[0]
         cluster_submitted = self.add_chain_cluster(node, max_cluster_count)
-        self.check_feerate_diagram(node)
+        check_feerate_diagram_monotonically_decreasing(node.getmempoolfeeratediagram())
         for result in cluster_submitted:
             assert_equal(node.getmempoolcluster(result["txid"])['txcount'], max_cluster_count)
 
@@ -292,6 +283,151 @@ class MempoolClusterTest(BitcoinTestFramework):
         assert tx_replacer_sponsor["txid"] in node.getrawmempool()
         assert_equal(node.getmempoolcluster(tx_replacer["txid"])['txcount'], 2)
 
+ [@cleanup](/bitcoin-bitcoin/contributor/cleanup/)
+    def test_feerate_diagram(self):
+        node = self.nodes[0]
+        self.log.info("Test that the feerate diagram shows chunks correctly")
+
+        # 1 sat/vB as Decimal BTC/kvB
+        feerate_1000sat_kvb = Decimal(1000) / COIN
+
+        def sats_to_btc(sats):
+            """Convert int sats to Decimal BTC with 8 decimal places"""
+            return Decimal(sats) / Decimal(1e8)
+
+        # txA (0sat / 500vB) <- txB (1000sat / 500vB)
+        # Use v3 to allow 0 fee
+        txA = self.wallet.create_self_transfer(confirmed_only=True, fee=0, fee_rate=0, version=3, target_vsize=500)
+        txB = self.wallet.create_self_transfer(utxo_to_spend=txA["new_utxo"], fee=sats_to_btc(1000), version=3, target_vsize=500)
+        result_ab = node.submitpackage([txA["hex"], txB["hex"]])
+        assert_equal(result_ab["package_msg"], "success")
+
+        # one cluster, one chunk with feerate 1sat/vB
+        assert_equal(result_ab["tx-results"][txA["wtxid"]]["fees"]["effective-feerate"], feerate_1000sat_kvb)
+        assert_equal(result_ab["tx-results"][txB["wtxid"]]["fees"]["effective-feerate"], feerate_1000sat_kvb)
+        assert_equal(node.getmempoolcluster(txA["txid"])['txcount'], 2)
+        expected_feerate_diagram_ab = [
+            [0, 0],
+            [1000, 1000], # [txA, txB] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_ab, node.getmempoolfeeratediagram())
+
+        # txC (0sat / 1000vB) <- txD (2000sat / 1000vB)
+        # Use v3 to allow 0 fee
+        txC = self.wallet.create_self_transfer(confirmed_only=True, fee=0, fee_rate=0, version=3, target_vsize=1000)
+        txD = self.wallet.create_self_transfer(utxo_to_spend=txC["new_utxo"], fee=sats_to_btc(2000), version=3, target_vsize=1000)
+        result_cd = node.submitpackage([txC["hex"], txD["hex"]])
+
+        # one cluster, one chunks with feerate 1sat/vB
+        assert_equal(result_cd["package_msg"], "success")
+        assert_equal(result_cd["tx-results"][txC["wtxid"]]["fees"]["effective-feerate"], feerate_1000sat_kvb)
+        assert_equal(result_cd["tx-results"][txD["wtxid"]]["fees"]["effective-feerate"], feerate_1000sat_kvb)
+        assert_equal(node.getmempoolcluster(txC["txid"])['txcount'], 2)
+        # Same chunk feerate as [txA, txB], but [txC, txD] has larger vsize.
+        expected_feerate_diagram_cd = [
+            [0, 0],
+            [1000, 1000], # [txA, txB] 1sat/vB
+            [3000, 3000], # [txC, txD] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_cd, node.getmempoolfeeratediagram())
+
+        self.log.info("Test that the feerate diagram uses modified fees")
+        # txE (800sat / 400vB)
+        # 799sat of fees will come from prioritisetransaction
+        txE = self.wallet.create_self_transfer(confirmed_only=True, fee=sats_to_btc(1), target_vsize=400)
+        node.prioritisetransaction(txid=txE["txid"], fee_delta=799)
+        node.sendrawtransaction(txE["hex"])
+        assert_equal(node.getmempoolcluster(txE["txid"])['txcount'], 1)
+        expected_feerate_diagram_e = [
+            [0, 0],
+            [800, 400], # [txE] 2sat/vB
+            [1800, 1400], # [txA, txB] 1sat/vB
+            [3800, 3400], # [txC, txD] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_e, node.getmempoolfeeratediagram())
+
+        # txF (750sat / 500vB) <- txG (6250sat / 500vB)
+        txF = self.wallet.create_self_transfer(confirmed_only=True, fee=sats_to_btc(750), target_vsize=500)
+        txG = self.wallet.create_self_transfer(utxo_to_spend=txF["new_utxo"], fee=sats_to_btc(6250), target_vsize=500)
+
+        # Submit them individually to see txF's chunk feerate change.
+        node.sendrawtransaction(txF["hex"])
+        assert_equal(node.getmempoolcluster(txF["txid"])['txcount'], 1)
+        # txF has a feerate of 1.5sat/vB, so it's in the middle
+        expected_feerate_diagram_f = [
+            [0, 0],
+            [800, 400], # [txE] 2sat/vB
+            [1550, 900], # [txF] 1.5sat/vB
+            [2550, 1900], # [txA, txB] 1sat/vB
+            [4550, 3900], # [txC, txD] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_f, node.getmempoolfeeratediagram())
+
+        # txG bumps txF's chunk feerate to 7sat/vB
+        node.sendrawtransaction(txG["hex"])
+        assert_equal(node.getmempoolcluster(txF["txid"])['txcount'], 2)
+        expected_feerate_diagram_g = [
+            [0, 0],
+            [7000, 1000], # [txF, txG] 7sat/vB
+            [7800, 1400], # [txE] 2sat/vB
+            [8800, 2400], # [txA, txB] 1sat/vB
+            [10800, 4400], # [txC, txD] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_g, node.getmempoolfeeratediagram())
+
+        self.log.info("Test that prioritisetransaction on a mempool entry affects the feerate diagram")
+        # Prioritise txD to make its chunk feerate a little more than 8sat/vB
+        node.prioritisetransaction(txid=txD["txid"], fee_delta=14012)
+        expected_feerate_diagram_d_prio = [
+            [0, 0],
+            [16012, 2000], # [txC, txD] 8.006sat/vB
+            [23012, 3000], # [txF, txG] 7sat/vB
+            [23812, 3400], # [txE] 2sat/vB
+            [24812, 4400], # [txA, txB] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_d_prio, node.getmempoolfeeratediagram())
+
+        # De-prioritise txG to split up the chunk, putting txF behind txE and txG at the very end.
+        node.prioritisetransaction(txid=txG["txid"], fee_delta=-6195)
+        expected_feerate_diagram_g_deprio = [
+            [0, 0],
+            [16012, 2000], # [txC, txD] 8.006sat/vB
+            [16812, 2400], # [txE] 2sat/vB
+            [17562, 2900], # [txF] 1.5sat/vB
+            [18562, 3900], # [txA, txB] 1sat/vB
+            [18617, 4400], # [txG] 0.11sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_g_deprio, node.getmempoolfeeratediagram())
+
+        # txH (30sat / 300vB) Spend txE and txG to merge their clusters, but keeping the chunking the same.
+        txH = self.wallet.create_self_transfer_multi(utxos_to_spend=[txE["new_utxo"], txG["new_utxo"]], fee_per_output=30, target_vsize=300)
+        node.sendrawtransaction(txH["hex"])
+        # The cluster is now EFGH
+        assert_equal(node.getmempoolcluster(txE["txid"])['txcount'], 4)
+        expected_feerate_diagram_h = [
+            [0, 0],
+            [16012, 2000], # [txC, txD] 8.006sat/vB
+            [16812, 2400], # [txE] 2sat/vB
+            [17562, 2900], # [txF] 1.5sat/vB
+            [18562, 3900], # [txA, txB] 1sat/vB
+            [18617, 4400], # [txG] 0.11sat/vB
+            [18647, 4700], # [txH] 0.1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_h, node.getmempoolfeeratediagram())
+
+        # txI (2150sat / 200vB) bumps txF, txG, txH to 1.99sat/vB, combining them into a single chunk
+        txI = self.wallet.create_self_transfer(utxo_to_spend=txH["new_utxos"][0], fee=sats_to_btc(2150), target_vsize=200)
+        node.sendrawtransaction(txI["hex"])
+        # The cluster is now EFGHI
+        assert_equal(node.getmempoolcluster(txI["txid"])['txcount'], 5)
+        expected_feerate_diagram_i = [
+            [0, 0],
+            [16012, 2000], # [txC, txD] 8.006sat/vB
+            [16812, 2400], # [txE] 2sat/vB
+            [19797, 3900], # [txF, txG, txH, txI] 1.99sat/vB
+            [20797, 4900], # [txA, txB] 1sat/vB
+        ]
+        assert_equal_feerate_diagram(expected_feerate_diagram_i, node.getmempoolfeeratediagram())
 
     def run_test(self):
         node = self.nodes[0]
@@ -299,6 +435,7 @@ class MempoolClusterTest(BitcoinTestFramework):
         self.generate(self.wallet, 400)
 
         self.test_cluster_limit_rbf(DEFAULT_CLUSTER_LIMIT)
+        self.test_feerate_diagram()
 
         for cluster_size_limit_kvb in [10, 20, 33, 100, DEFAULT_CLUSTER_SIZE_LIMIT_KVB]:
             self.log.info(f"-> Resetting node with -limitclustersize={cluster_size_limit_kvb}")
diff --git a/test/functional/test_framework/mempool_util.py b/test/functional/test_framework/mempool_util.py
index 89e2558307e..2bce87bda2f 100644
--- a/test/functional/test_framework/mempool_util.py
+++ b/test/functional/test_framework/mempool_util.py
@@ -10,6 +10,7 @@ from .blocktools import (
 )
 from .messages import (
     COutPoint,
+    COIN,
     CTransaction,
     CTxIn,
     CTxInWitness,
@@ -22,6 +23,7 @@ from .script import (
 from .util import (
     assert_equal,
     assert_greater_than,
+    assert_greater_than_or_equal,
     create_lots_of_big_transactions,
     gen_return_txouts,
 )
@@ -131,3 +133,28 @@ def create_large_orphan():
     tx.wit.vtxinwit[0].scriptWitness.stack = [CScript(b'X' * 390000)]
     tx.vout = [CTxOut(100, CScript([OP_RETURN, b'a' * 20]))]
     return tx
+
+def check_feerate_diagram_monotonically_decreasing(feerate_diagram):
+    """Sanity check the feerate diagram."""
+    last_val = [0, 0]
+    for x in feerate_diagram:
+        # The vsize is always positive, except for the first iteration
+        assert x['vsize'] > 0 or x['fee'] == 0
+        # Monotonically decreasing fee per vsize
+        assert_greater_than_or_equal(last_val[0] * x['vsize'], last_val[1] * x['fee'])
+        last_val = [x['vsize'], x['fee']]
+
+def assert_equal_feerate_diagram(expected, actual):
+    """Check that expected and actual are equal, handling Decimal values and giving helpful error messages.
+    expected: list of [fee, vsize] pairs where fee is an integer number of satoshis
+    actual: list of { "fee": Decimal, "vsize": int } from the getmempoolfeeratediagram RPC
+    Also sanity checks that the actual feerates are monotonically decreasing.
+    """
+    assert_equal(len(expected), len(actual))
+    for i in range(len(expected)):
+        # We convert the Decimal to an integer number to avoid Decimal comparisons.
+        # For example, Decimal('0') == Decimal('0E-8') and Decimal('0.0001') == Decimal('0.00010000')
+        assert_equal(expected[i][0], int(actual[i]["fee"] * COIN))
+        assert_equal(expected[i][1], actual[i]["vsize"])
+
+    check_feerate_diagram_monotonically_decreasing(actual)

</details>

My hesitation to include stricter tests on the chunks is that we currently have no guarantee that our linearizations will be anything more than topological, so it feels brittle to add tests that put an expectation on linearization quality. EDIT: actually we can say more, specifically about the properties of chunking, which this code does test -- but if I'm understanding some of the test cases right I think there are also assumptions about linearization quality being mixed in too.

Perhaps something like this would make more sense in the context of implementing SFL?

In "Use cluster linearization for transaction relay sort order" 936f04e770eeb4ef8477722cb1f23f29746883a1

nit: This comment is stale?

         * higher mining score to sort later. */

Done.

In "Remove CTxMemPool::GetSortedDepthAndScore" 9b31836abfc086e4693ecdb1ceaec0a8e21dbb8f

nit

            // We are iterating through the mempool entries sorted topologically and by mining score.

Done.

In "Add test case for cluster size limits to TRUC logic" cf2f5211a8fab1438feb1cf1ccb86dccedd4b6c8

also add a test for cluster count

        self.log.info("Test that a decreased limitclustercount also applies to TRUC cluster")
        self.restart_node(0, extra_args=["-limitclustercount=1", "-acceptnonstdtxn=1"])
        assert_raises_rpc_error(-26, "too-large-cluster", node.sendrawtransaction, tx_v3_child_large2["hex"])
        self.check_mempool([tx_v3_parent_large2["txid"]])

I took this change but I just realized that this is redundant with the first test that appears earlier in this function, right?

In "Use mempool/txgraph to determine if a tx has descendants" b23b156c7bdf112a4fe64acd71e398cc7c0bd231

nice I like this pattern, not leaking internals, I think it will be better to adopt this pattern also in https://github.com/bitcoin/bitcoin/pull/33629/commits/d2f75c555caf1f6a62b8ab1ef0f2543f0c84cc39#r2432661442

Can you clarify what you have in mind here?

I think this is better to do it in like it's done in the diff below for two reasons

1. In Internal interface guidelines It's stated that

Interface method definitions should wrap existing functionality instead of implementing new functionality. Any substantial new node or wallet functionality should be implemented in src/node/ or src/wallet/ and just exposed in src/interfaces/ instead of being implemented there, so it can be more modular and accessible to unit tests.

2. The locking responsibility, knowing how to use the changestate interface, staging addition params are now local to the mempool. Which is more modular and can be reused and tested in isolation IMO.

We can even go further and make the error message returned by CheckPolicyLimits.

<details> <summary>see diff</summary>

diff --git a/src/node/interfaces.cpp b/src/node/interfaces.cpp
index a04b476e1a2..de2c24fbbf3 100644
--- a/src/node/interfaces.cpp
+++ b/src/node/interfaces.cpp
@@ -716,13 +716,7 @@ public:
     util::Result<void> checkChainLimits(const CTransactionRef& tx) override
     {
         if (!m_node.mempool) return {};
-        LOCK(m_node.mempool->cs);
-        // Use CTxMemPool's ChangeSet interface to check whether the chain
-        // limits would be violated. Note that the changeset will be destroyed
-        // when it goes out of scope.
-        auto changeset = m_node.mempool->GetChangeSet();
-        (void) changeset->StageAddition(tx, 0, 0, 0, 0, false, 0, LockPoints{});
-        if (!changeset->CheckMemPoolPolicyLimits()) {
+        if (!m_node.mempool->CheckPolicyLimits(tx)) {
             return util::Error{Untranslated("too many unconfirmed transactions in cluster")};
         }
         return {};
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 99b966360ea..7c776eb83af 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -3,6 +3,7 @@
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include "primitives/transaction.h"
 #include <txmempool.h>
 
 #include <chain.h>
@@ -339,6 +340,18 @@ void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReaso
         RemoveStaged(setAllRemoves, false, reason);
 }
 
+bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx)
+{
+    LOCK(cs);
+    // Use ChangeSet interface to check whether the chain
+    // limits would be violated. Note that the changeset will be destroyed
+    // when it goes out of scope.
+    auto changeset = GetChangeSet();
+    (void) changeset->StageAddition(tx, 0, 0, 0, 0, false, 0, LockPoints{});
+    if (!changeset->CheckMemPoolPolicyLimits()) return false;
+    return true;
+}
+
 void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
 {
     // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
diff --git a/src/txmempool.h b/src/txmempool.h
index 8c520ef518f..5c904e32459 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -548,6 +548,8 @@ public:
         if (exists(txid)) m_unbroadcast_txids.insert(txid);
     };
 
+    bool CheckPolicyLimits(const CTransactionRef& tx);
+
     /** Removes a transaction from the unbroadcast set */
     void RemoveUnbroadcastTx(const Txid& txid, const bool unchecked = false);
 

</details>

I took this change, thanks.

in e6315c24326016cfaee5bd046e8b2e4e1088ac6b

Nice! We should also remove "All conflicting clusters (connected components of mempool transactions) must be clusters of up to size 2." from the package RBF rules in policy/packages.md

Done in 845ec3a3f806dee6c9ad053655fb466bd599a73d

fba5200d59af87db240a1b061f995c63b0ed5ee8 nit: Could be "(Removed)" to be consistent with the other rules we no longer implement?

Done.

* Feerate diagram policy enabled in conjunction with switch to cluster mempool as of **v31.0**.

fba5200d59af87db240a1b061f995c63b0ed5ee8

Happy for this to go into a followup:

Maybe worth adding a bit more color for people who don't have any context: A singleton replacing a singleton must pay higher total fees and have a higher feerate (covers vast majority of cases). For more complex cases, see this link to more comprehensive explanation.

b9cbca76762 Reviewer note, I originally wanted to point out the extra commented line but then read the commit message and saw it changes back later in e6315c24326

e6315c24326: In both single and package settings, ImprovesFeerateDiagram is where cluster size limits are checked for the first time if RBF is happening. The check is cached and many RBF checks are cheaper than CheckMemPoolPolicyLimits, so that doesn't seem problematic.

However, this is assigning TX_RECONSIDERABLE as the error when cluster limits are exceeded, which will cause net_processing to give it some special treatment (we may redownload and revalidate in some circumstances, which may waste resources), which should only be for errors that can be fixed by adding a child (e.g. to pay for fee requirements or sweep dust). I don't think it makes sense to apply that here, or it should at least be consistent with the other too-large-cluster error.

Also, I think the error string should be "too-large-cluster" (but that's more of a nit).

Putting CheckMemPoolPolicyLimits before replacement checks would automatically fix this. That feels cleaner to me, so ImprovesFeerateDiagram doesn't need to do double duty.

We could also examine the err_string here and assign TX_RECONSIDERABLE if it's actually a feerate diagram error, TX_MEMPOOL_POLICY if it's a cluster limit error.

Not sure I follow the reasoning here -- an RBF that fails due to cluster size limits might succeed if a child is added that adds additional conflicts, thereby making space in the affected cluster.

EDIT: Oh -- I guess your point is that a transaction which is NOT an RBF might fail due to cluster size limits, and not be treated as RECONSIDERABLE even though a child might be able to free up cluster space as well by introducing new conflicts... That seems like a reasonable objection, but it's not clear to me the best way to address.

I'm inclined to implement your suggestion, so that any cluster size limit failures are treated as non-RECONSIDERABLE for now. TRUC transactions would never hit these cluster limits, so users who would be concerned about cluster size limits as a potential pinning vector for CPFP packages already have a mechanism to avoid it.

(I also considered having all cluster size limits being treated as RECONSIDERABLE, but decided that is also not great, partly because we certainly shouldn't let a transaction whose cluster size just with its own unconfirmed ancestors be treated as RECONSIDERABLE, and I didn't want to spend a lot of time trying to figure out if there might be some DoS vector that opened up as a result.)

We can try to improve on this behavior in the future if there are use cases that would need smarter behavior here; but for now this would be consistent with how the mempool's ancestor/descendant limits have always worked anyway.

we certainly shouldn't let a transaction whose cluster size just with its own unconfirmed ancestors be treated as RECONSIDERABLE,

certainly seems like Future Kindred Eviction Work, agreed on distinguishing error types and not attempting a package RBF in this case.

I also considered having all cluster size limits being treated as RECONSIDERABLE, but decided that is also not great, partly because we certainly shouldn't let a transaction whose cluster size just with its own unconfirmed ancestors be treated as RECONSIDERABLE

👍 definitely think we should not allow reconsideration in that case

Sounds good to me to make it non-reconsiderable for now, and maybe change it in the future in a consistent way. I agree it's possible for a child to make a tx no longer break cluster limits, but it's not clear to me how important it is to support that case.

Implemented this change in 1ae9fd3f7a4fddc786e9921e7fc2af41ab96bf9a. Should I try to squash this into place or is this fine as its own commit?

I prefer a squash but up to you.

If not squashed, perhaps move it earlier so that the test can have the correct string when introduced?

I think I managed to squash this into 9d0c8d4d5ec2a50ba4756b9882d8801f24542a2e; hopefully the changes all look sane...

Looks good to me

Maybe for a followup, but since CheckTopologyLimits is being removed, I think the package RBF logic can have one more tweak in e6315c24326016cfaee5bd046e8b2e4e1088ac6b, which I think @sipa brought up a few weeks ago:

We currently have the requirement that the package feerate is higher than the parent feerate because "we don't want the child to be only paying anti-DoS fees" but that's more restrictive than it needs to be. It's ok if the child has a lower feerate than the parent and only pays anti-DoS fees, as long as it pays for itself to be above the mempool minimum feerate.

Here's a branch to do this + a few test cases and a doc update: https://github.com/glozow/bitcoin/commits/2025-10-cluster-package-rbf/

<details>

diff --git a/doc/policy/packages.md b/doc/policy/packages.md
index 7522a984435..2e8f5cf8e0d 100644
--- a/doc/policy/packages.md
+++ b/doc/policy/packages.md
@@ -38,17 +38,10 @@ The following rules are enforced for all packages:
 
    - Packages are 1-parent-1-child, with no in-mempool ancestors of the package.
 
-   - All conflicting clusters (connected components of mempool transactions) must be clusters of up to size 2.
+   - The child's individual feerate must meet the mempool minimum feerate.
 
-   - No more than MAX_REPLACEMENT_CANDIDATES transactions can be replaced, analogous to
-     regular [replacement rule](./mempool-replacements.md) 5).
-
-   - Replacements must pay more total fees at the incremental relay fee (analogous to
-     regular [replacement rules](./mempool-replacements.md) 3 and 4).
-
-   - Parent feerate must be lower than package feerate.
-
-   - Must improve [feerate diagram](https://delvingbitcoin.org/t/mempool-incentive-compatibility/553). (#29242)
+   - All other [replacement rules](./mempool-replacements.md) are met: no more than 100 distinct clusters, total package
+   fees pay for the package size at the incremental relay feerate, and the feerate diagram improves.
 
    - *Rationale*: Basic support for package RBF can be used by wallets
      by making chains of no longer than two, then directly conflicting
@@ -56,18 +49,6 @@ The following rules are enforced for all packages:
      result in more robust fee bumping. More general package RBF may be
      enabled in the future.
 
-* When packages are evaluated against ancestor/descendant limits, the union of all transactions'
-  descendants and ancestors is considered. (#21800)
-
-   - *Rationale*: This is essentially a "worst case" heuristic intended for packages that are
-     heavily connected, i.e. some transaction in the package is the ancestor or descendant of all
-     the other transactions.
-
-* [CPFP Carve Out](./mempool-limits.md#CPFP-Carve-Out) is disabled in packaged contexts. (#21800)
-
-   - *Rationale*: This carve out cannot be accurately applied when there are multiple transactions'
-     ancestors and descendants being considered at the same time.
-
 The following rules are only enforced for packages to be submitted to the mempool (not
 enforced for test accepts):
 
diff --git a/src/test/txpackage_tests.cpp b/src/test/txpackage_tests.cpp
index 1f167586fe9..fbdaa49f70e 100644
--- a/src/test/txpackage_tests.cpp
+++ b/src/test/txpackage_tests.cpp
@@ -1078,6 +1078,7 @@ BOOST_AUTO_TEST_CASE(package_cpfp_tests)
 BOOST_AUTO_TEST_CASE(package_rbf_tests)
 {
     mineBlocks(5);
+    MockMempoolMinFee(CFeeRate(1000));
     LOCK(::cs_main);
     size_t expected_pool_size = m_node.mempool->size();
     CKey child_key{GenerateRandomKey()};
@@ -1159,16 +1160,19 @@ BOOST_AUTO_TEST_CASE(package_rbf_tests)
             tx_parent_3, /*input_vout=*/0, /*input_height=*/101,
             child_key, child_spk, coinbase_value - 199 - 1300, /*submit=*/false));
 
+        CTransactionRef tx_parent_4 = MakeTransactionRef(CreateValidMempoolTransaction(
+            m_coinbase_txns[1], /*input_vout=*/0, /*input_height=*/0,
+            coinbaseKey, parent_spk, coinbase_value - 1763, /*submit=*/false));
+        CTransactionRef tx_child_4 = MakeTransactionRef(CreateValidMempoolTransaction(
+            tx_parent_4, /*input_vout=*/0, /*input_height=*/101,
+            child_key, child_spk, coinbase_value - 1763 - 60, /*submit=*/false));
+
         // In all packages, the parents conflict with each other
         BOOST_CHECK(tx_parent_1->GetHash() != tx_parent_2->GetHash() && tx_parent_2->GetHash() != tx_parent_3->GetHash());
 
         // 1 parent paying 200sat, 1 child paying 200sat.
         Package package1{tx_parent_1, tx_child_1};
-        // 1 parent paying 800sat, 1 child paying 200sat.
-        Package package2{tx_parent_2, tx_child_2};
-        // 1 parent paying 199sat, 1 child paying 1300sat.
-        Package package3{tx_parent_3, tx_child_3};
-
+        {
         const auto submit1 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package1, false, std::nullopt);
         if (auto err_1{CheckPackageMempoolAcceptResult(package1, submit1, /*expect_valid=*/true, m_node.mempool.get())}) {
             BOOST_ERROR(err_1.value());
@@ -1177,11 +1181,20 @@ BOOST_AUTO_TEST_CASE(package_rbf_tests)
         auto it_child_1 = submit1.m_tx_results.find(tx_child_1->GetWitnessHash());
         BOOST_CHECK_EQUAL(it_parent_1->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
         BOOST_CHECK_EQUAL(it_child_1->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        // Both validated individually.
+        BOOST_CHECK_EQUAL(it_parent_1->second.m_wtxids_fee_calculations.value().size(), 1);
+        BOOST_CHECK_EQUAL(it_parent_1->second.m_wtxids_fee_calculations.value().front(), tx_parent_1->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_child_1->second.m_wtxids_fee_calculations.value().size(), 1);
+        BOOST_CHECK_EQUAL(it_child_1->second.m_wtxids_fee_calculations.value().front(), tx_child_1->GetWitnessHash());
+        }
         expected_pool_size += 2;
         BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
 
         // This replacement is actually not package rbf; the parent carries enough fees
         // to replace the entire package on its own.
+        // 1 parent paying 800sat, 1 child paying 200sat.
+        Package package2{tx_parent_2, tx_child_2};
+        {
         const auto submit2 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package2, false, std::nullopt);
         if (auto err_2{CheckPackageMempoolAcceptResult(package2, submit2, /*expect_valid=*/true, m_node.mempool.get())}) {
             BOOST_ERROR(err_2.value());
@@ -1190,8 +1203,17 @@ BOOST_AUTO_TEST_CASE(package_rbf_tests)
         auto it_child_2 = submit2.m_tx_results.find(tx_child_2->GetWitnessHash());
         BOOST_CHECK_EQUAL(it_parent_2->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
         BOOST_CHECK_EQUAL(it_child_2->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        // Both validated individually.
+        BOOST_CHECK_EQUAL(it_parent_2->second.m_wtxids_fee_calculations.value().size(), 1);
+        BOOST_CHECK_EQUAL(it_parent_2->second.m_wtxids_fee_calculations.value().front(), tx_parent_2->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_child_2->second.m_wtxids_fee_calculations.value().size(), 1);
+        BOOST_CHECK_EQUAL(it_child_2->second.m_wtxids_fee_calculations.value().front(), tx_child_2->GetWitnessHash());
+        }
         BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
 
+        // 1 parent paying 199sat, 1 child paying 1300sat.
+        Package package3{tx_parent_3, tx_child_3};
+        {
         // Package RBF, in which the replacement transaction's child sponsors the fees to meet RBF feerate rules
         const auto submit3 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package3, false, std::nullopt);
         if (auto err_3{CheckPackageMempoolAcceptResult(package3, submit3, /*expect_valid=*/true, m_node.mempool.get())}) {
@@ -1212,27 +1234,91 @@ BOOST_AUTO_TEST_CASE(package_rbf_tests)
         BOOST_CHECK(it_child_3->second.m_wtxids_fee_calculations.value() == expected_package3_wtxids);
         BOOST_CHECK_EQUAL(it_parent_3->second.m_effective_feerate.value().GetFee(package3_total_vsize), 199 + 1300);
         BOOST_CHECK_EQUAL(it_child_3->second.m_effective_feerate.value().GetFee(package3_total_vsize), 199 + 1300);
-
+        }
         BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
 
         // Finally, check that we can prioritise tx_child_1 to get package1 into the mempool.
         // It should not be possible to resubmit package1 and get it in without prioritisation.
+        // 1 parent paying 200sat, 1 child paying 200sat.
+        Package package4{package1};
+        {
         const auto submit4 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package1, false, std::nullopt);
-        if (auto err_4{CheckPackageMempoolAcceptResult(package1, submit4, /*expect_valid=*/false, m_node.mempool.get())}) {
+        if (auto err_4{CheckPackageMempoolAcceptResult(package4, submit4, /*expect_valid=*/false, m_node.mempool.get())}) {
             BOOST_ERROR(err_4.value());
         }
+        }
+
+        // 1 parent paying 200sat, 1 child paying 1563sat.
+        Package package5{package1};
         m_node.mempool->PrioritiseTransaction(tx_child_1->GetHash(), 1363);
-        const auto submit5 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package1, false, std::nullopt);
-        if (auto err_5{CheckPackageMempoolAcceptResult(package1, submit5, /*expect_valid=*/true, m_node.mempool.get())}) {
+        {
+        const auto submit5 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package5, false, std::nullopt);
+        if (auto err_5{CheckPackageMempoolAcceptResult(package5, submit5, /*expect_valid=*/true, m_node.mempool.get())}) {
             BOOST_ERROR(err_5.value());
         }
-        it_parent_1 = submit5.m_tx_results.find(tx_parent_1->GetWitnessHash());
-        it_child_1 = submit5.m_tx_results.find(tx_child_1->GetWitnessHash());
-        BOOST_CHECK_EQUAL(it_parent_1->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
-        BOOST_CHECK_EQUAL(it_child_1->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
-        LOCK(m_node.mempool->cs);
-        BOOST_CHECK(m_node.mempool->GetIter(tx_parent_1->GetHash()).has_value());
-        BOOST_CHECK(m_node.mempool->GetIter(tx_child_1->GetHash()).has_value());
+        auto it_parent_5 = submit5.m_tx_results.find(tx_parent_1->GetWitnessHash());
+        auto it_child_5 = submit5.m_tx_results.find(tx_child_1->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_parent_5->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        BOOST_CHECK_EQUAL(it_child_5->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        // Validated together.
+        const auto expected_wtxids_5 = std::vector<Wtxid>({tx_parent_1->GetWitnessHash(), tx_child_1->GetWitnessHash()});
+        BOOST_CHECK(it_parent_5->second.m_wtxids_fee_calculations.value() == expected_wtxids_5);
+        BOOST_CHECK(it_child_5->second.m_wtxids_fee_calculations.value() == expected_wtxids_5);
+        const CFeeRate feerate_parent_child_5(1363 + 200 + 200, GetVirtualTransactionSize(*tx_parent_1) + GetVirtualTransactionSize(*tx_child_1));
+        BOOST_CHECK(it_parent_5->second.m_effective_feerate.value() == feerate_parent_child_5);
+        BOOST_CHECK(it_child_5->second.m_effective_feerate.value() == feerate_parent_child_5);
+        }
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+
+        // Check that the grouping for package RBF does not allow a parent to pay for a child below mempool minimum feerate.
+        // This parent cannot pay for its own replacement, and can get assistance from the child, but the child should
+        // not be eligible for submission at all.
+        // 1 parent paying 1763sat, 1 child paying 60sat.
+        Package package6{tx_parent_4, tx_child_4};
+        {
+        const auto submit6 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package6, false, std::nullopt);
+        if (auto err_6{CheckPackageMempoolAcceptResult(package6, submit6, /*expect_valid=*/false, m_node.mempool.get())}) {
+            BOOST_ERROR(err_6.value());
+        }
+        auto it_parent_6 = submit6.m_tx_results.find(tx_parent_4->GetWitnessHash());
+        auto it_child_6 = submit6.m_tx_results.find(tx_child_4->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_parent_6->second.m_result_type, MempoolAcceptResult::ResultType::INVALID);
+        BOOST_CHECK_EQUAL(it_child_6->second.m_result_type, MempoolAcceptResult::ResultType::INVALID);
+        // Parent does not meet rule 4
+        BOOST_CHECK_EQUAL(it_parent_6->second.m_state.GetResult(), TxValidationResult::TX_RECONSIDERABLE);
+        BOOST_CHECK_EQUAL(it_parent_6->second.m_state.GetRejectReason(), "insufficient fee");
+        // Child needs parent's output
+        BOOST_CHECK_EQUAL(it_child_6->second.m_state.GetResult(), TxValidationResult::TX_MISSING_INPUTS);
+        BOOST_CHECK_EQUAL(it_child_6->second.m_state.GetRejectReason(), "bad-txns-inputs-missingorspent");
+        }
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+
+        // It is ok if the child pays fewer fees but subsidizes the parent's replacement cost, as long as the child meets the mempool minimum feerate.
+        // 1 parent paying 1763sat, 1 child paying 160sat.
+        // Even though the parent has a higher feerate, this isn't "parent pays for child" because the child meets the mempool minimum feerate.
+        Package package7{package6};
+        m_node.mempool->PrioritiseTransaction(tx_child_4->GetHash(), 100);
+        {
+        const auto submit7 = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool, package7, false, std::nullopt);
+        if (auto err_7{CheckPackageMempoolAcceptResult(package7, submit7, /*expect_valid=*/true, m_node.mempool.get())}) {
+            BOOST_ERROR(err_7.value());
+        }
+        auto it_parent_7 = submit7.m_tx_results.find(tx_parent_4->GetWitnessHash());
+        auto it_child_7 = submit7.m_tx_results.find(tx_child_4->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_parent_7->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        BOOST_CHECK_EQUAL(it_child_7->second.m_result_type, MempoolAcceptResult::ResultType::VALID);
+        // The two transactions were validated together.
+        BOOST_CHECK_EQUAL(it_parent_7->second.m_wtxids_fee_calculations.value().size(), 2);
+        BOOST_CHECK_EQUAL(it_parent_7->second.m_wtxids_fee_calculations.value().front(), tx_parent_4->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_parent_7->second.m_wtxids_fee_calculations.value().back(), tx_child_4->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_child_7->second.m_wtxids_fee_calculations.value().size(), 2);
+        BOOST_CHECK_EQUAL(it_child_7->second.m_wtxids_fee_calculations.value().front(), tx_parent_4->GetWitnessHash());
+        BOOST_CHECK_EQUAL(it_child_7->second.m_wtxids_fee_calculations.value().back(), tx_child_4->GetWitnessHash());
+        const CFeeRate feerate_parent_child_7(1763 + 160, GetVirtualTransactionSize(*tx_parent_4) + GetVirtualTransactionSize(*tx_child_4));
+        BOOST_CHECK(it_parent_7->second.m_effective_feerate.value() == feerate_parent_child_7);
+        BOOST_CHECK(it_child_7->second.m_effective_feerate.value() == feerate_parent_child_7);
+        }
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
     }
 }
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
index 1102f2bb051..508892faea2 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -1048,8 +1048,23 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
         return package_state.Invalid(PackageValidationResult::PCKG_POLICY, "package RBF failed: package must be 1-parent-1-child");
     }
 
-    // If the package has in-mempool parents, we won't consider a package RBF
-    // since it would result in a cluster larger than 2.
+    // Use the child as the transaction for attributing errors because it is presumably sponsoring this package RBF.
+    auto& child_ws = workspaces[1];
+    const Txid& child_hash = child_ws.m_ptx->GetHash();
+
+    // Check if this child is eligible to be a sponsor. We allow a child with a lower feerate than that of its
+    // parents (and thus only helping pay for the replacement). However, the child itself must meet the mempool minimum
+    // feerate, otherwise it would sponsor this replacement, potentially using the parents' fees to pay for its entry,
+    // but be immediately evicted next time we trim the mempool.
+    if (!CheckFeeRate(child_ws.m_vsize, child_ws.m_modified_fees, child_ws.m_state)) {
+        // Add the CheckFeeRate error as the debug string.
+        return package_state.Invalid(PackageValidationResult::PCKG_POLICY,
+                                     "package RBF failed: child cannot sponsor because it does not meet mempool minimum feerate",
+                                     child_ws.m_state.ToString());
+    }
+
+
+    // If the package has in-mempool parents, we won't consider a package RBF for now.
     // N.B. To relax this constraint we will need to revisit how CCoinsViewMemPool::PackageAddTransaction
     // is being used inside AcceptMultipleTransactions to track available inputs while processing a package.
     // Specifically we would need to check that the ancestors of the new
@@ -1062,6 +1077,7 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
         }
     }
 
+    // The remaining checks are similar to those for a single transaction's replacement(s).
     // Aggregate all conflicts into one set.
     CTxMemPool::setEntries direct_conflict_iters;
     for (Workspace& ws : workspaces) {
@@ -1069,9 +1085,6 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
         direct_conflict_iters.merge(ws.m_iters_conflicting);
     }
 
-    const auto& parent_ws = workspaces[0];
-    const auto& child_ws = workspaces[1];
-
     // Don't consider replacements that would cause us to remove a large number of mempool entries.
     // This limit is not increased in a package RBF. Use the aggregate number of transactions.
     CTxMemPool::setEntries all_conflicts;
@@ -1087,8 +1100,6 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
         m_subpackage.m_conflicting_size += it->GetTxSize();
     }
 
-    // Use the child as the transaction for attributing errors to.
-    const Txid& child_hash = child_ws.m_ptx->GetHash();
     if (const auto err_string{PaysForRBF(/*original_fees=*/m_subpackage.m_conflicting_fees,
                                          /*replacement_fees=*/m_subpackage.m_total_modified_fees,
                                          /*replacement_vsize=*/m_subpackage.m_total_vsize,
@@ -1097,16 +1108,6 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
                                      "package RBF failed: insufficient anti-DoS fees", *err_string);
     }
 
-    // Ensure this two transaction package is a "chunk" on its own; we don't want the child
-    // to be only paying anti-DoS fees
-    const CFeeRate parent_feerate(parent_ws.m_modified_fees, parent_ws.m_vsize);
-    const CFeeRate package_feerate(m_subpackage.m_total_modified_fees, m_subpackage.m_total_vsize);
-    if (package_feerate <= parent_feerate) {
-        return package_state.Invalid(PackageValidationResult::PCKG_POLICY,
-                                     "package RBF failed: package feerate is less than or equal to parent feerate",
-                                     strprintf("package feerate %s <= parent feerate is %s", package_feerate.ToString(), parent_feerate.ToString()));
-    }
-
     // Check if it's economically rational to mine this package rather than the ones it replaces.
     // This takes the place of ReplacementChecks()'s PaysMoreThanConflicts() in the package RBF setting.
     if (const auto err_tup{ImprovesFeerateDiagram(*m_subpackage.m_changeset)}) {
diff --git a/test/functional/mempool_package_rbf.py b/test/functional/mempool_package_rbf.py
index 759e3cb07d3..c1983cab57b 100755
--- a/test/functional/mempool_package_rbf.py
+++ b/test/functional/mempool_package_rbf.py
@@ -178,14 +178,10 @@ class PackageRBFTest(BitcoinTestFramework):
         package_hex4, package_txns4 = self.create_simple_package(coin, parent_fee=DEFAULT_FEE, child_fee=DEFAULT_CHILD_FEE)
         node.submitpackage(package_hex4)
         self.assert_mempool_contents(expected=package_txns4)
-        package_hex5, _package_txns5 = self.create_simple_package(coin, parent_fee=DEFAULT_CHILD_FEE, child_fee=DEFAULT_CHILD_FEE)
-        pkg_results5 = node.submitpackage(package_hex5)
-        assert 'package RBF failed: package feerate is less than or equal to parent feerate' in pkg_results5["package_msg"]
-        self.assert_mempool_contents(expected=package_txns4)
+        package_hex5, package_txns5 = self.create_simple_package(coin, parent_fee=DEFAULT_CHILD_FEE + DEFAULT_FEE, child_fee=DEFAULT_CHILD_FEE)
+        node.submitpackage(package_hex5)
+        self.assert_mempool_contents(expected=package_txns5)
 
-        package_hex5_1, package_txns5_1 = self.create_simple_package(coin, parent_fee=DEFAULT_CHILD_FEE, child_fee=DEFAULT_CHILD_FEE + Decimal("0.00000001"))
-        node.submitpackage(package_hex5_1)
-        self.assert_mempool_contents(expected=package_txns5_1)
         self.generate(node, 1)
 
     def test_package_rbf_max_conflicts(self):

</details>

Agreed, though I think this type of behavior change regarding what packages we accept can happen in a separate PR after cluster mempool. (In particular I think it's worth a separate discussion around what use cases we would be trying to enable with such a change.)

Great, marking resolved and will refer to this in a followup!

Unkilled mutant:

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index b0c9ab043c..8d7e4d2bb9 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -994,7 +994,7 @@ void CTxMemPool::ChangeSet::ProcessDependencies()
             }
         }
     }
-    m_dependencies_processed = true;
+    m_dependencies_processed = false;
     return;
  }

@brunoerg This mutant seems expected, as it just avoids redoing work by remembering it's already done. Is there any suggested/best practice for avoiding things like that?

Unkilled mutant:

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index b0c9ab043c..aef4fdde8d 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -129,7 +129,7 @@ CTxMemPool::setEntries CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEnt
 {
     auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
     setEntries ret;
-    if (ancestors.size() > 0) {
+    if (ancestors.size() < 0) {
         for (auto ancestor : ancestors) {
             if (ancestor != &entry) {
                 ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor)));

In commit "Use txgraph to calculate ancestors"

This unkilled mutant looks concerning, as it means we have no testing in place that relies on correctly computing a non-empty set of ancestors?

Maybe misunderstanding, but this just means it's purely an optimzation?

If it's not in the main graph, it still is able to gather ancestors via more expensive mempool queries.

@instagibbs Oh, you're right - the mutation just causes the code to always use the fallback path, which needs to exist for non-mempool transactions anyway.

Unkilled mutant:

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index b0c9ab043c..bdbbc8325d 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -121,7 +121,7 @@ bool CTxMemPool::HasDescendants(const Txid& txid) const
 {
     LOCK(cs);
     auto entry = GetEntry(txid);
-    if (!entry) return false;
+    if (1==0) return false;
     return m_txgraph->GetDescendants(*entry, TxGraph::Level::MAIN).size() > 1;
 }

there's a single lasting reference to "package-mempool-limits" in the comment in this file

Fixed in f784ae88327c61b08684e1e073b010a244e2b52e.

Unkilled mutant:

diff --git a/src/txmempool.h b/src/txmempool.h
index 4aeae00f69..c4332f3344 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -398,7 +398,7 @@ public:
     }
     std::vector<const CTxMemPoolEntry*> GetCluster(Txid txid) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
         auto tx = GetIter(txid);
-        if (!tx) return {};
+        if (1==0) return {};
         auto cluster = m_txgraph->GetCluster(**tx, TxGraph::Level::MAIN);
         std::vector<const CTxMemPoolEntry*> ret;
         ret.reserve(cluster.size());

Unkilled mutant:

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index b0c9ab043c..9142d8d2c6 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -947,7 +947,7 @@ CTxMemPool::ChangeSet::TxHandle CTxMemPool::ChangeSet::StageAddition(const CTran

     TxGraph::Ref ref(m_pool->m_txgraph->AddTransaction(FeePerWeight(fee+delta, GetSigOpsAdjustedWeight(GetTransactionWeight(*tx), sigops_cost, ::nBytesPerSigOp))));
     auto newit = m_to_add.emplace(std::move(ref), tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first;
-    if (delta) {
+    if (1==1) {
         m_to_add.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
     }

Yes, calling UpdateModifiedFee(0) does nothing. I think it's fine to keep this :shrug:

Perfect, I wasn't aware of UpdateModifiedFee, I just took a look and this is a saturated addition, so it won't have any effect. This can be ignored.

Removing this doesn't make the test to fail:

diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp
index 45dd8bcb12..8ef8f0618c 100644
--- a/src/test/rbf_tests.cpp
+++ b/src/test/rbf_tests.cpp
@@ -225,7 +225,7 @@ BOOST_FIXTURE_TEST_CASE(rbf_conflicts_calculator, TestChain100Setup)

     // Add some descendants now to each of the direct children (we can do this now that the clusters have split).
     for (const auto& child : direct_children) {
-        add_descendants(child, 10, pool);
+
     }

Unkilled mutant:

diff --git a/src/policy/truc_policy.cpp b/src/policy/truc_policy.cpp
index dd16eccb7c..c60dff899f 100644
--- a/src/policy/truc_policy.cpp
+++ b/src/policy/truc_policy.cpp
@@ -204,7 +204,7 @@ std::optional<std::pair<std::string, CTransactionRef>> SingleTRUCChecks(const CT
     }

     // Check that TRUC_ANCESTOR_LIMIT would not be violated.
-    if (mempool_parents.size() + 1 > TRUC_ANCESTOR_LIMIT) {
+    if (mempool_parents.size() / 1 > TRUC_ANCESTOR_LIMIT) {
         return std::make_pair(strprintf("tx %s (wtxid=%s) would have too many ancestors",
                          ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString()),
             nullptr);

In 4c359dabd2a7ca5a5d7469070f55e66a88196291

Is this benchmark supposed to be deleted? It seems like it was written a long time ago.

Oops, yes I think this must be a holdover from a very early draft of this PR, prior to txgraph. I'll remove.

Gone now in 110e62ce76f029e32eeed44238db8d3c09ddb2f7.

in 83c8753abf9c2af75cfbacd5488605332da588a4, I think this is missing a few words?

/** How many linearization iterations required for TxGraph clusters to have "acceptable" quality, if they cannot be optimally linearized with fewer iterations. */

Done in a6649dffe92319a17790bf2add5206a84726f34d.

nit 91d9bfcca62bd6c168476f6af442bd7049ff872e

I was going to complain about this magic number, maybe squash 83c8753abf9c2af75cfbacd5488605332da588a4 into its parent?

This was squashed.

2812471c2bfce6215d6d58c1defd39c7a050edbd: Maybe deserves a comment

            // PrioritiseTransaction calls stack on previous ones. Set the new transaction fee to be current modified fee + feedelta.
            m_txgraph->SetTransactionFee(*it, it->GetModifiedFee() + nFeeDelta);

Done in b0c8081258fc37816e4675e17fa9ea8d308921f3

in 0e25736d6e0

It would help the fuzzer run faster to just call check once at the end, instead of after each round of potential removals.

Done in 0097138011b6e502bfbae528304a6a7e6b6462ad.

It seems a bit unfortunate that, prior to 675fa79bb280129fb87e5d1884e670a35a03f5cd, there isn't a cap on ancestor count when we call CalculateMemPoolAncestors. Could the rework be done earlier?

I took a stab at it and it's a bit tedious (I managed to move it up earlier in the commit history, but stopped when I got to a conflict with a commit that also touches truc_policy in different ways).

My overall take is it's not such a big deal, as the concern is not around correctness of the code but a potential CPU DoS if exposed over the network, which doesn't strike me as all that concerning for an intermediate commit.

Adds some GetFeerateDiagram coverage that will get hit in various contexts including fuzz

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index b0c9ab043c..3dcc0dd3e4 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -426,7 +426,13 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
 
+    const auto score_with_topo{GetSortedScoreWithTopology()};
+
+    // Number of chunks bounded by number of txs
+    const auto diagram{GetFeerateDiagram()};
+    assert(diagram.size() <= score_with_topo.size());
+
     std::optional<Wtxid> last_wtxid = std::nullopt;
 
-    for (const auto& it : GetSortedScoreWithTopology()) {
+    for (const auto& it : score_with_topo) {
         checkTotal += it->GetTxSize();
         check_total_fee += it->GetFee();

There was an off-by-one here (feerate diagrams start with a [0, 0]), but otherwise I incorporated this into ed23b4537ae8a8a814738909fe9a84c548f2855d.

what does dummy mean here?

I think this was a copy-paste thing from elsewhere in the code (this "dummy" comment appears at line 123 as well, and seems to have been introduced when this fuzz test was first created) -- I presume the origin is just that the MemPoolRemovalReason doesn't matter for how removeRecursive() behaves, it's just passed on to callbacks.

Anyway I've removed it from this line.

no-op trimming makes sense too (probably a smarter of way of having this hit than I suggest here)

        tx_pool.TrimToSize(fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0U, tx_pool.DynamicMemoryUsage() * 2));

Incorporated in 0097138011b6

could we get this magic number explained?

Done in d00d8a8a84e43cb79e81482a2a85532209dd9ab2

without comment I found this hard to understand

            // If we don't set the # of sig ops in the CTxMemPoolEntry, template creation fails during sanity checks
            AddToMempool(tx_mempool, entry.Fee(LOWFEE).Time(Now<NodeSeconds>()).SpendsCoinbase(true).FromTx(t));

Done in d00d8a8a84e43cb79e81482a2a85532209dd9ab2

        # It should also limit cluster sizes during replacement

Done in 74654eaf1bef5b578b97111af20b3de39c39cec6

        # Multiply fee by 5, which should easily cover the cost to replace (but is still too large a cluster). Otherwise, use the target vsize at 10sat/vB

Done in 74654eaf1bef5b578b97111af20b3de39c39cec6

Since this harness is making blocks, I think it'd be good to have sigops naturally appearing in the constructed blocks. Ran this for a bit, seemed to work?

diff --git a/src/test/fuzz/tx_pool.cpp b/src/test/fuzz/tx_pool.cpp
index 8a5863c5d5..413ab0db4c 100644
--- a/src/test/fuzz/tx_pool.cpp
+++ b/src/test/fuzz/tx_pool.cpp
@@ -291,9 +291,18 @@ FUZZ_TARGET(tx_pool_standard, .init = initialize_tx_pool)
                 tx_mut.vin.push_back(in);
             }
+
+            // Check sigops in mempool + block template creation
+            bool add_sigops{fuzzed_data_provider.ConsumeBool()};
+
             const auto amount_fee = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-1000, amount_in);
             const auto amount_out = (amount_in - amount_fee) / num_out;
             for (int i = 0; i < num_out; ++i) {
-                tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE);
+                if (i == 0 && add_sigops) {
+                    tx_mut.vout.emplace_back(amount_out, CScript() << std::vector<unsigned char>(33, 0x02) << OP_CHECKSIG);
+                } else {
+                    tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE);
+                }
             }
+
             auto tx = MakeTransactionRef(tx_mut);
             // Restore previously removed outpoints

Done in 0097138011b6e502bfbae528304a6a7e6b6462ad

In commit "Allow moving CTxMemPoolEntry objects, disallow copying"

Ultranit: push_back instead of emplace_back (no real downside to using emplace_back, but push_back makes it more clear that nothing is really being constructed in-place).

Done.

In commit "Create a txgraph inside CTxMemPool"

Based on the Linearize64TxWorstCase15000Iters and Linearize64TxWorstCase5000Iters benchmarks, it seems one iteration costs around:

• Ryzen 5950X: ~41 ns
• Ryzen 9980X: ~30 ns

So 1200-1700 is probably a more reasonable range here to get to the "~50 μs per cluster" number.

In #32545 the cost metric is changed, and aims for ~2 ns per "iteration", so after that PR, a number like 25000 should be more in line with what we want.

Changed to 1700.

In commit "Add sigops adjusted weight calculator"

This can be done more accurately (avoiding the rounding):

return {feerate.fee * WITNESS_SCALE_FACTOR, feerate.size};

Would that be desirable? It's used inside BlockAssembler::addChunks where it would be useful I think, but also in TxMempool where it's less clear to me if sticking to the old rounding-up behavior may be necessary.

One potential pitfall is that the resulting size member variable of the returned FeePerVSize will be misleading, so if it's used directly (not as a fraction) it could lead to wrong results.

Neat idea-- however it looks like I also use this in CTxMemPool::GetFeerateDiagram(), where we want the size to be accurate.

I do like getting rid of the rounding error, but perhaps that would be best accomplished by changing the internal units of things like the blockminfeerate to be in terms of fee-per-weight, in a followup PR?

Fair enough, and that's easier to do more granuarly then all-at-once guaranteeing that all uses of FeePerVSize are size-independent right now.

In commit "Add transactions to txgraph, but without cluster dependencies"

Could this repeat of the adjustment be avoided by swapping? I.e.,

mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); });
m_txgraph->SetTransactionFee(*it, it->GetModifiedFee());

If so, that would seem more natural.

Took this change (and the related one below). Planning to add a commit to the followup PR to get rid of the usage of mapTx.modify() here as well, now that the mempool doesn't keep any indices tied to feerate.

See also https://github.com/bitcoin/bitcoin/pull/33591/commits/7e715bc2749378f92284a1924f2079492adccf3f

In commit "Add transactions to txgraph, but without cluster dependencies"

Possibly the same can be done here as I suggested above, but with a separate call:

TxGraph::Ref ref(m_pool->m_txgraph->AddTransaction(FeePerWeight(fee, GetSigOpsAdjustedWeight(GetTransactionWeight(*tx), sigops_cost, ::nBytesPerSigOp))));
auto newit = m_to_add.emplace(std::move(ref), tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first;
if (delta) {
    m_to_add.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); });
    m_txgraph->SetTransactionFee(*newit, newit->GetModifiedFee());
}

moving all responsibility for deciding the modified fee inside UpdateModifiedFee.

Done.

In commit "Add transactions to txgraph, but without cluster dependencies"

There should always exist a txgraph staging when a ChangeSet is destroyed, right?

Assume(m_pool->m_txgraph->HaveStaging());
Assume(m_pool->m_have_changeset);
m_pool->m_txgraph->AbortStaging();
m_pool->m_have_changeset = false;

Ah, no -- if we Apply() the changes from a changeset then the staging goes away before the destructor is called.

In commit "squashme: fix locking so that mempool lock is held through subpackage destruction"

It seems strange to use the AndCleanup version here (both for MultipleTransactions here and SingleTransaction below), for two reasons:

• The AndCleanup version grabs its own m_pool.cs lock, but is called here in a place that already holds that lock.
• The call here in AcceptSubPackage is followed by a ClearSubPackageState(); below, which is already invoked inside the AndCleanup versions.

I can't say I fully understand the intended semantics here, so I may be off, but it's a red flag for me so want to point it out.

I'm planning to take @glozow's suggestion above (https://github.com/bitcoin/bitcoin/pull/33629#issuecomment-3499901560).

https://github.com/glozow/bitcoin/commit/85895de30cc09db2b1f6be5f1057f79a68a6ccc9#r170215881

note that the suggested branch has at least one behavior change

@instagibbs Good catch, thanks. (We should add a test for that usage of submitpackage!)

Good catch 👍

I'm very very happy to save this for a followup, but since the repeated locking and cleanups aren't ideal, I thought I'd give another approach a shot: https://github.com/glozow/bitcoin/tree/2025-10-mempoolaccept-layers

It keeps two routes, AcceptSingleTransaction and AcceptPackage (which allows packages of size 1). I had to make m_pool a public member of CTxMemPool (that felt bad at first, but the caller needs to provide it, so it seems reasonable to have access?).

One note is that only testmempoolaccept complains about "txn-already-in-mempool". Every other codepath (sendrawtransaction and the wallet) uses BroadcastTransaction which checks for presence in the mempool before calling ATMP. This means we could have testmempoolaccept manually return a "txn-already-in-mempool" error in the future, if we still want to consolidate it all into AcceptPackage.

It's not clear to me what the plan is, but if the approach isn't switched, the following patch compiles, looks more sensible, and seems to pass all tests:

diff --git a/src/validation.cpp b/src/validation.cpp
index ee46f99add8..37015ef69e6 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -1613,11 +1613,11 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptSubPackage(const std::vector<CTr
     AssertLockHeld(m_pool.cs);
     auto result = [&]() EXCLUSIVE_LOCKS_REQUIRED(::cs_main, m_pool.cs) {
         if (subpackage.size() > 1) {
-            return AcceptMultipleTransactionsAndCleanup(subpackage, args);
+            return AcceptMultipleTransactionsInternal(subpackage, args);
         }
         const auto& tx = subpackage.front();
         ATMPArgs single_args = ATMPArgs::SingleInPackageAccept(args);
-        const auto single_res = AcceptSingleTransactionAndCleanup(tx, single_args);
+        const auto single_res = AcceptSingleTransactionInternal(tx, single_args);
         PackageValidationState package_state_wrapped;
         if (single_res.m_result_type != MempoolAcceptResult::ResultType::VALID) {
             package_state_wrapped.Invalid(PackageValidationResult::PCKG_TX, "transaction failed");

I think @glozow's approach is definitely the right direction to go, but let's defer making that change to a future PR so that it can get more focused review, since it's not trivial to reason about how all this currently works. I'm taking @sipa's suggestion for now and will re-push.

In commit "Do not allow mempool clusters to exceed configured limits"

Given the Assume(!m_dependencies_process); above, is the reprocess comment correct here? It seems they're expected to not have been processed at all here.

I'll update the comment to match (and just as an fyi, there was some discussion that we might relax this assumption in the future but we can update the comment at that point).

Done in e6591f3ed

In commit "Select transactions for blocks based on chunk feerate"

This ought to be possible without a conversion to sats, something like:

if (chunk_feerate << m_options.blockMinFeeRate.GetFeePerVSize()) {

(where FeePerVSize CFeeRate::GetFeePerVSize() is a new member function to get the underlying fraction object)

I tried to improve this code in #33591, in commit https://github.com/bitcoin/bitcoin/commit/ee92868eb112ce59e385650f4bd0daf96eb715ab.

In commit "Reimplement GetTransactionAncestry() to not rely on cached data"

Nit, it seems cleaner to make these outputs rather than pass-by-reference inputs:

std::tuple<size_t, size_t, CAmount> CalculateAncestorData(const CTxMemPoolEntry& entry) const

which can then by used with structured bindings like (next commit):

auto [ancestor_count, ancestor_size, ancestor_fees] = CalculateAncestorData(e);

Redid this and CalculateDescendantData as you suggested.

In commit "Stop enforcing ancestor size/count limits"

I see this is addressed in a later commit already, but it was a bit confusing that this commit leaves descendants_to_remove in place, but doesn't use it anymore.

Should be fixed now in that commit.

In commit "Calculate descendant information for mempool RPC output on-the-fly"

Nit, seems cleaner to make these return values:

std::tuple<size_t, size_t, CAmount> CalculateDescendantData(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);

In commit "wallet: Replace max descendantsize with clustersize"

Nit: maybe call the new variable cluster_count (so it isn't confused with total vsize/weight of a cluster).

Done.

In commit "Expose cluster information via rpc"

This is one place where the size member of the output of ToFeePerVSize() matters (see earlier suggestion in this review to use (fee*4, size) for that function). However, perhaps it's worth using weights instead of vsizes in these RPCs anyway?

I believe we've always thought about feerate in our RPCs/user interface as being fee-per-vsize, so I'd be reluctant to make that change as a one-off here; if we don't follow through and make fee-per-weight the norm, then I think our interface would feel more confusing for users.

Wouldn't it be better to return the results by chunk instead of tx? eg:

{
  "vsize": 3500,
  "txcount": 25,
  "chunks": [
    {
      "chunk_fee": 0.00000143,
      "chunk_vsize": 140,
      "txs": [
        "c2b9bd0493e4b919ee34710ed411144e5b296d2004434fd0f932b8f3bff93f74"
      ]
    },
    {
      "chunk_fee": 0.00001001,
      "chunk_vsize": 976,
      "txs": [
        "0ec3b21902ac9091311eb8e0db3533fb54990c6f9987adbc4015a0fc79136910",
        "0dea2da2eaff995f54604d48716f531bf5cba8726b1551d4a213500224abc390",
        "b35a842ebde722d753804e0f4c0d7f19bd0a831ff1e3a5c989981d0f2871da62",
        "10c6edd55249aef3a00575880fcb8ba4890c9a5511b337392905e456cfc211ee",
        "ef648d13a9fb728810288e0d0122f6d71938e445bcc45a9a0bf6342fc7379425",
        "2eb8850755f61fcd39efb108cd93a68e532293ef6f48f7dd45cbbdbf8e8b8c7f"
      ]
    },
    ...
  ]
}

Would extracting the txgraph for a cluster a reasonable thing for the RPC interface to support? Having all the info for a cluster available in one place, without having to find each tx's entry in getrawmempool's output seems like a nice-to-have. Can obviously be a followup.

I agree your output looks better; I'm working on a commit that would implement this and will look to include it in #33591.

Also, see #33629 (review) -- I decided to go ahead and switch all the new cluster-mempool related RPCs to output chunk and cluster feerates using FeePerWeight, rather then FeePerVSize. This makes it so that we don't introduce rounding error in things like the feerate diagram output or chunk output, which would be confusing (as it could make it look like chunks are sorted in an incorrect order).

General comment on commit "fuzz: remove comparison between mini_miner block construction and miner"

This says this is preparation for a change to mini_miner, but it doesn't look like that change itself is part of this PR, or of #33591)?

I rewrote the commit message -- should be a bit better now.

(Also, it's worth noting that mini_miner is only used by the wallet, and we may want the wallet's behavior to change more slowly than with the next release, as it will take time for new software to be widely deployed.)

In commit "fuzz: remove comparison between mini_miner block construction and miner"

Ok. This commit belongs much earlier in the PR, though (just before "Select transactions for blocks based on chunk feerate"). Otherwise, the range of commits in between will fail fuzz tests if run long enough.

I moved this commit much earlier in the PR (to right before the commit: "Select transactions for blocks based on chunk feerate").

nit in cf1bcbbb8e1a4cb72cd37a44dcd8811db8a1958b: clustercount would be a better name. Looks like *size is used to mean aggregate size here in ancestorsize

Fixed in 607b61c8b186

in 6b791cc4ee9: this arg is not necessary

        self.extra_args = [['-limitdescendantsize=1000', '-limitancestorsize=1000', f'-limitancestorcount={CUSTOM_ANCESTOR_COUNT}', f'-limitdescendantcount={CUSTOM_DESCENDANT_COUNT}', "-limitclustersize=1000"]]

Done.

in 6b791cc4ee9eda5cccc310e3efb869af36057935

        /** Check if any cluster limits are exceeded. Returns true if pass, false if fail.*/
        bool CheckMemPoolPolicyLimits();

Done in da5ddd2002bfe46f56c45b260ebda226c2fd45ee

nitty nity in 6b791cc4ee9eda5cccc310e3efb869af36057935: it feels nice and future-proof to have annotations like

                m_txgraph->AddDependency(/*parent=*/*it, /*child=*/*childIter);

Done in da5ddd2002bf

187f78991fad3c521e55508a9d1901d3767c2f89: I'm not sure if there is coverage for the case we were trying to prevent with the old Rule 2:

diff --git a/test/functional/feature_rbf.py b/test/functional/feature_rbf.py
index 288a501d53e..f29e7a77803 100755
--- a/test/functional/feature_rbf.py
+++ b/test/functional/feature_rbf.py
@@ -13,6 +13,7 @@ from test_framework.messages import (
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import (
     assert_equal,
+    assert_greater_than,
     assert_greater_than_or_equal,
     assert_raises_rpc_error,
     get_fee,
@@ -39,6 +40,7 @@ class ReplaceByFeeTest(BitcoinTestFramework):
 
     def run_test(self):
         self.wallet = MiniWallet(self.nodes[0])
+        self.generate(self.nodes[0], 100)
 
         self.log.info("Running test simple doublespend...")
         self.test_simple_doublespend()
@@ -58,6 +60,9 @@ class ReplaceByFeeTest(BitcoinTestFramework):
         self.log.info("Running test new unconfirmed inputs...")
         self.test_new_unconfirmed_inputs()
 
+        self.log.info("Running test new unconfirmed input from low feerate tx...")
+        self.test_new_unconfirmed_input_with_low_feerate()
+
         self.log.info("Running test too many replacements...")
         self.test_too_many_replacements()
 
@@ -334,6 +339,21 @@ class ReplaceByFeeTest(BitcoinTestFramework):
         tx2_id = self.nodes[0].sendrawtransaction(tx2_hex, 0)
         assert tx2_id in self.nodes[0].getrawmempool()
 
+    def test_new_unconfirmed_input_with_low_feerate(self):
+        """Replacements that add new unconfirmed inputs are allowed, but must pass the feerate diagram check"""
+        confirmed_utxos = [self.make_utxo(self.nodes[0], int(1.1 * COIN)) for _ in range(3)]
+        large_low_feerate = self.wallet.create_self_transfer(utxo_to_spend=confirmed_utxos[0], target_vsize=10000, fee=Decimal("0.00001000"))
+        self.nodes[0].sendrawtransaction(large_low_feerate['hex'])
+        unconfirmed_utxo = large_low_feerate["new_utxo"]
+
+        # These two transactions are approximately the same size. The replacement tx pays twice the fee.
+        tx_to_replace = self.wallet.create_self_transfer_multi(utxos_to_spend=[confirmed_utxos[1], confirmed_utxos[2]], fee_per_output=2000)
+        tx_replacement = self.wallet.create_self_transfer_multi(utxos_to_spend=[confirmed_utxos[1], unconfirmed_utxo], fee_per_output=4000)
+        assert_greater_than(tx_replacement['fee']/tx_replacement['tx'].get_vsize(), tx_to_replace['fee']/tx_to_replace['tx'].get_vsize())
+
+        self.nodes[0].sendrawtransaction(tx_to_replace['hex'])
+        assert_raises_rpc_error(-26, "insufficient feerate: does not improve feerate diagram", self.nodes[0].sendrawtransaction, tx_replacement['hex'])
+
     def test_too_many_replacements(self):
         """Replacements that conflict with too many clusters are rejected"""
         # Try directly replacing transactions in more than MAX_REPLACEMENT_LIMIT

Incorporated in 017b21286a30374fc8ed21c3b8b92239c6cff55a

double-checked test that it would go through properly funded (works):

diff --git a/test/functional/feature_rbf.py b/test/functional/feature_rbf.py
index 4b2c89f3d9..10e3239a33 100755
--- a/test/functional/feature_rbf.py
+++ b/test/functional/feature_rbf.py
@@ -346,4 +346,7 @@ class ReplaceByFeeTest(BitcoinTestFramework):
         assert_raises_rpc_error(-26, "insufficient feerate: does not improve feerate diagram", self.nodes[0].sendrawtransaction, tx_replacement['hex'])
 
+        # But if child is sufficiently well-funded, it works
+        tx_replacement_sufficient = self.wallet.create_self_transfer_multi(utxos_to_spend=[confirmed_utxos[1], unconfirmed_utxo], fee_per_output=400_000)
+        self.nodes[0].sendrawtransaction(tx_replacement_sufficient['hex'])

Could also report txid? Seems strange to report the mempool entry by wtxid only, but its parents and children by txid only (prevout.hash for parents because it's cheap, GetTx().GetHash() for children because it's consistent?). Likewise looking up the cluster requires (and results in) txids.

I think generally you know what the txid is already, either because you would have queried for the mempool entry by txid, or because in the output of getrawmempool the results are keyed on txid? Is there a situation where we'd output a mempool entry and the user wouldn't know the txid?

When should someone use this RPC? (Otherwise, should it be hidden and/or marked as EXPERIMENTAL?)

was marked as hidden now

in a6c9f19c7d523fd6c2573e47e1992448b76f1977

Note to self/reviewers: we can't assert that the feerate diagram's last value matches cached txTotalSize, because it converts from weight to vsize happens per-chunk. These chunk vsizes can be smaller than the summed individual vsizes of the transactions.

In 91a44988a14037e9c923a789f1b7a616ff902ee1 Stop enforcing descendant size/count limits

After this commit, the limitdescendantcount set to 64 in feature_rbf.py test is no longer necessary. The limitancestorcount set to 64 is also not necessary since we stopped enforcing that in some previous commit.

This can be removed in the followup along with other stale once in feature_dbcrash.py and wallet_basic.py.

Done, and I also fixed feature_dbcrash.py.

Note that in wallet_basic.py, the usage of -limitancestorcount does have an effect on how the wallet will select inputs when constructing transactions.

in ca18549ee72: Perhaps set the expectation that there could be interface changes.

        {"hidden", &getmempoolfeeratediagram},

in ca18549ee72: Maybe creeped in during a rebase? This string is already on another line.

Fixed, thanks for catching!

in ca18549ee7288f16f7c93ef9f9cac932d29a0eba

(Happy to make this a followup, because there are other RPCs that need this change too)

        RPCResult{RPCResult::Type::NUM, "vsize", "Sigops-adjusted virtual transaction size: the maximum of BIP 141 virtual size and the transaction's sigops multiplied by -bytespersigop."

After further discussion I opted to make the new mempool RPC's output all chunk data in fee-per-adjusted-weight, rather than fee-per-vsize.

nit, also happy to put in followup

                            {RPCResult::Type::NUM, "vsize", "cumulative sigops-adjusted vsize"},
                            {RPCResult::Type::NUM, "fee", "cumulative modified fee"}

nit if you retouch: commit message for cec26203732 should replace "descendantsize" with "descendant count"

Fixed this commit message (8e49477e86b3089ea70d1f2659b9fd3a8a1f7db4).

nit in 1eddff0b0ab if you retouch: GetDescendantCount, GetAncestorCount would be more similar to existing naming, and slightly less confusing since the count includes the tx itself.

Fixed in b9a2039f51226dce2c4e38ce5f26eefee171744b.

If you retouch: f02ff837008 can be squashed into the commit above it. I think the diff may have shrunk over time - the commit message mentions addUnchecked which no longer exists in the codebase.

Squashed.

ccf7c5ac417 looks good and can be squashed

In commit "squashme: only output weight, not vsize, for cluster/chunk information"

Squash the squashme?

Squashed.