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 <policy/policy.h> 10 #include <primitives/transaction.h> 11 #include <script/script.h> 12 #include <sync.h> 13 #include <test/fuzz/FuzzedDataProvider.h> 14 #include <test/fuzz/fuzz.h> 15 #include <test/fuzz/util.h> 16 #include <test/util/setup_common.h> 17 #include <txorphanage.h> 18 #include <uint256.h> 19 #include <util/check.h> 20 #include <util/time.h> 21 22 #include <cstdint> 23 #include <memory> 24 #include <set> 25 #include <utility> 26 #include <vector> 27 28 void initialize_orphanage() 29 { 30 static const auto testing_setup = MakeNoLogFileContext(); 31 } 32 33 FUZZ_TARGET(txorphan, .init = initialize_orphanage) 34 { 35 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 36 FastRandomContext orphanage_rng{/*fDeterministic=*/true}; 37 SetMockTime(ConsumeTime(fuzzed_data_provider)); 38 39 TxOrphanage orphanage; 40 std::vector<COutPoint> outpoints; // Duplicates are tolerated 41 outpoints.reserve(200'000); 42 43 // initial outpoints used to construct transactions later 44 for (uint8_t i = 0; i < 4; i++) { 45 outpoints.emplace_back(Txid::FromUint256(uint256{i}), 0); 46 } 47 48 CTransactionRef ptx_potential_parent = nullptr; 49 50 std::vector<CTransactionRef> tx_history; 51 52 LIMITED_WHILE(outpoints.size() < 200'000 && fuzzed_data_provider.ConsumeBool(), 10 * DEFAULT_MAX_ORPHAN_TRANSACTIONS) 53 { 54 // construct transaction 55 const CTransactionRef tx = [&] { 56 CMutableTransaction tx_mut; 57 const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, outpoints.size()); 58 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, 256); 59 // pick outpoints from outpoints as input. We allow input duplicates on purpose, given we are not 60 // running any transaction validation logic before adding transactions to the orphanage 61 tx_mut.vin.reserve(num_in); 62 for (uint32_t i = 0; i < num_in; i++) { 63 auto& prevout = PickValue(fuzzed_data_provider, outpoints); 64 // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen 65 tx_mut.vin.emplace_back(prevout, CScript{}, fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, CTxIn::SEQUENCE_FINAL)); 66 } 67 // output amount will not affect txorphanage 68 tx_mut.vout.reserve(num_out); 69 for (uint32_t i = 0; i < num_out; i++) { 70 tx_mut.vout.emplace_back(CAmount{0}, CScript{}); 71 } 72 auto new_tx = MakeTransactionRef(tx_mut); 73 // add newly constructed outpoints to the coin pool 74 for (uint32_t i = 0; i < num_out; i++) { 75 outpoints.emplace_back(new_tx->GetHash(), i); 76 } 77 return new_tx; 78 }(); 79 80 tx_history.push_back(tx); 81 82 const auto wtxid{tx->GetWitnessHash()}; 83 84 // Trigger orphanage functions that are called using parents. ptx_potential_parent is a tx we constructed in a 85 // previous loop and potentially the parent of this tx. 86 if (ptx_potential_parent) { 87 // Set up future GetTxToReconsider call. 88 orphanage.AddChildrenToWorkSet(*ptx_potential_parent, orphanage_rng); 89 90 // Check that all txns returned from GetChildrenFrom* are indeed a direct child of this tx. 91 NodeId peer_id = fuzzed_data_provider.ConsumeIntegral<NodeId>(); 92 for (const auto& child : orphanage.GetChildrenFromSamePeer(ptx_potential_parent, peer_id)) { 93 assert(std::any_of(child->vin.cbegin(), child->vin.cend(), [&](const auto& input) { 94 return input.prevout.hash == ptx_potential_parent->GetHash(); 95 })); 96 } 97 } 98 99 // trigger orphanage functions 100 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10 * DEFAULT_MAX_ORPHAN_TRANSACTIONS) 101 { 102 NodeId peer_id = fuzzed_data_provider.ConsumeIntegral<NodeId>(); 103 const auto total_bytes_start{orphanage.TotalOrphanUsage()}; 104 const auto total_peer_bytes_start{orphanage.UsageByPeer(peer_id)}; 105 const auto tx_weight{GetTransactionWeight(*tx)}; 106 107 CallOneOf( 108 fuzzed_data_provider, 109 [&] { 110 { 111 CTransactionRef ref = orphanage.GetTxToReconsider(peer_id); 112 if (ref) { 113 Assert(orphanage.HaveTx(ref->GetWitnessHash())); 114 } 115 } 116 }, 117 [&] { 118 bool have_tx = orphanage.HaveTx(tx->GetWitnessHash()); 119 // AddTx should return false if tx is too big or already have it 120 // tx weight is unknown, we only check when tx is already in orphanage 121 { 122 bool add_tx = orphanage.AddTx(tx, peer_id); 123 // have_tx == true -> add_tx == false 124 Assert(!have_tx || !add_tx); 125 126 if (add_tx) { 127 Assert(orphanage.UsageByPeer(peer_id) == tx_weight + total_peer_bytes_start); 128 Assert(orphanage.TotalOrphanUsage() == tx_weight + total_bytes_start); 129 Assert(tx_weight <= MAX_STANDARD_TX_WEIGHT); 130 } else { 131 // Peer may have been added as an announcer. 132 if (orphanage.UsageByPeer(peer_id) == tx_weight + total_peer_bytes_start) { 133 Assert(orphanage.HaveTxFromPeer(wtxid, peer_id)); 134 } else { 135 // Otherwise, there must not be any change to the peer byte count. 136 Assert(orphanage.UsageByPeer(peer_id) == total_peer_bytes_start); 137 } 138 139 // Regardless, total bytes should not have changed. 140 Assert(orphanage.TotalOrphanUsage() == total_bytes_start); 141 } 142 } 143 have_tx = orphanage.HaveTx(tx->GetWitnessHash()); 144 { 145 bool add_tx = orphanage.AddTx(tx, peer_id); 146 // if have_tx is still false, it must be too big 147 Assert(!have_tx == (tx_weight > MAX_STANDARD_TX_WEIGHT)); 148 Assert(!have_tx || !add_tx); 149 } 150 }, 151 [&] { 152 bool have_tx = orphanage.HaveTx(tx->GetWitnessHash()); 153 bool have_tx_and_peer = orphanage.HaveTxFromPeer(tx->GetWitnessHash(), peer_id); 154 // AddAnnouncer should return false if tx doesn't exist or we already HaveTxFromPeer. 155 { 156 bool added_announcer = orphanage.AddAnnouncer(tx->GetWitnessHash(), peer_id); 157 // have_tx == false -> added_announcer == false 158 Assert(have_tx || !added_announcer); 159 // have_tx_and_peer == true -> added_announcer == false 160 Assert(!have_tx_and_peer || !added_announcer); 161 162 // Total bytes should not have changed. If peer was added as announcer, byte 163 // accounting must have been updated. 164 Assert(orphanage.TotalOrphanUsage() == total_bytes_start); 165 if (added_announcer) { 166 Assert(orphanage.UsageByPeer(peer_id) == tx_weight + total_peer_bytes_start); 167 } else { 168 Assert(orphanage.UsageByPeer(peer_id) == total_peer_bytes_start); 169 } 170 } 171 }, 172 [&] { 173 bool have_tx = orphanage.HaveTx(tx->GetWitnessHash()); 174 bool have_tx_and_peer{orphanage.HaveTxFromPeer(wtxid, peer_id)}; 175 // EraseTx should return 0 if m_orphans doesn't have the tx 176 { 177 auto bytes_from_peer_before{orphanage.UsageByPeer(peer_id)}; 178 Assert(have_tx == orphanage.EraseTx(tx->GetWitnessHash())); 179 if (have_tx) { 180 Assert(orphanage.TotalOrphanUsage() == total_bytes_start - tx_weight); 181 if (have_tx_and_peer) { 182 Assert(orphanage.UsageByPeer(peer_id) == bytes_from_peer_before - tx_weight); 183 } else { 184 Assert(orphanage.UsageByPeer(peer_id) == bytes_from_peer_before); 185 } 186 } else { 187 Assert(orphanage.TotalOrphanUsage() == total_bytes_start); 188 } 189 } 190 have_tx = orphanage.HaveTx(tx->GetWitnessHash()); 191 have_tx_and_peer = orphanage.HaveTxFromPeer(wtxid, peer_id); 192 // have_tx should be false and EraseTx should fail 193 { 194 Assert(!have_tx && !have_tx_and_peer && !orphanage.EraseTx(wtxid)); 195 } 196 }, 197 [&] { 198 orphanage.EraseForPeer(peer_id); 199 Assert(!orphanage.HaveTxFromPeer(tx->GetWitnessHash(), peer_id)); 200 Assert(orphanage.UsageByPeer(peer_id) == 0); 201 }, 202 [&] { 203 // Make a block out of txs and then EraseForBlock 204 CBlock block; 205 int num_txs = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 1000); 206 for (int i{0}; i < num_txs; ++i) { 207 auto& tx_to_remove = PickValue(fuzzed_data_provider, tx_history); 208 block.vtx.push_back(tx_to_remove); 209 } 210 orphanage.EraseForBlock(block); 211 for (const auto& tx_removed : block.vtx) { 212 Assert(!orphanage.HaveTx(tx_removed->GetWitnessHash())); 213 Assert(!orphanage.HaveTxFromPeer(tx_removed->GetWitnessHash(), peer_id)); 214 } 215 }, 216 [&] { 217 // test mocktime and expiry 218 SetMockTime(ConsumeTime(fuzzed_data_provider)); 219 auto limit = fuzzed_data_provider.ConsumeIntegral<unsigned int>(); 220 orphanage.LimitOrphans(limit, orphanage_rng); 221 Assert(orphanage.Size() <= limit); 222 }); 223 224 } 225 226 // Set tx as potential parent to be used for future GetChildren() calls. 227 if (!ptx_potential_parent || fuzzed_data_provider.ConsumeBool()) { 228 ptx_potential_parent = tx; 229 } 230 231 const bool have_tx{orphanage.HaveTx(tx->GetWitnessHash())}; 232 const bool get_tx_nonnull{orphanage.GetTx(tx->GetWitnessHash()) != nullptr}; 233 Assert(have_tx == get_tx_nonnull); 234 } 235 orphanage.SanityCheck(); 236 }