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