Merge bitcoin/bitcoin#25228: test: add BIP-125 rule 5 testcase with default mempool

687addaf136356e0f3698d6345c92d875e0a3362 test: add BIP-125 rule 5 testcase with default mempool (James O'Beirne)
6120e8e2871fecfec5ab3099c97e13951e062a4d test: allow passing sequence through create_self_transfer_multi (James O'Beirne)

Pull request description:

  Currently, we only test rule 5 of BIP-125 (replacement transactions cannot evict more than 100 transactions) by changing default mempool parameters to allow for more descendants. The current test works on a single transaction graph that has over 100 descendants.

  This patch adds a test to exercise rule 5 using the default mempool parameters. The case is a little more sophisticated: instead of working on a single transaction graph, it uses a replacement transaction to "unite" several UTXOs which join independent transaction graphs. The total number of transactions in these graphs sum to more than the max allowable replacement.

  I think the difference in transaction topology makes this a worthwhile testcase to have, setting aside the fact that this testcase works without having to use atypical mempool params.

  See also: [relevant discussion from IRC](https://www.erisian.com.au/bitcoin-core-dev/log-2022-05-27.html#l-126)

ACKs for top commit:
  laanwj:
    Code review ACK 687addaf136356e0f3698d6345c92d875e0a3362
  LarryRuane:
    ACK 687addaf136356e0f3698d6345c92d875e0a3362

Tree-SHA512: e589aeaf9d6f137d546b7809f8795d6f6043d87b15e97c2efe85b42ce8b49d977ee7d79440c542ca4b0b5ca2de527488029841a1ffc0d96c5771897df4b3f324

2 files changed, 106 insertions, 4 deletions

diff --git a/test/functional/feature_rbf.py b/test/functional/feature_rbf.py
index f0ed914461..a8492bd6eb 100755
--- a/test/functional/feature_rbf.py
+++ b/test/functional/feature_rbf.py
@@ -32,7 +32,7 @@ from test_framework.address import ADDRESS_BCRT1_UNSPENDABLE
 MAX_REPLACEMENT_LIMIT = 100
 class ReplaceByFeeTest(BitcoinTestFramework):
     def set_test_params(self):
-        self.num_nodes = 1
+        self.num_nodes = 2
         self.extra_args = [
             [
                 "-acceptnonstdtxn=1",
@@ -42,6 +42,9 @@ class ReplaceByFeeTest(BitcoinTestFramework):
                 "-limitdescendantcount=200",
                 "-limitdescendantsize=101",
             ],
+            # second node has default mempool parameters
+            [
+            ],
         ]
         self.supports_cli = False
 
@@ -73,6 +76,9 @@ class ReplaceByFeeTest(BitcoinTestFramework):
         self.log.info("Running test too many replacements...")
         self.test_too_many_replacements()
 
+        self.log.info("Running test too many replacements using default mempool params...")
+        self.test_too_many_replacements_with_default_mempool_params()
+
         self.log.info("Running test opt-in...")
         self.test_opt_in()
 
@@ -397,6 +403,94 @@ class ReplaceByFeeTest(BitcoinTestFramework):
         double_tx_hex = double_tx.serialize().hex()
         self.nodes[0].sendrawtransaction(double_tx_hex, 0)
 
+    def test_too_many_replacements_with_default_mempool_params(self):
+        """
+        Test rule 5 of BIP125 (do not allow replacements that cause more than 100
+        evictions) without having to rely on non-default mempool parameters.
+
+        In order to do this, create a number of "root" UTXOs, and then hang
+        enough transactions off of each root UTXO to exceed the MAX_REPLACEMENT_LIMIT.
+        Then create a conflicting RBF replacement transaction.
+        """
+        normal_node = self.nodes[1]
+        wallet = MiniWallet(normal_node)
+        wallet.rescan_utxos()
+        # Clear mempools to avoid cross-node sync failure.
+        for node in self.nodes:
+            self.generate(node, 1)
+
+        # This has to be chosen so that the total number of transactions can exceed
+        # MAX_REPLACEMENT_LIMIT without having any one tx graph run into the descendant
+        # limit; 10 works.
+        num_tx_graphs = 10
+
+        # (Number of transactions per graph, BIP125 rule 5 failure expected)
+        cases = [
+            # Test the base case of evicting fewer than MAX_REPLACEMENT_LIMIT
+            # transactions.
+            ((MAX_REPLACEMENT_LIMIT // num_tx_graphs) - 1, False),
+
+            # Test hitting the rule 5 eviction limit.
+            (MAX_REPLACEMENT_LIMIT // num_tx_graphs, True),
+        ]
+
+        for (txs_per_graph, failure_expected) in cases:
+            self.log.debug(f"txs_per_graph: {txs_per_graph}, failure: {failure_expected}")
+            # "Root" utxos of each txn graph that we will attempt to double-spend with
+            # an RBF replacement.
+            root_utxos = []
+
+            # For each root UTXO, create a package that contains the spend of that
+            # UTXO and `txs_per_graph` children tx.
+            for graph_num in range(num_tx_graphs):
+                root_utxos.append(wallet.get_utxo())
+
+                optin_parent_tx = wallet.send_self_transfer_multi(
+                    from_node=normal_node,
+                    sequence=BIP125_SEQUENCE_NUMBER,
+                    utxos_to_spend=[root_utxos[graph_num]],
+                    num_outputs=txs_per_graph,
+                )
+                assert_equal(True, normal_node.getmempoolentry(optin_parent_tx['txid'])['bip125-replaceable'])
+                new_utxos = optin_parent_tx['new_utxos']
+
+                for utxo in new_utxos:
+                    # Create spends for each output from the "root" of this graph.
+                    child_tx = wallet.send_self_transfer(
+                        from_node=normal_node,
+                        utxo_to_spend=utxo,
+                    )
+
+                    assert normal_node.getmempoolentry(child_tx['txid'])
+
+            num_txs_invalidated = len(root_utxos) + (num_tx_graphs * txs_per_graph)
+
+            if failure_expected:
+                assert num_txs_invalidated > MAX_REPLACEMENT_LIMIT
+            else:
+                assert num_txs_invalidated <= MAX_REPLACEMENT_LIMIT
+
+            # Now attempt to submit a tx that double-spends all the root tx inputs, which
+            # would invalidate `num_txs_invalidated` transactions.
+            double_tx = wallet.create_self_transfer_multi(
+                from_node=normal_node,
+                utxos_to_spend=root_utxos,
+                fee_per_output=10_000_000,  # absurdly high feerate
+            )
+            tx_hex = double_tx.serialize().hex()
+
+            if failure_expected:
+                assert_raises_rpc_error(
+                    -26, "too many potential replacements", normal_node.sendrawtransaction, tx_hex, 0)
+            else:
+                txid = normal_node.sendrawtransaction(tx_hex, 0)
+                assert normal_node.getmempoolentry(txid)
+
+        # Clear the mempool once finished, and rescan the other nodes' wallet
+        # to account for the spends we've made on `normal_node`.
+        self.generate(normal_node, 1)
+        self.wallet.rescan_utxos()
+
     def test_opt_in(self):
         """Replacing should only work if orig tx opted in"""
         tx0_outpoint = self.make_utxo(self.nodes[0], int(1.1 * COIN))
diff --git a/test/functional/test_framework/wallet.py b/test/functional/test_framework/wallet.py
index 336b2afe26..e43dd9f61a 100644
--- a/test/functional/test_framework/wallet.py
+++ b/test/functional/test_framework/wallet.py
@@ -10,6 +10,7 @@ from enum import Enum
 from random import choice
 from typing import (
     Any,
+    List,
     Optional,
 )
 from test_framework.address import (
@@ -147,7 +148,7 @@ class MiniWallet:
     def get_address(self):
         return self._address
 
-    def get_utxo(self, *, txid: str = '', vout: Optional[int] = None, mark_as_spent=True):
+    def get_utxo(self, *, txid: str = '', vout: Optional[int] = None, mark_as_spent=True) -> dict:
         """
         Returns a utxo and marks it as spent (pops it from the internal list)
 
@@ -215,14 +216,21 @@ class MiniWallet:
         return {'new_utxos': [self.get_utxo(txid=txid, vout=vout) for vout in range(len(tx.vout))],
                 'txid': txid, 'hex': tx.serialize().hex(), 'tx': tx}
 
-    def create_self_transfer_multi(self, *, from_node, utxos_to_spend=None, num_outputs=1, fee_per_output=1000):
+    def create_self_transfer_multi(
+            self, *, from_node,
+            utxos_to_spend: Optional[List[dict]] = None,
+            num_outputs=1,
+            sequence=0,
+            fee_per_output=1000):
         """
         Create and return a transaction that spends the given UTXOs and creates a
         certain number of outputs with equal amounts.
         """
         utxos_to_spend = utxos_to_spend or [self.get_utxo()]
         # create simple tx template (1 input, 1 output)
-        tx = self.create_self_transfer(fee_rate=0, from_node=from_node, utxo_to_spend=utxos_to_spend[0], mempool_valid=False)['tx']
+        tx = self.create_self_transfer(
+            fee_rate=0, from_node=from_node,
+            utxo_to_spend=utxos_to_spend[0], sequence=sequence, mempool_valid=False)['tx']
 
         # duplicate inputs, witnesses and outputs
         tx.vin = [deepcopy(tx.vin[0]) for _ in range(len(utxos_to_spend))]