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