txdownloadman.cpp raw
1 // Copyright (c) 2023 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/validation.h>
6 #include <node/context.h>
7 #include <node/mempool_args.h>
8 #include <node/miner.h>
9 #include <node/txdownloadman.h>
10 #include <node/txdownloadman_impl.h>
11 #include <test/fuzz/FuzzedDataProvider.h>
12 #include <test/fuzz/fuzz.h>
13 #include <test/fuzz/util.h>
14 #include <test/fuzz/util/mempool.h>
15 #include <test/util/mining.h>
16 #include <test/util/script.h>
17 #include <test/util/setup_common.h>
18 #include <test/util/txmempool.h>
19 #include <util/hasher.h>
20 #include <util/rbf.h>
21 #include <util/time.h>
22 #include <txmempool.h>
23 #include <validation.h>
24 #include <validationinterface.h>
25
26 namespace {
27
28 const TestingSetup* g_setup;
29
30 constexpr size_t NUM_COINS{50};
31 COutPoint COINS[NUM_COINS];
32
33 static TxValidationResult TESTED_TX_RESULTS[] = {
34 // Skip TX_RESULT_UNSET
35 TxValidationResult::TX_CONSENSUS,
36 TxValidationResult::TX_INPUTS_NOT_STANDARD,
37 TxValidationResult::TX_NOT_STANDARD,
38 TxValidationResult::TX_MISSING_INPUTS,
39 TxValidationResult::TX_PREMATURE_SPEND,
40 TxValidationResult::TX_WITNESS_MUTATED,
41 TxValidationResult::TX_WITNESS_STRIPPED,
42 TxValidationResult::TX_CONFLICT,
43 TxValidationResult::TX_MEMPOOL_POLICY,
44 // Skip TX_NO_MEMPOOL
45 TxValidationResult::TX_RECONSIDERABLE,
46 TxValidationResult::TX_UNKNOWN,
47 };
48
49 // Precomputed transactions. Some may conflict with each other.
50 std::vector<CTransactionRef> TRANSACTIONS;
51
52 // Limit the total number of peers because we don't expect coverage to change much with lots more peers.
53 constexpr int NUM_PEERS = 16;
54
55 // Precomputed random durations (positive and negative, each ~exponentially distributed).
56 std::chrono::microseconds TIME_SKIPS[128];
57
58 static CTransactionRef MakeTransactionSpending(const std::vector<COutPoint>& outpoints, size_t num_outputs, bool add_witness)
59 {
60 CMutableTransaction tx;
61 // If no outpoints are given, create a random one.
62 for (const auto& outpoint : outpoints) {
63 tx.vin.emplace_back(outpoint);
64 }
65 if (add_witness) {
66 tx.vin[0].scriptWitness.stack.push_back({1});
67 }
68 for (size_t o = 0; o < num_outputs; ++o) tx.vout.emplace_back(CENT, P2WSH_OP_TRUE);
69 return MakeTransactionRef(tx);
70 }
71 static std::vector<COutPoint> PickCoins(FuzzedDataProvider& fuzzed_data_provider)
72 {
73 std::vector<COutPoint> ret;
74 ret.push_back(fuzzed_data_provider.PickValueInArray(COINS));
75 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10) {
76 ret.push_back(fuzzed_data_provider.PickValueInArray(COINS));
77 }
78 return ret;
79 }
80
81 void initialize()
82 {
83 static const auto testing_setup = MakeNoLogFileContext<const TestingSetup>();
84 g_setup = testing_setup.get();
85 for (uint32_t i = 0; i < uint32_t{NUM_COINS}; ++i) {
86 COINS[i] = COutPoint{Txid::FromUint256((HashWriter() << i).GetHash()), i};
87 }
88 size_t outpoints_index = 0;
89 // 2 transactions same txid different witness
90 {
91 auto tx1{MakeTransactionSpending({COINS[outpoints_index]}, /*num_outputs=*/5, /*add_witness=*/false)};
92 auto tx2{MakeTransactionSpending({COINS[outpoints_index]}, /*num_outputs=*/5, /*add_witness=*/true)};
93 Assert(tx1->GetHash() == tx2->GetHash());
94 TRANSACTIONS.emplace_back(tx1);
95 TRANSACTIONS.emplace_back(tx2);
96 outpoints_index += 1;
97 }
98 // 2 parents 1 child
99 {
100 auto tx_parent_1{MakeTransactionSpending({COINS[outpoints_index++]}, /*num_outputs=*/1, /*add_witness=*/true)};
101 TRANSACTIONS.emplace_back(tx_parent_1);
102 auto tx_parent_2{MakeTransactionSpending({COINS[outpoints_index++]}, /*num_outputs=*/1, /*add_witness=*/false)};
103 TRANSACTIONS.emplace_back(tx_parent_2);
104 TRANSACTIONS.emplace_back(MakeTransactionSpending({COutPoint{tx_parent_1->GetHash(), 0}, COutPoint{tx_parent_2->GetHash(), 0}},
105 /*num_outputs=*/1, /*add_witness=*/true));
106 }
107 // 1 parent 2 children
108 {
109 auto tx_parent{MakeTransactionSpending({COINS[outpoints_index++]}, /*num_outputs=*/2, /*add_witness=*/true)};
110 TRANSACTIONS.emplace_back(tx_parent);
111 TRANSACTIONS.emplace_back(MakeTransactionSpending({COutPoint{tx_parent->GetHash(), 0}},
112 /*num_outputs=*/1, /*add_witness=*/true));
113 TRANSACTIONS.emplace_back(MakeTransactionSpending({COutPoint{tx_parent->GetHash(), 1}},
114 /*num_outputs=*/1, /*add_witness=*/true));
115 }
116 // chain of 5 segwit
117 {
118 COutPoint& last_outpoint = COINS[outpoints_index++];
119 for (auto i{0}; i < 5; ++i) {
120 auto tx{MakeTransactionSpending({last_outpoint}, /*num_outputs=*/1, /*add_witness=*/true)};
121 TRANSACTIONS.emplace_back(tx);
122 last_outpoint = COutPoint{tx->GetHash(), 0};
123 }
124 }
125 // chain of 5 non-segwit
126 {
127 COutPoint& last_outpoint = COINS[outpoints_index++];
128 for (auto i{0}; i < 5; ++i) {
129 auto tx{MakeTransactionSpending({last_outpoint}, /*num_outputs=*/1, /*add_witness=*/false)};
130 TRANSACTIONS.emplace_back(tx);
131 last_outpoint = COutPoint{tx->GetHash(), 0};
132 }
133 }
134 // Also create a loose tx for each outpoint. Some of these transactions conflict with the above
135 // or have the same txid.
136 for (const auto& outpoint : COINS) {
137 TRANSACTIONS.emplace_back(MakeTransactionSpending({outpoint}, /*num_outputs=*/1, /*add_witness=*/true));
138 }
139
140 // Create random-looking time jumps
141 int i = 0;
142 // TIME_SKIPS[N] for N=0..15 is just N microseconds.
143 for (; i < 16; ++i) {
144 TIME_SKIPS[i] = std::chrono::microseconds{i};
145 }
146 // TIME_SKIPS[N] for N=16..127 has randomly-looking but roughly exponentially increasing values up to
147 // 198.416453 seconds.
148 for (; i < 128; ++i) {
149 int diff_bits = ((i - 10) * 2) / 9;
150 uint64_t diff = 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits));
151 TIME_SKIPS[i] = TIME_SKIPS[i - 1] + std::chrono::microseconds{diff};
152 }
153 }
154
155 void CheckPackageToValidate(const node::PackageToValidate& package_to_validate, NodeId peer)
156 {
157 Assert(package_to_validate.m_senders.size() == 2);
158 Assert(package_to_validate.m_senders.front() == peer);
159 Assert(package_to_validate.m_senders.back() < NUM_PEERS);
160
161 // Package is a 1p1c
162 const auto& package = package_to_validate.m_txns;
163 Assert(IsChildWithParents(package));
164 Assert(package.size() == 2);
165 }
166
167 FUZZ_TARGET(txdownloadman, .init = initialize)
168 {
169 SeedRandomStateForTest(SeedRand::ZEROS);
170 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
171 SetMockTime(ConsumeTime(fuzzed_data_provider));
172
173 // Initialize txdownloadman
174 bilingual_str error;
175 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
176 const auto max_orphan_count = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 300);
177 FastRandomContext det_rand{true};
178 node::TxDownloadManager txdownloadman{node::TxDownloadOptions{pool, det_rand, max_orphan_count, true}};
179
180 std::chrono::microseconds time{244466666};
181
182 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
183 {
184 NodeId rand_peer = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, NUM_PEERS - 1);
185
186 // Transaction can be one of the premade ones or a randomly generated one
187 auto rand_tx = fuzzed_data_provider.ConsumeBool() ?
188 MakeTransactionSpending(PickCoins(fuzzed_data_provider),
189 /*num_outputs=*/fuzzed_data_provider.ConsumeIntegralInRange(1, 500),
190 /*add_witness=*/fuzzed_data_provider.ConsumeBool()) :
191 TRANSACTIONS.at(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, TRANSACTIONS.size() - 1));
192
193 CallOneOf(
194 fuzzed_data_provider,
195 [&] {
196 node::TxDownloadConnectionInfo info{
197 .m_preferred = fuzzed_data_provider.ConsumeBool(),
198 .m_relay_permissions = fuzzed_data_provider.ConsumeBool(),
199 .m_wtxid_relay = fuzzed_data_provider.ConsumeBool()
200 };
201 txdownloadman.ConnectedPeer(rand_peer, info);
202 },
203 [&] {
204 txdownloadman.DisconnectedPeer(rand_peer);
205 txdownloadman.CheckIsEmpty(rand_peer);
206 },
207 [&] {
208 txdownloadman.ActiveTipChange();
209 },
210 [&] {
211 CBlock block;
212 block.vtx.push_back(rand_tx);
213 txdownloadman.BlockConnected(std::make_shared<CBlock>(block));
214 },
215 [&] {
216 txdownloadman.BlockDisconnected();
217 },
218 [&] {
219 txdownloadman.MempoolAcceptedTx(rand_tx);
220 },
221 [&] {
222 TxValidationState state;
223 state.Invalid(fuzzed_data_provider.PickValueInArray(TESTED_TX_RESULTS), "");
224 bool first_time_failure{fuzzed_data_provider.ConsumeBool()};
225
226 node::RejectedTxTodo todo = txdownloadman.MempoolRejectedTx(rand_tx, state, rand_peer, first_time_failure);
227 Assert(first_time_failure || !todo.m_should_add_extra_compact_tx);
228 },
229 [&] {
230 GenTxid gtxid = fuzzed_data_provider.ConsumeBool() ?
231 GenTxid::Txid(rand_tx->GetHash()) :
232 GenTxid::Wtxid(rand_tx->GetWitnessHash());
233 txdownloadman.AddTxAnnouncement(rand_peer, gtxid, time);
234 },
235 [&] {
236 txdownloadman.GetRequestsToSend(rand_peer, time);
237 },
238 [&] {
239 txdownloadman.ReceivedTx(rand_peer, rand_tx);
240 const auto& [should_validate, maybe_package] = txdownloadman.ReceivedTx(rand_peer, rand_tx);
241 // The only possible results should be:
242 // - Don't validate the tx, no package.
243 // - Don't validate the tx, package.
244 // - Validate the tx, no package.
245 // The only combination that doesn't make sense is validate both tx and package.
246 Assert(!(should_validate && maybe_package.has_value()));
247 if (maybe_package.has_value()) CheckPackageToValidate(*maybe_package, rand_peer);
248 },
249 [&] {
250 txdownloadman.ReceivedNotFound(rand_peer, {rand_tx->GetWitnessHash()});
251 },
252 [&] {
253 const bool expect_work{txdownloadman.HaveMoreWork(rand_peer)};
254 const auto ptx = txdownloadman.GetTxToReconsider(rand_peer);
255 // expect_work=true doesn't necessarily mean the next item from the workset isn't a
256 // nullptr, as the transaction could have been removed from orphanage without being
257 // removed from the peer's workset.
258 if (ptx) {
259 // However, if there was a non-null tx in the workset, HaveMoreWork should have
260 // returned true.
261 Assert(expect_work);
262 }
263 }
264 );
265 // Jump forwards or backwards
266 auto time_skip = fuzzed_data_provider.PickValueInArray(TIME_SKIPS);
267 if (fuzzed_data_provider.ConsumeBool()) time_skip *= -1;
268 time += time_skip;
269 }
270 // Disconnect everybody, check that all data structures are empty.
271 for (NodeId nodeid = 0; nodeid < NUM_PEERS; ++nodeid) {
272 txdownloadman.DisconnectedPeer(nodeid);
273 txdownloadman.CheckIsEmpty(nodeid);
274 }
275 txdownloadman.CheckIsEmpty();
276 }
277
278 // Give node 0 relay permissions, and nobody else. This helps us remember who is a RelayPermissions
279 // peer without tracking anything (this is only for the txdownload_impl target).
280 static bool HasRelayPermissions(NodeId peer) { return peer == 0; }
281
282 static void CheckInvariants(const node::TxDownloadManagerImpl& txdownload_impl, size_t max_orphan_count)
283 {
284 const TxOrphanage& orphanage = txdownload_impl.m_orphanage;
285
286 // Orphanage usage should never exceed what is allowed
287 Assert(orphanage.Size() <= max_orphan_count);
288 txdownload_impl.m_orphanage.SanityCheck();
289
290 // We should never have more than the maximum in-flight requests out for a peer.
291 for (NodeId peer = 0; peer < NUM_PEERS; ++peer) {
292 if (!HasRelayPermissions(peer)) {
293 Assert(txdownload_impl.m_txrequest.Count(peer) <= node::MAX_PEER_TX_ANNOUNCEMENTS);
294 }
295 }
296 txdownload_impl.m_txrequest.SanityCheck();
297 }
298
299 FUZZ_TARGET(txdownloadman_impl, .init = initialize)
300 {
301 SeedRandomStateForTest(SeedRand::ZEROS);
302 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
303 SetMockTime(ConsumeTime(fuzzed_data_provider));
304
305 // Initialize a TxDownloadManagerImpl
306 bilingual_str error;
307 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
308 const auto max_orphan_count = fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(0, 300);
309 FastRandomContext det_rand{true};
310 node::TxDownloadManagerImpl txdownload_impl{node::TxDownloadOptions{pool, det_rand, max_orphan_count, true}};
311
312 std::chrono::microseconds time{244466666};
313
314 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
315 {
316 NodeId rand_peer = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, NUM_PEERS - 1);
317
318 // Transaction can be one of the premade ones or a randomly generated one
319 auto rand_tx = fuzzed_data_provider.ConsumeBool() ?
320 MakeTransactionSpending(PickCoins(fuzzed_data_provider),
321 /*num_outputs=*/fuzzed_data_provider.ConsumeIntegralInRange(1, 500),
322 /*add_witness=*/fuzzed_data_provider.ConsumeBool()) :
323 TRANSACTIONS.at(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, TRANSACTIONS.size() - 1));
324
325 CallOneOf(
326 fuzzed_data_provider,
327 [&] {
328 node::TxDownloadConnectionInfo info{
329 .m_preferred = fuzzed_data_provider.ConsumeBool(),
330 .m_relay_permissions = HasRelayPermissions(rand_peer),
331 .m_wtxid_relay = fuzzed_data_provider.ConsumeBool()
332 };
333 txdownload_impl.ConnectedPeer(rand_peer, info);
334 },
335 [&] {
336 txdownload_impl.DisconnectedPeer(rand_peer);
337 txdownload_impl.CheckIsEmpty(rand_peer);
338 },
339 [&] {
340 txdownload_impl.ActiveTipChange();
341 // After a block update, nothing should be in the rejection caches
342 for (const auto& tx : TRANSACTIONS) {
343 Assert(!txdownload_impl.RecentRejectsFilter().contains(tx->GetWitnessHash().ToUint256()));
344 Assert(!txdownload_impl.RecentRejectsFilter().contains(tx->GetHash().ToUint256()));
345 Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(tx->GetWitnessHash().ToUint256()));
346 Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(tx->GetHash().ToUint256()));
347 }
348 },
349 [&] {
350 CBlock block;
351 block.vtx.push_back(rand_tx);
352 txdownload_impl.BlockConnected(std::make_shared<CBlock>(block));
353 // Block transactions must be removed from orphanage
354 Assert(!txdownload_impl.m_orphanage.HaveTx(rand_tx->GetWitnessHash()));
355 },
356 [&] {
357 txdownload_impl.BlockDisconnected();
358 Assert(!txdownload_impl.RecentConfirmedTransactionsFilter().contains(rand_tx->GetWitnessHash().ToUint256()));
359 Assert(!txdownload_impl.RecentConfirmedTransactionsFilter().contains(rand_tx->GetHash().ToUint256()));
360 },
361 [&] {
362 txdownload_impl.MempoolAcceptedTx(rand_tx);
363 },
364 [&] {
365 TxValidationState state;
366 state.Invalid(fuzzed_data_provider.PickValueInArray(TESTED_TX_RESULTS), "");
367 bool first_time_failure{fuzzed_data_provider.ConsumeBool()};
368
369 bool reject_contains_wtxid{txdownload_impl.RecentRejectsFilter().contains(rand_tx->GetWitnessHash().ToUint256())};
370
371 node::RejectedTxTodo todo = txdownload_impl.MempoolRejectedTx(rand_tx, state, rand_peer, first_time_failure);
372 Assert(first_time_failure || !todo.m_should_add_extra_compact_tx);
373 if (!reject_contains_wtxid) Assert(todo.m_unique_parents.size() <= rand_tx->vin.size());
374 },
375 [&] {
376 GenTxid gtxid = fuzzed_data_provider.ConsumeBool() ?
377 GenTxid::Txid(rand_tx->GetHash()) :
378 GenTxid::Wtxid(rand_tx->GetWitnessHash());
379 txdownload_impl.AddTxAnnouncement(rand_peer, gtxid, time);
380 },
381 [&] {
382 const auto getdata_requests = txdownload_impl.GetRequestsToSend(rand_peer, time);
383 // TxDownloadManager should not be telling us to request things we already have.
384 // Exclude m_lazy_recent_rejects_reconsiderable because it may request low-feerate parent of orphan.
385 for (const auto& gtxid : getdata_requests) {
386 Assert(!txdownload_impl.AlreadyHaveTx(gtxid, /*include_reconsiderable=*/false));
387 }
388 },
389 [&] {
390 const auto& [should_validate, maybe_package] = txdownload_impl.ReceivedTx(rand_peer, rand_tx);
391 // The only possible results should be:
392 // - Don't validate the tx, no package.
393 // - Don't validate the tx, package.
394 // - Validate the tx, no package.
395 // The only combination that doesn't make sense is validate both tx and package.
396 Assert(!(should_validate && maybe_package.has_value()));
397 if (should_validate) {
398 Assert(!txdownload_impl.AlreadyHaveTx(GenTxid::Wtxid(rand_tx->GetWitnessHash()), /*include_reconsiderable=*/true));
399 }
400 if (maybe_package.has_value()) {
401 CheckPackageToValidate(*maybe_package, rand_peer);
402
403 const auto& package = maybe_package->m_txns;
404 // Parent is in m_lazy_recent_rejects_reconsiderable and child is in m_orphanage
405 Assert(txdownload_impl.RecentRejectsReconsiderableFilter().contains(rand_tx->GetWitnessHash().ToUint256()));
406 Assert(txdownload_impl.m_orphanage.HaveTx(maybe_package->m_txns.back()->GetWitnessHash()));
407 // Package has not been rejected
408 Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(GetPackageHash(package)));
409 // Neither is in m_lazy_recent_rejects
410 Assert(!txdownload_impl.RecentRejectsFilter().contains(package.front()->GetWitnessHash().ToUint256()));
411 Assert(!txdownload_impl.RecentRejectsFilter().contains(package.back()->GetWitnessHash().ToUint256()));
412 }
413 },
414 [&] {
415 txdownload_impl.ReceivedNotFound(rand_peer, {rand_tx->GetWitnessHash()});
416 },
417 [&] {
418 const bool expect_work{txdownload_impl.HaveMoreWork(rand_peer)};
419 const auto ptx{txdownload_impl.GetTxToReconsider(rand_peer)};
420 // expect_work=true doesn't necessarily mean the next item from the workset isn't a
421 // nullptr, as the transaction could have been removed from orphanage without being
422 // removed from the peer's workset.
423 if (ptx) {
424 // However, if there was a non-null tx in the workset, HaveMoreWork should have
425 // returned true.
426 Assert(expect_work);
427 Assert(txdownload_impl.AlreadyHaveTx(GenTxid::Wtxid(ptx->GetWitnessHash()), /*include_reconsiderable=*/false));
428 // Presumably we have validated this tx. Use "missing inputs" to keep it in the
429 // orphanage longer. Later iterations might call MempoolAcceptedTx or
430 // MempoolRejectedTx with a different error.
431 TxValidationState state_missing_inputs;
432 state_missing_inputs.Invalid(TxValidationResult::TX_MISSING_INPUTS, "");
433 txdownload_impl.MempoolRejectedTx(ptx, state_missing_inputs, rand_peer, fuzzed_data_provider.ConsumeBool());
434 }
435 }
436 );
437
438 auto time_skip = fuzzed_data_provider.PickValueInArray(TIME_SKIPS);
439 if (fuzzed_data_provider.ConsumeBool()) time_skip *= -1;
440 time += time_skip;
441 }
442 CheckInvariants(txdownload_impl, max_orphan_count);
443 // Disconnect everybody, check that all data structures are empty.
444 for (NodeId nodeid = 0; nodeid < NUM_PEERS; ++nodeid) {
445 txdownload_impl.DisconnectedPeer(nodeid);
446 txdownload_impl.CheckIsEmpty(nodeid);
447 }
448 txdownload_impl.CheckIsEmpty();
449 }
450
451 } // namespace
452