[policy] sibling eviction for v3 transactions

5 files changed, 76 insertions, 27 deletions

diff --git a/src/policy/v3_policy.cpp b/src/policy/v3_policy.cpp
index c98262c364..3c3942d707 100644
--- a/src/policy/v3_policy.cpp
+++ b/src/policy/v3_policy.cpp
@@ -130,10 +130,11 @@ std::optional<std::string> PackageV3Checks(const CTransactionRef& ptx, int64_t v
             }
 
             // It shouldn't be possible to have any mempool siblings at this point. SingleV3Checks
-            // catches mempool siblings. Also, if the package consists of connected transactions,
+            // catches mempool siblings and sibling eviction is not extended to packages. Also, if the package consists of connected transactions,
             // any tx having a mempool ancestor would mean the package exceeds ancestor limits.
             if (!Assume(!parent_info.m_has_mempool_descendant)) {
-                return strprintf("tx %u would exceed descendant count limit", parent_info.m_wtxid.ToString());
+                return strprintf("tx %s (wtxid=%s) would exceed descendant count limit",
+                                parent_info.m_txid.ToString(), parent_info.m_wtxid.ToString());
             }
         }
     } else {
@@ -214,10 +215,20 @@ std::optional<std::pair<std::string, CTransactionRef>> SingleV3Checks(const CTra
             std::any_of(children.cbegin(), children.cend(),
                 [&direct_conflicts](const CTxMemPoolEntry& child){return direct_conflicts.count(child.GetTx().GetHash()) > 0;});
         if (parent_entry->GetCountWithDescendants() + 1 > V3_DESCENDANT_LIMIT && !child_will_be_replaced) {
+            // Allow sibling eviction for v3 transaction: if another child already exists, even if
+            // we don't conflict inputs with it, consider evicting it under RBF rules. We rely on v3 rules
+            // only permitting 1 descendant, as otherwise we would need to have logic for deciding
+            // which descendant to evict. Skip if this isn't true, e.g. if the transaction has
+            // multiple children or the sibling also has descendants due to a reorg.
+            const bool consider_sibling_eviction{parent_entry->GetCountWithDescendants() == 2 &&
+                children.begin()->get().GetCountWithAncestors() == 2};
+
+            // Return the sibling if its eviction can be considered. Provide the "descendant count
+            // limit" string either way, as the caller may decide not to do sibling eviction.
             return std::make_pair(strprintf("tx %u (wtxid=%s) would exceed descendant count limit",
-                             parent_entry->GetSharedTx()->GetHash().ToString(),
-                             parent_entry->GetSharedTx()->GetWitnessHash().ToString()),
-                nullptr);
+                                            parent_entry->GetSharedTx()->GetHash().ToString(),
+                                            parent_entry->GetSharedTx()->GetWitnessHash().ToString()),
+                                  consider_sibling_eviction ?  children.begin()->get().GetSharedTx() : nullptr);
         }
     }
     return std::nullopt;
