Bitcoin ABC  0.28.12
P2P Digital Currency
chained_tx.cpp
Go to the documentation of this file.
1 // Copyright (c) 2021 The Bitcoin 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 <bench/bench.h>
6 #include <config.h>
7 #include <consensus/amount.h>
8 #include <node/context.h>
9 #include <node/miner.h>
10 #include <primitives/transaction.h>
11 #include <script/script.h>
12 #include <txmempool.h>
13 #include <util/string.h>
14 #include <util/system.h>
15 #include <validation.h>
16 
17 #include <test/util/mining.h>
18 #include <test/util/setup_common.h>
19 
20 #include <list>
21 #include <queue>
22 #include <vector>
23 
26 
27 static const CScript REDEEM_SCRIPT = CScript() << OP_DROP << OP_TRUE;
28 
29 static const CScript SCRIPT_PUB_KEY =
31  << OP_EQUAL;
32 
33 static const CScript SCRIPT_SIG = CScript() << std::vector<uint8_t>(100, 0xff)
35 
37 static std::vector<CTxIn> createUTXOs(const Config &config, size_t n,
39  std::vector<CTxIn> utxos;
40  utxos.reserve(n);
41 
42  for (size_t i = 0; i < n; ++i) {
43  utxos.emplace_back(MineBlock(config, node, SCRIPT_PUB_KEY));
44  }
45 
46  for (size_t i = 0; i < COINBASE_MATURITY + 1; ++i) {
47  MineBlock(config, node, SCRIPT_PUB_KEY);
48  }
49 
50  return utxos;
51 }
52 
54 static CTransactionRef toTx(const Config &config, CTxIn txin) {
56  tx.vin.emplace_back(txin);
57  tx.vin.back().scriptSig = SCRIPT_SIG;
58  tx.vout.emplace_back(25 * COIN - 1337 * SATOSHI, SCRIPT_PUB_KEY);
59  return MakeTransactionRef(tx);
60 }
61 
63 static std::vector<CTransactionRef>
64 oneInOneOutChain(const Config &config, CTxIn utxo, const size_t chainLength) {
65  auto firstTx = toTx(config, std::move(utxo));
66 
67  // Build the chain
68  std::vector<CTransactionRef> chain = {firstTx};
69  chain.reserve(chainLength);
70  while (chain.size() < chainLength) {
71  const COutPoint parent(chain.back()->GetId(), 0);
72  const Amount inAmount(chain.back()->vout[0].nValue);
74  tx.vin.emplace_back(CTxIn(parent, SCRIPT_SIG));
75  tx.vout.emplace_back(inAmount - 1337 * SATOSHI, SCRIPT_PUB_KEY);
76  chain.emplace_back(MakeTransactionRef(tx));
77  }
78  assert(chain.size() == chainLength);
79  return chain;
80 }
81 
85 static std::vector<CTransactionRef> twoInOneOutTree(const Config &config,
87  const size_t treeDepth) {
88  // Total number of txs is the sum of nodes at each depth of a binary tree.
89  size_t txs = 0;
90  for (size_t i = 0; i <= treeDepth; ++i) {
91  txs += std::pow(2, i);
92  }
93  const size_t leafs = std::pow(2, treeDepth);
94 
95  std::vector<CTransactionRef> chain;
96  chain.reserve(txs);
97 
98  std::queue<CTransactionRef> queue;
99  for (auto txin : createUTXOs(config, leafs, node)) {
100  auto tx = toTx(config, std::move(txin));
101  queue.push(tx);
102  chain.emplace_back(tx);
103  }
104 
105  while (true) {
107 
108  const CTransactionRef txin1 = queue.front();
109  queue.pop();
110  const CTransactionRef txin2 = queue.front();
111  queue.pop();
112 
113  const Amount inAmount = txin1->vout[0].nValue + txin2->vout[0].nValue;
114 
115  tx.vin.emplace_back(CTxIn(COutPoint(txin1->GetId(), 0), SCRIPT_SIG));
116  tx.vin.emplace_back(CTxIn(COutPoint(txin2->GetId(), 0), SCRIPT_SIG));
117  tx.vout.emplace_back(inAmount - 1337 * SATOSHI, SCRIPT_PUB_KEY);
118 
120  chain.push_back(txref);
121  if (queue.empty()) {
122  break;
123  }
124  queue.emplace(txref);
125  }
126  assert(chain.size() == txs);
127  return chain;
128 }
129 
132  const std::vector<CTransactionRef> chainedTxs) {
133  auto chainman = Assert(node.chainman.get());
134  Chainstate &activeChainState = chainman->ActiveChainstate();
135 
136  CTxMemPool &mempool{*Assert(activeChainState.GetMempool())};
137  assert(mempool.size() == 0);
138 
139  bench.run([&] {
140  LOCK(::cs_main);
141  for (const auto &tx : chainedTxs) {
142  MempoolAcceptResult result =
143  AcceptToMemoryPool(activeChainState, tx, GetTime(),
144  /*bypass_limits=*/false);
145  assert(result.m_result_type ==
147  }
148  mempool.clear();
149  });
150 }
151 
157 static void benchReorg(const Config &config, node::NodeContext &node,
158  benchmark::Bench &bench, size_t reorgDepth,
159  size_t chainSizePerBlock, bool includeMempoolTxRemoval) {
160  auto utxos = createUTXOs(config, reorgDepth, node);
161  std::vector<std::vector<CTransactionRef>> chains;
162  for (auto &utxo : utxos) {
163  chains.emplace_back(
164  oneInOneOutChain(config, std::move(utxo), chainSizePerBlock));
165  }
166 
167  auto chainman = Assert(node.chainman.get());
168  Chainstate &activeChainState = chainman->ActiveChainstate();
169 
170  // Current tip will be last valid block.
171  CBlockIndex *tipBeforeInvalidate = activeChainState.m_chain.Tip();
172  assert(tipBeforeInvalidate != nullptr);
173 
174  CBlockIndex *blockToInvalidate = nullptr;
175 
176  CTxMemPool &mempool{*Assert(activeChainState.GetMempool())};
177  assert(mempool.size() == 0);
178 
179  // Build blocks
180  TestMemPoolEntryHelper entry;
181  entry.nFee = 1337 * SATOSHI;
182  for (const auto &chain : chains) {
183  {
184  LOCK2(cs_main, mempool.cs);
185  for (const auto &tx : chain) {
186  mempool.addUnchecked(entry.FromTx(tx));
187  }
188  }
189  assert(mempool.size() == chain.size());
190  MineBlock(config, node, SCRIPT_PUB_KEY);
191  assert(mempool.size() == 0);
192 
193  assert(activeChainState.m_chain.Tip()->nTx ==
194  chain.size() + 1 /* coinbase */);
195 
196  if (blockToInvalidate == nullptr) {
197  blockToInvalidate = activeChainState.m_chain.Tip();
198  }
199  }
200  CBlockIndex *mostWorkTip = activeChainState.m_chain.Tip();
201 
202  bench.run([&] {
203  BlockValidationState state;
204 
205  // Disconnect blocks with long transaction chains
206  activeChainState.InvalidateBlock(state, blockToInvalidate);
207  assert(state.IsValid());
208 
209  activeChainState.ActivateBestChain(state);
210  assert(state.IsValid());
211  assert(activeChainState.m_chain.Tip() == tipBeforeInvalidate);
212 
213  // Transactions should be stuffed back into the mempool.
214  assert(mempool.size() == reorgDepth * chainSizePerBlock);
215 
216  if (!includeMempoolTxRemoval) {
217  // As of writing this test, removing transactions from mempool
218  // during re-connect takes significant amount of time, so we allow
219  // to test both with and without this process.
220  mempool.clear();
221  }
222 
223  // Reconnect block
224  {
225  LOCK(cs_main);
226  activeChainState.ResetBlockFailureFlags(blockToInvalidate);
227  }
228 
229  activeChainState.ActivateBestChain(state);
230  assert(state.IsValid());
231  assert(activeChainState.m_chain.Tip() == mostWorkTip);
232  assert(mempool.size() == 0);
233  });
234 }
235 
236 static void
238  benchmark::Bench &bench,
239  const std::vector<std::vector<CTransactionRef>> &chains) {
240  TestMemPoolEntryHelper entry;
241  entry.nFee = 1337 * SATOSHI;
242 
243  auto chainman = Assert(node.chainman.get());
244  Chainstate &activeChainState = chainman->ActiveChainstate();
245  CTxMemPool &mempool{*Assert(activeChainState.GetMempool())};
246 
247  // Fill mempool
248  size_t txCount = 0;
249  for (const auto &chain : chains) {
250  LOCK2(cs_main, mempool.cs);
251  for (const auto &tx : chain) {
252  mempool.addUnchecked(entry.FromTx(tx));
253  ++txCount;
254  }
255  }
256  assert(mempool.size() == txCount);
257 
258  const CScript dummy = CScript() << OP_TRUE;
259  bench.run([&] {
260  auto blocktemplate =
261  node::BlockAssembler{config, activeChainState, &mempool}
262  .CreateNewBlock(dummy);
263  assert(blocktemplate);
264  // +1 for coinbase
265  assert(blocktemplate->block.vtx.size() == txCount + 1);
266  });
267 }
268 
269 static void
271  const std::vector<std::vector<CTransactionRef>> &chains,
272  bool revFee = true) {
273  std::list<CTxMemPool> pools;
274 
275  // Note: in order to isolate how long eviction takes (as opposed to add +
276  // eviction), we are forced to pre-create all the pools we will be needing
277  // up front.
278 
279  bench.epochs(2).epochIterations(1);
280 
281  for (uint64_t i = 0; i < bench.epochs() * bench.epochIterations() + 1;
282  ++i) {
283  CTxMemPool::Options mempool_opts{
284  .check_ratio = 0,
285  };
286  pools.emplace_back(mempool_opts);
287  CTxMemPool &pool = pools.back();
288  TestMemPoolEntryHelper entry;
289  // Fill mempool
290  size_t txCount = 0;
291  entry.nFee = 1337 * SATOSHI;
292  // add in order of decreasing fee if revFee, increasing otherwise
293  const Amount feeBump =
294  revFee ? int64_t(-1) * SATOSHI : int64_t(1) * SATOSHI;
295  for (const auto &chain : chains) {
296  if (revFee) {
297  entry.nFee += int64_t(chain.size()) * SATOSHI;
298  }
299  LOCK2(cs_main, pool.cs);
300  for (const auto &tx : chain) {
301  pool.addUnchecked(entry.FromTx(tx));
302  entry.nFee += feeBump;
303  // Setting spendCoinbase to false here assumes it's a chain of
304  // 1-in-1-out transaction chain.
305  ++txCount;
306  }
307  if (revFee) {
308  entry.nFee += int64_t(chain.size()) * SATOSHI;
309  }
310  }
311  assert(pool.size() == txCount);
312  }
313 
314  auto it = pools.begin();
315 
316  bench.run([&] {
317  assert(it != pools.end());
318  auto &pool = *it++;
319  LOCK2(cs_main, pool.cs);
320  while (auto prevSize = pool.size()) {
321  pool.TrimToSize(pool.DynamicMemoryUsage() * 99 / 100);
322  assert(pool.size() < prevSize);
323  }
324  });
325 }
326 
329  RegTestingSetup test_setup{};
330  const Config &config = GetConfig();
331  const std::vector<CTransactionRef> chainedTxs = oneInOneOutChain(
332  config, createUTXOs(config, 1, test_setup.m_node).back(), 50);
333  benchATMP(test_setup.m_node, bench, chainedTxs);
334 }
335 
338  RegTestingSetup test_setup{};
339  const Config &config = GetConfig();
340  const std::vector<CTransactionRef> chainedTxs = oneInOneOutChain(
341  config, createUTXOs(config, 1, test_setup.m_node).back(), 500);
342  benchATMP(test_setup.m_node, bench, chainedTxs);
343 }
344 
347  RegTestingSetup test_setup{};
348  const Config &config = GetConfig();
349  const std::vector<CTransactionRef> chainedTxs =
350  twoInOneOutTree(config, test_setup.m_node, 5);
351  assert(chainedTxs.size() == 63);
352  benchATMP(test_setup.m_node, bench, chainedTxs);
353 }
354 
357  RegTestingSetup test_setup{};
358  const Config &config = GetConfig();
359  const std::vector<CTransactionRef> chainedTxs =
360  twoInOneOutTree(config, test_setup.m_node, 8);
361  assert(chainedTxs.size() == 511);
362  benchATMP(test_setup.m_node, bench, chainedTxs);
363 }
364 
368  RegTestingSetup test_setup{};
369  const Config &config = GetConfig();
370  benchReorg(config, test_setup.m_node, bench, 10, 50, true);
371 }
372 
376  RegTestingSetup test_setup{};
377  const Config &config = GetConfig();
378  benchReorg(config, test_setup.m_node, bench, 10, 500, true);
379 }
380 
385  RegTestingSetup test_setup{};
386  const Config &config = GetConfig();
387  benchReorg(config, test_setup.m_node, bench, 10, 50, false);
388 }
389 
394  RegTestingSetup test_setup{};
395  const Config &config = GetConfig();
396  benchReorg(config, test_setup.m_node, bench, 10, 500, false);
397 }
398 
401  RegTestingSetup test_setup{};
402  const Config &config = GetConfig();
403  const CTxIn utxo = createUTXOs(config, 1, test_setup.m_node).back();
404  benchGenerateNewBlock(config, test_setup.m_node, bench,
405  {oneInOneOutChain(config, std::move(utxo), 50)});
406 }
407 
410  RegTestingSetup test_setup{};
411  const Config &config = GetConfig();
412  const CTxIn utxo = createUTXOs(config, 1, test_setup.m_node).back();
413  benchGenerateNewBlock(config, test_setup.m_node, bench,
414  {oneInOneOutChain(config, std::move(utxo), 500)});
415 }
416 
419 static void EvictChained50Tx(benchmark::Bench &bench) {
420  RegTestingSetup test_setup{};
421  const Config &config = GetConfig();
422  // create 2000 chains of 50 1-in-1-out each
423  std::vector<std::vector<CTransactionRef>> chains;
424  constexpr int NChains = 2000;
425  const auto utxos = createUTXOs(config, NChains, test_setup.m_node);
426  for (int i = 0; i < NChains; ++i) {
427  chains.push_back(oneInOneOutChain(config, utxos[i], 50));
428  }
429  benchEviction(config, bench, chains, false);
430 }
431 
435  RegTestingSetup test_setup{};
436  const Config &config = GetConfig();
437  // create 2000 chains of 50 1-in-1-out each
438  std::vector<std::vector<CTransactionRef>> chains;
439  constexpr int NChains = 2000;
440  const auto utxos = createUTXOs(config, NChains, test_setup.m_node);
441  for (int i = 0; i < NChains; ++i) {
442  chains.push_back(oneInOneOutChain(config, utxos[i], 50));
443  }
444  benchEviction(config, bench, chains, true);
445 }
446 
451 
456 
459 
static constexpr Amount SATOSHI
Definition: amount.h:143
static constexpr Amount COIN
Definition: amount.h:144
static void EvictChained50Tx(benchmark::Bench &bench)
Fill a mempool then evict 2000 x 50 1-input-1-output transactions, CTxMemPool version,...
Definition: chained_tx.cpp:419
static void Reorg10BlocksWith500TxChain(benchmark::Bench &bench)
Try to reorg a chain of depth 10 where each block has a 500 tx 1-input-1-output chain.
Definition: chained_tx.cpp:375
static void MempoolAcceptance50ChainedTxs(benchmark::Bench &bench)
Tests a chain of 50 1-input-1-output transactions.
Definition: chained_tx.cpp:328
static void MempoolAcceptance511TxTree(benchmark::Bench &bench)
Test a tree of 511 2-inputs-1-output transactions.
Definition: chained_tx.cpp:356
static void MempoolAcceptance63TxTree(benchmark::Bench &bench)
Test a tree of 63 2-inputs-1-output transactions.
Definition: chained_tx.cpp:346
static void EvictChained50TxRev(benchmark::Bench &bench)
Fill a mempool then evict 2000 x 50 1-input-1-output transactions, CTxMemPool version,...
Definition: chained_tx.cpp:434
static std::vector< CTxIn > createUTXOs(const Config &config, size_t n, node::NodeContext &node)
Mine new utxos.
Definition: chained_tx.cpp:37
static void benchGenerateNewBlock(const Config &config, node::NodeContext &node, benchmark::Bench &bench, const std::vector< std::vector< CTransactionRef >> &chains)
Definition: chained_tx.cpp:237
static void Reorg10BlocksWith500TxChainSkipMempool(benchmark::Bench &bench)
Try to reorg a chain of depth 10 where each block has a 500 tx 1-input-1-output chain,...
Definition: chained_tx.cpp:393
static void MempoolAcceptance500ChainedTxs(benchmark::Bench &bench)
Tests a chain of 500 1-input-1-output transactions.
Definition: chained_tx.cpp:337
static std::vector< CTransactionRef > twoInOneOutTree(const Config &config, node::NodeContext &node, const size_t treeDepth)
Creates a tree of transactions with 2-inputs-1-output.
Definition: chained_tx.cpp:85
static void GenerateBlock50ChainedTxs(benchmark::Bench &bench)
Generate a block with 50 1-input-1-output transactions.
Definition: chained_tx.cpp:400
static void Reorg10BlocksWith50TxChain(benchmark::Bench &bench)
Try to reorg a chain of depth 10 where each block has a 50 tx 1-input-1-output chain.
Definition: chained_tx.cpp:367
static void benchEviction(const Config &, benchmark::Bench &bench, const std::vector< std::vector< CTransactionRef >> &chains, bool revFee=true)
Definition: chained_tx.cpp:270
static void benchReorg(const Config &config, node::NodeContext &node, benchmark::Bench &bench, size_t reorgDepth, size_t chainSizePerBlock, bool includeMempoolTxRemoval)
Run benchmark that reorganizes blocks with one-input-one-output transaction chains in them.
Definition: chained_tx.cpp:157
static std::vector< CTransactionRef > oneInOneOutChain(const Config &config, CTxIn utxo, const size_t chainLength)
Creates a chain of transactions with 1-input-1-output.
Definition: chained_tx.cpp:64
static const CScript REDEEM_SCRIPT
This file contains benchmarks focusing on chained transactions in the mempool.
Definition: chained_tx.cpp:27
static void GenerateBlock500ChainedTxs(benchmark::Bench &bench)
Generate a block with 500 1-input-1-output transactions.
Definition: chained_tx.cpp:409
static const CScript SCRIPT_PUB_KEY
Definition: chained_tx.cpp:29
static void Reorg10BlocksWith50TxChainSkipMempool(benchmark::Bench &bench)
Try to reorg a chain of depth 10 where each block has a 50 tx 1-input-1-output chain,...
Definition: chained_tx.cpp:384
BENCHMARK(MempoolAcceptance50ChainedTxs)
static CTransactionRef toTx(const Config &config, CTxIn txin)
Create a transaction spending a coinbase utxo.
Definition: chained_tx.cpp:54
static const CScript SCRIPT_SIG
Definition: chained_tx.cpp:33
static void benchATMP(node::NodeContext &node, benchmark::Bench &bench, const std::vector< CTransactionRef > chainedTxs)
Run benchmark on AcceptToMemoryPool.
Definition: chained_tx.cpp:131
#define Assert(val)
Identity function.
Definition: check.h:84
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: blockindex.h:26
unsigned int nTx
Number of transactions in this block.
Definition: blockindex.h:61
CBlockIndex * Tip() const
Returns the index entry for the tip of this chain, or nullptr if none.
Definition: chain.h:156
A mutable version of CTransaction.
Definition: transaction.h:274
std::vector< CTxOut > vout
Definition: transaction.h:277
std::vector< CTxIn > vin
Definition: transaction.h:276
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:20
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:431
A reference to a CScript: the Hash160 of its serialization (see script.h)
Definition: standard.h:24
An input of a transaction.
Definition: transaction.h:59
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:209
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:296
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(CTxMemPoolEntryRef entry) EXCLUSIVE_LOCKS_REQUIRED(cs
If sanity-checking is turned on, check makes sure the pool is consistent (does not contain two transa...
Definition: txmempool.h:361
unsigned long size() const
Definition: txmempool.h:475
Chainstate stores and provides an API to update our local knowledge of the current best chain.
Definition: validation.h:648
CTxMemPool * GetMempool()
Definition: validation.h:796
CChain m_chain
The current chain of blockheaders we consult and build on.
Definition: validation.h:757
bool InvalidateBlock(BlockValidationState &state, CBlockIndex *pindex) EXCLUSIVE_LOCKS_REQUIRED(!m_chainstate_mutex
Mark a block as invalid.
bool ActivateBestChain(BlockValidationState &state, std::shared_ptr< const CBlock > pblock=nullptr) EXCLUSIVE_LOCKS_REQUIRED(!m_chainstate_mutex
Find the best known block, and make it the tip of the block chain.
void ResetBlockFailureFlags(CBlockIndex *pindex) EXCLUSIVE_LOCKS_REQUIRED(cs_main)
Remove invalidity status from a block and its descendants.
Definition: config.h:17
bool IsValid() const
Definition: validation.h:112
Main entry point to nanobench's benchmarking facility.
Definition: nanobench.h:616
Bench & run(char const *benchmarkName, Op &&op)
Repeatedly calls op() based on the configuration, and performs measurements.
Definition: nanobench.h:1183
Bench & epochIterations(uint64_t numIters) noexcept
Sets exactly the number of iterations for each epoch.
Bench & epochs(size_t numEpochs) noexcept
Controls number of epochs, the number of measurements to perform.
Generate a new block, without valid proof-of-work.
Definition: miner.h:49
const Config & GetConfig()
Definition: config.cpp:34
static const int COINBASE_MATURITY
Coinbase transaction outputs can only be spent after this number of new blocks (network rule).
Definition: consensus.h:32
RecursiveMutex cs_main
Mutex to guard access to validation specific variables, such as reading or changing the chainstate.
Definition: cs_main.cpp:7
Definition: init.h:28
static CTransactionRef MakeTransactionRef()
Definition: transaction.h:316
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:315
std::vector< uint8_t > ToByteVector(const T &in)
Definition: script.h:42
@ OP_EQUAL
Definition: script.h:119
@ OP_HASH160
Definition: script.h:160
@ OP_TRUE
Definition: script.h:57
@ OP_DROP
Definition: script.h:97
Definition: amount.h:19
Validation result for a single transaction mempool acceptance.
Definition: validation.h:205
const ResultType m_result_type
Definition: validation.h:215
@ VALID
Fully validated, valid.
Options struct containing options for constructing a CTxMemPool.
int check_ratio
The ratio used to determine how often sanity checks will run.
NodeContext struct containing references to chain state and connection state.
Definition: context.h:38
#define LOCK2(cs1, cs2)
Definition: sync.h:309
#define LOCK(cs)
Definition: sync.h:306
int64_t GetTime()
Definition: time.cpp:109
MempoolAcceptResult AcceptToMemoryPool(Chainstate &active_chainstate, const CTransactionRef &tx, int64_t accept_time, bool bypass_limits, bool test_accept, unsigned int heightOverride)
Try to add a transaction to the mempool.
assert(!tx.IsCoinBase())