Merge bitcoin/bitcoin#22539: Re-include RBF replacement txs in fee estimation

3b613722f6b895d7b268b3f878fddfc888381226 Add release notes for fee est with replacement txs (Antoine Poinsot)
45564065627ada5dfadff13bc32bc672a4edf152 qa: test fee estimation with replacement transactions (Antoine Poinsot)
053415b297b8665f2d2c4dce7c2c54bcc5298ef4 qa: split run_test into smaller parts (Antoine Poinsot)
06c5ce9714f7090bfb494309980f375975b7a00e Re-include RBF replacement txs in fee estimation (Antoine Poinsot)

Pull request description:

  This effectively reverts #9519.

  RBF is now largely in use on the network (signaled for by around 20% of
  all transactions on average) and replacement logic is implemented in
  most end-user wallets. The rate of replaced transactions is also
  expected to rise as fee-bumping techniques are being developed for
  pre-signed transaction ("L2") protocols.

ACKs for top commit:
  prayank23:
    reACK https://github.com/bitcoin/bitcoin/pull/22539/commits/3b613722f6b895d7b268b3f878fddfc888381226
  Zero-1729:
    re-ACK 3b613722f6b895d7b268b3f878fddfc888381226
  benthecarman:
    reACK 3b613722f6b895d7b268b3f878fddfc888381226
  glozow:
    ACK 3b613722f6b895d7b268b3f878fddfc888381226
  theStack:
    re-ACK 3b613722f6b895d7b268b3f878fddfc888381226 🍪

Tree-SHA512: a6146d15c80ff4ba9249314b0ef953a66a15673e61b8f98979642814f1b169b5695e330e3ee069fa9a7e4d1f8aa10e1dcb7f9aa79181cea5a4c4dbcaf5483023

3 files changed, 131 insertions, 35 deletions

diff --git a/doc/release-notes-22539.md b/doc/release-notes-22539.md
new file mode 100644
index 0000000000..9f56071451
--- /dev/null
+++ b/doc/release-notes-22539.md
@@ -0,0 +1,8 @@
+Notable changes
+===============
+
+P2P and network changes
+-----------------------
+
+- Fee estimation now takes the feerate of replacement (RBF) transactions into
+  account.
diff --git a/src/validation.cpp b/src/validation.cpp
index 880a01eb7d..14dcd2c24b 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -474,7 +474,6 @@ private:
         std::unique_ptr<CTxMemPoolEntry> m_entry;
         std::list<CTransactionRef> m_replaced_transactions;
 
-        bool m_replacement_transaction;
         CAmount m_base_fees;
         CAmount m_modified_fees;
         /** Total modified fees of all transactions being replaced. */
@@ -556,7 +555,6 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     CTxMemPool::setEntries& allConflicting = ws.m_all_conflicting;
     CTxMemPool::setEntries& setAncestors = ws.m_ancestors;
     std::unique_ptr<CTxMemPoolEntry>& entry = ws.m_entry;
-    bool& fReplacementTransaction = ws.m_replacement_transaction;
     CAmount& nModifiedFees = ws.m_modified_fees;
     CAmount& nConflictingFees = ws.m_conflicting_fees;
     size_t& nConflictingSize = ws.m_conflicting_size;