diff --git a/src/policy/v3_policy.h b/src/policy/v3_policy.h
index c61d8ac4cc..2e56f8822b 100644
--- a/src/policy/v3_policy.h
+++ b/src/policy/v3_policy.h
@@ -48,7 +48,13 @@ static_assert(V3_CHILD_MAX_VSIZE + MAX_STANDARD_TX_WEIGHT / WITNESS_SCALE_FACTOR
  *                                      count of in-mempool ancestors.
  * @param[in]   vsize                   The sigop-adjusted virtual size of ptx.
  *
- * @returns debug string if an error occurs, std::nullopt otherwise.
+ * @returns 3 possibilities:
+ * - std::nullopt if all v3 checks were applied successfully
+ * - debug string + pointer to a mempool sibling if this transaction would be the second child in a
+ *   1-parent-1-child cluster; the caller may consider evicting the specified sibling or return an
+ *   error with the debug string.
+ * - debug string + nullptr if this transaction violates some v3 rule and sibling eviction is not
+ *   applicable.
  */
 std::optional<std::pair<std::string, CTransactionRef>> SingleV3Checks(const CTransactionRef& ptx,
                                           const CTxMemPool::setEntries& mempool_ancestors,
diff --git a/src/test/txvalidation_tests.cpp b/src/test/txvalidation_tests.cpp
index 04bb7c4828..530c8837d6 100644
--- a/src/test/txvalidation_tests.cpp
+++ b/src/test/txvalidation_tests.cpp
@@ -329,18 +329,21 @@ BOOST_FIXTURE_TEST_CASE(version3_tests, RegTestingSetup)
         BOOST_CHECK(PackageV3Checks(tx_mempool_v3_child, GetVirtualTransactionSize(*tx_mempool_v3_child), package_v3_1p1c, empty_ancestors) == std::nullopt);
     }
 
-    // A v3 transaction cannot have more than 1 descendant.
-    // Configuration where tx has multiple direct children.
+    // A v3 transaction cannot have more than 1 descendant. Sibling is returned when exactly 1 exists.
     {
         auto tx_v3_child2 = make_tx({COutPoint{mempool_tx_v3->GetHash(), 1}}, /*version=*/3);
-        auto ancestors{pool.CalculateMemPoolAncestors(entry.FromTx(tx_v3_child2), m_limits)};
+
+        // Configuration where parent already has 1 other child in mempool
+        auto ancestors_1sibling{pool.CalculateMemPoolAncestors(entry.FromTx(tx_v3_child2), m_limits)};
         const auto expected_error_str{strprintf("tx %s (wtxid=%s) would exceed descendant count limit",
             mempool_tx_v3->GetHash().ToString(), mempool_tx_v3->GetWitnessHash().ToString())};
-        auto result{SingleV3Checks(tx_v3_child2, *ancestors, empty_conflicts_set, GetVirtualTransactionSize(*tx_v3_child2))};
-        BOOST_CHECK_EQUAL(result->first, expected_error_str);
-        BOOST_CHECK_EQUAL(result->second, nullptr);
-        // If replacing the child, make sure there is no double-counting.
-        BOOST_CHECK(SingleV3Checks(tx_v3_child2, *ancestors, {tx_mempool_v3_child->GetHash()}, GetVirtualTransactionSize(*tx_v3_child2))
+        auto result_with_sibling_eviction{SingleV3Checks(tx_v3_child2, *ancestors_1sibling, empty_conflicts_set, GetVirtualTransactionSize(*tx_v3_child2))};
+        BOOST_CHECK_EQUAL(result_with_sibling_eviction->first, expected_error_str);
+        // The other mempool child is returned to allow for sibling eviction.
+        BOOST_CHECK_EQUAL(result_with_sibling_eviction->second, tx_mempool_v3_child);
+
+        // If directly replacing the child, make sure there is no double-counting.
+        BOOST_CHECK(SingleV3Checks(tx_v3_child2, *ancestors_1sibling, {tx_mempool_v3_child->GetHash()}, GetVirtualTransactionSize(*tx_v3_child2))
                     == std::nullopt);
 
         Package package_v3_1p2c{mempool_tx_v3, tx_mempool_v3_child, tx_v3_child2};
diff --git a/src/validation.cpp b/src/validation.cpp
index 2c36f0d00d..ddaefbf274 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -585,12 +585,14 @@ private:
     // of checking a given transaction.
     struct Workspace {
         explicit Workspace(const CTransactionRef& ptx) : m_ptx(ptx), m_hash(ptx->GetHash()) {}
-        /** Txids of mempool transactions that this transaction directly conflicts with. */
+        /** Txids of mempool transactions that this transaction directly conflicts with or may
+         * replace via sibling eviction. */
         std::set<Txid> m_conflicts;
-        /** Iterators to mempool entries that this transaction directly conflicts with. */
+        /** Iterators to mempool entries that this transaction directly conflicts with or may
+         * replace via sibling eviction. */
         CTxMemPool::setEntries m_iters_conflicting;
         /** Iterators to all mempool entries that would be replaced by this transaction, including
-         * those it directly conflicts with and their descendants. */
+         * m_conflicts and their descendants. */
         CTxMemPool::setEntries m_all_conflicting;
         /** All mempool ancestors of this transaction. */
         CTxMemPool::setEntries m_ancestors;
@@ -598,9 +600,12 @@ private:
          * inserted into the mempool until Finalize(). */
         std::unique_ptr<CTxMemPoolEntry> m_entry;
         /** Pointers to the transactions that have been removed from the mempool and replaced by
-         * this transaction, used to return to the MemPoolAccept caller. Only populated if
+         * this transaction (everything in m_all_conflicting), used to return to the MemPoolAccept caller. Only populated if
          * validation is successful and the original transactions are removed. */
         std::list<CTransactionRef> m_replaced_transactions;
+        /** Whether RBF-related data structures (m_conflicts, m_iters_conflicting, m_all_conflicting,
+         * m_replaced_transactions) include a sibling in addition to txns with conflicting inputs. */
+        bool m_sibling_eviction{false};
 
         /** Virtual size of the transaction as used by the mempool, calculated using serialized size
          * of the transaction and sigops. */
@@ -690,7 +695,8 @@ private:
 
     Chainstate& m_active_chainstate;
 
-    /** Whether the transaction(s) would replace any mempool transactions. If so, RBF rules apply. */
+    /** Whether the transaction(s) would replace any mempool transactions and/or evict any siblings.
+     * If so, RBF rules apply. */
     bool m_rbf{false};
 };
 
@@ -954,8 +960,27 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     }
 
     ws.m_ancestors = *ancestors;
+    // Even though just checking direct mempool parents for inheritance would be sufficient, we
+    // check using the full ancestor set here because it's more convenient to use what we have
+    // already calculated.
     if (const auto err{SingleV3Checks(ws.m_ptx, ws.m_ancestors, ws.m_conflicts, ws.m_vsize)}) {
-        return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "v3-rule-violation", err->first);
+        // Disabled within package validation.
+        if (err->second != nullptr && args.m_allow_replacement) {
+            // Potential sibling eviction. Add the sibling to our list of mempool conflicts to be
+            // included in RBF checks.
+            ws.m_conflicts.insert(err->second->GetHash());
+            // Adding the sibling to m_iters_conflicting here means that it doesn't count towards
+            // RBF Carve Out above. This is correct, since removing to-be-replaced transactions from
+            // the descendant count is done separately in SingleV3Checks for v3 transactions.
+            ws.m_iters_conflicting.insert(m_pool.GetIter(err->second->GetHash()).value());
+            ws.m_sibling_eviction = true;
+            // The sibling will be treated as part of the to-be-replaced set in ReplacementChecks.
+            // Note that we are not checking whether it opts in to replaceability via BIP125 or v3
+            // (which is normally done in PreChecks). However, the only way a v3 transaction can
+            // have a non-v3 and non-BIP125 descendant is due to a reorg.
+        } else {
+            return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "v3-rule-violation", err->first);
+        }
     }
 
     // A transaction that spends outputs that would be replaced by it is invalid. Now
