Merge bitcoin/bitcoin#22796: RBF move (1/3): extract BIP125 Rule 5 into policy/rbf

f293c68be0469894c988711559f5528020c0ff71 MOVEONLY: getting mempool conflicts to policy/rbf (glozow)
8d7179633552f58ca0d23305196dcb4249b6dce7 [validation] quit RBF logic earlier and separate loops (glozow)
badb9b11a6f7e1e693cecc8cd5aae55a197d70e2 call SignalsOptInRBF instead of checking all inputs (glozow)
e0df41d7d584b854c2914d4afe7b21e0af3fbf69 [validation] default conflicting fees and size to 0 (glozow)
b001b9f6de7a039a468cf0f9645f3f0a430fa889 MOVEONLY: BIP125 max conflicts limit to policy/rbf.h (glozow)

Pull request description:

  See #22675 for motivation, this is one chunk of it. It extracts some BIP125 logic into policy/rbf:

  - Defines a constant for specifying the maximum number of mempool entries we'd consider replacing by RBF
  - Calls the available `SignalsOptInRBF` function instead of manually iterating through inputs
  - Moves the logic for getting the list of conflicting mempool entries to a helper function
  - Also does a bit of preparation for future moves - moving declarations around, etc
  Also see #22677 for addressing the circular dependency.

ACKs for top commit:
  jnewbery:
    Code review ACK f293c68be0469894c988711559f5528020c0ff71
  theStack:
    Code-review ACK f293c68be0469894c988711559f5528020c0ff71 📔
  ariard:
    ACK f293c68b

Tree-SHA512: a60370994569cfc91d4b2ad5e94542d4855a48927ae8b174880216074e4fa50d4523dd4ee36efdd6edf2bf7adb87a8beff9c3aaaf6dd323b286b287233e63790

4 files changed, 85 insertions, 51 deletions

diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp
index 8125b41c41..43624c7993 100644
--- a/src/policy/rbf.cpp
+++ b/src/policy/rbf.cpp
@@ -3,6 +3,10 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <policy/rbf.h>
+
+#include <policy/settings.h>
+#include <tinyformat.h>
+#include <util/moneystr.h>
 #include <util/rbf.h>
 
 RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool)
@@ -42,3 +46,34 @@ RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx)
     // If we don't have a local mempool we can only check the transaction itself.
     return SignalsOptInRBF(tx) ? RBFTransactionState::REPLACEABLE_BIP125 : RBFTransactionState::UNKNOWN;
 }
+
+bool GetEntriesForConflicts(const CTransaction& tx,
+                            CTxMemPool& m_pool,
+                            const CTxMemPool::setEntries& setIterConflicting,
+                            CTxMemPool::setEntries& allConflicting,
+                            std::string& err_string)
+{
+    AssertLockHeld(m_pool.cs);
+    const uint256 hash = tx.GetHash();
+    uint64_t nConflictingCount = 0;
+    for (const auto& mi : setIterConflicting) {
+        nConflictingCount += mi->GetCountWithDescendants();
+        // This potentially overestimates the number of actual descendants
+        // but we just want to be conservative to avoid doing too much
+        // work.
+        if (nConflictingCount > MAX_BIP125_REPLACEMENT_CANDIDATES) {
+            err_string = strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
+                        hash.ToString(),
+                        nConflictingCount,
+                        MAX_BIP125_REPLACEMENT_CANDIDATES);
+            return false;
+        }
+    }
+    // If not too many to replace, then calculate the set of
+    // transactions that would have to be evicted
+    for (CTxMemPool::txiter it : setIterConflicting) {
+        m_pool.CalculateDescendants(it, allConflicting);
+    }
+    return true;
+}
+
diff --git a/src/policy/rbf.h b/src/policy/rbf.h
index e078070c1c..a67e9058df 100644
--- a/src/policy/rbf.h
+++ b/src/policy/rbf.h
@@ -7,6 +7,10 @@
 
 #include <txmempool.h>
 
