Inside Bitcoin

1// Copyright (c) 2021-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4#include <common/system.h>
5#include <policy/rbf.h>
6#include <random.h>
7#include <test/util/txmempool.h>
8#include <txmempool.h>
9#include <util/time.h>
10
11#include <test/util/setup_common.h>
12
13#include <boost/test/unit_test.hpp>
14#include <optional>
15#include <vector>
16
17BOOST_FIXTURE_TEST_SUITE(rbf_tests, BasicTestingSetup)
18
19static inline CTransactionRef make_tx(const std::vector<CTransactionRef>& inputs,
20                                      const std::vector<CAmount>& output_values)
21{
22    CMutableTransaction tx = CMutableTransaction();
23    tx.vin.resize(inputs.size());
24    tx.vout.resize(output_values.size());
25    for (size_t i = 0; i < inputs.size(); ++i) {
26        tx.vin[i].prevout.hash = inputs[i]->GetHash();
27        tx.vin[i].prevout.n = 0;
28        // Add a witness so wtxid != txid
29        CScriptWitness witness;
30        witness.stack.emplace_back(i + 10);
31        tx.vin[i].scriptWitness = witness;
32    }
33    for (size_t i = 0; i < output_values.size(); ++i) {
34        tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
35        tx.vout[i].nValue = output_values[i];
36    }
37    return MakeTransactionRef(tx);
38}
39
40static CTransactionRef add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool)
41    EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs)
42{
43    AssertLockHeld(::cs_main);
44    AssertLockHeld(pool.cs);
45    TestMemPoolEntryHelper entry;
46    // Assumes this isn't already spent in mempool
47    auto tx_to_spend = tx;
48    for (int32_t i{0}; i < num_descendants; ++i) {
49        auto next_tx = make_tx(/*inputs=*/{tx_to_spend}, /*output_values=*/{(50 - i) * CENT});
50        TryAddToMempool(pool, entry.FromTx(next_tx));
51        BOOST_CHECK(pool.GetIter(next_tx->GetHash()).has_value());
52        tx_to_spend = next_tx;
53    }
54    // Return last created tx
55    return tx_to_spend;
56}
57
58BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
59{
60    CTxMemPool& pool = *Assert(m_node.mempool);
61    LOCK2(::cs_main, pool.cs);
62    TestMemPoolEntryHelper entry;
63
64    const CAmount low_fee{CENT/100};
65    const CAmount normal_fee{CENT/10};
66    const CAmount high_fee{CENT};
67
68    // Create a parent tx1 and child tx2 with normal fees:
69    const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
70    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx1));
71    const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
72    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx2));
73
74    // Create a low-feerate parent tx3 and high-feerate child tx4 (cpfp)
75    const auto tx3 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {1099 * CENT});
76    TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx3));
77    const auto tx4 = make_tx(/*inputs=*/ {tx3}, /*output_values=*/ {999 * CENT});
78    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx4));
79
80    // Create a parent tx5 and child tx6 where both have very low fees
81    const auto tx5 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {1099 * CENT});
82    TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx5));
83    const auto tx6 = make_tx(/*inputs=*/ {tx5}, /*output_values=*/ {1098 * CENT});
84    TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx6));
85    // Make tx6's modified fee much higher than its base fee. This should cause it to pass
86    // the fee-related checks despite being low-feerate.
87    pool.PrioritiseTransaction(tx6->GetHash(), 1 * COIN);
88
89    // Two independent high-feerate transactions, tx7 and tx8
90    const auto tx7 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {999 * CENT});
91    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx7));
92    const auto tx8 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {999 * CENT});
93    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx8));
94
95    // Will make these two parents of single child
96    const auto tx11 = make_tx(/*inputs=*/ {m_coinbase_txns[7]}, /*output_values=*/ {995 * CENT});
97    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx11));
98    const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT});
99    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx12));
100
101    // Will make two children of this single parent
102    const auto tx13 = make_tx(/*inputs=*/ {m_coinbase_txns[9]}, /*output_values=*/ {995 * CENT, 995 * CENT});
103    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx13));
104
105    const auto entry1_normal = pool.GetIter(tx1->GetHash()).value();
106    const auto entry2_normal = pool.GetIter(tx2->GetHash()).value();
107    const auto entry3_low = pool.GetIter(tx3->GetHash()).value();
108    const auto entry4_high = pool.GetIter(tx4->GetHash()).value();
109    const auto entry5_low = pool.GetIter(tx5->GetHash()).value();
110    const auto entry6_low_prioritised = pool.GetIter(tx6->GetHash()).value();
111    const auto entry7_high = pool.GetIter(tx7->GetHash()).value();
112    const auto entry8_high = pool.GetIter(tx8->GetHash()).value();
113
114    BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee);
115    BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee);
116    BOOST_CHECK_EQUAL(entry3_low->GetFee(), low_fee);
117    BOOST_CHECK_EQUAL(entry4_high->GetFee(), high_fee);
118    BOOST_CHECK_EQUAL(entry5_low->GetFee(), low_fee);
119    BOOST_CHECK_EQUAL(entry6_low_prioritised->GetFee(), low_fee);
120    BOOST_CHECK_EQUAL(entry7_high->GetFee(), high_fee);
121    BOOST_CHECK_EQUAL(entry8_high->GetFee(), high_fee);
122
123    CTxMemPool::setEntries set_12_normal{entry1_normal, entry2_normal};
124    CTxMemPool::setEntries empty_set;
125
126    const auto unused_txid = Txid::FromUint256(GetRandHash());
127
128    // Tests for EntriesAndTxidsDisjoint
129    BOOST_CHECK(EntriesAndTxidsDisjoint(empty_set, {tx1->GetHash()}, unused_txid) == std::nullopt);
130    BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx3->GetHash()}, unused_txid) == std::nullopt);
131    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx2->GetHash()}, unused_txid).has_value());
132    BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx1->GetHash()}, unused_txid).has_value());
133    BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx2->GetHash()}, unused_txid).has_value());
134    // EntriesAndTxidsDisjoint does not calculate descendants of iters_conflicting; it uses whatever
135    // the caller passed in. As such, no error is returned even though entry2_normal is a descendant of tx1.
136    BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx1->GetHash()}, unused_txid) == std::nullopt);
137
138    // Tests for PaysForRBF
139    const CFeeRate incremental_relay_feerate{DEFAULT_INCREMENTAL_RELAY_FEE};
140    const CFeeRate higher_relay_feerate{2 * DEFAULT_INCREMENTAL_RELAY_FEE};
141    // Must pay at least as much as the original.
142    BOOST_CHECK(PaysForRBF(/*original_fees=*/high_fee,
143                           /*replacement_fees=*/high_fee,
144                           /*replacement_vsize=*/1,
145                           /*relay_fee=*/CFeeRate(0),
146                           /*txid=*/unused_txid)
147                           == std::nullopt);
148    BOOST_CHECK(PaysForRBF(high_fee, high_fee - 1, 1, CFeeRate(0), unused_txid).has_value());
149    BOOST_CHECK(PaysForRBF(high_fee + 1, high_fee, 1, CFeeRate(0), unused_txid).has_value());
150    // Additional fees must cover the replacement's vsize at incremental relay fee
151    BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 11, incremental_relay_feerate, unused_txid).has_value());
152    BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 10, incremental_relay_feerate, unused_txid) == std::nullopt);
153    BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 11, higher_relay_feerate, unused_txid).has_value());
154    BOOST_CHECK(PaysForRBF(high_fee, high_fee + 4, 20, higher_relay_feerate, unused_txid) == std::nullopt);
155    BOOST_CHECK(PaysForRBF(low_fee, high_fee, 99999999, incremental_relay_feerate, unused_txid).has_value());
156    BOOST_CHECK(PaysForRBF(low_fee, high_fee + 99999999, 99999999, incremental_relay_feerate, unused_txid) == std::nullopt);
157}
158
159BOOST_FIXTURE_TEST_CASE(rbf_conflicts_calculator, TestChain100Setup)
160{
161    CTxMemPool& pool = *Assert(m_node.mempool);
162    LOCK2(::cs_main, pool.cs);
163    TestMemPoolEntryHelper entry;
164
165    const CAmount normal_fee{CENT/10};
166
167    // Create two parent transactions with 51 outputs each
168    const int NUM_OUTPUTS = 51;
169    std::vector<CAmount> output_values;
170    output_values.reserve(NUM_OUTPUTS);
171    for (int i = 0; i < NUM_OUTPUTS; ++i) {
172        output_values.push_back(1 * COIN);
173    }
174
175    const auto parent_tx_1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ output_values);
176    const auto parent_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ output_values);
177    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(parent_tx_1));
178    TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(parent_tx_2));
179
180    std::vector<CTransactionRef> direct_children;
181
182    // Create individual spends of these outputs
183    for (const auto& parent_tx : {parent_tx_1, parent_tx_2}) {
184        for (auto i = 0; i < NUM_OUTPUTS; ++i) {
185            auto pretx = make_tx(/*inputs=*/ {parent_tx}, /*output_values=*/ {995 * CENT});
186            CMutableTransaction tx(*pretx);
187            tx.vin[0].prevout.n = i;
188            TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx));
189            BOOST_CHECK(pool.GetIter(tx.GetHash()).has_value());
190            direct_children.push_back(MakeTransactionRef(tx));
191        }
192    }
193
194    // At this point, we should have 2 clusters in the mempool, each with 52
195    // transactions.
196
197    // parent_tx and all children are in one cluster, so we can have as many
198    // conflicts within this cluster as we want without violating the RBF conflicts
199    // limit.
200    const auto parent_entry_1 = pool.GetIter(parent_tx_1->GetHash()).value();
201    const auto parent_entry_2 = pool.GetIter(parent_tx_2->GetHash()).value();
202    const auto conflicting_transaction = make_tx({parent_tx_1, parent_tx_2}, {50 * CENT});
203    CTxMemPool::setEntries all_conflicts, dummy;
204    BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
205                                       /*pool=*/ pool,
206                                       /*iters_conflicting=*/ {parent_entry_1, parent_entry_2},
207                                       /*all_conflicts=*/ all_conflicts) == std::nullopt);
208
209    dummy.clear();
210    // Conflicting directly with all those conflicts doesn't change anything.
211    BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
212                                       /*pool=*/ pool,
213                                       /*iters_conflicting=*/ all_conflicts,
214                                       /*all_conflicts=*/ dummy) == std::nullopt);
215    BOOST_CHECK_EQUAL(all_conflicts.size(), dummy.size());
216    dummy.clear();
217
218    // If we mine the parent_tx's, then the clusters split (102 clusters).
219    pool.removeForBlock({parent_tx_1, parent_tx_2});
220
221    // Add some descendants now to each of the direct children (we can do this now that the clusters have split).
222    for (const auto& child : direct_children) {
223        add_descendants(child, 10, pool);
224    }
225
226    // We can conflict with 100 different clusters, even if they have lots of transactions.
227    CTxMemPool::setEntries conflicts;
228    for (auto i = 0; i < 100; ++i) {
229        conflicts.insert(pool.GetIter(direct_children[i]->GetHash()).value());
230    }
231    BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
232                                       /*pool=*/ pool,
233                                       /*iters_conflicting=*/ conflicts,
234                                       /*all_conflicts=*/ dummy) == std::nullopt);
235
236    // Conflicting with 1 more distinct cluster causes failure, however.
237    conflicts.insert(pool.GetIter(direct_children[100]->GetHash()).value());
238    BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
239                                       /*pool=*/ pool,
240                                       /*iters_conflicting=*/ conflicts,
241                                       /*all_conflicts=*/ dummy).has_value());
242}
243
244BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup)
245{
246    CTxMemPool& pool = *Assert(m_node.mempool);
247    LOCK2(::cs_main, pool.cs);
248    TestMemPoolEntryHelper entry;
249
250    const CAmount low_fee{CENT/100};