Merge bitcoin/bitcoin#22675: RBF move 2/3: extract RBF logic into policy/rbf

32748da0f47f7aa9fba78dfb29aa426b14f15624 whitespace fixups after move and scripted-diff (glozow)
fa47622e8dc66bec9ea690aec3f0999108d76dc9 scripted-diff: rename variables in policy/rbf (glozow)
ac761f0a23c9c469fa00885edf3d5c9ae7c6a2b3 MOVEONLY: fee checks (Rules 3 and 4) to policy/rbf (glozow)
9c2f9f89846264b503d5573341bb78cf609cbc5e MOVEONLY: check that fees > direct conflicts to policy/rbf (glozow)
3f033f01a6b0f7772ae1b21044903b8f4249ad08 MOVEONLY: check for disjoint conflicts and ancestors to policy/rbf (glozow)
7b60c02b7d5e2ab12288393d2258873ebb26d811 MOVEONLY: BIP125 Rule 2 to policy/rbf (glozow)
f8ad2a57c61d1e817e2445226688e03080fc8688 Make GetEntriesForConflicts return std::optional (glozow)

Pull request description:

  This PR does not change behavior. It extracts the BIP125 logic into helper functions (and puts them in the policy/rbf* files). This enables three things - I think each one individually is pretty good:

  - Implementation of package RBF (see #22290). I want it to be as close to BIP125 as possible so that it doesn't become a distinct fee-bumping mechanism. Doing these move-only commits first means the diff is mostly mechanical to review, and I just need to create a function that mirrors the single transaction validation.
  - We will be able to isolate and test our RBF logic alone. Recently, there have been some discussions on discrepancies between our code and BIP125, as well as proposals for improving it. Generally, I think making this code more modular and de-bloating validation.cpp is probably a good idea.
  - Witness Replacement (replacing same-txid-different-wtxid when the witness is significantly smaller and therefore higher feerate) in a BIP125-similar way. Hopefully it can just be implemented with calls to the rbf functions (i.e. `PaysForRBF`) and an edit to the relevant mempool entries.

ACKs for top commit:
  mjdietzx:
    ACK 32748da0f47f7aa9fba78dfb29aa426b14f15624
  theStack:
    Code-review ACK 32748da0f47f7aa9fba78dfb29aa426b14f15624 📐
  MarcoFalke:
    review ACK 32748da0f47f7aa9fba78dfb29aa426b14f15624 🦇

Tree-SHA512: d89985c8b4b42b54861018deb89468e04968c85a3fb1113bbcb2eb2609577bc4fd9bf254593b5bd0e7ab059a0fa8192d1a903b00f77e6f120c7a80488ffcbfc0

4 files changed, 189 insertions, 131 deletions

diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp
index 43624c7993..15527afb8a 100644
--- a/src/policy/rbf.cpp
+++ b/src/policy/rbf.cpp
@@ -13,7 +13,7 @@ RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool)
 {
     AssertLockHeld(pool.cs);
 
-    CTxMemPool::setEntries setAncestors;
+    CTxMemPool::setEntries ancestors;
 
     // First check the transaction itself.
     if (SignalsOptInRBF(tx)) {
@@ -31,9 +31,9 @@ RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool)
     uint64_t noLimit = std::numeric_limits<uint64_t>::max();
     std::string dummy;
     CTxMemPoolEntry entry = *pool.mapTx.find(tx.GetHash());
-    pool.CalculateMemPoolAncestors(entry, setAncestors, noLimit, noLimit, noLimit, noLimit, dummy, false);
+    pool.CalculateMemPoolAncestors(entry, ancestors, noLimit, noLimit, noLimit, noLimit, dummy, false);
 
-    for (CTxMemPool::txiter it : setAncestors) {
+    for (CTxMemPool::txiter it : ancestors) {
         if (SignalsOptInRBF(it->GetTx())) {
             return RBFTransactionState::REPLACEABLE_BIP125;
         }
@@ -47,33 +47,127 @@ RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx)
     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)
+std::optional<std::string> GetEntriesForConflicts(const CTransaction& tx,
+                            CTxMemPool& pool,
+                            const CTxMemPool::setEntries& iters_conflicting,
+                            CTxMemPool::setEntries& all_conflicts)
 {
-    AssertLockHeld(m_pool.cs);
-    const uint256 hash = tx.GetHash();
+    AssertLockHeld(pool.cs);
+    const uint256 txid = tx.GetHash();
     uint64_t nConflictingCount = 0;
-    for (const auto& mi : setIterConflicting) {
+    for (const auto& mi : iters_conflicting) {
         nConflictingCount += mi->GetCountWithDescendants();
-        // This potentially overestimates the number of actual descendants
-        // but we just want to be conservative to avoid doing too much
-        // work.
+        // 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;
+            return strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
+                             txid.ToString(),
+                             nConflictingCount,
+                             MAX_BIP125_REPLACEMENT_CANDIDATES);
         }
     }
     // 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 : iters_conflicting) {
+        pool.CalculateDescendants(it, all_conflicts);
     }
