Bitcoin Core  24.99.0
P2P Digital Currency
tx_pool.cpp
Go to the documentation of this file.
1 // Copyright (c) 2021 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>
10 #include <test/fuzz/fuzz.h>
11 #include <test/fuzz/util.h>
12 #include <test/fuzz/util/mempool.h>
13 #include <test/util/mining.h>
14 #include <test/util/script.h>
15 #include <test/util/setup_common.h>
16 #include <util/rbf.h>
17 #include <validation.h>
18 #include <validationinterface.h>
19 
21 using node::NodeContext;
22 
23 namespace {
24 
25 const TestingSetup* g_setup;
26 std::vector<COutPoint> g_outpoints_coinbase_init_mature;
27 std::vector<COutPoint> g_outpoints_coinbase_init_immature;
28 
29 struct MockedTxPool : public CTxMemPool {
30  void RollingFeeUpdate() EXCLUSIVE_LOCKS_REQUIRED(!cs)
31  {
32  LOCK(cs);
33  lastRollingFeeUpdate = GetTime();
34  blockSinceLastRollingFeeBump = true;
35  }
36 };
37 
38 void initialize_tx_pool()
39 {
40  static const auto testing_setup = MakeNoLogFileContext<const TestingSetup>();
41  g_setup = testing_setup.get();
42 
43  for (int i = 0; i < 2 * COINBASE_MATURITY; ++i) {
44  CTxIn in = MineBlock(g_setup->m_node, P2WSH_OP_TRUE);
45  // Remember the txids to avoid expensive disk access later on
46  auto& outpoints = i < COINBASE_MATURITY ?
47  g_outpoints_coinbase_init_mature :
48  g_outpoints_coinbase_init_immature;
49  outpoints.push_back(in.prevout);
50  }
52 }
53 
54 struct TransactionsDelta final : public CValidationInterface {
55  std::set<CTransactionRef>& m_removed;
56  std::set<CTransactionRef>& m_added;
57 
58  explicit TransactionsDelta(std::set<CTransactionRef>& r, std::set<CTransactionRef>& a)
59  : m_removed{r}, m_added{a} {}
60 
61  void TransactionAddedToMempool(const CTransactionRef& tx, uint64_t /* mempool_sequence */) override
62  {
63  Assert(m_added.insert(tx).second);
64  }
65 
66  void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
67  {
68  Assert(m_removed.insert(tx).second);
69  }
70 };
71 
72 void SetMempoolConstraints(ArgsManager& args, FuzzedDataProvider& fuzzed_data_provider)
73 {
74  args.ForceSetArg("-limitancestorcount",
75  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50)));
76  args.ForceSetArg("-limitancestorsize",
77  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202)));
78  args.ForceSetArg("-limitdescendantcount",
79  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50)));
80  args.ForceSetArg("-limitdescendantsize",
81  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202)));
82  args.ForceSetArg("-maxmempool",
83  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 200)));
84  args.ForceSetArg("-mempoolexpiry",
85  ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 999)));
86 }
87 
88 void Finish(FuzzedDataProvider& fuzzed_data_provider, MockedTxPool& tx_pool, Chainstate& chainstate)
89 {
90  WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1));
91  {
92  BlockAssembler::Options options;
93  options.nBlockMaxWeight = fuzzed_data_provider.ConsumeIntegralInRange(0U, MAX_BLOCK_WEIGHT);
94  options.blockMinFeeRate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
95  auto assembler = BlockAssembler{chainstate, &tx_pool, options};
96  auto block_template = assembler.CreateNewBlock(CScript{} << OP_TRUE);
97  Assert(block_template->block.vtx.size() >= 1);
98  }
99  const auto info_all = tx_pool.infoAll();
100  if (!info_all.empty()) {
101  const auto& tx_to_remove = *PickValue(fuzzed_data_provider, info_all).tx;
102  WITH_LOCK(tx_pool.cs, tx_pool.removeRecursive(tx_to_remove, MemPoolRemovalReason::BLOCK /* dummy */));
103  std::vector<uint256> all_txids;
104  tx_pool.queryHashes(all_txids);
105  assert(all_txids.size() < info_all.size());
106  WITH_LOCK(::cs_main, tx_pool.check(chainstate.CoinsTip(), chainstate.m_chain.Height() + 1));
107  }
109 }
110 
111 void MockTime(FuzzedDataProvider& fuzzed_data_provider, const Chainstate& chainstate)
112 {
113  const auto time = ConsumeTime(fuzzed_data_provider,
114  chainstate.m_chain.Tip()->GetMedianTimePast() + 1,
115  std::numeric_limits<decltype(chainstate.m_chain.Tip()->nTime)>::max());
116  SetMockTime(time);
117 }
118 
119 CTxMemPool MakeMempool(FuzzedDataProvider& fuzzed_data_provider, const NodeContext& node)
120 {
121  // Take the default options for tests...
123 
124  // ...override specific options for this specific fuzz suite
125  mempool_opts.estimator = nullptr;
126  mempool_opts.check_ratio = 1;
127  mempool_opts.require_standard = fuzzed_data_provider.ConsumeBool();
128 
129  // ...and construct a CTxMemPool from it
130  return CTxMemPool{mempool_opts};
131 }
132 
133 FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
134 {
135  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
136  const auto& node = g_setup->m_node;
137  auto& chainstate{static_cast<DummyChainState&>(node.chainman->ActiveChainstate())};
138 
139  MockTime(fuzzed_data_provider, chainstate);
140 
141  // All RBF-spendable outpoints
142  std::set<COutPoint> outpoints_rbf;
143  // All outpoints counting toward the total supply (subset of outpoints_rbf)
144  std::set<COutPoint> outpoints_supply;
145  for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
146  Assert(outpoints_supply.insert(outpoint).second);
147  }
148  outpoints_rbf = outpoints_supply;
149 
150  // The sum of the values of all spendable outpoints
151  constexpr CAmount SUPPLY_TOTAL{COINBASE_MATURITY * 50 * COIN};
152 
153  SetMempoolConstraints(*node.args, fuzzed_data_provider);
154  CTxMemPool tx_pool_{MakeMempool(fuzzed_data_provider, node)};
155  MockedTxPool& tx_pool = *static_cast<MockedTxPool*>(&tx_pool_);
156 
157  chainstate.SetMempool(&tx_pool);
158 
159  // Helper to query an amount
160  const CCoinsViewMemPool amount_view{WITH_LOCK(::cs_main, return &chainstate.CoinsTip()), tx_pool};
161  const auto GetAmount = [&](const COutPoint& outpoint) {
162  Coin c;
163  Assert(amount_view.GetCoin(outpoint, c));
164  return c.out.nValue;
165  };
166 
167  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 300)
168  {
169  {
170  // Total supply is the mempool fee + all outpoints
171  CAmount supply_now{WITH_LOCK(tx_pool.cs, return tx_pool.GetTotalFee())};
172  for (const auto& op : outpoints_supply) {
173  supply_now += GetAmount(op);
174  }
175  Assert(supply_now == SUPPLY_TOTAL);
176  }
177  Assert(!outpoints_supply.empty());
178 
179  // Create transaction to add to the mempool
180  const CTransactionRef tx = [&] {
181  CMutableTransaction tx_mut;
183  tx_mut.nLockTime = fuzzed_data_provider.ConsumeBool() ? 0 : fuzzed_data_provider.ConsumeIntegral<uint32_t>();
184  const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size());
185  const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size() * 2);
186 
187  CAmount amount_in{0};
188  for (int i = 0; i < num_in; ++i) {
189  // Pop random outpoint
190  auto pop = outpoints_rbf.begin();
191  std::advance(pop, fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, outpoints_rbf.size() - 1));
192  const auto outpoint = *pop;
193  outpoints_rbf.erase(pop);
194  amount_in += GetAmount(outpoint);
195 
196  // Create input
197  const auto sequence = ConsumeSequence(fuzzed_data_provider);
198  const auto script_sig = CScript{};
199  const auto script_wit_stack = std::vector<std::vector<uint8_t>>{WITNESS_STACK_ELEM_OP_TRUE};
200  CTxIn in;
201  in.prevout = outpoint;
202  in.nSequence = sequence;
203  in.scriptSig = script_sig;
204  in.scriptWitness.stack = script_wit_stack;
205 
206  tx_mut.vin.push_back(in);
207  }
208  const auto amount_fee = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-1000, amount_in);
209  const auto amount_out = (amount_in - amount_fee) / num_out;
210  for (int i = 0; i < num_out; ++i) {
211  tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE);
212  }
213  const auto tx = MakeTransactionRef(tx_mut);
214  // Restore previously removed outpoints
215  for (const auto& in : tx->vin) {
216  Assert(outpoints_rbf.insert(in.prevout).second);
217  }
218  return tx;
219  }();
220 
221  if (fuzzed_data_provider.ConsumeBool()) {
222  MockTime(fuzzed_data_provider, chainstate);
223  }
224  if (fuzzed_data_provider.ConsumeBool()) {
225  tx_pool.RollingFeeUpdate();
226  }
227  if (fuzzed_data_provider.ConsumeBool()) {
228  const auto& txid = fuzzed_data_provider.ConsumeBool() ?
229  tx->GetHash() :
230  PickValue(fuzzed_data_provider, outpoints_rbf).hash;
231  const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN);
232  tx_pool.PrioritiseTransaction(txid, delta);
233  }
234 
235  // Remember all removed and added transactions
236  std::set<CTransactionRef> removed;
237  std::set<CTransactionRef> added;
238  auto txr = std::make_shared<TransactionsDelta>(removed, added);
240  const bool bypass_limits = fuzzed_data_provider.ConsumeBool();
241 
242  // Make sure ProcessNewPackage on one transaction works.
243  // The result is not guaranteed to be the same as what is returned by ATMP.
244  const auto result_package = WITH_LOCK(::cs_main,
245  return ProcessNewPackage(chainstate, tx_pool, {tx}, true));
246  // If something went wrong due to a package-specific policy, it might not return a
247  // validation result for the transaction.
248  if (result_package.m_state.GetResult() != PackageValidationResult::PCKG_POLICY) {
249  auto it = result_package.m_tx_results.find(tx->GetWitnessHash());
250  Assert(it != result_package.m_tx_results.end());
251  Assert(it->second.m_result_type == MempoolAcceptResult::ResultType::VALID ||
252  it->second.m_result_type == MempoolAcceptResult::ResultType::INVALID);
253  }
254 
255  const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx, GetTime(), bypass_limits, /*test_accept=*/false));
256  const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
259 
260  Assert(accepted != added.empty());
261  Assert(accepted == res.m_state.IsValid());
262  Assert(accepted != res.m_state.IsInvalid());
263  if (accepted) {
264  Assert(added.size() == 1); // For now, no package acceptance
265  Assert(tx == *added.begin());
266  } else {
267  // Do not consider rejected transaction removed
268  removed.erase(tx);
269  }
270 
271  // Helper to insert spent and created outpoints of a tx into collections
272  using Sets = std::vector<std::reference_wrapper<std::set<COutPoint>>>;
273  const auto insert_tx = [](Sets created_by_tx, Sets consumed_by_tx, const auto& tx) {
274  for (size_t i{0}; i < tx.vout.size(); ++i) {
275  for (auto& set : created_by_tx) {
276  Assert(set.get().emplace(tx.GetHash(), i).second);
277  }
278  }
279  for (const auto& in : tx.vin) {
280  for (auto& set : consumed_by_tx) {
281  Assert(set.get().insert(in.prevout).second);
282  }
283  }
284  };
285  // Add created outpoints, remove spent outpoints
286  {
287  // Outpoints that no longer exist at all
288  std::set<COutPoint> consumed_erased;
289  // Outpoints that no longer count toward the total supply
290  std::set<COutPoint> consumed_supply;
291  for (const auto& removed_tx : removed) {
292  insert_tx(/*created_by_tx=*/{consumed_erased}, /*consumed_by_tx=*/{outpoints_supply}, /*tx=*/*removed_tx);
293  }
294  for (const auto& added_tx : added) {
295  insert_tx(/*created_by_tx=*/{outpoints_supply, outpoints_rbf}, /*consumed_by_tx=*/{consumed_supply}, /*tx=*/*added_tx);
296  }
297  for (const auto& p : consumed_erased) {
298  Assert(outpoints_supply.erase(p) == 1);
299  Assert(outpoints_rbf.erase(p) == 1);
300  }
301  for (const auto& p : consumed_supply) {
302  Assert(outpoints_supply.erase(p) == 1);
303  }
304  }
305  }
306  Finish(fuzzed_data_provider, tx_pool, chainstate);
307 }
308 
309 FUZZ_TARGET_INIT(tx_pool, initialize_tx_pool)
310 {
311  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
312  const auto& node = g_setup->m_node;
313  auto& chainstate = node.chainman->ActiveChainstate();
314 
315  MockTime(fuzzed_data_provider, chainstate);
316 
317  std::vector<uint256> txids;
318  for (const auto& outpoint : g_outpoints_coinbase_init_mature) {
319  txids.push_back(outpoint.hash);
320  }
321  for (int i{0}; i <= 3; ++i) {
322  // Add some immature and non-existent outpoints
323  txids.push_back(g_outpoints_coinbase_init_immature.at(i).hash);
324  txids.push_back(ConsumeUInt256(fuzzed_data_provider));
325  }
326 
327  SetMempoolConstraints(*node.args, fuzzed_data_provider);
328  CTxMemPool tx_pool_{MakeMempool(fuzzed_data_provider, node)};
329  MockedTxPool& tx_pool = *static_cast<MockedTxPool*>(&tx_pool_);
330 
331  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 300)
332  {
333  const auto mut_tx = ConsumeTransaction(fuzzed_data_provider, txids);
334 
335  if (fuzzed_data_provider.ConsumeBool()) {
336  MockTime(fuzzed_data_provider, chainstate);
337  }
338  if (fuzzed_data_provider.ConsumeBool()) {
339  tx_pool.RollingFeeUpdate();
340  }
341  if (fuzzed_data_provider.ConsumeBool()) {
342  const auto& txid = fuzzed_data_provider.ConsumeBool() ?
343  mut_tx.GetHash() :
344  PickValue(fuzzed_data_provider, txids);
345  const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN);
346  tx_pool.PrioritiseTransaction(txid, delta);
347  }
348 
349  const auto tx = MakeTransactionRef(mut_tx);
350  const bool bypass_limits = fuzzed_data_provider.ConsumeBool();
351  const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx, GetTime(), bypass_limits, /*test_accept=*/false));
352  const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
353  if (accepted) {
354  txids.push_back(tx->GetHash());
355  }
356  }
357  Finish(fuzzed_data_provider, tx_pool, chainstate);
358 }
359 } // namespace
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
RecursiveMutex cs_main
Mutex to guard access to validation specific variables, such as reading or changing the chainstate.
Definition: validation.cpp:121
#define Assert(val)
Identity function.
Definition: check.h:74
void ForceSetArg(const std::string &strArg, const std::string &strValue)
Definition: system.cpp:693
uint32_t nTime
Definition: chain.h:206
int64_t GetMedianTimePast() const
Definition: chain.h:296
CBlockIndex * Tip() const
Returns the index entry for the tip of this chain, or nullptr if none.
Definition: chain.h:439
int Height() const
Return the maximal height in the chain.
Definition: chain.h:468
CCoinsView that brings transactions from a mempool into view.
Definition: txmempool.h:908
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:35
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:411
static const int32_t CURRENT_VERSION
Definition: transaction.h:291
An input of a transaction.
Definition: transaction.h:74
uint32_t nSequence
Definition: transaction.h:78
CScript scriptSig
Definition: transaction.h:77
CScriptWitness scriptWitness
Only serialized through CTransaction.
Definition: transaction.h:79
COutPoint prevout
Definition: transaction.h:76
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:432
CAmount nValue
Definition: transaction.h:159
Implement this to subscribe to events generated in validation.
virtual void TransactionAddedToMempool(const CTransactionRef &tx, uint64_t mempool_sequence)
Notifies listeners of a transaction having been added to mempool.
virtual void TransactionRemovedFromMempool(const CTransactionRef &tx, MemPoolRemovalReason reason, uint64_t mempool_sequence)
Notifies listeners of a transaction leaving mempool.
Chainstate stores and provides an API to update our local knowledge of the current best chain.
Definition: validation.h:435
CChain m_chain
The current chain of blockheaders we consult and build on.
Definition: validation.h:516
CCoinsViewCache & CoinsTip() EXCLUSIVE_LOCKS_REQUIRED(
Definition: validation.h:538
A UTXO entry.
Definition: coins.h:31
CTxOut out
unspent transaction output
Definition: coins.h:34
T ConsumeIntegralInRange(T min, T max)
Generate a new block, without valid proof-of-work.
Definition: miner.h:129
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
Definition: consensus.h:15
static const int COINBASE_MATURITY
Coinbase transaction outputs can only be spent after this number of new blocks (network rule)
Definition: consensus.h:19
#define FUZZ_TARGET_INIT(name, init_fun)
Definition: fuzz.h:34
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
static void pool cs
Definition: init.h:25
ArgsManager args
@ PCKG_POLICY
The package itself is invalid (e.g. too many transactions).
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:415
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:414
@ OP_TRUE
Definition: script.h:80
CTxMemPool::Options MemPoolOptionsForTest(const NodeContext &node)
std::string ToString(const T &t)
Locale-independent version of std::to_string.
Definition: string.h:109
node::NodeContext m_node
Definition: setup_common.h:84
A mutable version of CTransaction.
Definition: transaction.h:373
std::vector< CTxOut > vout
Definition: transaction.h:375
std::vector< CTxIn > vin
Definition: transaction.h:374
std::vector< std::vector< unsigned char > > stack
Definition: script.h:566
@ INVALID
Fully validated, valid.
Testing setup that configures a complete environment.
Definition: setup_common.h:109
Options struct containing options for constructing a CTxMemPool.
CBlockPolicyEstimator * estimator
NodeContext struct containing references to chain state and connection state.
Definition: context.h:43
#define LOCK(cs)
Definition: sync.h:261
#define WITH_LOCK(cs, code)
Run code while locking a mutex.
Definition: sync.h:305
uint32_t ConsumeSequence(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition: util.cpp:432
CMutableTransaction ConsumeTransaction(FuzzedDataProvider &fuzzed_data_provider, const std::optional< std::vector< uint256 >> &prevout_txids, const int max_num_in, const int max_num_out) noexcept
Definition: util.cpp:315
int64_t ConsumeTime(FuzzedDataProvider &fuzzed_data_provider, const std::optional< int64_t > &min, const std::optional< int64_t > &max) noexcept
Definition: util.cpp:307
CAmount ConsumeMoney(FuzzedDataProvider &fuzzed_data_provider, const std::optional< CAmount > &max) noexcept
Definition: util.cpp:302
auto & PickValue(FuzzedDataProvider &fuzzed_data_provider, Collection &col)
Definition: util.h:100
uint256 ConsumeUInt256(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition: util.h:201
CTxIn MineBlock(const NodeContext &node, const CScript &coinbase_scriptPubKey)
Returns the generated coin.
Definition: mining.cpp:62
static const std::vector< uint8_t > WITNESS_STACK_ELEM_OP_TRUE
Definition: script.h:11
static const CScript P2WSH_OP_TRUE
Definition: script.h:12
#define EXCLUSIVE_LOCKS_REQUIRED(...)
Definition: threadsafety.h:49
int64_t GetTime()
Definition: time.cpp:115
void SetMockTime(int64_t nMockTimeIn)
DEPRECATED Use SetMockTime with chrono type.
Definition: time.cpp:89
MemPoolRemovalReason
Reason why a transaction was removed from the mempool, this is passed to the notification signal.
Definition: txmempool.h:349
@ BLOCK
Removed for block.
MempoolAcceptResult AcceptToMemoryPool(Chainstate &active_chainstate, const CTransactionRef &tx, int64_t accept_time, bool bypass_limits, bool test_accept) EXCLUSIVE_LOCKS_REQUIRED(
Try to add a transaction to the mempool.
PackageMempoolAcceptResult ProcessNewPackage(Chainstate &active_chainstate, CTxMemPool &pool, const Package &package, bool test_accept)
Validate (and maybe submit) a package to the mempool.
assert(!tx.IsCoinBase())
void UnregisterSharedValidationInterface(std::shared_ptr< CValidationInterface > callbacks)
Unregister subscriber.
void SyncWithValidationInterfaceQueue()
This is a synonym for the following, which asserts certain locks are not held: std::promise<void> pro...
void RegisterSharedValidationInterface(std::shared_ptr< CValidationInterface > callbacks)
Register subscriber.