rbf.cpp raw
1 // Copyright (c) 2020-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
5 #include <node/mempool_args.h>
6 #include <policy/rbf.h>
7 #include <primitives/transaction.h>
8 #include <sync.h>
9 #include <test/fuzz/FuzzedDataProvider.h>
10 #include <test/fuzz/fuzz.h>
11 #include <test/fuzz/util.h>
12 #include <test/fuzz/util/mempool.h>
13 #include <test/util/setup_common.h>
14 #include <test/util/time.h>
15 #include <test/util/txmempool.h>
16 #include <txmempool.h>
17 #include <util/check.h>
18 #include <util/translation.h>
19
20 #include <cstdint>
21 #include <optional>
22 #include <string>
23 #include <vector>
24
25 namespace {
26 const BasicTestingSetup* g_setup;
27 } // namespace
28
29 const int NUM_ITERS = 10000;
30
31 std::vector<COutPoint> g_outpoints;
32
33 void initialize_rbf()
34 {
35 static const auto testing_setup = MakeNoLogFileContext<>();
36 g_setup = testing_setup.get();
37 }
38
39 void initialize_package_rbf()
40 {
41 static const auto testing_setup = MakeNoLogFileContext<>();
42 g_setup = testing_setup.get();
43
44 // Create a fixed set of unique "UTXOs" to source parents from
45 // to avoid fuzzer giving circular references
46 for (int i = 0; i < NUM_ITERS; ++i) {
47 g_outpoints.emplace_back();
48 g_outpoints.back().n = i;
49 }
50
51 }
52
53 FUZZ_TARGET(rbf, .init = initialize_rbf)
54 {
55 SeedRandomStateForTest(SeedRand::ZEROS);
56 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
57 FakeNodeClock clock{ConsumeTime(fuzzed_data_provider)};
58 std::optional<CMutableTransaction> mtx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
59 if (!mtx) {
60 return;
61 }
62
63 bilingual_str error;
64 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
65 Assert(error.empty());
66
67 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), NUM_ITERS)
68 {
69 const std::optional<CMutableTransaction> another_mtx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
70 if (!another_mtx) {
71 break;
72 }
73 const CTransaction another_tx{*another_mtx};
74 if (fuzzed_data_provider.ConsumeBool() && !mtx->vin.empty()) {
75 mtx->vin[0].prevout = COutPoint{another_tx.GetHash(), 0};
76 }
77 LOCK2(cs_main, pool.cs);
78 if (!pool.GetIter(another_tx.GetHash())) {
79 TryAddToMempool(pool, ConsumeTxMemPoolEntry(fuzzed_data_provider, another_tx));
80 }
81 }
82 const CTransaction tx{*mtx};
83 if (fuzzed_data_provider.ConsumeBool()) {
84 LOCK2(cs_main, pool.cs);
85 if (!pool.GetIter(tx.GetHash())) {
86 TryAddToMempool(pool, ConsumeTxMemPoolEntry(fuzzed_data_provider, tx));
87 }
88 }
89 {
90 LOCK(pool.cs);
91 (void)IsRBFOptIn(tx, pool);
92 }
93 }
94
95 FUZZ_TARGET(package_rbf, .init = initialize_package_rbf)
96 {
97 SeedRandomStateForTest(SeedRand::ZEROS);
98 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
99 FakeNodeClock clock{ConsumeTime(fuzzed_data_provider)};
100
101 // "Real" virtual size is not important for this test since ConsumeTxMemPoolEntry generates its own virtual size values
102 // so we construct small transactions for performance reasons. Child simply needs an input for later to perhaps connect to parent.
103 CMutableTransaction child;
104 child.vin.resize(1);
105
106 bilingual_str error;
107 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
108 Assert(error.empty());
109
110 // Add a bunch of parent-child pairs to the mempool, and remember them.
111 std::vector<CTransaction> mempool_txs;
112 uint32_t iter{0};
113
114 // Keep track of the total vsize of CTxMemPoolEntry's being added to the mempool to avoid overflow
115 // Add replacement_vsize since this is added to new diagram during RBF check
116 std::optional<CMutableTransaction> replacement_tx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
117 if (!replacement_tx) {
118 return;
119 }
120 replacement_tx->vin.resize(1);
121 replacement_tx->vin[0].prevout = g_outpoints.at(iter++);
122 CTransaction replacement_tx_final{*replacement_tx};
123 auto replacement_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, replacement_tx_final);
124 int32_t replacement_weight = replacement_entry.GetAdjustedWeight();
125 // Ensure that we don't hit FeeFrac limits, as we store TxGraph entries in terms of FeePerWeight
126 int64_t running_vsize_total{replacement_entry.GetTxSize()};
127
128 LOCK2(cs_main, pool.cs);
129
130 while (fuzzed_data_provider.ConsumeBool()) {
131 if (iter >= NUM_ITERS) break;
132
133 // Make sure txns only have one input, and that a unique input is given to avoid circular references
134 CMutableTransaction parent;
135 parent.vin.resize(1);
136 parent.vin[0].prevout = g_outpoints.at(iter++);
137 parent.vout.emplace_back(0, CScript());
138
139 mempool_txs.emplace_back(parent);
140 const auto parent_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back());
141 running_vsize_total += parent_entry.GetTxSize();
142 if (running_vsize_total * WITNESS_SCALE_FACTOR > std::numeric_limits<int32_t>::max()) {
143 // We aren't adding this final tx to mempool, so we don't want to conflict with it
144 mempool_txs.pop_back();
145 break;
146 }
147 assert(!pool.GetIter(parent_entry.GetTx().GetHash()));
148 TryAddToMempool(pool, parent_entry);
149
150 // It's possible that adding this to the mempool failed due to cluster
151 // size limits; if so bail out.
152 if(!pool.GetIter(parent_entry.GetTx().GetHash())) {
153 mempool_txs.pop_back();
154 continue;
155 }
156
157 child.vin[0].prevout = COutPoint{mempool_txs.back().GetHash(), 0};
158 mempool_txs.emplace_back(child);
159 const auto child_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back());
160 running_vsize_total += child_entry.GetTxSize();
161 if (running_vsize_total * WITNESS_SCALE_FACTOR > std::numeric_limits<int32_t>::max()) {
162 // We aren't adding this final tx to mempool, so we don't want to conflict with it
163 mempool_txs.pop_back();
164 break;
165 }
166 if (!pool.GetIter(child_entry.GetTx().GetHash())) {
167 TryAddToMempool(pool, child_entry);
168 // Adding this transaction to the mempool may fail due to cluster
169 // size limits; if so bail out.
170 if(!pool.GetIter(child_entry.GetTx().GetHash())) {
171 mempool_txs.pop_back();
172 continue;
173 }
174 }
175
176 if (fuzzed_data_provider.ConsumeBool()) {
177 pool.PrioritiseTransaction(mempool_txs.back().GetHash(), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(-100000, 100000));
178 }
179 }
180
181 // Pick some transactions at random to be the direct conflicts
182 CTxMemPool::setEntries direct_conflicts;
183 for (auto& tx : mempool_txs) {
184 if (fuzzed_data_provider.ConsumeBool() && pool.GetIter(tx.GetHash())) {
185 direct_conflicts.insert(*pool.GetIter(tx.GetHash()));
186 }
187 }
188
189 // Calculate all conflicts:
190 CTxMemPool::setEntries all_conflicts;
191 for (auto& txiter : direct_conflicts) {
192 pool.CalculateDescendants(txiter, all_conflicts);
193 }
194
195 CAmount replacement_fees = ConsumeMoney(fuzzed_data_provider);
196 auto changeset = pool.GetChangeSet();
197 for (auto& txiter : all_conflicts) {
198 changeset->StageRemoval(txiter);
199 }
200 changeset->StageAddition(replacement_entry.GetSharedTx(), replacement_fees,
201 replacement_entry.GetTime().count(), replacement_entry.GetHeight(),
202 replacement_entry.GetSequence(), replacement_entry.GetSpendsCoinbase(),
203 replacement_entry.GetSigOpCost(), replacement_entry.GetLockPoints());
204 // Calculate the chunks for a replacement.
205 auto calc_results{changeset->CalculateChunksForRBF()};
206
207 if (calc_results.has_value()) {
208 // Sanity checks on the chunks.
209
210 // Feerates are monotonically decreasing.
211 FeeFrac first_sum;
212 for (size_t i = 0; i < calc_results->first.size(); ++i) {
213 first_sum += calc_results->first[i];
214 if (i) assert(ByRatio{calc_results->first[i - 1]} >= ByRatio{calc_results->first[i]});
215 }
216 FeeFrac second_sum;
217 for (size_t i = 0; i < calc_results->second.size(); ++i) {
218 second_sum += calc_results->second[i];
219 if (i) assert(ByRatio{calc_results->second[i - 1]} >= ByRatio{calc_results->second[i]});
220 }
221
222 FeeFrac replaced;
223 for (auto txiter : all_conflicts) {
224 replaced.fee += txiter->GetModifiedFee();
225 replaced.size += txiter->GetAdjustedWeight();
226 }
227 // The total fee & size of the new diagram minus replaced fee & size should be the total
228 // fee & size of the old diagram minus replacement fee & size.
229 assert((first_sum - replaced) == (second_sum - FeeFrac{replacement_fees, replacement_weight}));
230 }
231
232 // If internals report error, wrapper should too
233 auto err_tuple{ImprovesFeerateDiagram(*changeset)};
234 if (!calc_results.has_value()) {
235 assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE);
236 } else {
237 // Diagram check succeeded
238 auto old_sum = std::accumulate(calc_results->first.begin(), calc_results->first.end(), FeeFrac{});
239 auto new_sum = std::accumulate(calc_results->second.begin(), calc_results->second.end(), FeeFrac{});
240 if (!err_tuple.has_value()) {
241 // New diagram's final fee should always match or exceed old diagram's
242 assert(old_sum.fee <= new_sum.fee);
243 } else if (old_sum.fee > new_sum.fee) {
244 // Or it failed, and if old diagram had higher fees, it should be a failure
245 assert(err_tuple.value().first == DiagramCheckError::FAILURE);
246 }
247 }
248 }
249