+/** Maximum number of transactions that can be replaced by BIP125 RBF (Rule #5). This includes all
+ * mempool conflicts and their descendants. */
+static constexpr uint32_t MAX_BIP125_REPLACEMENT_CANDIDATES{100};
+
 /** The rbf state of unconfirmed transactions */
 enum class RBFTransactionState {
     /** Unconfirmed tx that does not signal rbf and is not in the mempool */
@@ -31,4 +35,19 @@ enum class RBFTransactionState {
 RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool) EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
 RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx);
 
+/** Get all descendants of setIterConflicting. Also enforce BIP125 Rule #5, "The number of original
+ * transactions to be replaced and their descendant transactions which will be evicted from the
+ * mempool must not exceed a total of 100 transactions." Quit as early as possible. There cannot be
+ * more than MAX_BIP125_REPLACEMENT_CANDIDATES potential entries.
+ * @param[in]   setIterConflicting  The set of iterators to mempool entries.
+ * @param[out]  err_string          Used to return errors, if any.
+ * @param[out]  allConflicting      Populated with all the mempool entries that would be replaced,
+ *                                  which includes descendants of setIterConflicting. Not cleared at
+ *                                  the start; any existing mempool entries will remain in the set.
+ * @returns false if Rule 5 is broken.
+ */
+bool GetEntriesForConflicts(const CTransaction& tx, CTxMemPool& m_pool,
+                            const CTxMemPool::setEntries& setIterConflicting,
+                            CTxMemPool::setEntries& allConflicting,
+                            std::string& err_string) EXCLUSIVE_LOCKS_REQUIRED(m_pool.cs);
 #endif // BITCOIN_POLICY_RBF_H
diff --git a/src/util/rbf.h b/src/util/rbf.h
index 6a20b37de5..4eb44b904f 100644
--- a/src/util/rbf.h
+++ b/src/util/rbf.h
@@ -11,8 +11,15 @@ class CTransaction;
 
 static const uint32_t MAX_BIP125_RBF_SEQUENCE = 0xfffffffd;
 
-// Check whether the sequence numbers on this transaction are signaling
-// opt-in to replace-by-fee, according to BIP 125
+/** Check whether the sequence numbers on this transaction are signaling
+* opt-in to replace-by-fee, according to BIP 125.
+* Allow opt-out of transaction replacement by setting
+* nSequence > MAX_BIP125_RBF_SEQUENCE (SEQUENCE_FINAL-2) on all inputs.
+*
+* SEQUENCE_FINAL-1 is picked to still allow use of nLockTime by
+* non-replaceable transactions. All inputs rather than just one
+* is for the sake of multi-party protocols, where we don't
+* want a single party to be able to disable replacement. */
 bool SignalsOptInRBF(const CTransaction &tx);
 
 #endif // BITCOIN_UTIL_RBF_H
diff --git a/src/validation.cpp b/src/validation.cpp
index 9944e31557..753b824167 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -25,6 +25,7 @@
 #include <node/coinstats.h>
 #include <node/ui_interface.h>
 #include <policy/policy.h>
+#include <policy/rbf.h>
 #include <policy/settings.h>
 #include <pow.h>
 #include <primitives/block.h>
@@ -474,8 +475,10 @@ private:
         bool m_replacement_transaction;
         CAmount m_base_fees;
         CAmount m_modified_fees;
-        CAmount m_conflicting_fees;
-        size_t m_conflicting_size;
+        /** Total modified fees of all transactions being replaced. */
+        CAmount m_conflicting_fees{0};
+        /** Total virtual size of all transactions being replaced. */
+        size_t m_conflicting_size{0};
 
         const CTransactionRef& m_ptx;
         const uint256& m_hash;