-    return true;
+    return std::nullopt;
 }
 
+std::optional<std::string> HasNoNewUnconfirmed(const CTransaction& tx,
+                                               const CTxMemPool& pool,
+                                               const CTxMemPool::setEntries& iters_conflicting)
+{
+    AssertLockHeld(pool.cs);
+    std::set<uint256> parents_of_conflicts;
+    for (const auto& mi : iters_conflicting) {
+        for (const CTxIn &txin : mi->GetTx().vin) {
+            parents_of_conflicts.insert(txin.prevout.hash);
+        }
+    }
+
+    for (unsigned int j = 0; j < tx.vin.size(); j++) {
+        // We don't want to accept replacements that require low feerate junk to be mined first.
+        // Ideally we'd keep track of the ancestor feerates and make the decision based on that, but
+        // for now requiring all new inputs to be confirmed works.
+        //
+        // Note that if you relax this to make RBF a little more useful, this may break the
+        // CalculateMempoolAncestors RBF relaxation, above. See the comment above the first
+        // CalculateMempoolAncestors call for more info.
+        if (!parents_of_conflicts.count(tx.vin[j].prevout.hash)) {
+            // Rather than check the UTXO set - potentially expensive - it's cheaper to just check
+            // if the new input refers to a tx that's in the mempool.
+            if (pool.exists(tx.vin[j].prevout.hash)) {
+                return strprintf("replacement %s adds unconfirmed input, idx %d",
+                                 tx.GetHash().ToString(), j);
+            }
+        }
+    }
+    return std::nullopt;
+}
+
+std::optional<std::string> EntriesAndTxidsDisjoint(const CTxMemPool::setEntries& ancestors,
+                                                   const std::set<uint256>& direct_conflicts,
+                                                   const uint256& txid)
+{
+    for (CTxMemPool::txiter ancestorIt : ancestors) {
+        const uint256 &hashAncestor = ancestorIt->GetTx().GetHash();
+        if (direct_conflicts.count(hashAncestor)) {
+            return strprintf("%s spends conflicting transaction %s",
+                             txid.ToString(),
+                             hashAncestor.ToString());
+        }
+    }
+    return std::nullopt;
+}
+
+std::optional<std::string> PaysMoreThanConflicts(const CTxMemPool::setEntries& iters_conflicting,
+                                                 CFeeRate replacement_feerate,
+                                                 const uint256& txid)
+{
+    for (const auto& mi : iters_conflicting) {
+        // Don't allow the replacement to reduce the feerate of the mempool.
+        //
+        // We usually don't want to accept replacements with lower feerates than what they replaced
+        // as that would lower the feerate of the next block. Requiring that the feerate always be
+        // increased is also an easy-to-reason about way to prevent DoS attacks via replacements.
+        //
+        // We only consider the feerates of transactions being directly replaced, not their indirect
+        // descendants. While that does mean high feerate children are ignored when deciding whether
+        // or not to replace, we do require the replacement to pay more overall fees too, mitigating
+        // most cases.
+        CFeeRate original_feerate(mi->GetModifiedFee(), mi->GetTxSize());
+        if (replacement_feerate <= original_feerate) {
+            return strprintf("rejecting replacement %s; new feerate %s <= old feerate %s",
+                             txid.ToString(),
+                             replacement_feerate.ToString(),
+                             original_feerate.ToString());
+        }
+    }
+    return std::nullopt;
+}
+
+std::optional<std::string> PaysForRBF(CAmount original_fees,
+                                      CAmount replacement_fees,
+                                      size_t replacement_vsize,
+                                      const uint256& txid)
+{
+    // The replacement must pay greater fees than the transactions it
+    // replaces - if we did the bandwidth used by those conflicting
+    // transactions would not be paid for.
+    if (replacement_fees < original_fees) {
+        return strprintf("rejecting replacement %s, less fees than conflicting txs; %s < %s",
+                         txid.ToString(), FormatMoney(replacement_fees), FormatMoney(original_fees));
+    }
+
+    // Finally in addition to paying more fees than the conflicts the
+    // new transaction must pay for its own bandwidth.
+    CAmount additional_fees = replacement_fees - original_fees;
+    if (additional_fees < ::incrementalRelayFee.GetFee(replacement_vsize)) {
+        return strprintf("rejecting replacement %s, not enough additional fees to relay; %s < %s",
+                         txid.ToString(),
+                         FormatMoney(additional_fees),
+                         FormatMoney(::incrementalRelayFee.GetFee(replacement_vsize)));
+    }
+    return std::nullopt;
+}
diff --git a/src/policy/rbf.h b/src/policy/rbf.h
index a67e9058df..56468a09b2 100644
--- a/src/policy/rbf.h
+++ b/src/policy/rbf.h
@@ -35,19 +35,61 @@ 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
+/** Get all descendants of iters_conflicting. 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
+ * @param[in]   iters_conflicting   The set of iterators to mempool entries.
+ * @param[out]  all_conflicts       Populated with all the mempool entries that would be replaced,
+ *                                  which includes descendants of iters_conflicting. Not cleared at
  *                                  the start; any existing mempool entries will remain in the set.
- * @returns false if Rule 5 is broken.
+ * @returns an error message if Rule #5 is broken, otherwise a std::nullopt.
  */
