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/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      FastRandomContext det_rand{true};
177      node::TxDownloadManager txdownloadman{node::TxDownloadOptions{pool, det_rand, true}};
178  
179      std::chrono::microseconds time{244466666};
180  
181      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 500)
182      {
183          NodeId rand_peer = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, NUM_PEERS - 1);
184  
185          // Transaction can be one of the premade ones or a randomly generated one
186          auto rand_tx = fuzzed_data_provider.ConsumeBool() ?
187              MakeTransactionSpending(PickCoins(fuzzed_data_provider),
188                                      /*num_outputs=*/fuzzed_data_provider.ConsumeIntegralInRange(1, 500),
189                                      /*add_witness=*/fuzzed_data_provider.ConsumeBool()) :
190              TRANSACTIONS.at(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, TRANSACTIONS.size() - 1));
191  
192          CallOneOf(
193              fuzzed_data_provider,
194              [&] {
195                  node::TxDownloadConnectionInfo info{
196                      .m_preferred = fuzzed_data_provider.ConsumeBool(),
197                      .m_relay_permissions = fuzzed_data_provider.ConsumeBool(),
198                      .m_wtxid_relay = fuzzed_data_provider.ConsumeBool()
199                  };
200                  txdownloadman.ConnectedPeer(rand_peer, info);
201              },
202              [&] {
203                  txdownloadman.DisconnectedPeer(rand_peer);
204                  txdownloadman.CheckIsEmpty(rand_peer);
205              },
206              [&] {
207                  txdownloadman.ActiveTipChange();
208              },
209              [&] {
210                  CBlock block;
211                  block.vtx.push_back(rand_tx);
212                  txdownloadman.BlockConnected(std::make_shared<CBlock>(block));
213              },
214              [&] {
215                  txdownloadman.BlockDisconnected();
216              },
217              [&] {
218                  txdownloadman.MempoolAcceptedTx(rand_tx);
219              },
220              [&] {
221                  TxValidationState state;
222                  state.Invalid(fuzzed_data_provider.PickValueInArray(TESTED_TX_RESULTS), "");
223                  bool first_time_failure{fuzzed_data_provider.ConsumeBool()};
224  
225                  node::RejectedTxTodo todo = txdownloadman.MempoolRejectedTx(rand_tx, state, rand_peer, first_time_failure);
226                  Assert(first_time_failure || !todo.m_should_add_extra_compact_tx);
227              },
228              [&] {
229                  auto gtxid = fuzzed_data_provider.ConsumeBool() ?
230                               GenTxid{rand_tx->GetHash()} :
231                               GenTxid{rand_tx->GetWitnessHash()};
232                  txdownloadman.AddTxAnnouncement(rand_peer, gtxid, time);
233              },
234              [&] {
235                  txdownloadman.GetRequestsToSend(rand_peer, time);
236              },
237              [&] {
238                  txdownloadman.ReceivedTx(rand_peer, rand_tx);
239                  const auto& [should_validate, maybe_package] = txdownloadman.ReceivedTx(rand_peer, rand_tx);
240                  // The only possible results should be:
241                  // - Don't validate the tx, no package.
242                  // - Don't validate the tx, package.
243                  // - Validate the tx, no package.
244                  // The only combination that doesn't make sense is validate both tx and package.
245                  Assert(!(should_validate && maybe_package.has_value()));
246                  if (maybe_package.has_value()) CheckPackageToValidate(*maybe_package, rand_peer);
247              },
248              [&] {
249                  txdownloadman.ReceivedNotFound(rand_peer, {rand_tx->GetWitnessHash()});
250              },
251              [&] {
252                  const bool expect_work{txdownloadman.HaveMoreWork(rand_peer)};
253                  const auto ptx = txdownloadman.GetTxToReconsider(rand_peer);
254                  // expect_work=true doesn't necessarily mean the next item from the workset isn't a
255                  // nullptr, as the transaction could have been removed from orphanage without being
256                  // removed from the peer's workset.
257                  if (ptx) {
258                      // However, if there was a non-null tx in the workset, HaveMoreWork should have
259                      // returned true.
260                      Assert(expect_work);
261                  }
262              });
263          // Jump forwards or backwards
264          auto time_skip = fuzzed_data_provider.PickValueInArray(TIME_SKIPS);
265          if (fuzzed_data_provider.ConsumeBool()) time_skip *= -1;
266          time += time_skip;
267      }
268      // Disconnect everybody, check that all data structures are empty.
269      for (NodeId nodeid = 0; nodeid < NUM_PEERS; ++nodeid) {
270          txdownloadman.DisconnectedPeer(nodeid);
271          txdownloadman.CheckIsEmpty(nodeid);
272      }
273      txdownloadman.CheckIsEmpty();
274  }
275  
276  // Give node 0 relay permissions, and nobody else. This helps us remember who is a RelayPermissions
277  // peer without tracking anything (this is only for the txdownload_impl target).
278  static bool HasRelayPermissions(NodeId peer) { return peer == 0; }
279  
280  static void CheckInvariants(const node::TxDownloadManagerImpl& txdownload_impl)
281  {
282      txdownload_impl.m_orphanage->SanityCheck();
283      // We should never have more than the maximum in-flight requests out for a peer.
284      for (NodeId peer = 0; peer < NUM_PEERS; ++peer) {
285          if (!HasRelayPermissions(peer)) {
286              Assert(txdownload_impl.m_txrequest.Count(peer) <= node::MAX_PEER_TX_ANNOUNCEMENTS);
287          }
288      }
289      txdownload_impl.m_txrequest.SanityCheck();
290  }
291  
292  FUZZ_TARGET(txdownloadman_impl, .init = initialize)
293  {
294      SeedRandomStateForTest(SeedRand::ZEROS);
295      FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
296      SetMockTime(ConsumeTime(fuzzed_data_provider));
297  
298      // Initialize a TxDownloadManagerImpl
299      bilingual_str error;
300      CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error};
301      FastRandomContext det_rand{true};
302      node::TxDownloadManagerImpl txdownload_impl{node::TxDownloadOptions{pool, det_rand, true}};
303  
304      std::chrono::microseconds time{244466666};
305  
306      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 500)
307      {
308          NodeId rand_peer = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, NUM_PEERS - 1);
309  
310          // Transaction can be one of the premade ones or a randomly generated one
311          auto rand_tx = fuzzed_data_provider.ConsumeBool() ?
312              MakeTransactionSpending(PickCoins(fuzzed_data_provider),
313                                      /*num_outputs=*/fuzzed_data_provider.ConsumeIntegralInRange(1, 500),
314                                      /*add_witness=*/fuzzed_data_provider.ConsumeBool()) :
315              TRANSACTIONS.at(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, TRANSACTIONS.size() - 1));
316  
317          CallOneOf(
318              fuzzed_data_provider,
319              [&] {
320                  node::TxDownloadConnectionInfo info{
321                      .m_preferred = fuzzed_data_provider.ConsumeBool(),
322                      .m_relay_permissions = HasRelayPermissions(rand_peer),
323                      .m_wtxid_relay = fuzzed_data_provider.ConsumeBool()
324                  };
325                  txdownload_impl.ConnectedPeer(rand_peer, info);
326              },
327              [&] {
328                  txdownload_impl.DisconnectedPeer(rand_peer);
329                  txdownload_impl.CheckIsEmpty(rand_peer);
330              },
331              [&] {
332                  txdownload_impl.ActiveTipChange();
333                  // After a block update, nothing should be in the rejection caches
334                  for (const auto& tx : TRANSACTIONS) {
335                      Assert(!txdownload_impl.RecentRejectsFilter().contains(tx->GetWitnessHash().ToUint256()));
336                      Assert(!txdownload_impl.RecentRejectsFilter().contains(tx->GetHash().ToUint256()));
337                      Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(tx->GetWitnessHash().ToUint256()));
338                      Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(tx->GetHash().ToUint256()));
339                  }
340              },
341              [&] {
342                  CBlock block;
343                  block.vtx.push_back(rand_tx);
344                  txdownload_impl.BlockConnected(std::make_shared<CBlock>(block));
345                  // Block transactions must be removed from orphanage
346                  Assert(!txdownload_impl.m_orphanage->HaveTx(rand_tx->GetWitnessHash()));
347              },
348              [&] {
349                  txdownload_impl.BlockDisconnected();
350                  Assert(!txdownload_impl.RecentConfirmedTransactionsFilter().contains(rand_tx->GetWitnessHash().ToUint256()));
351                  Assert(!txdownload_impl.RecentConfirmedTransactionsFilter().contains(rand_tx->GetHash().ToUint256()));
352              },
353              [&] {
354                  txdownload_impl.MempoolAcceptedTx(rand_tx);
355              },
356              [&] {
357                  TxValidationState state;
358                  state.Invalid(fuzzed_data_provider.PickValueInArray(TESTED_TX_RESULTS), "");
359                  bool first_time_failure{fuzzed_data_provider.ConsumeBool()};
360  
361                  bool reject_contains_wtxid{txdownload_impl.RecentRejectsFilter().contains(rand_tx->GetWitnessHash().ToUint256())};
362  
363                  node::RejectedTxTodo todo = txdownload_impl.MempoolRejectedTx(rand_tx, state, rand_peer, first_time_failure);
364                  Assert(first_time_failure || !todo.m_should_add_extra_compact_tx);
365                  if (!reject_contains_wtxid) Assert(todo.m_unique_parents.size() <= rand_tx->vin.size());
366              },
367              [&] {
368                  auto gtxid = fuzzed_data_provider.ConsumeBool() ?
369                               GenTxid{rand_tx->GetHash()} :
370                               GenTxid{rand_tx->GetWitnessHash()};
371                  txdownload_impl.AddTxAnnouncement(rand_peer, gtxid, time);
372              },
373              [&] {
374                  const auto getdata_requests = txdownload_impl.GetRequestsToSend(rand_peer, time);
375                  // TxDownloadManager should not be telling us to request things we already have.
376                  // Exclude m_lazy_recent_rejects_reconsiderable because it may request low-feerate parent of orphan.
377                  for (const auto& gtxid : getdata_requests) {
378                      Assert(!txdownload_impl.AlreadyHaveTx(gtxid, /*include_reconsiderable=*/false));
379                  }
380              },
381              [&] {
382                  const auto& [should_validate, maybe_package] = txdownload_impl.ReceivedTx(rand_peer, rand_tx);
383                  // The only possible results should be:
384                  // - Don't validate the tx, no package.
385                  // - Don't validate the tx, package.
386                  // - Validate the tx, no package.
387                  // The only combination that doesn't make sense is validate both tx and package.
388                  Assert(!(should_validate && maybe_package.has_value()));
389                  if (should_validate) {
390                      Assert(!txdownload_impl.AlreadyHaveTx(rand_tx->GetWitnessHash(), /*include_reconsiderable=*/true));
391                  }
392                  if (maybe_package.has_value()) {
393                      CheckPackageToValidate(*maybe_package, rand_peer);
394  
395                      const auto& package = maybe_package->m_txns;
396                      // Parent is in m_lazy_recent_rejects_reconsiderable and child is in m_orphanage
397                      Assert(txdownload_impl.RecentRejectsReconsiderableFilter().contains(rand_tx->GetWitnessHash().ToUint256()));
398                      Assert(txdownload_impl.m_orphanage->HaveTx(maybe_package->m_txns.back()->GetWitnessHash()));
399                      // Package has not been rejected
400                      Assert(!txdownload_impl.RecentRejectsReconsiderableFilter().contains(GetPackageHash(package)));
401                      // Neither is in m_lazy_recent_rejects
402                      Assert(!txdownload_impl.RecentRejectsFilter().contains(package.front()->GetWitnessHash().ToUint256()));
403                      Assert(!txdownload_impl.RecentRejectsFilter().contains(package.back()->GetWitnessHash().ToUint256()));
404                  }
405              },
406              [&] {
407                  txdownload_impl.ReceivedNotFound(rand_peer, {rand_tx->GetWitnessHash()});
408              },
409              [&] {
410                  const bool expect_work{txdownload_impl.HaveMoreWork(rand_peer)};
411                  const auto ptx{txdownload_impl.GetTxToReconsider(rand_peer)};
412                  // expect_work=true doesn't necessarily mean the next item from the workset isn't a
413                  // nullptr, as the transaction could have been removed from orphanage without being
414                  // removed from the peer's workset.
415                  if (ptx) {
416                      // However, if there was a non-null tx in the workset, HaveMoreWork should have
417                      // returned true.
418                      Assert(expect_work);
419                      Assert(txdownload_impl.AlreadyHaveTx(ptx->GetWitnessHash(), /*include_reconsiderable=*/false));
420                      // Presumably we have validated this tx. Use "missing inputs" to keep it in the
421                      // orphanage longer. Later iterations might call MempoolAcceptedTx or
422                      // MempoolRejectedTx with a different error.
423                      TxValidationState state_missing_inputs;
424                      state_missing_inputs.Invalid(TxValidationResult::TX_MISSING_INPUTS, "");
425                      txdownload_impl.MempoolRejectedTx(ptx, state_missing_inputs, rand_peer, fuzzed_data_provider.ConsumeBool());
426                  }
427              });
428  
429          auto time_skip = fuzzed_data_provider.PickValueInArray(TIME_SKIPS);
430          if (fuzzed_data_provider.ConsumeBool()) time_skip *= -1;
431          time += time_skip;
432      }
433      CheckInvariants(txdownload_impl);
434      // Disconnect everybody, check that all data structures are empty.
435      for (NodeId nodeid = 0; nodeid < NUM_PEERS; ++nodeid) {
436          txdownload_impl.DisconnectedPeer(nodeid);
437          txdownload_impl.CheckIsEmpty(nodeid);
438      }
439      txdownload_impl.CheckIsEmpty();
440  }
441  
442  } // namespace