@@ -602,14 +605,6 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
             }
             if (!setConflicts.count(ptxConflicting->GetHash()))
             {
-                // Allow opt-out of transaction replacement by setting
-                // nSequence > MAX_BIP125_RBF_SEQUENCE (SEQUENCE_FINAL-2) on all inputs.
-                //
-                // SEQUENCE_FINAL-1 is picked to still allow use of nLockTime by
-                // non-replaceable transactions. All inputs rather than just one
-                // is for the sake of multi-party protocols, where we don't
-                // want a single party to be able to disable replacement.
-                //
                 // Transactions that don't explicitly signal replaceability are
                 // *not* replaceable with the current logic, even if one of their
                 // unconfirmed ancestors signals replaceability. This diverges
@@ -617,16 +612,7 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
                 // Applications relying on first-seen mempool behavior should
                 // check all unconfirmed ancestors; otherwise an opt-in ancestor
                 // might be replaced, causing removal of this descendant.
-                bool fReplacementOptOut = true;
-                for (const CTxIn &_txin : ptxConflicting->vin)
-                {
-                    if (_txin.nSequence <= MAX_BIP125_RBF_SEQUENCE)
-                    {
-                        fReplacementOptOut = false;
-                        break;
-                    }
-                }
-                if (fReplacementOptOut) {
+                if (!SignalsOptInRBF(*ptxConflicting)) {
                     return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "txn-mempool-conflict");
                 }
 
@@ -796,11 +782,6 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
         }
     }
 
-    // Check if it's economically rational to mine this transaction rather
-    // than the ones it replaces.
-    nConflictingFees = 0;
-    nConflictingSize = 0;
-    uint64_t nConflictingCount = 0;
 
     // If we don't hold the lock allConflicting might be incomplete; the
     // subsequent RemoveStaged() and addUnchecked() calls don't guarantee
@@ -808,9 +789,8 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     fReplacementTransaction = setConflicts.size();
     if (fReplacementTransaction)
     {
+        std::string err_string;
         CFeeRate newFeeRate(nModifiedFees, nSize);
-        std::set<uint256> setConflictsParents;
-        const int maxDescendantsToVisit = 100;
         for (const auto& mi : setIterConflicting) {
             // Don't allow the replacement to reduce the feerate of the
             // mempool.
@@ -835,33 +815,26 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
                             newFeeRate.ToString(),
                             oldFeeRate.ToString()));
             }
+        }
+
+        // Calculate all conflicting entries and enforce Rule #5.
+        if (!GetEntriesForConflicts(tx, m_pool, setIterConflicting, allConflicting, err_string)) {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "too many potential replacements", err_string);
+        }
+
+        // Check if it's economically rational to mine this transaction rather
+        // than the ones it replaces.
+        for (CTxMemPool::txiter it : allConflicting) {
+            nConflictingFees += it->GetModifiedFee();
+            nConflictingSize += it->GetTxSize();
+        }
 
+        std::set<uint256> setConflictsParents;
+        for (const auto& mi : setIterConflicting) {
             for (const CTxIn &txin : mi->GetTx().vin)
             {
                 setConflictsParents.insert(txin.prevout.hash);
             }
-
-            nConflictingCount += mi->GetCountWithDescendants();
-        }
-        // This potentially overestimates the number of actual descendants
-        // but we just want to be conservative to avoid doing too much
-        // work.
-        if (nConflictingCount <= maxDescendantsToVisit) {
-            // If not too many to replace, then calculate the set of
-            // transactions that would have to be evicted
-            for (CTxMemPool::txiter it : setIterConflicting) {
-                m_pool.CalculateDescendants(it, allConflicting);
-            }
-            for (CTxMemPool::txiter it : allConflicting) {
-                nConflictingFees += it->GetModifiedFee();
-                nConflictingSize += it->GetTxSize();
-            }
-        } else {
-            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "too many potential replacements",
-                    strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
-                        hash.ToString(),
-                        nConflictingCount,
-                        maxDescendantsToVisit));
         }
 
         for (unsigned int j = 0; j < tx.vin.size(); j++)