-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);
+std::optional<std::string> GetEntriesForConflicts(const CTransaction& tx, CTxMemPool& pool,
+                                                  const CTxMemPool::setEntries& iters_conflicting,
+                                                  CTxMemPool::setEntries& all_conflicts)
+                                                  EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
+
+/** BIP125 Rule #2: "The replacement transaction may only include an unconfirmed input if that input
+ * was included in one of the original transactions."
+ * @returns error message if Rule #2 is broken, otherwise std::nullopt. */
+std::optional<std::string> HasNoNewUnconfirmed(const CTransaction& tx, const CTxMemPool& pool,
+                                               const CTxMemPool::setEntries& iters_conflicting)
+                                               EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
+
+/** Check the intersection between two sets of transactions (a set of mempool entries and a set of
+ * txids) to make sure they are disjoint.
+ * @param[in]   ancestors           Set of mempool entries corresponding to ancestors of the
+ *                                  replacement transactions.
+ * @param[in]   direct_conflicts    Set of txids corresponding to the mempool conflicts
+ *                                  (candidates to be replaced).
+ * @param[in]   txid                Transaction ID, included in the error message if violation occurs.
+ * @returns error message if the sets intersect, std::nullopt if they are disjoint.
+ */
+std::optional<std::string> EntriesAndTxidsDisjoint(const CTxMemPool::setEntries& ancestors,
+                                                   const std::set<uint256>& direct_conflicts,
+                                                   const uint256& txid);
+
+/** Check that the feerate of the replacement transaction(s) is higher than the feerate of each
+ * of the transactions in iters_conflicting.
+ * @param[in]   iters_conflicting  The set of mempool entries.
+ * @returns error message if fees insufficient, otherwise std::nullopt.
+ */
+std::optional<std::string> PaysMoreThanConflicts(const CTxMemPool::setEntries& iters_conflicting,
+                                                 CFeeRate replacement_feerate, const uint256& txid);
+
+/** Enforce BIP125 Rule #3 "The replacement transaction pays an absolute fee of at least the sum
+ * paid by the original transactions." Enforce BIP125 Rule #4 "The replacement transaction must also
+ * pay for its own bandwidth at or above the rate set by the node's minimum relay fee setting."
+ * @param[in]   original_fees       Total modified fees of original transaction(s).
+ * @param[in]   replacement_fees    Total modified fees of replacement transaction(s).
+ * @param[in]   replacement_vsize   Total virtual size of replacement transaction(s).
+ * @param[in]   txid                Transaction ID, included in the error message if violation occurs.
+ * @returns error string if fees are insufficient, otherwise std::nullopt.
+ */
+std::optional<std::string> PaysForRBF(CAmount original_fees,
+                                      CAmount replacement_fees,
+                                      size_t replacement_vsize,
+                                      const uint256& txid);
+
 #endif // BITCOIN_POLICY_RBF_H
diff --git a/src/util/rbf.h b/src/util/rbf.h
index 4eb44b904f..6d44a2cb83 100644
--- a/src/util/rbf.h
+++ b/src/util/rbf.h
@@ -11,15 +11,13 @@ 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.
-* Allow opt-out of transaction replacement by setting
-* nSequence > MAX_BIP125_RBF_SEQUENCE (SEQUENCE_FINAL-2) on all inputs.
+/** 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. */
+* 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 7e3663c465..8696f1af85 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -770,16 +770,8 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     // that we have the set of all ancestors we can detect this
     // pathological case by making sure setConflicts and setAncestors don't
     // intersect.
