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