@@ -779,8 +777,7 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     }
 
 
-    fReplacementTransaction = setConflicts.size();
-    if (fReplacementTransaction) {
+    if (!setConflicts.empty()) {
         CFeeRate newFeeRate(nModifiedFees, nSize);
         // It's possible that the replacement pays more fees than its direct conflicts but not more
         // than all conflicts (i.e. the direct conflicts have high-fee descendants). However, if the
@@ -885,7 +882,6 @@ bool MemPoolAccept::Finalize(const ATMPArgs& args, Workspace& ws)
     const CAmount& nModifiedFees = ws.m_modified_fees;
     const CAmount& nConflictingFees = ws.m_conflicting_fees;
     const size_t& nConflictingSize = ws.m_conflicting_size;
-    const bool fReplacementTransaction = ws.m_replacement_transaction;
     std::unique_ptr<CTxMemPoolEntry>& entry = ws.m_entry;
 
     // Remove conflicting transactions from the mempool
@@ -901,11 +897,10 @@ bool MemPoolAccept::Finalize(const ATMPArgs& args, Workspace& ws)
     m_pool.RemoveStaged(allConflicting, false, MemPoolRemovalReason::REPLACED);
 
     // This transaction should only count for fee estimation if:
-    // - it isn't a BIP 125 replacement transaction (may not be widely supported)
     // - it's not being re-added during a reorg which bypasses typical mempool fee limits
     // - the node is not behind
     // - the transaction is not dependent on any other transactions in the mempool
-    bool validForFeeEstimation = !fReplacementTransaction && !bypass_limits && IsCurrentForFeeEstimation(m_active_chainstate) && m_pool.HasNoInputsOf(tx);
+    bool validForFeeEstimation = !bypass_limits && IsCurrentForFeeEstimation(m_active_chainstate) && m_pool.HasNoInputsOf(tx);
 
     // Store transaction in memory
     m_pool.addUnchecked(*entry, setAncestors, validForFeeEstimation);
diff --git a/test/functional/feature_fee_estimation.py b/test/functional/feature_fee_estimation.py
index 9c225dc687..ac00db8ff0 100755
--- a/test/functional/feature_fee_estimation.py
+++ b/test/functional/feature_fee_estimation.py
@@ -4,6 +4,7 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 """Test fee estimation code."""
 from decimal import Decimal
+import os
 import random
 
 from test_framework.messages import (
@@ -155,6 +156,21 @@ def check_estimates(node, fees_seen):
     check_raw_estimates(node, fees_seen)
     check_smart_estimates(node, fees_seen)
 
+
+def send_tx(node, utxo, feerate):
+    """Broadcast a 1in-1out transaction with a specific input and feerate (sat/vb)."""
+    overhead, op, scriptsig, nseq, value, spk = 10, 36, 5, 4, 8, 24
+    tx_size = overhead + op + scriptsig + nseq + value + spk
+    fee = tx_size * feerate
+
+    tx = CTransaction()
+    tx.vin = [CTxIn(COutPoint(int(utxo["txid"], 16), utxo["vout"]), SCRIPT_SIG[utxo["vout"]])]
+    tx.vout = [CTxOut(int(utxo["amount"] * COIN) - fee, P2SH_1)]
+    txid = node.sendrawtransaction(tx.serialize().hex())
+
+    return txid
+
+
 class EstimateFeeTest(BitcoinTestFramework):
     def set_test_params(self):
         self.num_nodes = 3
@@ -212,20 +228,16 @@ class EstimateFeeTest(BitcoinTestFramework):
                     newmem.append(utx)
             self.memutxo = newmem
 
-    def run_test(self):
-        self.log.info("This test is time consuming, please be patient")
-        self.log.info("Splitting inputs so we can generate tx's")
-
-        # Start node0
-        self.start_node(0)
+    def initial_split(self, node):
+        """Split two coinbase UTxOs into many small coins"""
         self.txouts = []
         self.txouts2 = []
         # Split a coinbase into two transaction puzzle outputs
-        split_inputs(self.nodes[0], self.nodes[0].listunspent(0), self.txouts, True)
+        split_inputs(node, node.listunspent(0), self.txouts, True)
 
         # Mine
-        while len(self.nodes[0].getrawmempool()) > 0:
-            self.generate(self.nodes[0], 1)
+        while len(node.getrawmempool()) > 0:
+            self.generate(node, 1)
 
         # Repeatedly split those 2 outputs, doubling twice for each rep
         # Use txouts to monitor the available utxo, since these won't be tracked in wallet
@@ -233,27 +245,19 @@ class EstimateFeeTest(BitcoinTestFramework):
         while reps < 5:
             # Double txouts to txouts2
             while len(self.txouts) > 0:
-                split_inputs(self.nodes[0], self.txouts, self.txouts2)
-            while len(self.nodes[0].getrawmempool()) > 0:
-                self.generate(self.nodes[0], 1)
+                split_inputs(node, self.txouts, self.txouts2)
+            while len(node.getrawmempool()) > 0:
+                self.generate(node, 1)
             # Double txouts2 to txouts
             while len(self.txouts2) > 0:
-                split_inputs(self.nodes[0], self.txouts2, self.txouts)
-            while len(self.nodes[0].getrawmempool()) > 0:
-                self.generate(self.nodes[0], 1)
+                split_inputs(node, self.txouts2, self.txouts)
+            while len(node.getrawmempool()) > 0:
+                self.generate(node, 1)
             reps += 1
-        self.log.info("Finished splitting")
-
-        # Now we can connect the other nodes, didn't want to connect them earlier
-        # so the estimates would not be affected by the splitting transactions
-        self.start_node(1)
-        self.start_node(2)
-        self.connect_nodes(1, 0)
-        self.connect_nodes(0, 2)
-        self.connect_nodes(2, 1)
-
-        self.sync_all()
 
+    def sanity_check_estimates_range(self):
+        """Populate estimation buckets, assert estimates are in a sane range and
+        are strictly increasing as the target decreases."""
         self.fees_per_kb = []
         self.memutxo = []
         self.confutxo = self.txouts  # Start with the set of confirmed txouts after splitting
@@ -279,11 +283,100 @@ class EstimateFeeTest(BitcoinTestFramework):
         self.log.info("Final estimates after emptying mempools")
         check_estimates(self.nodes[1], self.fees_per_kb)
 
-        # check that the effective feerate is greater than or equal to the mempoolminfee even for high mempoolminfee
-        self.log.info("Test fee rate estimation after restarting node with high MempoolMinFee")
+    def test_feerate_mempoolminfee(self):
         high_val = 3*self.nodes[1].estimatesmartfee(1)['feerate']
         self.restart_node(1, extra_args=[f'-minrelaytxfee={high_val}'])
         check_estimates(self.nodes[1], self.fees_per_kb)
+        self.restart_node(1)
+
+    def sanity_check_rbf_estimates(self, utxos):
+        """During 5 blocks, broadcast low fee transactions. Only 10% of them get
+        confirmed and the remaining ones get RBF'd with a high fee transaction at
+        the next block.
+        The block policy estimator should return the high feerate.
+        """
+        # The broadcaster and block producer
+        node = self.nodes[0]
+        miner = self.nodes[1]
+        # In sat/vb
+        low_feerate = 1
+        high_feerate = 10
+        # Cache the utxos of which to replace the spender after it failed to get
+        # confirmed
+        utxos_to_respend = []
+        txids_to_replace = []
+
+        assert len(utxos) >= 250
+        for _ in range(5):
+            # Broadcast 45 low fee transactions that will need to be RBF'd
+            for _ in range(45):
+                u = utxos.pop(0)
+                txid = send_tx(node, u, low_feerate)
+                utxos_to_respend.append(u)
+                txids_to_replace.append(txid)
+            # Broadcast 5 low fee transaction which don't need to
+            for _ in range(5):
+                send_tx(node, utxos.pop(0), low_feerate)
+            # Mine the transactions on another node
+            self.sync_mempools(wait=.1, nodes=[node, miner])
+            for txid in txids_to_replace:
+                miner.prioritisetransaction(txid=txid, fee_delta=-COIN)
+            self.generate(miner, 1)
+            self.sync_blocks(wait=.1, nodes=[node, miner])
+            # RBF the low-fee transactions
+            while True:
+                try:
+                    u = utxos_to_respend.pop(0)
+                    send_tx(node, u, high_feerate)
+                except IndexError:
+                    break
+
+        # Mine the last replacement txs
+        self.sync_mempools(wait=.1, nodes=[node, miner])
+        self.generate(miner, 1)
+        self.sync_blocks(wait=.1, nodes=[node, miner])
+
+        # Only 10% of the transactions were really confirmed with a low feerate,
+        # the rest needed to be RBF'd. We must return the 90% conf rate feerate.
+        high_feerate_kvb = Decimal(high_feerate) / COIN * 10**3
+        est_feerate = node.estimatesmartfee(2)["feerate"]
+        assert est_feerate == high_feerate_kvb
+
+    def run_test(self):
+        self.log.info("This test is time consuming, please be patient")
+        self.log.info("Splitting inputs so we can generate tx's")
+
+        # Split two coinbases into many small utxos
+        self.start_node(0)
+        self.initial_split(self.nodes[0])
+        self.log.info("Finished splitting")
+
+        # Now we can connect the other nodes, didn't want to connect them earlier
+        # so the estimates would not be affected by the splitting transactions
+        self.start_node(1)
+        self.start_node(2)
+        self.connect_nodes(1, 0)
+        self.connect_nodes(0, 2)
+        self.connect_nodes(2, 1)
+        self.sync_all()
+
+        self.log.info("Testing estimates with single transactions.")
+        self.sanity_check_estimates_range()
+
+        # check that the effective feerate is greater than or equal to the mempoolminfee even for high mempoolminfee
+        self.log.info("Test fee rate estimation after restarting node with high MempoolMinFee")
+        self.test_feerate_mempoolminfee()
+
+        self.log.info("Restarting node with fresh estimation")
+        self.stop_node(0)
+        fee_dat = os.path.join(self.nodes[0].datadir, self.chain, "fee_estimates.dat")
+        os.remove(fee_dat)
+        self.start_node(0)
+        self.connect_nodes(0, 1)
+        self.connect_nodes(0, 2)
+
+        self.log.info("Testing estimates with RBF.")
+        self.sanity_check_rbf_estimates(self.confutxo + self.memutxo)
 
         self.log.info("Testing that fee estimation is disabled in blocksonly.")
         self.restart_node(0, ["-blocksonly"])