-    for (CTxMemPool::txiter ancestorIt : setAncestors)
-    {
-        const uint256 &hashAncestor = ancestorIt->GetTx().GetHash();
-        if (setConflicts.count(hashAncestor))
-        {
-            return state.Invalid(TxValidationResult::TX_CONSENSUS, "bad-txns-spends-conflicting-tx",
-                    strprintf("%s spends conflicting transaction %s",
-                        hash.ToString(),
-                        hashAncestor.ToString()));
-        }
+    if (const auto err_string{EntriesAndTxidsDisjoint(setAncestors, setConflicts, hash)}) {
+        return state.Invalid(TxValidationResult::TX_CONSENSUS, "bad-txns-spends-conflicting-tx", *err_string);
     }
 
 
@@ -789,98 +781,30 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     fReplacementTransaction = setConflicts.size();
     if (fReplacementTransaction)
     {
-        std::string err_string;
         CFeeRate newFeeRate(nModifiedFees, nSize);
-        for (const auto& mi : setIterConflicting) {
-            // Don't allow the replacement to reduce the feerate of the
-            // mempool.
-            //
-            // We usually don't want to accept replacements with lower
-            // feerates than what they replaced as that would lower the
-            // feerate of the next block. Requiring that the feerate always
-            // be increased is also an easy-to-reason about way to prevent
-            // DoS attacks via replacements.
-            //
-            // We only consider the feerates of transactions being directly
-            // replaced, not their indirect descendants. While that does
-            // mean high feerate children are ignored when deciding whether
-            // or not to replace, we do require the replacement to pay more
-            // overall fees too, mitigating most cases.
-            CFeeRate oldFeeRate(mi->GetModifiedFee(), mi->GetTxSize());
-            if (newFeeRate <= oldFeeRate)
-            {
-                return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee",
-                        strprintf("rejecting replacement %s; new feerate %s <= old feerate %s",
-                            hash.ToString(),
-                            newFeeRate.ToString(),
-                            oldFeeRate.ToString()));
-            }
+        if (const auto err_string{PaysMoreThanConflicts(setIterConflicting, newFeeRate, hash)}) {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee", *err_string);
         }
 
         // 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);
+        if (const auto err_string{GetEntriesForConflicts(tx, m_pool, setIterConflicting, allConflicting)}) {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
+                                 "too many potential replacements", *err_string);
+        }
+        // Enforce Rule #2.
+        if (const auto err_string{HasNoNewUnconfirmed(tx, m_pool, setIterConflicting)}) {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
+                                 "replacement-adds-unconfirmed", *err_string);
         }
 
         // Check if it's economically rational to mine this transaction rather
-        // than the ones it replaces.
+        // than the ones it replaces. Enforce Rules #3 and #4.
         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);
-            }
-        }
-
-        for (unsigned int j = 0; j < tx.vin.size(); j++)
-        {
-            // We don't want to accept replacements that require low
-            // feerate junk to be mined first. Ideally we'd keep track of
-            // the ancestor feerates and make the decision based on that,
-            // but for now requiring all new inputs to be confirmed works.
-            //
-            // Note that if you relax this to make RBF a little more useful,
-            // this may break the CalculateMempoolAncestors RBF relaxation,
-            // above. See the comment above the first CalculateMempoolAncestors
-            // call for more info.
-            if (!setConflictsParents.count(tx.vin[j].prevout.hash))
-            {
-                // Rather than check the UTXO set - potentially expensive -
-                // it's cheaper to just check if the new input refers to a
-                // tx that's in the mempool.
-                if (m_pool.exists(tx.vin[j].prevout.hash)) {
-                    return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "replacement-adds-unconfirmed",
-                            strprintf("replacement %s adds unconfirmed input, idx %d",
-                                hash.ToString(), j));
-                }
-            }
-        }
-
-        // The replacement must pay greater fees than the transactions it
-        // replaces - if we did the bandwidth used by those conflicting
-        // transactions would not be paid for.
-        if (nModifiedFees < nConflictingFees)
-        {
-            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee",
-                    strprintf("rejecting replacement %s, less fees than conflicting txs; %s < %s",
-                        hash.ToString(), FormatMoney(nModifiedFees), FormatMoney(nConflictingFees)));
-        }
-
-        // Finally in addition to paying more fees than the conflicts the
-        // new transaction must pay for its own bandwidth.
-        CAmount nDeltaFees = nModifiedFees - nConflictingFees;
-        if (nDeltaFees < ::incrementalRelayFee.GetFee(nSize))
-        {
-            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee",
-                    strprintf("rejecting replacement %s, not enough additional fees to relay; %s < %s",
-                        hash.ToString(),
-                        FormatMoney(nDeltaFees),
-                        FormatMoney(::incrementalRelayFee.GetFee(nSize))));
+        if (const auto err_string{PaysForRBF(nConflictingFees, nModifiedFees, nSize, hash)}) {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee", *err_string);
         }
     }
     return true;