txorphan.cpp raw
1 // Copyright (c) 2022-present The Limenka 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 }
237