v3 transaction policy for anti-pinning #28948

34+ * @returns a tuple (parent wtxid, child wtxid, bool) where one is V3 but the other is not, if at
35+ * least one such pair exists. The bool represents whether the child is v3 or not. There may be
36+ * other such pairs that are not returned.
37+ * Otherwise std::nullopt.
38+ */
39+std::optional<std::tuple<uint256, uint256, bool>> CheckV3Inheritance(const Package& package);

52+ *
53+ * @returns an error string if any V3 rule was violated, otherwise std::nullopt.
54+ */
55+std::optional<std::string> ApplyV3Rules(const CTransactionRef& ptx,
56+                                        const CTxMemPool::setEntries& ancestors,
57+                                        const std::set<uint256>& direct_conflicts);

313+                Assert(entry.GetTxWeight() <= V3_CHILD_MAX_WEIGHT);
314+            }
315+        }
316+        // Transactions with fees of 0 or lower should be proactively trimmed.
317+        if (tx_pool.m_min_relay_feerate.GetFeePerK() > 0) {
318+            Assert(entry.GetModFeesWithDescendants() > 0);

79+    if (ancestors.empty()) {
80+        return std::nullopt;
81+    } else {
82+        const auto tx_weight{GetTransactionWeight(*ptx)};
83+        // If this transaction spends V3 parents, it cannot be too large.
84+        if (tx_weight > V3_CHILD_MAX_WEIGHT) {

77+    if (ancestors.size() + 1 > V3_ANCESTOR_LIMIT) {
78+        return strprintf("tx %s would have too many ancestors", ptx->GetWitnessHash().ToString());
79+    }
80+    if (ancestors.empty()) {
81+        return std::nullopt;
82+    } else {

87+        }
88+        if (sigops > V3_CHILD_MAX_SIGOPS) {
89+            return strprintf("v3 child tx has too many sigops: %u > %u sigops", sigops, V3_CHILD_MAX_SIGOPS);
90+        }
91+        // Any ancestor of a V3 transaction must also be V3.
92+        const auto& parent_entry = *ancestors.begin();

76+
77+    if (ancestors.size() + 1 > V3_ANCESTOR_LIMIT) {
78+        return strprintf("tx %s would have too many ancestors", ptx->GetWitnessHash().ToString());
79+    }
80+    if (ancestors.empty()) {
81+        return std::nullopt;

45+/** Every transaction that spends an unconfirmed V3 transaction must also be V3. */
46+std::optional<std::string> CheckV3Inheritance(const CTransactionRef& ptx,
47+                                              const CTxMemPool::setEntries& ancestors);
48+
49+/** The following rules apply to V3 transactions:
50+ * 1. Tx with all of its ancestors (including non-nVersion=3) must be within V3_ANCESTOR_SIZE_LIMIT_KVB.

374@@ -372,11 +375,16 @@ void Chainstate::MaybeUpdateMempoolForReorg(
375             }
376         }
377         // Transaction is still valid and cached LockPoints are updated.
378+        auto ancestors{m_mempool->AssumeCalculateMemPoolAncestors(func, *it, CTxMemPool::Limits::NoLimits(),

64+        }
65+    }
66+    return std::nullopt;
67+}
68+
69+std::optional<std::string> ApplyV3Rules(const CTransactionRef& ptx,

1163 
1164+        // Keep trimming as long as memory is above the maximum.
1165+        // Also, unless min relay feerate allows it, skim away everything paying <=0 fees.
1166+        const bool keep_trimming{DynamicMemoryUsage() > sizelimit ||
1167+            (m_min_relay_feerate.GetFeePerK() > 0 && it->GetModFeesWithDescendants() <= 0)};
1168+        if (!keep_trimming) break;

328@@ -328,11 +329,12 @@ void Chainstate::MaybeUpdateMempoolForReorg(
329     m_mempool->UpdateTransactionsFromBlock(vHashUpdate);
330 
331     // Predicate to use for filtering transactions in removeForReorg.
332+    // Checks whether a non-v3 transaction spends v3 and or vice versa.

947@@ -946,6 +948,16 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
948     }
949 
950     ws.m_ancestors = *ancestors;
951+    if (const auto err_string{CheckV3Inheritance(ws.m_ptx, ws.m_ancestors)}) {

1299@@ -1288,6 +1300,31 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1300                    [](const auto& tx) { return Workspace(tx); });
1301     std::map<uint256, MempoolAcceptResult> results;
1302 
1303+    if (const auto v3_violation{CheckV3Inheritance(txns)}) {

1162-        removed += m_incremental_relay_feerate;
1163-        trackPackageRemoved(removed);
1164-        maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1165+        if (removed >= m_min_relay_feerate) {
1166+            removed += m_incremental_relay_feerate;
1167+            trackPackageRemoved(removed);

 6+
 7+#include <coins.h>
 8+#include <consensus/amount.h>
 9+#include <logging.h>
10+#include <tinyformat.h>
11+

28+// additionally check ancestor/descendant limits for V3 transactions.
29+static_assert(V3_CHILD_MAX_VSIZE + MAX_STANDARD_TX_WEIGHT / WITNESS_SCALE_FACTOR <= DEFAULT_ANCESTOR_SIZE_LIMIT_KVB * 1000);
30+static_assert(V3_CHILD_MAX_VSIZE + MAX_STANDARD_TX_WEIGHT / WITNESS_SCALE_FACTOR <= DEFAULT_DESCENDANT_SIZE_LIMIT_KVB * 1000);
31+
32+/** Any two unconfirmed transactions with a dependency relationship must either both be V3 or both
33+ * non-V3. Check this rule for any list of unconfirmed transactions.

275             self.nodes[0].setmocktime(cur_time + 600)
276             self.generate(self.wallet, 1, sync_fun=self.no_op)
277             cur_time += 600
278 
279-        assert tx2.hash in self.nodes[0].getrawmempool()
280+        assert tx2.hash not in self.nodes[0].getrawmempool()

289@@ -290,7 +290,8 @@ def create_self_transfer_multi(
290         sequence=0,
291         fee_per_output=1000,
292         target_weight=0,
293-        confirmed_only=False
294+        confirmed_only=False,
295+        version=2

302@@ -300,5 +303,21 @@ FUZZ_TARGET(tx_package_eval, .init = initialize_tx_pool)
303     UnregisterSharedValidationInterface(outpoints_updater);
304 
305     WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1));
306+    LOCK(tx_pool.cs);
307+    for (const auto& tx_info : tx_pool.infoAll()) {

1034@@ -1014,6 +1035,7 @@ bool MemPoolAccept::ReplacementChecks(Workspace& ws)
1035 }
1036 
1037 bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txns,
1038+                                         const std::vector<Workspace>& workspaces,

1050@@ -1029,6 +1051,7 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
1051         // This is a package-wide error, separate from an individual transaction error.
1052         return package_state.Invalid(PackageValidationResult::PCKG_POLICY, "package-mempool-limits", err_string);
1053     }
1054+

113+    // If this transaction spends V3 parents, it cannot be too large.
114+    if (vsize > V3_CHILD_MAX_VSIZE) {
115+        return strprintf("v3 child tx is too big: %u > %u virtual bytes", vsize, V3_CHILD_MAX_VSIZE);
116+    }
117+    // Any ancestor of a V3 transaction must also be V3.
118+    const auto& parent_entry = *ancestors.begin();

1361@@ -1332,11 +1362,24 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1362             MempoolAcceptResult::FeeFailure(placeholder_state, CFeeRate(m_total_modified_fees, m_total_vsize), all_package_wtxids)}});
1363     }
1364 
1365+    // Check the last transaction's v3 ancestor limits again, assuming that all transactions
1366+    // are in the ancestor set of the last tx (which is the case when a package IsChildWithParents)

250+            fee_per_output=10000,
251+            version=3
252+        )
253+        assert_equal(node.getrawmempool(), [])
254+        result = node.submitpackage([tx_v3_parent_normal["hex"], tx_v3_parent_2_normal["hex"], tx_v3_child_heavy["hex"]])
255+        assert result['package_msg'] != 'success'

280+        # tx_child_violator is our transaction "C"; create it:
281+        tx_child_violator = self.wallet.create_self_transfer_multi(utxos_to_spend=[tx_0fee_parent["new_utxo"]], version=3)
282+
283+        # submitpackage(B, C) should fail
284+        result = node.submitpackage([tx_0fee_parent["hex"], tx_child_violator["hex"]])
285+        assert result['package_msg'] != 'success'

37+ * If a V3 tx has V3 ancestors,
38+ * 1. The tx vsize must be within V3_CHILD_MAX_VSIZE.
39+ *
40+ * @returns an error string if any V3 rule was violated, otherwise std::nullopt.
41+ */
42+std::optional<std::string> ApplyV3Rules(const CTransactionRef& ptx,

82+        }
83+    }
84+
85+    // Sanity check that package itself obeys ancestor/descendant limits. Assumes that this is
86+    // ancestor package-shaped.
87+    if (!package.empty() && package.size() > V3_CHILD_MAX_VSIZE && package.back()->nVersion == 3) {

130+            // If this transaction has at least 1 ancestor, it's a "child" and has restricted weight.
131+            if (entry.GetCountWithAncestors() > 1) {
132+                Assert(entry.GetTxSize() <= V3_CHILD_MAX_VSIZE);
133+            }
134+        }
135+        // Transactions with fees of 0 or lower should be proactively trimmed.

58+std::optional<std::tuple<Wtxid, Wtxid, bool>> CheckV3Inheritance(const Package& package);
59+
60+/** Check inheritance of v3 and ancestor/descendant limits within a package (this assumes that all
61+ * transactions are in the ancestor set of the last tx, which is true if IsChildWithParents). This
62+ * check does not fully check all v3 rules, but allows us to quit early before accessing mempool.  */
63+std::optional<std::string> PackageV3SanityChecks(const Package& package);

128+            Assert(entry.GetCountWithDescendants() <= V3_DESCENDANT_LIMIT);
129+            Assert(entry.GetCountWithAncestors() <= V3_ANCESTOR_LIMIT);
130+            // If this transaction has at least 1 ancestor, it's a "child" and has restricted weight.
131+            if (entry.GetCountWithAncestors() > 1) {
132+                Assert(entry.GetTxSize() <= V3_CHILD_MAX_VSIZE);
133+            }

293+        # submitpackage(B, C) should fail
294+        result = node.submitpackage([tx_0fee_parent["hex"], tx_child_violator["hex"]])
295+        assert_equal(result['package_msg'], "transaction failed")
296+        assert_equal(result['tx-results'][tx_child_violator['wtxid']]['error'], f"v3-rule-violation, tx {tx_child_violator['wtxid']} would have too many ancestors")
297+        self.check_mempool([tx_in_mempool["txid"]])
298+

307+        self.test_v3_bip125()
308+        self.test_v3_reorg()
309+        self.test_nondefault_package_limits()
310+        self.test_fee_dependency_replacements()
311+        self.test_v3_ancestors_package()
312+        self.test_v3_ancestors_package_and_mempool()

56+}
57+
58+std::optional<std::string> PackageV3SanityChecks(const Package& package)
59+{
60+    // Check inheritance rules within package.
61+    if (const auto inheritance_error{CheckV3Inheritance(package)}) {

67+        }
68+    }
69+
70+    // Sanity check that package itself obeys ancestor/descendant limits. Assumes that this is
71+    // ancestor package-shaped. This check is not complete as we have not seen in-mempool ancestors yet.
72+    if (!package.empty() && package.size() > V3_ANCESTOR_LIMIT && package.back()->nVersion == 3) {

1329+
1330     LOCK(m_pool.cs);
1331 
1332     // Do all PreChecks first and fail fast to avoid running expensive script checks when unnecessary.
1333     for (Workspace& ws : workspaces) {
1334+        // This process is O(n^2) in the number of transactions, so only do it when v3 rules are

87@@ -88,4 +88,8 @@ bool IsChildWithParents(const Package& package);
88  * other (the package is a "tree").
89  */
90 bool IsChildWithParentsTree(const Package& package);
91+
92+/** Construct a map from the txid of a transaction to the txids of its in-package ancestor set,
93+ * including itself. Input must be IsConsistentPackage, otherwise this returns an empty map. */

159+           std::map<Txid, std::set<Txid>>& ancestor_set_map)
160+{
161+    const Txid& curr_txid = curr_tx->GetHash();
162+    // Already visited? Return now.
163+    auto curr_result_iter = ancestor_set_map.find(curr_txid);
164+    if (curr_result_iter == ancestor_set_map.end()) return;

211+        std::set<Txid> empty;
212+        result.emplace(tx->GetHash(), empty);
213+    }
214+
215+    // For each tx from beginning to end, populate the ancestor set map. This does a recursive DFS
216+    // by tracing input prevouts; best-case runtime is when the list is already sorted.

1334 
1335     // Do all PreChecks first and fail fast to avoid running expensive script checks when unnecessary.
1336     for (Workspace& ws : workspaces) {
1337+        // This process is O(n^2) in the number of transactions, so only do it when v3 rules are
1338+        // applicable. PackageV3Checks helps significantly limit the computation here.
1339+        if (check_v3_rules && ws.m_ptx->nVersion == 3) {

14+#include <numeric>
15+#include <vector>
16+
17+util::Result<std::map<Txid, std::set<Txid>>> PackageV3Checks(const Package& package)
18+{
19+    // Keep track of in-package ancestors and descendants as we find them so we can catch topology violations.

71+                        }
72+
73+                        // A v3 transaction with unconfirmed ancestors must be within
74+                        // V3_CHILD_MAX_VSIZE. This check is not complete as we have not calculated
75+                        // the sigop cost, which can increase the virtual size.
76+                        const int64_t vsize = GetVirtualTransactionSize(*tx);

1310@@ -1288,10 +1311,56 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1311                    [](const auto& tx) { return Workspace(tx); });
1312     std::map<uint256, MempoolAcceptResult> results;
1313 
1314+    // Not a complete check of v3 rules, helps us detect failures early.
1315+    // Some data structures are only necessary if we are checking v3 rules; skip this work if those
1316+    // rules are not applicable.
1317+    const bool check_v3_rules{std::any_of(txns.cbegin(), txns.cend(), [](const auto& tx){ return tx->nVersion == 3; })};
1318+
1319+    // Map from txid of a transaction to its in-package ancestor set. Not MemPoolAccept-wide

1349+                // that it is the entire list of txns.
1350+                ws.m_num_in_package_ancestors = txns.size() - 1;
1351+            }
1352+
1353+            // If this tx is one of our ancestors, add all of its in-mempool ancestors to ours.
1354+            // If we are treating all transactions as our ancestor, always add.

1342+            const bool have_ancestor_set{ancestor_set_iter != in_package_ancestors.end() && ancestor_set_iter->second.size() >= 1};
1343+            if (Assume(have_ancestor_set)) {
1344+                // If there are in-package ancestors, update m_num_in_package_ancestors.
1345+                // Sets in in_package_ancestors include the tx itself, so subtract 1.
1346+                ws.m_num_in_package_ancestors = ancestor_set_iter->second.size() - 1;
1347+            } else if (!txns.empty()) {

54+ * @param[in]   vsize               The sigop-adjusted virtual size of ptx.
55+ * @returns an error string if any v3 rule was violated, otherwise std::nullopt.
56+ */
57+std::optional<std::string> ApplyV3Rules(const CTransactionRef& ptx,
58+                                        const CTxMemPool::setEntries& ancestors,
59+                                        unsigned int num_other_ancestors,

53+ *                                  would already be a violation of V3_ANCESTOR_LIMIT.
54+ * @param[in]   vsize               The sigop-adjusted virtual size of ptx.
55+ * @returns an error string if any v3 rule was violated, otherwise std::nullopt.
56+ */
57+std::optional<std::string> ApplyV3Rules(const CTransactionRef& ptx,
58+                                        const CTxMemPool::setEntries& ancestors,

65+ * Check the following rules for transactions within the package:
66+ * 1. A v3 tx must only have v3 unconfirmed ancestors.
67+ * 2. A non-v3 tx must only have non-v3 unconfirmed ancestors.
68+ * 3. A v3's ancestor set, including itself, must be within V3_ANCESTOR_LIMIT.
69+ * 4. A v3's descendant set, including itself, must be within V3_DESCENDANT_LIMIT.
70+ * 5. If a v3 tx has any unconfirmed ancestors, the tx's sigop-adjusted vsize must be within

68+ * 3. A v3's ancestor set, including itself, must be within V3_ANCESTOR_LIMIT.
69+ * 4. A v3's descendant set, including itself, must be within V3_DESCENDANT_LIMIT.
70+ * 5. If a v3 tx has any unconfirmed ancestors, the tx's sigop-adjusted vsize must be within
71+ * V3_CHILD_MAX_VSIZE.
72+ *
73+ * Important: this function is necessary but insufficient to enforce these rules.  ApplyV3Rules must

242+            target_weight=4004,
243+            version=3
244+        )
245+        tx_v3_child_multiparent = self.wallet.create_self_transfer_multi(
246+            utxos_to_spend=[tx_v3_parent_normal["new_utxo"], tx_v3_parent_2_normal["new_utxo"]],
247+            target_weight=4000,

77+ * @returns If all checks pass, a map from each v3 transaction, by txid, to the txids of its
78+ * in-package ancestor set. Every ancestor set includes the tx itself. If this passed, we know that
79+ * each connected component does not violate V3 inheritance or topology constraints within the
80+ * package itself. If any checks fail, an error string detailing what failed.
81+ * */
82+util::Result<std::map<Txid, std::set<Txid>>> PackageV3Checks(const Package& package);

 9+#include <policy/packages.h>
10+#include <policy/policy.h>
11+#include <primitives/transaction.h>
12+#include <txmempool.h>
13+#include <util/result.h>
14+

65+ * Check the following rules for transactions within the package:
66+ * 1. A v3 tx must only have v3 unconfirmed ancestors.
67+ * 2. A non-v3 tx must only have non-v3 unconfirmed ancestors.
68+ * 3. A v3's ancestor set, including itself, must be within V3_ANCESTOR_LIMIT.
69+ * 4. A v3's descendant set, including itself, must be within V3_DESCENDANT_LIMIT.
70+ * 5. If a v3 tx has any unconfirmed ancestors, its vsize must be within V3_CHILD_MAX_VSIZE.

20+    // Since we enforce v3 inheritance rules as we build this set, sets should consist exclusively
21+    // of v3 transactions.
22+    std::map<Txid, std::set<Txid>> v3_ancestor_sets;
23+    // Map from txid of a v3 transaction to its descendant set, including itself.
24+    std::map<Txid, std::set<Txid>> v3_descendant_sets;
25+

94+        }
95+    }
96+
97+    // Find violations of descendant limits. When a package is sorted, it's most efficient to build
98+    // descendant sets by iterating in reverse order.
99+    for (auto package_iter = package.rbegin(); package_iter != package.rend(); ++package_iter) {

 95+    }
 96+
 97+    // Find violations of descendant limits. When a package is sorted, it's most efficient to build
 98+    // descendant sets by iterating in reverse order.
 99+    for (auto package_iter = package.rbegin(); package_iter != package.rend(); ++package_iter) {
100+        if ((*package_iter)->nVersion == 3) {

104+            Assume(my_descendant_set.size() >= 1);
105+
106+            for (const auto& ancestor_txid : my_ancestor_set) {
107+                // My descendants are also my ancestor's descendants.
108+                auto& ancestors_descendant_set = v3_descendant_sets.at(ancestor_txid);
109+                ancestors_descendant_set.insert(my_descendant_set.cbegin(), my_descendant_set.cend());

135+                Assert(parents.begin()->get().GetSharedTx()->nVersion == 3);
136+            }
137+        } else if (entry.GetCountWithAncestors() > 1) {
138+            // All non-v3 transactions must only have non-v3 unconfirmed parents.
139+            const auto& parents = entry.GetMemPoolParentsConst();
140+            Assert(parents.begin()->get().GetSharedTx()->nVersion != 3);

23+            func(self)
24+        finally:
25+            # Clear mempool
26+            self.generate(self.nodes[0], 1)
27+            # Reset config options
28+            self.restart_node(0)

1373@@ -1304,6 +1374,7 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1374         // updated if package replace-by-fee is allowed in the future.
1375         assert(!args.m_allow_replacement);
1376         m_viewmempool.PackageAddTransaction(ws.m_ptx);
1377+        ++num_prechecks_passed;