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