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