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