tx_pool.cpp
1 // Copyright (c) 2021-2022 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 48 BlockAssembler::Options options; 49 options.coinbase_output_script = P2WSH_OP_TRUE; 50 51 for (int i = 0; i < 2 * COINBASE_MATURITY; ++i) { 52 COutPoint prevout{MineBlock(g_setup->m_node, options)}; 53 // Remember the txids to avoid expensive disk access later on 54 auto& outpoints = i < COINBASE_MATURITY ? 55 g_outpoints_coinbase_init_mature : 56 g_outpoints_coinbase_init_immature; 57 outpoints.push_back(prevout); 58 } 59 g_setup->m_node.validation_signals->SyncWithValidationInterfaceQueue(); 60 } 61 62 struct TransactionsDelta final : public CValidationInterface { 63 std::set<CTransactionRef>& m_removed; 64 std::set<CTransactionRef>& m_added; 65 66 explicit TransactionsDelta(std::set<CTransactionRef>& r, std::set<CTransactionRef>& a) 67 : m_removed{r}, m_added{a} {} 68 69 void TransactionAddedToMempool(const NewMempoolTransactionInfo& tx, uint64_t /* mempool_sequence */) override 70 { 71 Assert(m_added.insert(tx.info.m_tx).second); 72 } 73 74 void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override 75 { 76 Assert(m_removed.insert(tx).second); 77 } 78 }; 79 80 void SetMempoolConstraints(ArgsManager& args, FuzzedDataProvider& fuzzed_data_provider) 81 { 82 args.ForceSetArg("-limitancestorcount", 83 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50))); 84 args.ForceSetArg("-limitancestorsize", 85 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202))); 86 args.ForceSetArg("-limitdescendantcount", 87 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50))); 88 args.ForceSetArg("-limitdescendantsize", 89 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202))); 90 args.ForceSetArg("-maxmempool", 91 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 200))); 92 args.ForceSetArg("-mempoolexpiry", 93 ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 999))); 94 } 95 96 void Finish(FuzzedDataProvider& fuzzed_data_provider, MockedTxPool& tx_pool, Chainstate& chainstate) 97 { 98 WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1)); 99 { 100 BlockAssembler::Options options; 101 options.nBlockMaxWeight = fuzzed_data_provider.ConsumeIntegralInRange(0U, MAX_BLOCK_WEIGHT); 102 options.blockMinFeeRate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; 103 auto assembler = BlockAssembler{chainstate, &tx_pool, options}; 104 auto block_template = assembler.CreateNewBlock(); 105 Assert(block_template->block.vtx.size() >= 1); 106 } 107 const auto info_all = tx_pool.infoAll(); 108 if (!info_all.empty()) { 109 const auto& tx_to_remove = *PickValue(fuzzed_data_provider, info_all).tx; 110 WITH_LOCK(tx_pool.cs, tx_pool.removeRecursive(tx_to_remove, MemPoolRemovalReason::BLOCK /* dummy */)); 111 assert(tx_pool.size() < info_all.size()); 112 WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1)); 113 } 114 g_setup->m_node.validation_signals->SyncWithValidationInterfaceQueue(); 115 } 116 117 void MockTime(FuzzedDataProvider& fuzzed_data_provider, const Chainstate& chainstate) 118 { 119 const auto time = ConsumeTime(fuzzed_data_provider, 120 chainstate.m_chain.Tip()->GetMedianTimePast() + 1, 121 std::numeric_limits<decltype(chainstate.m_chain.Tip()->nTime)>::max()); 122 SetMockTime(time); 123 } 124 125 std::unique_ptr<CTxMemPool> MakeMempool(FuzzedDataProvider& fuzzed_data_provider, const NodeContext& node) 126 { 127 // Take the default options for tests... 128 CTxMemPool::Options mempool_opts{MemPoolOptionsForTest(node)}; 129 130 // ...override specific options for this specific fuzz suite 131 mempool_opts.check_ratio = 1; 132 mempool_opts.require_standard = fuzzed_data_provider.ConsumeBool(); 133 134 // ...and construct a CTxMemPool from it 135 bilingual_str error; 136 auto mempool{std::make_unique<CTxMemPool>(std::move(mempool_opts), error)}; 137 // ... ignore the error since it might be beneficial to fuzz even when the 138 // mempool size is unreasonably small 139 Assert(error.empty() || error.original.starts_with("-maxmempool must be at least ")); 140 return mempool; 141 } 142 143 void CheckATMPInvariants(const MempoolAcceptResult& res, bool txid_in_mempool, bool wtxid_in_mempool) 144 { 145 146 switch (res.m_result_type) { 147 case MempoolAcceptResult::ResultType::VALID: 148 { 149 Assert(txid_in_mempool); 150 Assert(wtxid_in_mempool); 151 Assert(res.m_state.IsValid()); 152 Assert(!res.m_state.IsInvalid()); 153 Assert(res.m_vsize); 154 Assert(res.m_base_fees); 155 Assert(res.m_effective_feerate); 156 Assert(res.m_wtxids_fee_calculations); 157 Assert(!res.m_other_wtxid); 158 break; 159 } 160 case MempoolAcceptResult::ResultType::INVALID: 161 { 162 // It may be already in the mempool since in ATMP cases we don't set MEMPOOL_ENTRY or DIFFERENT_WITNESS 163 Assert(!res.m_state.IsValid()); 164 Assert(res.m_state.IsInvalid()); 165 166 const bool is_reconsiderable{res.m_state.GetResult() == TxValidationResult::TX_RECONSIDERABLE}; 167 Assert(!res.m_vsize); 168 Assert(!res.m_base_fees); 169 // Fee information is provided if the failure is TX_RECONSIDERABLE. 170 // In other cases, validation may be unable or unwilling to calculate the fees. 171 Assert(res.m_effective_feerate.has_value() == is_reconsiderable); 172 Assert(res.m_wtxids_fee_calculations.has_value() == is_reconsiderable); 173 Assert(!res.m_other_wtxid); 174 break; 175 } 176 case MempoolAcceptResult::ResultType::MEMPOOL_ENTRY: 177 { 178 // ATMP never sets this; only set in package settings 179 Assert(false); 180 break; 181 } 182 case MempoolAcceptResult::ResultType::DIFFERENT_WITNESS: 183 { 184 // ATMP never sets this; only set in package settings 185 Assert(false); 186 break; 187 } 188 } 189 } 190 191 FUZZ_TARGET(tx_pool_standard, .init = initialize_tx_pool) 192 { 193 SeedRandomStateForTest(SeedRand::ZEROS); 194 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 195 const auto& node = g_setup->m_node; 196 auto& chainstate{static_cast<DummyChainState&>(node.chainman->ActiveChainstate())}; 197 198 MockTime(fuzzed_data_provider, chainstate); 199 200 // All RBF-spendable outpoints 201 std::set<COutPoint> outpoints_rbf; 202 // All outpoints counting toward the total supply (subset of outpoints_rbf) 203 std::set<COutPoint> outpoints_supply; 204 for (const auto& outpoint : g_outpoints_coinbase_init_mature) { 205 Assert(outpoints_supply.insert(outpoint).second); 206 } 207 outpoints_rbf = outpoints_supply; 208 209 // The sum of the values of all spendable outpoints 210 constexpr CAmount SUPPLY_TOTAL{COINBASE_MATURITY * 50 * COIN}; 211 212 SetMempoolConstraints(*node.args, fuzzed_data_provider); 213 auto tx_pool_{MakeMempool(fuzzed_data_provider, node)}; 214 MockedTxPool& tx_pool = *static_cast<MockedTxPool*>(tx_pool_.get()); 215 216 chainstate.SetMempool(&tx_pool); 217 218 // Helper to query an amount 219 const CCoinsViewMemPool amount_view{WITH_LOCK(::cs_main, return &chainstate.CoinsTip()), tx_pool}; 220 const auto GetAmount = [&](const COutPoint& outpoint) { 221 auto coin{amount_view.GetCoin(outpoint).value()}; 222 return coin.out.nValue; 223 }; 224 225 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 300) 226 { 227 { 228 // Total supply is the mempool fee + all outpoints 229 CAmount supply_now{WITH_LOCK(tx_pool.cs, return tx_pool.GetTotalFee())}; 230 for (const auto& op : outpoints_supply) { 231 supply_now += GetAmount(op); 232 } 233 Assert(supply_now == SUPPLY_TOTAL); 234 } 235 Assert(!outpoints_supply.empty()); 236 237 // Create transaction to add to the mempool 238 const CTransactionRef tx = [&] { 239 CMutableTransaction tx_mut; 240 tx_mut.version = fuzzed_data_provider.ConsumeBool() ? TRUC_VERSION : CTransaction::CURRENT_VERSION; 241 tx_mut.nLockTime = fuzzed_data_provider.ConsumeBool() ? 0 : fuzzed_data_provider.ConsumeIntegral<uint32_t>(); 242 const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size()); 243 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size() * 2); 244 245 CAmount amount_in{0}; 246 for (int i = 0; i < num_in; ++i) { 247 // Pop random outpoint 248 auto pop = outpoints_rbf.begin(); 249 std::advance(pop, fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, outpoints_rbf.size() - 1)); 250 const auto outpoint = *pop; 251 outpoints_rbf.erase(pop); 252 amount_in += GetAmount(outpoint); 253 254 // Create input 255 const auto sequence = ConsumeSequence(fuzzed_data_provider); 256 const auto script_sig = CScript{}; 257 const auto script_wit_stack = std::vector<std::vector<uint8_t>>{WITNESS_STACK_ELEM_OP_TRUE}; 258 CTxIn in; 259 in.prevout = outpoint; 260 in.nSequence = sequence; 261 in.scriptSig = script_sig; 262 in.scriptWitness.stack = script_wit_stack; 263 264 tx_mut.vin.push_back(in); 265 } 266 const auto amount_fee = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-1000, amount_in); 267 const auto amount_out = (amount_in - amount_fee) / num_out; 268 for (int i = 0; i < num_out; ++i) { 269 tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE); 270 } 271 auto tx = MakeTransactionRef(tx_mut); 272 // Restore previously removed outpoints 273 for (const auto& in : tx->vin) { 274 Assert(outpoints_rbf.insert(in.prevout).second); 275 } 276 return tx; 277 }(); 278 279 if (fuzzed_data_provider.ConsumeBool()) { 280 MockTime(fuzzed_data_provider, chainstate); 281 } 282 if (fuzzed_data_provider.ConsumeBool()) { 283 tx_pool.RollingFeeUpdate(); 284 } 285 if (fuzzed_data_provider.ConsumeBool()) { 286 const auto& txid = fuzzed_data_provider.ConsumeBool() ? 287 tx->GetHash() : 288 PickValue(fuzzed_data_provider, outpoints_rbf).hash; 289 const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN); 290 tx_pool.PrioritiseTransaction(txid.ToUint256(), delta); 291 } 292 293 // Remember all removed and added transactions 294 std::set<CTransactionRef> removed; 295 std::set<CTransactionRef> added; 296 auto txr = std::make_shared<TransactionsDelta>(removed, added); 297 node.validation_signals->RegisterSharedValidationInterface(txr); 298 const bool bypass_limits = fuzzed_data_provider.ConsumeBool(); 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, /*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 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 300) 397 { 398 const auto mut_tx = ConsumeTransaction(fuzzed_data_provider, txids); 399 400 if (fuzzed_data_provider.ConsumeBool()) { 401 MockTime(fuzzed_data_provider, chainstate); 402 } 403 if (fuzzed_data_provider.ConsumeBool()) { 404 tx_pool.RollingFeeUpdate(); 405 } 406 if (fuzzed_data_provider.ConsumeBool()) { 407 const auto txid = fuzzed_data_provider.ConsumeBool() ? 408 mut_tx.GetHash() : 409 PickValue(fuzzed_data_provider, txids); 410 const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN); 411 tx_pool.PrioritiseTransaction(txid.ToUint256(), delta); 412 } 413 414 const auto tx = MakeTransactionRef(mut_tx); 415 const bool bypass_limits = fuzzed_data_provider.ConsumeBool(); 416 const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx, GetTime(), bypass_limits, /*test_accept=*/false)); 417 const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID; 418 if (accepted) { 419 txids.push_back(tx->GetHash()); 420 CheckMempoolTRUCInvariants(tx_pool); 421 } 422 } 423 Finish(fuzzed_data_provider, tx_pool, chainstate); 424 } 425 } // namespace