txorphan.cpp
1 // Copyright (c) 2022-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/amount.h> 6 #include <consensus/validation.h> 7 #include <net_processing.h> 8 #include <node/eviction.h> 9 #include <node/txorphanage.h> 10 #include <policy/policy.h> 11 #include <primitives/transaction.h> 12 #include <script/script.h> 13 #include <sync.h> 14 #include <test/fuzz/FuzzedDataProvider.h> 15 #include <test/fuzz/fuzz.h> 16 #include <test/fuzz/util.h> 17 #include <test/util/setup_common.h> 18 #include <test/util/time.h> 19 #include <uint256.h> 20 #include <util/check.h> 21 #include <util/feefrac.h> 22 #include <util/time.h> 23 24 #include <algorithm> 25 #include <bitset> 26 #include <cmath> 27 #include <cstdint> 28 #include <iostream> 29 #include <memory> 30 #include <set> 31 #include <utility> 32 #include <vector> 33 34 void initialize_orphanage() 35 { 36 static const auto testing_setup = MakeNoLogFileContext(); 37 } 38 39 FUZZ_TARGET(txorphan, .init = initialize_orphanage) 40 { 41 SeedRandomStateForTest(SeedRand::ZEROS); 42 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 43 FastRandomContext orphanage_rng{ConsumeUInt256(fuzzed_data_provider)}; 44 NodeClockContext clock_ctx{ConsumeTime(fuzzed_data_provider)}; 45 46 auto orphanage = node::MakeTxOrphanage(); 47 std::vector<COutPoint> outpoints; // Duplicates are tolerated 48 outpoints.reserve(200'000); 49 50 // initial outpoints used to construct transactions later 51 for (uint8_t i = 0; i < 4; i++) { 52 outpoints.emplace_back(Txid::FromUint256(uint256{i}), 0); 53 } 54 55 CTransactionRef ptx_potential_parent = nullptr; 56 57 std::vector<CTransactionRef> tx_history; 58 59 LIMITED_WHILE(outpoints.size() < 200'000 && fuzzed_data_provider.ConsumeBool(), 1000) 60 { 61 // construct transaction 62 const CTransactionRef tx = [&] { 63 CMutableTransaction tx_mut; 64 const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, outpoints.size()); 65 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, 256); 66 // pick outpoints from outpoints as input. We allow input duplicates on purpose, given we are not 67 // running any transaction validation logic before adding transactions to the orphanage 68 tx_mut.vin.reserve(num_in); 69 for (uint32_t i = 0; i < num_in; i++) { 70 auto& prevout = PickValue(fuzzed_data_provider, outpoints); 71 // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen 72 tx_mut.vin.emplace_back(prevout, CScript{}, fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, CTxIn::SEQUENCE_FINAL)); 73 } 74 // output amount will not affect txorphanage 75 tx_mut.vout.reserve(num_out); 76 for (uint32_t i = 0; i < num_out; i++) { 77 tx_mut.vout.emplace_back(CAmount{0}, CScript{}); 78 } 79 auto new_tx = MakeTransactionRef(tx_mut); 80 // add newly constructed outpoints to the coin pool 81 for (uint32_t i = 0; i < num_out; i++) { 82 outpoints.emplace_back(new_tx->GetHash(), i); 83 } 84 return new_tx; 85 }(); 86 87 tx_history.push_back(tx); 88 89 const auto wtxid{tx->GetWitnessHash()}; 90 91 // Trigger orphanage functions that are called using parents. ptx_potential_parent is a tx we constructed in a 92 // previous loop and potentially the parent of this tx. 93 if (ptx_potential_parent) { 94 // Set up future GetTxToReconsider call. 95 orphanage->AddChildrenToWorkSet(*ptx_potential_parent, orphanage_rng); 96 97 // Check that all txns returned from GetChildrenFrom* are indeed a direct child of this tx. 98 NodeId peer_id = fuzzed_data_provider.ConsumeIntegral<NodeId>(); 99 for (const auto& child : orphanage->GetChildrenFromSamePeer(ptx_potential_parent, peer_id)) { 100 assert(std::any_of(child->vin.cbegin(), child->vin.cend(), [&](const auto& input) { 101 return input.prevout.hash == ptx_potential_parent->GetHash(); 102 })); 103 } 104 } 105 106 // trigger orphanage functions 107 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 1000) 108 { 109 NodeId peer_id = fuzzed_data_provider.ConsumeIntegral<NodeId>(); 110 const auto total_bytes_start{orphanage->TotalOrphanUsage()}; 111 const auto total_peer_bytes_start{orphanage->UsageByPeer(peer_id)}; 112 const auto tx_weight{GetTransactionWeight(*tx)}; 113 114 CallOneOf( 115 fuzzed_data_provider, 116 [&] { 117 { 118 CTransactionRef ref = orphanage->GetTxToReconsider(peer_id); 119 if (ref) { 120 Assert(orphanage->HaveTx(ref->GetWitnessHash())); 121 } 122 } 123 }, 124 [&] { 125 bool have_tx = orphanage->HaveTx(tx->GetWitnessHash()); 126 bool have_tx_and_peer = orphanage->HaveTxFromPeer(wtxid, peer_id); 127 // AddTx should return false if tx is too big or already have it 128 // tx weight is unknown, we only check when tx is already in orphanage 129 { 130 bool add_tx = orphanage->AddTx(tx, peer_id); 131 // have_tx == true -> add_tx == false 132 Assert(!have_tx || !add_tx); 133 // have_tx_and_peer == true -> add_tx == false 134 Assert(!have_tx_and_peer || !add_tx); 135 // After AddTx, the orphanage may trim itself, so the peer's usage may have gone up or down. 136 137 if (add_tx) { 138 Assert(tx_weight <= MAX_STANDARD_TX_WEIGHT); 139 } else { 140 // Peer may have been added as an announcer. 141 if (orphanage->UsageByPeer(peer_id) > total_peer_bytes_start) { 142 Assert(orphanage->HaveTxFromPeer(wtxid, peer_id)); 143 } 144 145 // If announcement was added, total bytes does not increase. 146 // However, if eviction was triggered, the value may decrease. 147 Assert(orphanage->TotalOrphanUsage() <= total_bytes_start); 148 } 149 } 150 // We are not guaranteed to have_tx after AddTx. There are a few possible reasons: 151 // - tx itself exceeds the per-peer memory usage limit, so LimitOrphans had to remove it immediately 152 // - tx itself exceeds the per-peer latency score limit, so LimitOrphans had to remove it immediately 153 // - the orphanage needed trim and all other announcements from this peer are reconsiderable 154 }, 155 [&] { 156 bool have_tx = orphanage->HaveTx(tx->GetWitnessHash()); 157 bool have_tx_and_peer = orphanage->HaveTxFromPeer(tx->GetWitnessHash(), peer_id); 158 // AddAnnouncer should return false if tx doesn't exist or we already HaveTxFromPeer. 159 { 160 bool added_announcer = orphanage->AddAnnouncer(tx->GetWitnessHash(), peer_id); 161 // have_tx == false -> added_announcer == false 162 Assert(have_tx || !added_announcer); 163 // have_tx_and_peer == true -> added_announcer == false 164 Assert(!have_tx_and_peer || !added_announcer); 165 166 // If announcement was added, total bytes does not increase. 167 // However, if eviction was triggered, the value may decrease. 168 Assert(orphanage->TotalOrphanUsage() <= total_bytes_start); 169 } 170 }, 171 [&] { 172 bool have_tx = orphanage->HaveTx(tx->GetWitnessHash()); 173 bool have_tx_and_peer{orphanage->HaveTxFromPeer(wtxid, peer_id)}; 174 // EraseTx should return 0 if m_orphans doesn't have the tx 175 { 176 auto bytes_from_peer_before{orphanage->UsageByPeer(peer_id)}; 177 Assert(have_tx == orphanage->EraseTx(tx->GetWitnessHash())); 178 // After EraseTx, the orphanage may trim itself, so all peers' usage may have gone up or down. 179 if (have_tx) { 180 if (!have_tx_and_peer) { 181 Assert(orphanage->UsageByPeer(peer_id) == bytes_from_peer_before); 182 } 183 } 184 } 185 have_tx = orphanage->HaveTx(tx->GetWitnessHash()); 186 have_tx_and_peer = orphanage->HaveTxFromPeer(wtxid, peer_id); 187 // have_tx should be false and EraseTx should fail 188 { 189 Assert(!have_tx && !have_tx_and_peer && !orphanage->EraseTx(wtxid)); 190 } 191 }, 192 [&] { 193 orphanage->EraseForPeer(peer_id); 194 Assert(!orphanage->HaveTxFromPeer(tx->GetWitnessHash(), peer_id)); 195 Assert(orphanage->UsageByPeer(peer_id) == 0); 196 }, 197 [&] { 198 // Make a block out of txs and then EraseForBlock 199 CBlock block; 200 int num_txs = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 1000); 201 for (int i{0}; i < num_txs; ++i) { 202 auto& tx_to_remove = PickValue(fuzzed_data_provider, tx_history); 203 block.vtx.push_back(tx_to_remove); 204 } 205 orphanage->EraseForBlock(block); 206 for (const auto& tx_removed : block.vtx) { 207 Assert(!orphanage->HaveTx(tx_removed->GetWitnessHash())); 208 Assert(!orphanage->HaveTxFromPeer(tx_removed->GetWitnessHash(), peer_id)); 209 } 210 } 211 ); 212 } 213 214 // Set tx as potential parent to be used for future GetChildren() calls. 215 if (!ptx_potential_parent || fuzzed_data_provider.ConsumeBool()) { 216 ptx_potential_parent = tx; 217 } 218 219 const bool have_tx{orphanage->HaveTx(tx->GetWitnessHash())}; 220 const bool get_tx_nonnull{orphanage->GetTx(tx->GetWitnessHash()) != nullptr}; 221 Assert(have_tx == get_tx_nonnull); 222 } 223 orphanage->SanityCheck(); 224 } 225 226 FUZZ_TARGET(txorphan_protected, .init = initialize_orphanage) 227 { 228 SeedRandomStateForTest(SeedRand::ZEROS); 229 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 230 FastRandomContext orphanage_rng{ConsumeUInt256(fuzzed_data_provider)}; 231 NodeClockContext clock_ctx{ConsumeTime(fuzzed_data_provider)}; 232 233 // We have num_peers peers. Some subset of them will never exceed their reserved weight or announcement count, and 234 // should therefore never have any orphans evicted. 235 const unsigned int MAX_PEERS = 125; 236 const unsigned int num_peers = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, MAX_PEERS); 237 // Generate a vector of bools for whether each peer is protected from eviction 238 std::bitset<MAX_PEERS> protected_peers; 239 for (unsigned int i = 0; i < num_peers; i++) { 240 protected_peers.set(i, fuzzed_data_provider.ConsumeBool()); 241 } 242 243 // Params for orphanage. 244 const unsigned int global_latency_score_limit = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(num_peers, 6'000); 245 const int64_t per_peer_weight_reservation = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(1, 4'040'000); 246 auto orphanage = node::MakeTxOrphanage(global_latency_score_limit, per_peer_weight_reservation); 247 248 // The actual limit, MaxPeerLatencyScore(), may be higher, since TxOrphanage only counts peers 249 // that have announced an orphan. The honest peer will not experience evictions if it never 250 // exceeds this. 251 const unsigned int honest_latency_limit = global_latency_score_limit / num_peers; 252 // Honest peer will not experience evictions if it never exceeds this. 253 const int64_t honest_mem_limit = per_peer_weight_reservation; 254 255 std::vector<COutPoint> outpoints; // Duplicates are tolerated 256 outpoints.reserve(400); 257 258 // initial outpoints used to construct transactions later 259 for (uint8_t i = 0; i < 4; i++) { 260 outpoints.emplace_back(Txid::FromUint256(uint256{i}), 0); 261 } 262 263 // These are honest peer's live announcements. We expect them to be protected from eviction. 264 std::set<Wtxid> protected_wtxids; 265 266 LIMITED_WHILE(outpoints.size() < 400 && fuzzed_data_provider.ConsumeBool(), 1000) 267 { 268 // construct transaction 269 const CTransactionRef tx = [&] { 270 CMutableTransaction tx_mut; 271 const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, outpoints.size()); 272 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, 256); 273 // pick outpoints from outpoints as input. We allow input duplicates on purpose, given we are not 274 // running any transaction validation logic before adding transactions to the orphanage 275 tx_mut.vin.reserve(num_in); 276 for (uint32_t i = 0; i < num_in; i++) { 277 auto& prevout = PickValue(fuzzed_data_provider, outpoints); 278 // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen 279 tx_mut.vin.emplace_back(prevout, CScript{}, fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, CTxIn::SEQUENCE_FINAL)); 280 } 281 // output amount or spendability will not affect txorphanage 282 tx_mut.vout.reserve(num_out); 283 for (uint32_t i = 0; i < num_out; i++) { 284 const auto payload_size = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 100000); 285 if (payload_size) { 286 tx_mut.vout.emplace_back(0, CScript() << OP_RETURN << std::vector<unsigned char>(payload_size)); 287 } else { 288 tx_mut.vout.emplace_back(0, CScript{}); 289 } 290 } 291 auto new_tx = MakeTransactionRef(tx_mut); 292 // add newly constructed outpoints to the coin pool 293 for (uint32_t i = 0; i < num_out; i++) { 294 outpoints.emplace_back(new_tx->GetHash(), i); 295 } 296 return new_tx; 297 }(); 298 299 const auto wtxid{tx->GetWitnessHash()}; 300 301 // orphanage functions 302 LIMITED_WHILE(fuzzed_data_provider.remaining_bytes(), 10 * global_latency_score_limit) 303 { 304 NodeId peer_id = fuzzed_data_provider.ConsumeIntegralInRange<NodeId>(0, num_peers - 1); 305 const auto tx_weight{GetTransactionWeight(*tx)}; 306 307 // This protected peer will never send orphans that would 308 // exceed their own personal allotment, so is never evicted. 309 const bool peer_is_protected{protected_peers[peer_id]}; 310 311 CallOneOf( 312 fuzzed_data_provider, 313 [&] { // AddTx 314 bool have_tx_and_peer = orphanage->HaveTxFromPeer(wtxid, peer_id); 315 if (peer_is_protected && !have_tx_and_peer && 316 (orphanage->UsageByPeer(peer_id) + tx_weight > honest_mem_limit || 317 orphanage->LatencyScoreFromPeer(peer_id) + (tx->vin.size() / 10) + 1 > honest_latency_limit)) { 318 // We never want our protected peer oversized or over-announced 319 } else { 320 orphanage->AddTx(tx, peer_id); 321 if (peer_is_protected && orphanage->HaveTxFromPeer(wtxid, peer_id)) { 322 protected_wtxids.insert(wtxid); 323 } 324 } 325 }, 326 [&] { // AddAnnouncer 327 bool have_tx_and_peer = orphanage->HaveTxFromPeer(tx->GetWitnessHash(), peer_id); 328 // AddAnnouncer should return false if tx doesn't exist or we already HaveTxFromPeer. 329 { 330 if (peer_is_protected && !have_tx_and_peer && 331 (orphanage->UsageByPeer(peer_id) + tx_weight > honest_mem_limit || 332 orphanage->LatencyScoreFromPeer(peer_id) + (tx->vin.size() / 10) + 1 > honest_latency_limit)) { 333 // We never want our protected peer oversized 334 } else { 335 orphanage->AddAnnouncer(tx->GetWitnessHash(), peer_id); 336 if (peer_is_protected && orphanage->HaveTxFromPeer(wtxid, peer_id)) { 337 protected_wtxids.insert(wtxid); 338 } 339 } 340 } 341 }, 342 [&] { // EraseTx 343 if (protected_wtxids.contains(tx->GetWitnessHash())) { 344 protected_wtxids.erase(wtxid); 345 } 346 orphanage->EraseTx(wtxid); 347 Assert(!orphanage->HaveTx(wtxid)); 348 }, 349 [&] { // EraseForPeer 350 if (!protected_peers[peer_id]) { 351 orphanage->EraseForPeer(peer_id); 352 Assert(orphanage->UsageByPeer(peer_id) == 0); 353 Assert(orphanage->LatencyScoreFromPeer(peer_id) == 0); 354 Assert(orphanage->AnnouncementsFromPeer(peer_id) == 0); 355 } 356 } 357 ); 358 } 359 } 360 361 orphanage->SanityCheck(); 362 // All of the honest peer's announcements are still present. 363 for (const auto& wtxid : protected_wtxids) { 364 Assert(orphanage->HaveTx(wtxid)); 365 } 366 } 367 368 FUZZ_TARGET(txorphanage_sim) 369 { 370 SeedRandomStateForTest(SeedRand::ZEROS); 371 // This is a comprehensive simulation fuzz test, which runs through a scenario involving up to 372 // 16 transactions (which may have simple or complex topology, and may have duplicate txids 373 // with distinct wtxids, and up to 16 peers. The scenario is performed both on a real 374 // TxOrphanage object and the behavior is compared with a naive reimplementation (just a vector 375 // of announcements) where possible, and tested for desired properties where not possible. 376 377 // 378 // 1. Setup. 379 // 380 381 /** The total number of transactions this simulation uses (not all of which will necessarily 382 * be present in the orphanage at once). */ 383 static constexpr unsigned NUM_TX = 16; 384 /** The number of peers this simulation uses (not all of which will necessarily be present in 385 * the orphanage at once). */ 386 static constexpr unsigned NUM_PEERS = 16; 387 /** The maximum number of announcements this simulation uses (which may be higher than the 388 * number permitted inside the orphanage). */ 389 static constexpr unsigned MAX_ANN = 64; 390 391 FuzzedDataProvider provider(buffer.data(), buffer.size()); 392 /** Local RNG. Only used for topology/sizes of the transaction set, the order of transactions 393 * in EraseForBlock, and for the randomized passed to AddChildrenToWorkSet. */ 394 InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>()); 395 396 // 397 // 2. Construct an interesting set of 16 transactions. 398 // 399 400 // - Pick a topological order among the transactions. 401 std::vector<unsigned> txorder(NUM_TX); 402 std::iota(txorder.begin(), txorder.end(), unsigned{0}); 403 std::shuffle(txorder.begin(), txorder.end(), rng); 404 // - Pick a set of dependencies (pair<child_index, parent_index>). 405 std::vector<std::pair<unsigned, unsigned>> deps; 406 deps.reserve((NUM_TX * (NUM_TX - 1)) / 2); 407 for (unsigned p = 0; p < NUM_TX - 1; ++p) { 408 for (unsigned c = p + 1; c < NUM_TX; ++c) { 409 deps.emplace_back(c, p); 410 } 411 } 412 std::shuffle(deps.begin(), deps.end(), rng); 413 deps.resize(provider.ConsumeIntegralInRange<unsigned>(0, NUM_TX * 4 - 1)); 414 // - Construct the actual transactions. 415 std::set<Wtxid> wtxids; 416 std::vector<CTransactionRef> txn(NUM_TX); 417 node::TxOrphanage::Usage total_usage{0}; 418 for (unsigned t = 0; t < NUM_TX; ++t) { 419 CMutableTransaction tx; 420 if (t > 0 && rng.randrange(4) == 0) { 421 // Occasionally duplicate the previous transaction, so that repetitions of the same 422 // txid are possible (with different wtxid). 423 tx = CMutableTransaction(*txn[txorder[t - 1]]); 424 } else { 425 tx.version = 1; 426 tx.nLockTime = 0xffffffff; 427 // Construct 1 to 16 outputs. 428 auto num_outputs = rng.randrange<unsigned>(1 << rng.randrange<unsigned>(5)) + 1; 429 for (unsigned output = 0; output < num_outputs; ++output) { 430 CScript scriptpubkey; 431 scriptpubkey.resize(provider.ConsumeIntegralInRange<unsigned>(20, 34)); 432 tx.vout.emplace_back(CAmount{0}, std::move(scriptpubkey)); 433 } 434 // Construct inputs (one for each dependency). 435 for (auto& [child, parent] : deps) { 436 if (child == t) { 437 auto& partx = txn[txorder[parent]]; 438 assert(partx->version == 1); 439 COutPoint outpoint(partx->GetHash(), rng.randrange<size_t>(partx->vout.size())); 440 tx.vin.emplace_back(outpoint); 441 tx.vin.back().scriptSig.resize(provider.ConsumeIntegralInRange<unsigned>(16, 200)); 442 } 443 } 444 // Construct fallback input in case there are no dependencies. 445 if (tx.vin.empty()) { 446 COutPoint outpoint(Txid::FromUint256(rng.rand256()), rng.randrange<size_t>(16)); 447 tx.vin.emplace_back(outpoint); 448 tx.vin.back().scriptSig.resize(provider.ConsumeIntegralInRange<unsigned>(16, 200)); 449 } 450 } 451 // Optionally modify the witness (allowing wtxid != txid), and certainly when the wtxid 452 // already exists. 453 while (wtxids.contains(CTransaction(tx).GetWitnessHash()) || rng.randrange(4) == 0) { 454 auto& input = tx.vin[rng.randrange(tx.vin.size())]; 455 if (rng.randbool()) { 456 input.scriptWitness.stack.resize(1); 457 input.scriptWitness.stack[0].resize(rng.randrange(100)); 458 } else { 459 input.scriptWitness.stack.resize(0); 460 } 461 } 462 // Convert to CTransactionRef. 463 txn[txorder[t]] = MakeTransactionRef(std::move(tx)); 464 wtxids.insert(txn[txorder[t]]->GetWitnessHash()); 465 auto weight = GetTransactionWeight(*txn[txorder[t]]); 466 assert(weight < MAX_STANDARD_TX_WEIGHT); 467 total_usage += GetTransactionWeight(*txn[txorder[t]]); 468 } 469 470 // 471 // 3. Initialize real orphanage 472 // 473 474 auto max_global_latency_score = provider.ConsumeIntegralInRange<node::TxOrphanage::Count>(NUM_PEERS, MAX_ANN); 475 auto reserved_peer_usage = provider.ConsumeIntegralInRange<node::TxOrphanage::Usage>(1, total_usage); 476 auto real = node::MakeTxOrphanage(max_global_latency_score, reserved_peer_usage); 477 478 // 479 // 4. Functions and data structures for the simulation. 480 // 481 482 /** Data structure representing one announcement (pair of (tx, peer), plus whether it's 483 * reconsiderable or not. */ 484 struct SimAnnouncement 485 { 486 unsigned tx; 487 NodeId announcer; 488 bool reconsider{false}; 489 SimAnnouncement(unsigned tx_in, NodeId announcer_in, bool reconsider_in) noexcept : 490 tx(tx_in), announcer(announcer_in), reconsider(reconsider_in) {} 491 }; 492 /** The entire simulated orphanage is represented by this list of announcements, in 493 * announcement order (unlike TxOrphanageImpl which uses a sequence number to represent 494 * announcement order). New announcements are added to the back. */ 495 std::vector<SimAnnouncement> sim_announcements; 496 497 /** Consume a transaction (index into txn) from provider. */ 498 auto read_tx_fn = [&]() -> unsigned { return provider.ConsumeIntegralInRange<unsigned>(0, NUM_TX - 1); }; 499 /** Consume a NodeId from provider. */ 500 auto read_peer_fn = [&]() -> NodeId { return provider.ConsumeIntegralInRange<unsigned>(0, NUM_PEERS - 1); }; 501 /** Consume both a transaction (index into txn) and a NodeId from provider. */ 502 auto read_tx_peer_fn = [&]() -> std::pair<unsigned, NodeId> { 503 auto code = provider.ConsumeIntegralInRange<unsigned>(0, NUM_TX * NUM_PEERS - 1); 504 return {code % NUM_TX, code / NUM_TX}; 505 }; 506 /** Determine if we have any announcements of the given transaction in the simulation. */ 507 auto have_tx_fn = [&](unsigned tx) -> bool { 508 for (auto& ann : sim_announcements) { 509 if (ann.tx == tx) return true; 510 } 511 return false; 512 }; 513 /** Count the number of peers in the simulation. */ 514 auto count_peers_fn = [&]() -> unsigned { 515 std::bitset<NUM_PEERS> mask; 516 for (auto& ann : sim_announcements) { 517 mask.set(ann.announcer); 518 } 519 return mask.count(); 520 }; 521 /** Determine if we have any reconsiderable announcements of a given transaction. */ 522 auto have_reconsiderable_fn = [&](unsigned tx) -> bool { 523 for (auto& ann : sim_announcements) { 524 if (ann.reconsider && ann.tx == tx) return true; 525 } 526 return false; 527 }; 528 /** Determine if a peer has any transactions to reconsider. */ 529 auto have_reconsider_fn = [&](NodeId peer) -> bool { 530 for (auto& ann : sim_announcements) { 531 if (ann.reconsider && ann.announcer == peer) return true; 532 } 533 return false; 534 }; 535 /** Get an iterator to an existing (wtxid, peer) pair in the simulation. */ 536 auto find_announce_wtxid_fn = [&](const Wtxid& wtxid, NodeId peer) -> std::vector<SimAnnouncement>::iterator { 537 for (auto it = sim_announcements.begin(); it != sim_announcements.end(); ++it) { 538 if (txn[it->tx]->GetWitnessHash() == wtxid && it->announcer == peer) return it; 539 } 540 return sim_announcements.end(); 541 }; 542 /** Get an iterator to an existing (tx, peer) pair in the simulation. */ 543 auto find_announce_fn = [&](unsigned tx, NodeId peer) { 544 for (auto it = sim_announcements.begin(); it != sim_announcements.end(); ++it) { 545 if (it->tx == tx && it->announcer == peer) return it; 546 } 547 return sim_announcements.end(); 548 }; 549 /** Compute a peer's DoS score according to simulation data. */ 550 auto dos_score_fn = [&](NodeId peer, int32_t max_count, int32_t max_usage) -> FeeFrac { 551 int64_t count{0}; 552 int64_t usage{0}; 553 for (auto& ann : sim_announcements) { 554 if (ann.announcer != peer) continue; 555 count += 1 + (txn[ann.tx]->vin.size() / 10); 556 usage += GetTransactionWeight(*txn[ann.tx]); 557 } 558 return std::max<ByRatioNegSize<FeeFrac>>(FeeFrac{count, max_count}, FeeFrac{usage, max_usage}); 559 }; 560 561 // 562 // 5. Run through a scenario of mutators on both real and simulated orphanage. 563 // 564 565 LIMITED_WHILE(provider.remaining_bytes() > 0, 200) { 566 int command = provider.ConsumeIntegralInRange<uint8_t>(0, 15); 567 while (true) { 568 if (sim_announcements.size() < MAX_ANN && command-- == 0) { 569 // AddTx 570 auto [tx, peer] = read_tx_peer_fn(); 571 bool added = real->AddTx(txn[tx], peer); 572 bool sim_have_tx = have_tx_fn(tx); 573 assert(added == !sim_have_tx); 574 if (find_announce_fn(tx, peer) == sim_announcements.end()) { 575 sim_announcements.emplace_back(tx, peer, false); 576 } 577 break; 578 } else if (sim_announcements.size() < MAX_ANN && command-- == 0) { 579 // AddAnnouncer 580 auto [tx, peer] = read_tx_peer_fn(); 581 bool added = real->AddAnnouncer(txn[tx]->GetWitnessHash(), peer); 582 bool sim_have_tx = have_tx_fn(tx); 583 auto sim_it = find_announce_fn(tx, peer); 584 assert(added == (sim_it == sim_announcements.end() && sim_have_tx)); 585 if (added) { 586 sim_announcements.emplace_back(tx, peer, false); 587 } 588 break; 589 } else if (command-- == 0) { 590 // EraseTx 591 auto tx = read_tx_fn(); 592 bool erased = real->EraseTx(txn[tx]->GetWitnessHash()); 593 bool sim_have = have_tx_fn(tx); 594 assert(erased == sim_have); 595 std::erase_if(sim_announcements, [&](auto& ann) { return ann.tx == tx; }); 596 break; 597 } else if (command-- == 0) { 598 // EraseForPeer 599 auto peer = read_peer_fn(); 600 real->EraseForPeer(peer); 601 std::erase_if(sim_announcements, [&](auto& ann) { return ann.announcer == peer; }); 602 break; 603 } else if (command-- == 0) { 604 // EraseForBlock 605 auto pattern = provider.ConsumeIntegralInRange<uint64_t>(0, (uint64_t{1} << NUM_TX) - 1); 606 CBlock block; 607 std::set<COutPoint> spent; 608 for (unsigned tx = 0; tx < NUM_TX; ++tx) { 609 if ((pattern >> tx) & 1) { 610 block.vtx.emplace_back(txn[tx]); 611 for (auto& txin : block.vtx.back()->vin) { 612 spent.insert(txin.prevout); 613 } 614 } 615 } 616 std::shuffle(block.vtx.begin(), block.vtx.end(), rng); 617 real->EraseForBlock(block); 618 std::erase_if(sim_announcements, [&](auto& ann) { 619 for (auto& txin : txn[ann.tx]->vin) { 620 if (spent.contains(txin.prevout)) return true; 621 } 622 return false; 623 }); 624 break; 625 } else if (command-- == 0) { 626 // AddChildrenToWorkSet 627 auto tx = read_tx_fn(); 628 FastRandomContext rand_ctx(rng.rand256()); 629 auto added = real->AddChildrenToWorkSet(*txn[tx], rand_ctx); 630 /** Set of not-already-reconsiderable child wtxids. */ 631 std::set<Wtxid> child_wtxids; 632 for (unsigned child_tx = 0; child_tx < NUM_TX; ++child_tx) { 633 if (!have_tx_fn(child_tx)) continue; 634 if (have_reconsiderable_fn(child_tx)) continue; 635 bool child_of = false; 636 for (auto& txin : txn[child_tx]->vin) { 637 if (txin.prevout.hash == txn[tx]->GetHash()) { 638 child_of = true; 639 break; 640 } 641 } 642 if (child_of) { 643 child_wtxids.insert(txn[child_tx]->GetWitnessHash()); 644 } 645 } 646 for (auto& [wtxid, peer] : added) { 647 // Wtxid must be a child of tx that is not yet reconsiderable. 648 auto child_wtxid_it = child_wtxids.find(wtxid); 649 assert(child_wtxid_it != child_wtxids.end()); 650 // Announcement must exist. 651 auto sim_ann_it = find_announce_wtxid_fn(wtxid, peer); 652 assert(sim_ann_it != sim_announcements.end()); 653 // Announcement must not yet be reconsiderable. 654 assert(sim_ann_it->reconsider == false); 655 // Make reconsiderable. 656 sim_ann_it->reconsider = true; 657 // Remove from child_wtxids map, to disallow it being reported a second time in added. 658 child_wtxids.erase(wtxid); 659 } 660 // Verify that AddChildrenToWorkSet does not select announcements that were already reconsiderable: 661 // Check all child wtxids which did not occur at least once in the result were already reconsiderable 662 // due to a previous AddChildrenToWorkSet. 663 assert(child_wtxids.empty()); 664 break; 665 } else if (command-- == 0) { 666 // GetTxToReconsider. 667 auto peer = read_peer_fn(); 668 auto result = real->GetTxToReconsider(peer); 669 if (result) { 670 // A transaction was found. It must have a corresponding reconsiderable 671 // announcement from peer. 672 auto sim_ann_it = find_announce_wtxid_fn(result->GetWitnessHash(), peer); 673 assert(sim_ann_it != sim_announcements.end()); 674 assert(sim_ann_it->announcer == peer); 675 assert(sim_ann_it->reconsider); 676 // Make it non-reconsiderable. 677 sim_ann_it->reconsider = false; 678 } else { 679 // No reconsiderable transaction was found from peer. Verify that it does not 680 // have any. 681 assert(!have_reconsider_fn(peer)); 682 } 683 break; 684 } 685 } 686 // Always trim after each command if needed. 687 const auto max_ann = max_global_latency_score / std::max<unsigned>(1, count_peers_fn()); 688 const auto max_mem = reserved_peer_usage; 689 while (true) { 690 // Count global usage and number of peers. 691 node::TxOrphanage::Usage total_usage{0}; 692 node::TxOrphanage::Count total_latency_score = sim_announcements.size(); 693 for (unsigned tx = 0; tx < NUM_TX; ++tx) { 694 if (have_tx_fn(tx)) { 695 total_usage += GetTransactionWeight(*txn[tx]); 696 total_latency_score += txn[tx]->vin.size() / 10; 697 } 698 } 699 auto num_peers = count_peers_fn(); 700 bool oversized = (total_usage > reserved_peer_usage * num_peers) || 701 (total_latency_score > real->MaxGlobalLatencyScore()); 702 if (!oversized) break; 703 // Find worst peer. 704 FeeFrac worst_dos_score{0, 1}; 705 unsigned worst_peer = unsigned(-1); 706 for (unsigned peer = 0; peer < NUM_PEERS; ++peer) { 707 auto dos_score = dos_score_fn(peer, max_ann, max_mem); 708 // Use >= so that the more recent peer (higher NodeId) wins in case of 709 // ties. 710 if (ByRatioNegSize{dos_score} >= ByRatioNegSize{worst_dos_score}) { 711 worst_dos_score = dos_score; 712 worst_peer = peer; 713 } 714 } 715 assert(worst_peer != unsigned(-1)); 716 assert(ByRatio{worst_dos_score} > ByRatio{FeeFrac(1, 1)}); 717 // Find oldest announcement from worst_peer, preferring non-reconsiderable ones. 718 bool done{false}; 719 for (int reconsider = 0; reconsider < 2; ++reconsider) { 720 for (auto it = sim_announcements.begin(); it != sim_announcements.end(); ++it) { 721 if (it->announcer != worst_peer || it->reconsider != reconsider) continue; 722 sim_announcements.erase(it); 723 done = true; 724 break; 725 } 726 if (done) break; 727 } 728 assert(done); 729 } 730 // We must now be within limits, otherwise LimitOrphans should have continued further. 731 // We don't check the contents of the orphanage until the end to make fuzz runs faster. 732 assert(real->TotalLatencyScore() <= real->MaxGlobalLatencyScore()); 733 assert(real->TotalOrphanUsage() <= real->MaxGlobalUsage()); 734 } 735 736 // 737 // 6. Perform a full comparison between the real orphanage's inspectors and the simulation. 738 // 739 740 real->SanityCheck(); 741 742 743 auto all_orphans = real->GetOrphanTransactions(); 744 node::TxOrphanage::Usage orphan_usage{0}; 745 std::vector<node::TxOrphanage::Usage> usage_by_peer(NUM_PEERS); 746 node::TxOrphanage::Count unique_orphans{0}; 747 std::vector<node::TxOrphanage::Count> count_by_peer(NUM_PEERS); 748 node::TxOrphanage::Count total_latency_score = sim_announcements.size(); 749 for (unsigned tx = 0; tx < NUM_TX; ++tx) { 750 bool sim_have_tx = have_tx_fn(tx); 751 if (sim_have_tx) { 752 orphan_usage += GetTransactionWeight(*txn[tx]); 753 total_latency_score += txn[tx]->vin.size() / 10; 754 } 755 unique_orphans += sim_have_tx; 756 auto orphans_it = std::find_if(all_orphans.begin(), all_orphans.end(), [&](auto& orph) { return orph.tx->GetWitnessHash() == txn[tx]->GetWitnessHash(); }); 757 // GetOrphanTransactions (OrphanBase existence) 758 assert((orphans_it != all_orphans.end()) == sim_have_tx); 759 // HaveTx 760 bool have_tx = real->HaveTx(txn[tx]->GetWitnessHash()); 761 assert(have_tx == sim_have_tx); 762 // GetTx 763 auto txref = real->GetTx(txn[tx]->GetWitnessHash()); 764 assert(!!txref == sim_have_tx); 765 if (sim_have_tx) assert(txref->GetWitnessHash() == txn[tx]->GetWitnessHash()); 766 767 for (NodeId peer = 0; peer < NUM_PEERS; ++peer) { 768 auto it_sim_ann = find_announce_fn(tx, peer); 769 bool sim_have_ann = it_sim_ann != sim_announcements.end(); 770 if (sim_have_ann) usage_by_peer[peer] += GetTransactionWeight(*txn[tx]); 771 count_by_peer[peer] += sim_have_ann; 772 // GetOrphanTransactions (announcers presence) 773 if (sim_have_ann) assert(sim_have_tx); 774 if (sim_have_tx) assert(orphans_it->announcers.count(peer) == sim_have_ann); 775 // HaveTxFromPeer 776 bool have_ann = real->HaveTxFromPeer(txn[tx]->GetWitnessHash(), peer); 777 assert(sim_have_ann == have_ann); 778 // GetChildrenFromSamePeer 779 auto children_from_peer = real->GetChildrenFromSamePeer(txn[tx], peer); 780 auto it = children_from_peer.rbegin(); 781 for (int phase = 0; phase < 2; ++phase) { 782 // First expect all children which have reconsiderable announcement from peer, then the others. 783 for (auto& ann : sim_announcements) { 784 if (ann.announcer != peer) continue; 785 if (ann.reconsider != (phase == 1)) continue; 786 bool matching_parent{false}; 787 for (const auto& vin : txn[ann.tx]->vin) { 788 if (vin.prevout.hash == txn[tx]->GetHash()) matching_parent = true; 789 } 790 if (!matching_parent) continue; 791 // Found an announcement from peer which is a child of txn[tx]. 792 assert(it != children_from_peer.rend()); 793 assert((*it)->GetWitnessHash() == txn[ann.tx]->GetWitnessHash()); 794 ++it; 795 } 796 } 797 assert(it == children_from_peer.rend()); 798 } 799 } 800 // TotalOrphanUsage 801 assert(orphan_usage == real->TotalOrphanUsage()); 802 for (NodeId peer = 0; peer < NUM_PEERS; ++peer) { 803 bool sim_have_reconsider = have_reconsider_fn(peer); 804 // HaveTxToReconsider 805 bool have_reconsider = real->HaveTxToReconsider(peer); 806 assert(have_reconsider == sim_have_reconsider); 807 // UsageByPeer 808 assert(usage_by_peer[peer] == real->UsageByPeer(peer)); 809 // AnnouncementsFromPeer 810 assert(count_by_peer[peer] == real->AnnouncementsFromPeer(peer)); 811 } 812 // CountAnnouncements 813 assert(sim_announcements.size() == real->CountAnnouncements()); 814 // CountUniqueOrphans 815 assert(unique_orphans == real->CountUniqueOrphans()); 816 // MaxGlobalLatencyScore 817 assert(max_global_latency_score == real->MaxGlobalLatencyScore()); 818 // ReservedPeerUsage 819 assert(reserved_peer_usage == real->ReservedPeerUsage()); 820 // MaxPeerLatencyScore 821 auto present_peers = count_peers_fn(); 822 assert(max_global_latency_score / std::max<unsigned>(1, present_peers) == real->MaxPeerLatencyScore()); 823 // MaxGlobalUsage 824 assert(reserved_peer_usage * std::max<unsigned>(1, present_peers) == real->MaxGlobalUsage()); 825 // TotalLatencyScore. 826 assert(real->TotalLatencyScore() == total_latency_score); 827 }