@@ -995,18 +1020,21 @@ bool MemPoolAccept::ReplacementChecks(Workspace& ws)
         // Even though this is a fee-related failure, this result is TX_MEMPOOL_POLICY, not
         // TX_RECONSIDERABLE, because it cannot be bypassed using package validation.
         // This must be changed if package RBF is enabled.
-        return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee", *err_string);
+        return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
+                             strprintf("insufficient fee%s", ws.m_sibling_eviction ? " (including sibling eviction)" : ""), *err_string);
     }
 
     // Calculate all conflicting entries and enforce Rule #5.
     if (const auto err_string{GetEntriesForConflicts(tx, m_pool, ws.m_iters_conflicting, ws.m_all_conflicting)}) {
         return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
-                             "too many potential replacements", *err_string);
+                             strprintf("too many potential replacements%s", ws.m_sibling_eviction ? " (including sibling eviction)" : ""), *err_string);
     }
     // Enforce Rule #2.
     if (const auto err_string{HasNoNewUnconfirmed(tx, m_pool, ws.m_iters_conflicting)}) {
+        // Sibling eviction is only done for v3 transactions, which cannot have multiple ancestors.
+        Assume(!ws.m_sibling_eviction);
         return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
-                             "replacement-adds-unconfirmed", *err_string);
+                             strprintf("replacement-adds-unconfirmed%s", ws.m_sibling_eviction ? " (including sibling eviction)" : ""), *err_string);
     }
     // Check if it's economically rational to mine this transaction rather than the ones it
     // replaces and pays for its own relay fees. Enforce Rules #3 and #4.
@@ -1019,7 +1047,8 @@ bool MemPoolAccept::ReplacementChecks(Workspace& ws)
         // Even though this is a fee-related failure, this result is TX_MEMPOOL_POLICY, not
         // TX_RECONSIDERABLE, because it cannot be bypassed using package validation.
         // This must be changed if package RBF is enabled.
-        return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "insufficient fee", *err_string);
+        return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY,
+                             strprintf("insufficient fee%s", ws.m_sibling_eviction ? " (including sibling eviction)" : ""), *err_string);
     }
     return true;
 }
diff --git a/test/functional/mempool_accept_v3.py b/test/functional/mempool_accept_v3.py
index 7ac3c97c4b..0be1a18aa8 100755
--- a/test/functional/mempool_accept_v3.py
+++ b/test/functional/mempool_accept_v3.py
@@ -311,8 +311,8 @@ class MempoolAcceptV3(BitcoinTestFramework):
             utxo_to_spend=tx_mempool_parent["new_utxos"][1],
             version=3
         )
-        expected_error_mempool_sibling = f"v3-rule-violation, tx {tx_mempool_parent['txid']} (wtxid={tx_mempool_parent['wtxid']}) would exceed descendant count limit"
-        assert_raises_rpc_error(-26, expected_error_mempool_sibling, node.sendrawtransaction, tx_has_mempool_sibling["hex"])
+        expected_error_mempool_sibling_no_eviction = f"insufficient fee (including sibling eviction), rejecting replacement"
+        assert_raises_rpc_error(-26, expected_error_mempool_sibling_no_eviction, node.sendrawtransaction, tx_has_mempool_sibling["hex"])
 
         tx_has_mempool_uncle = self.wallet.create_self_transfer(utxo_to_spend=tx_has_mempool_sibling["new_utxo"], version=3)
 
@@ -326,7 +326,7 @@ class MempoolAcceptV3(BitcoinTestFramework):
 
         # Also fails with a child via submitpackage
         result_submitpackage = node.submitpackage([tx_has_mempool_sibling["hex"], tx_has_mempool_uncle["hex"]])
-        assert_equal(result_submitpackage["tx-results"][tx_has_mempool_sibling['wtxid']]['error'], expected_error_mempool_sibling)
+        assert expected_error_mempool_sibling_no_eviction in result_submitpackage["tx-results"][tx_has_mempool_sibling['wtxid']]['error']
 
 
     @cleanup(extra_args=["-datacarriersize=1000", "-acceptnonstdtxn=1"])