tx_pool.cpp raw
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
5 #include <chain.h>
6 #include <coins.h>
7 #include <consensus/amount.h>
8 #include <consensus/consensus.h>
9 #include <consensus/validation.h>
10 #include <node/miner.h>
11 #include <node/mining_types.h>
12 #include <policy/feerate.h>
13 #include <policy/packages.h>
14 #include <policy/policy.h>
15 #include <policy/truc_policy.h>
16 #include <primitives/block.h>
17 #include <primitives/transaction.h>
18 #include <script/script.h>
19 #include <sync.h>
20 #include <test/fuzz/FuzzedDataProvider.h>
21 #include <test/fuzz/fuzz.h>
22 #include <test/fuzz/util.h>
23 #include <test/fuzz/util/mempool.h>
24 #include <test/util/mining.h>
25 #include <test/util/random.h>
26 #include <test/util/script.h>
27 #include <test/util/setup_common.h>
28 #include <test/util/txmempool.h>
29 #include <txmempool.h>
30 #include <util/check.h>
31 #include <util/string.h>
32 #include <util/time.h>
33 #include <util/translation.h>
34 #include <validation.h>
35 #include <validationinterface.h>
36
37 #include <cstddef>
38 #include <cstdint>
39 #include <functional>
40 #include <iterator>
41 #include <limits>
42 #include <map>
43 #include <memory>
44 #include <optional>
45 #include <set>
46 #include <span>
47 #include <string>
48 #include <utility>
49 #include <vector>
50 using node::BlockAssembler;
51 using node::BlockCreateOptions;
52 using node::NodeContext;
53 using util::ToString;
54
55 namespace {
56
57 const TestingSetup* g_setup;
58 std::vector<COutPoint> g_outpoints_coinbase_init_mature;
59 std::vector<COutPoint> g_outpoints_coinbase_init_immature;
60
61 struct MockedTxPool : public CTxMemPool {
62 void RollingFeeUpdate() EXCLUSIVE_LOCKS_REQUIRED(!cs)
63 {
64 LOCK(cs);
65 lastRollingFeeUpdate = GetTime();
66 blockSinceLastRollingFeeBump = true;
67 }
68 };
69
70 void initialize_tx_pool()
71 {
72 static const auto testing_setup = MakeNoLogFileContext<const TestingSetup>();
73 g_setup = testing_setup.get();
74 SetMockTime(WITH_LOCK(g_setup->m_node.chainman->GetMutex(), return g_setup->m_node.chainman->ActiveTip()->Time()));
75
76 for (int i = 0; i < 2 * COINBASE_MATURITY; ++i) {
77 COutPoint prevout{MineBlock(g_setup->m_node, {
78 .coinbase_output_script = P2WSH_OP_TRUE,
79 })};
80 // Remember the txids to avoid expensive disk access later on
81 auto& outpoints = i < COINBASE_MATURITY ?
82 g_outpoints_coinbase_init_mature :
83 g_outpoints_coinbase_init_immature;
84 outpoints.push_back(prevout);
85 }
86 g_setup->m_node.validation_signals->SyncWithValidationInterfaceQueue();
87 }
88
89 struct TransactionsDelta final : public CValidationInterface {
90 std::set<CTransactionRef>& m_removed;
91 std::set<CTransactionRef>& m_added;
92
93 explicit TransactionsDelta(std::set<CTransactionRef>& r, std::set<CTransactionRef>& a)
94 : m_removed{r}, m_added{a} {}
95
96 void TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /* mempool_sequence */) override
97 {
98 Assert(m_added.insert(tx.info.m_tx).second);
99 }
100
101 void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
102 {
103 Assert(m_removed.insert(tx).second);
104 }
105 };
106
107 void SetMempoolConstraints(ArgsManager& args, FuzzedDataProvider& fuzzed_data_provider)
108 {
109 args.ForceSetArg("-limitclustercount",
110 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(1, 64)));
111 args.ForceSetArg("-limitclustersize",
112 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(1, 250)));
113 args.ForceSetArg("-maxmempool",
114 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 200)));
115 args.ForceSetArg("-mempoolexpiry",
116 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 999)));
117 }
118
119 void Finish(FuzzedDataProvider& fuzzed_data_provider, MockedTxPool& tx_pool, Chainstate& chainstate)
120 {
121 WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1));
122 {
123 BlockCreateOptions options{
124 .block_min_fee_rate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)},
125 .block_max_weight = fuzzed_data_provider.ConsumeIntegralInRange<uint64_t>(DEFAULT_BLOCK_RESERVED_WEIGHT, MAX_BLOCK_WEIGHT),
126 };
127 auto assembler = BlockAssembler{chainstate, &tx_pool, options};
128 auto block_template = assembler.CreateNewBlock();
129 Assert(block_template->block.vtx.size() >= 1);
130
131 // Try updating the mempool for this block, as though it were mined.
132 LOCK2(::cs_main, tx_pool.cs);
133 tx_pool.removeForBlock(block_template->block.vtx, chainstate.m_chain.Height() + 1);
134
135 // Now try to add those transactions back, as though a reorg happened.
136 std::vector<Txid> hashes_to_update;
137 for (const auto& tx : block_template->block.vtx) {
138 const auto res = AcceptToMemoryPool(chainstate, tx, GetTime(), true, /*test_accept=*/false);
139 if (res.m_result_type == MempoolAcceptResult::ResultType::VALID) {
140 hashes_to_update.push_back(tx->GetHash());
141 } else {
142 tx_pool.removeRecursive(*tx, MemPoolRemovalReason::REORG);
143 }
144 }
145 tx_pool.UpdateTransactionsFromBlock(hashes_to_update);
146 }
147 const auto info_all = tx_pool.infoAll();
148 if (!info_all.empty()) {
149 const auto& tx_to_remove = *PickValue(fuzzed_data_provider, info_all).tx;
150 WITH_LOCK(tx_pool.cs, tx_pool.removeRecursive(tx_to_remove, MemPoolRemovalReason::BLOCK /* dummy */));
151 assert(tx_pool.size() < info_all.size());
152 }
153
154 if (fuzzed_data_provider.ConsumeBool()) {
155 // Try eviction
156 LOCK2(::cs_main, tx_pool.cs);
157 tx_pool.TrimToSize(fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0U, tx_pool.DynamicMemoryUsage() * 2));
158 }
159 if (fuzzed_data_provider.ConsumeBool()) {
160 // Try expiry
161 LOCK2(::cs_main, tx_pool.cs);
162 tx_pool.Expire(GetMockTime() - std::chrono::seconds(fuzzed_data_provider.ConsumeIntegral<uint32_t>()));
163 }
164 WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1));
165 g_setup->m_node.validation_signals->SyncWithValidationInterfaceQueue();
166 }
167
168 void MockTime(FuzzedDataProvider& fuzzed_data_provider, const Chainstate& chainstate)
169 {
170 const auto time = ConsumeTime(fuzzed_data_provider,
171 chainstate.m_chain.Tip()->GetMedianTimePast() + 1,
172 std::numeric_limits<decltype(chainstate.m_chain.Tip()->nTime)>::max());
173 SetMockTime(time);
174 }
175
176 std::unique_ptr<CTxMemPool> MakeMempool(FuzzedDataProvider& fuzzed_data_provider, const NodeContext& node)
177 {
178 // Take the default options for tests...
179 CTxMemPool::Options mempool_opts{MemPoolOptionsForTest(node)};
180
181 // ...override specific options for this specific fuzz suite
182 mempool_opts.check_ratio = 1;
183 mempool_opts.require_standard = fuzzed_data_provider.ConsumeBool();
184
185 // ...and construct a CTxMemPool from it
186 bilingual_str error;
187 auto mempool{std::make_unique<CTxMemPool>(std::move(mempool_opts), error)};
188 // ... ignore the error since it might be beneficial to fuzz even when the
189 // mempool size is unreasonably small
190 Assert(error.empty() || error.original.starts_with("-maxmempool must be at least "));
191 return mempool;
192 }
193
194 void CheckATMPInvariants(const MempoolAcceptResult& res, bool txid_in_mempool, bool wtxid_in_mempool)
195 {
196
197 switch (res.m_result_type) {
198 case MempoolAcceptResult::ResultType::VALID:
199 {
200 Assert(txid_in_mempool);
201 Assert(wtxid_in_mempool);
202 Assert(res.m_state.IsValid());
203 Assert(!res.m_state.IsInvalid());
204 Assert(res.m_vsize);
205 Assert(res.m_base_fees);
206 Assert(res.m_effective_feerate);
207 Assert(res.m_wtxids_fee_calculations);
208 Assert(!res.m_other_wtxid);
209 break;
210 }
211 case MempoolAcceptResult::ResultType::INVALID:
212 {
213 // It may be already in the mempool since in ATMP cases we don't set MEMPOOL_ENTRY or DIFFERENT_WITNESS
214 Assert(!res.m_state.IsValid());
215 Assert(res.m_state.IsInvalid());
216
217 const bool is_reconsiderable{res.m_state.GetResult() == TxValidationResult::TX_RECONSIDERABLE};
218 Assert(!res.m_vsize);
219 Assert(!res.m_base_fees);
220 // Fee information is provided if the failure is TX_RECONSIDERABLE.
221 // In other cases, validation may be unable or unwilling to calculate the fees.
222 Assert(res.m_effective_feerate.has_value() == is_reconsiderable);
223 Assert(res.m_wtxids_fee_calculations.has_value() == is_reconsiderable);
224 Assert(!res.m_other_wtxid);
225 break;
226 }
227 case MempoolAcceptResult::ResultType::MEMPOOL_ENTRY:
228 {
229 // ATMP never sets this; only set in package settings
230 Assert(false);
231 break;
232 }
233 case MempoolAcceptResult::ResultType::DIFFERENT_WITNESS:
234 {
235 // ATMP never sets this; only set in package settings
236 Assert(false);
237 break;
238 }
239 }
240 }
241
242 FUZZ_TARGET(tx_pool_standard, .init = initialize_tx_pool)
243 {
244 SeedRandomStateForTest(SeedRand::ZEROS);
245 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
246 const auto& node = g_setup->m_node;
247 auto& chainstate{static_cast<DummyChainState&>(node.chainman->ActiveChainstate())};
248
249 MockTime(fuzzed_data_provider, chainstate);
250
251 // All RBF-spendable outpoints
252 std::set<COutPoint> outpoints_rbf;
253 // All outpoints counting toward the total supply (subset of outpoints_rbf)
254 std::set<COutPoint> outpoints_supply;
255 for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
256 Assert(outpoints_supply.insert(outpoint).second);
257 }
258 outpoints_rbf = outpoints_supply;
259
260 // The sum of the values of all spendable outpoints
261 constexpr CAmount SUPPLY_TOTAL{COINBASE_MATURITY * 50 * COIN};
262
263 SetMempoolConstraints(*node.args, fuzzed_data_provider);
264 auto tx_pool_{MakeMempool(fuzzed_data_provider, node)};
265 MockedTxPool& tx_pool = *static_cast<MockedTxPool*>(tx_pool_.get());
266
267 chainstate.SetMempool(&tx_pool);
268
269 // Helper to query an amount
270 const CCoinsViewMemPool amount_view{WITH_LOCK(::cs_main, return &chainstate.CoinsTip()), tx_pool};
271 const auto GetAmount = [&](const COutPoint& outpoint) {
272 auto coin{amount_view.GetCoin(outpoint).value()};
273 return coin.out.nValue;
274 };
275
276 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100)
277 {
278 {
279 // Total supply is the mempool fee + all outpoints
280 CAmount supply_now{WITH_LOCK(tx_pool.cs, return tx_pool.GetTotalFee())};
281 for (const auto& op : outpoints_supply) {
282 supply_now += GetAmount(op);
283 }
284 Assert(supply_now == SUPPLY_TOTAL);
285 }
286 Assert(!outpoints_supply.empty());
287
288 // Create transaction to add to the mempool
289 const CTransactionRef tx = [&] {
290 CMutableTransaction tx_mut;
291 tx_mut.version = fuzzed_data_provider.ConsumeBool() ? TRUC_VERSION : CTransaction::CURRENT_VERSION;
292 tx_mut.nLockTime = fuzzed_data_provider.ConsumeBool() ? 0 : fuzzed_data_provider.ConsumeIntegral<uint32_t>();
293 const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size());
294 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size() * 2);
295
296 CAmount amount_in{0};
297 for (int i = 0; i < num_in; ++i) {
298 // Pop random outpoint
299 auto pop = outpoints_rbf.begin();
300 std::advance(pop, fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, outpoints_rbf.size() - 1));
301 const auto outpoint = *pop;
302 outpoints_rbf.erase(pop);
303 amount_in += GetAmount(outpoint);
304
305 // Create input
306 const auto sequence = ConsumeSequence(fuzzed_data_provider);
307 const auto script_sig = CScript{};
308 const auto script_wit_stack = std::vector<std::vector<uint8_t>>{WITNESS_STACK_ELEM_OP_TRUE};
309 CTxIn in;
310 in.prevout = outpoint;
311 in.nSequence = sequence;
312 in.scriptSig = script_sig;
313 in.scriptWitness.stack = script_wit_stack;
314
315 tx_mut.vin.push_back(in);
316 }
317
318 // Check sigops in mempool + block template creation
319 bool add_sigops{fuzzed_data_provider.ConsumeBool()};
320
321 const auto amount_fee = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-1000, amount_in);
322 const auto amount_out = (amount_in - amount_fee) / num_out;
323 for (int i = 0; i < num_out; ++i) {
324 if (i == 0 && add_sigops) {
325 tx_mut.vout.emplace_back(amount_out, CScript() << std::vector<unsigned char>(33, 0x02) << OP_CHECKSIG);
326 } else {
327 tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE);
328 }
329 }
330
331 auto tx = MakeTransactionRef(tx_mut);
332 // Restore previously removed outpoints
333 for (const auto& in : tx->vin) {
334 Assert(outpoints_rbf.insert(in.prevout).second);
335 }
336 return tx;
337 }();
338
339 if (fuzzed_data_provider.ConsumeBool()) {
340 MockTime(fuzzed_data_provider, chainstate);
341 }
342 if (fuzzed_data_provider.ConsumeBool()) {
343 tx_pool.RollingFeeUpdate();
344 }
345 if (fuzzed_data_provider.ConsumeBool()) {
346 const auto& txid = fuzzed_data_provider.ConsumeBool() ?
347 tx->GetHash() :
348 PickValue(fuzzed_data_provider, outpoints_rbf).hash;
349 const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN);
350 tx_pool.PrioritiseTransaction(txid, delta);
351 }
352
353 // Remember all removed and added transactions
354 std::set<CTransactionRef> removed;
355 std::set<CTransactionRef> added;
356 auto txr = std::make_shared<TransactionsDelta>(removed, added);
357 node.validation_signals->RegisterSharedValidationInterface(txr);
358
359 // Make sure ProcessNewPackage on one transaction works.
360 // The result is not guaranteed to be the same as what is returned by ATMP.
361 const auto result_package = WITH_LOCK(::cs_main,
362 return ProcessNewPackage(chainstate, tx_pool, {tx}, true, /*client_maxfeerate=*/{}));
363 // If something went wrong due to a package-specific policy, it might not return a
364 // validation result for the transaction.
365 if (result_package.m_state.GetResult() != PackageValidationResult::PCKG_POLICY) {
366 auto it = result_package.m_tx_results.find(tx->GetWitnessHash());
367 Assert(it != result_package.m_tx_results.end());
368 Assert(it->second.m_result_type == MempoolAcceptResult::ResultType::VALID ||
369 it->second.m_result_type == MempoolAcceptResult::ResultType::INVALID);
370 }
371
372 const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx, GetTime(), /*bypass_limits=*/false, /*test_accept=*/false));
373 const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
374 node.validation_signals->SyncWithValidationInterfaceQueue();
375 node.validation_signals->UnregisterSharedValidationInterface(txr);
376
377 bool txid_in_mempool = tx_pool.exists(tx->GetHash());
378 bool wtxid_in_mempool = tx_pool.exists(tx->GetWitnessHash());
379 CheckATMPInvariants(res, txid_in_mempool, wtxid_in_mempool);
380
381 Assert(accepted != added.empty());
382 if (accepted) {
383 Assert(added.size() == 1); // For now, no package acceptance
384 Assert(tx == *added.begin());
385 CheckMempoolTRUCInvariants(tx_pool);
386 } else {
387 // Do not consider rejected transaction removed
388 removed.erase(tx);
389 }
390
391 // Helper to insert spent and created outpoints of a tx into collections
392 using Sets = std::vector<std::reference_wrapper<std::set<COutPoint>>>;
393 const auto insert_tx = [](Sets created_by_tx, Sets consumed_by_tx, const auto& tx) {
394 for (size_t i{0}; i < tx.vout.size(); ++i) {
395 for (auto& set : created_by_tx) {
396 Assert(set.get().emplace(tx.GetHash(), i).second);
397 }
398 }
399 for (const auto& in : tx.vin) {
400 for (auto& set : consumed_by_tx) {
401 Assert(set.get().insert(in.prevout).second);
402 }
403 }
404 };
405 // Add created outpoints, remove spent outpoints
406 {
407 // Outpoints that no longer exist at all
408 std::set<COutPoint> consumed_erased;
409 // Outpoints that no longer count toward the total supply
410 std::set<COutPoint> consumed_supply;
411 for (const auto& removed_tx : removed) {
412 insert_tx(/*created_by_tx=*/{consumed_erased}, /*consumed_by_tx=*/{outpoints_supply}, /*tx=*/*removed_tx);
413 }
414 for (const auto& added_tx : added) {
415 insert_tx(/*created_by_tx=*/{outpoints_supply, outpoints_rbf}, /*consumed_by_tx=*/{consumed_supply}, /*tx=*/*added_tx);
416 }
417 for (const auto& p : consumed_erased) {
418 Assert(outpoints_supply.erase(p) == 1);
419 Assert(outpoints_rbf.erase(p) == 1);
420 }
421 for (const auto& p : consumed_supply) {
422 Assert(outpoints_supply.erase(p) == 1);
423 }
424 }
425 }
426 Finish(fuzzed_data_provider, tx_pool, chainstate);
427 }
428
429 FUZZ_TARGET(tx_pool, .init = initialize_tx_pool)
430 {
431 SeedRandomStateForTest(SeedRand::ZEROS);
432 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
433 const auto& node = g_setup->m_node;
434 auto& chainstate{static_cast<DummyChainState&>(node.chainman->ActiveChainstate())};
435
436 MockTime(fuzzed_data_provider, chainstate);
437
438 std::vector<Txid> txids;
439 txids.reserve(g_outpoints_coinbase_init_mature.size());
440 for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
441 txids.push_back(outpoint.hash);
442 }
443 for (int i{0}; i <= 3; ++i) {
444 // Add some immature and non-existent outpoints
445 txids.push_back(g_outpoints_coinbase_init_immature.at(i).hash);
446 txids.push_back(Txid::FromUint256(ConsumeUInt256(fuzzed_data_provider)));
447 }
448
449 SetMempoolConstraints(*node.args, fuzzed_data_provider);
450 auto tx_pool_{MakeMempool(fuzzed_data_provider, node)};
451 MockedTxPool& tx_pool = *static_cast<MockedTxPool*>(tx_pool_.get());
452
453 chainstate.SetMempool(&tx_pool);
454
455 // If we ever bypass limits, do not do TRUC invariants checks
456 bool ever_bypassed_limits{false};
457
458 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 300)
459 {
460 const auto mut_tx = ConsumeTransaction(fuzzed_data_provider, txids);
461
462 if (fuzzed_data_provider.ConsumeBool()) {
463 MockTime(fuzzed_data_provider, chainstate);
464 }
465 if (fuzzed_data_provider.ConsumeBool()) {
466 tx_pool.RollingFeeUpdate();
467 }
468 if (fuzzed_data_provider.ConsumeBool()) {
469 const auto txid = fuzzed_data_provider.ConsumeBool() ?
470 mut_tx.GetHash() :
471 PickValue(fuzzed_data_provider, txids);
472 const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN);
473 tx_pool.PrioritiseTransaction(txid, delta);
474 }
475
476 const bool bypass_limits{fuzzed_data_provider.ConsumeBool()};
477 ever_bypassed_limits |= bypass_limits;
478
479 const auto tx = MakeTransactionRef(mut_tx);
480 const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx, GetTime(), bypass_limits, /*test_accept=*/false));
481 const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
482 if (accepted) {
483 txids.push_back(tx->GetHash());
484 if (!ever_bypassed_limits) {
485 CheckMempoolTRUCInvariants(tx_pool);
486 }
487 }
488 }
489 Finish(fuzzed_data_provider, tx_pool, chainstate);
490 }
491 } // namespace
492