Bitcoin Core  24.99.0
P2P Digital Currency
mempool_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2011-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 <policy/policy.h>
6 #include <txmempool.h>
7 #include <util/system.h>
8 #include <util/time.h>
9 
10 #include <test/util/setup_common.h>
11 
12 #include <boost/test/unit_test.hpp>
13 #include <vector>
14 
15 BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
16 
17 static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED;
18 
19 class MemPoolTest final : public CTxMemPool
20 {
21 public:
23 };
24 
25 BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
26 {
27  // Test CTxMemPool::remove functionality
28 
30  // Parent transaction with three children,
31  // and three grand-children:
32  CMutableTransaction txParent;
33  txParent.vin.resize(1);
34  txParent.vin[0].scriptSig = CScript() << OP_11;
35  txParent.vout.resize(3);
36  for (int i = 0; i < 3; i++)
37  {
38  txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
39  txParent.vout[i].nValue = 33000LL;
40  }
41  CMutableTransaction txChild[3];
42  for (int i = 0; i < 3; i++)
43  {
44  txChild[i].vin.resize(1);
45  txChild[i].vin[0].scriptSig = CScript() << OP_11;
46  txChild[i].vin[0].prevout.hash = txParent.GetHash();
47  txChild[i].vin[0].prevout.n = i;
48  txChild[i].vout.resize(1);
49  txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
50  txChild[i].vout[0].nValue = 11000LL;
51  }
52  CMutableTransaction txGrandChild[3];
53  for (int i = 0; i < 3; i++)
54  {
55  txGrandChild[i].vin.resize(1);
56  txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
57  txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
58  txGrandChild[i].vin[0].prevout.n = 0;
59  txGrandChild[i].vout.resize(1);
60  txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
61  txGrandChild[i].vout[0].nValue = 11000LL;
62  }
63 
64 
65  CTxMemPool& testPool = *Assert(m_node.mempool);
66  LOCK2(cs_main, testPool.cs);
67 
68  // Nothing in pool, remove should do nothing:
69  unsigned int poolSize = testPool.size();
71  BOOST_CHECK_EQUAL(testPool.size(), poolSize);
72 
73  // Just the parent:
74  testPool.addUnchecked(entry.FromTx(txParent));
75  poolSize = testPool.size();
77  BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
78 
79  // Parent, children, grandchildren:
80  testPool.addUnchecked(entry.FromTx(txParent));
81  for (int i = 0; i < 3; i++)
82  {
83  testPool.addUnchecked(entry.FromTx(txChild[i]));
84  testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
85  }
86  // Remove Child[0], GrandChild[0] should be removed:
87  poolSize = testPool.size();
88  testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
89  BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
90  // ... make sure grandchild and child are gone:
91  poolSize = testPool.size();
92  testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY);
93  BOOST_CHECK_EQUAL(testPool.size(), poolSize);
94  poolSize = testPool.size();
95  testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
96  BOOST_CHECK_EQUAL(testPool.size(), poolSize);
97  // Remove parent, all children/grandchildren should go:
98  poolSize = testPool.size();
100  BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
101  BOOST_CHECK_EQUAL(testPool.size(), 0U);
102 
103  // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
104  for (int i = 0; i < 3; i++)
105  {
106  testPool.addUnchecked(entry.FromTx(txChild[i]));
107  testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
108  }
109  // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
110  // put into the mempool (maybe because it is non-standard):
111  poolSize = testPool.size();
113  BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
114  BOOST_CHECK_EQUAL(testPool.size(), 0U);
115 }
116 
117 template <typename name>
118 static void CheckSort(CTxMemPool& pool, std::vector<std::string>& sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs)
119 {
120  BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
121  typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin();
122  int count = 0;
123  for (; it != pool.mapTx.get<name>().end(); ++it, ++count) {
124  BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
125  }
126 }
127 
128 BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
129 {
130  CTxMemPool& pool = *Assert(m_node.mempool);
131  LOCK2(cs_main, pool.cs);
133 
134  /* 3rd highest fee */
136  tx1.vout.resize(1);
137  tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
138  tx1.vout[0].nValue = 10 * COIN;
139  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
140 
141  /* highest fee */
143  tx2.vout.resize(1);
144  tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
145  tx2.vout[0].nValue = 2 * COIN;
146  pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
147 
148  /* lowest fee */
150  tx3.vout.resize(1);
151  tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
152  tx3.vout[0].nValue = 5 * COIN;
153  pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
154 
155  /* 2nd highest fee */
157  tx4.vout.resize(1);
158  tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
159  tx4.vout[0].nValue = 6 * COIN;
160  pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
161 
162  /* equal fee rate to tx1, but newer */
164  tx5.vout.resize(1);
165  tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
166  tx5.vout[0].nValue = 11 * COIN;
167  entry.nTime = 1;
168  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
169  BOOST_CHECK_EQUAL(pool.size(), 5U);
170 
171  std::vector<std::string> sortedOrder;
172  sortedOrder.resize(5);
173  sortedOrder[0] = tx3.GetHash().ToString(); // 0
174  sortedOrder[1] = tx5.GetHash().ToString(); // 10000
175  sortedOrder[2] = tx1.GetHash().ToString(); // 10000
176  sortedOrder[3] = tx4.GetHash().ToString(); // 15000
177  sortedOrder[4] = tx2.GetHash().ToString(); // 20000
178  CheckSort<descendant_score>(pool, sortedOrder);
179 
180  /* low fee but with high fee child */
181  /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
183  tx6.vout.resize(1);
184  tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
185  tx6.vout[0].nValue = 20 * COIN;
186  pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
187  BOOST_CHECK_EQUAL(pool.size(), 6U);
188  // Check that at this point, tx6 is sorted low
189  sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
190  CheckSort<descendant_score>(pool, sortedOrder);
191 
192  CTxMemPool::setEntries setAncestors;
193  setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
195  tx7.vin.resize(1);
196  tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
197  tx7.vin[0].scriptSig = CScript() << OP_11;
198  tx7.vout.resize(2);
199  tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
200  tx7.vout[0].nValue = 10 * COIN;
201  tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
202  tx7.vout[1].nValue = 1 * COIN;
203 
204  CTxMemPool::setEntries setAncestorsCalculated;
205  std::string dummy;
206  BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
207  BOOST_CHECK(setAncestorsCalculated == setAncestors);
208 
209  pool.addUnchecked(entry.FromTx(tx7), setAncestors);
210  BOOST_CHECK_EQUAL(pool.size(), 7U);
211 
212  // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
213  sortedOrder.erase(sortedOrder.begin());
214  sortedOrder.push_back(tx6.GetHash().ToString());
215  sortedOrder.push_back(tx7.GetHash().ToString());
216  CheckSort<descendant_score>(pool, sortedOrder);
217 
218  /* low fee child of tx7 */
220  tx8.vin.resize(1);
221  tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
222  tx8.vin[0].scriptSig = CScript() << OP_11;
223  tx8.vout.resize(1);
224  tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
225  tx8.vout[0].nValue = 10 * COIN;
226  setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
227  pool.addUnchecked(entry.Fee(0LL).Time(2).FromTx(tx8), setAncestors);
228 
229  // Now tx8 should be sorted low, but tx6/tx both high
230  sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
231  CheckSort<descendant_score>(pool, sortedOrder);
232 
233  /* low fee child of tx7 */
235  tx9.vin.resize(1);
236  tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
237  tx9.vin[0].scriptSig = CScript() << OP_11;
238  tx9.vout.resize(1);
239  tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
240  tx9.vout[0].nValue = 1 * COIN;
241  pool.addUnchecked(entry.Fee(0LL).Time(3).FromTx(tx9), setAncestors);
242 
243  // tx9 should be sorted low
244  BOOST_CHECK_EQUAL(pool.size(), 9U);
245  sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
246  CheckSort<descendant_score>(pool, sortedOrder);
247 
248  std::vector<std::string> snapshotOrder = sortedOrder;
249 
250  setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
251  setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
252  /* tx10 depends on tx8 and tx9 and has a high fee*/
254  tx10.vin.resize(2);
255  tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
256  tx10.vin[0].scriptSig = CScript() << OP_11;
257  tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
258  tx10.vin[1].scriptSig = CScript() << OP_11;
259  tx10.vout.resize(1);
260  tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
261  tx10.vout[0].nValue = 10 * COIN;
262 
263  setAncestorsCalculated.clear();
264  BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(4).FromTx(tx10), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
265  BOOST_CHECK(setAncestorsCalculated == setAncestors);
266 
267  pool.addUnchecked(entry.FromTx(tx10), setAncestors);
268 
284  sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
285  sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
286  sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
287  sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
288  CheckSort<descendant_score>(pool, sortedOrder);
289 
290  // there should be 10 transactions in the mempool
291  BOOST_CHECK_EQUAL(pool.size(), 10U);
292 
293  // Now try removing tx10 and verify the sort order returns to normal
294  pool.removeRecursive(pool.mapTx.find(tx10.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
295  CheckSort<descendant_score>(pool, snapshotOrder);
296 
297  pool.removeRecursive(pool.mapTx.find(tx9.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
298  pool.removeRecursive(pool.mapTx.find(tx8.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
299 }
300 
301 BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)
302 {
303  CTxMemPool& pool = *Assert(m_node.mempool);
304  LOCK2(cs_main, pool.cs);
306 
307  /* 3rd highest fee */
309  tx1.vout.resize(1);
310  tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
311  tx1.vout[0].nValue = 10 * COIN;
312  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
313 
314  /* highest fee */
316  tx2.vout.resize(1);
317  tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
318  tx2.vout[0].nValue = 2 * COIN;
319  pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
320  uint64_t tx2Size = GetVirtualTransactionSize(CTransaction(tx2));
321 
322  /* lowest fee */
324  tx3.vout.resize(1);
325  tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
326  tx3.vout[0].nValue = 5 * COIN;
327  pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
328 
329  /* 2nd highest fee */
331  tx4.vout.resize(1);
332  tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
333  tx4.vout[0].nValue = 6 * COIN;
334  pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
335 
336  /* equal fee rate to tx1, but newer */
338  tx5.vout.resize(1);
339  tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
340  tx5.vout[0].nValue = 11 * COIN;
341  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
342  BOOST_CHECK_EQUAL(pool.size(), 5U);
343 
344  std::vector<std::string> sortedOrder;
345  sortedOrder.resize(5);
346  sortedOrder[0] = tx2.GetHash().ToString(); // 20000
347  sortedOrder[1] = tx4.GetHash().ToString(); // 15000
348  // tx1 and tx5 are both 10000
349  // Ties are broken by hash, not timestamp, so determine which
350  // hash comes first.
351  if (tx1.GetHash() < tx5.GetHash()) {
352  sortedOrder[2] = tx1.GetHash().ToString();
353  sortedOrder[3] = tx5.GetHash().ToString();
354  } else {
355  sortedOrder[2] = tx5.GetHash().ToString();
356  sortedOrder[3] = tx1.GetHash().ToString();
357  }
358  sortedOrder[4] = tx3.GetHash().ToString(); // 0
359 
360  CheckSort<ancestor_score>(pool, sortedOrder);
361 
362  /* low fee parent with high fee child */
363  /* tx6 (0) -> tx7 (high) */
365  tx6.vout.resize(1);
366  tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
367  tx6.vout[0].nValue = 20 * COIN;
368  uint64_t tx6Size = GetVirtualTransactionSize(CTransaction(tx6));
369 
370  pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
371  BOOST_CHECK_EQUAL(pool.size(), 6U);
372  // Ties are broken by hash
373  if (tx3.GetHash() < tx6.GetHash())
374  sortedOrder.push_back(tx6.GetHash().ToString());
375  else
376  sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString());
377 
378  CheckSort<ancestor_score>(pool, sortedOrder);
379 
381  tx7.vin.resize(1);
382  tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
383  tx7.vin[0].scriptSig = CScript() << OP_11;
384  tx7.vout.resize(1);
385  tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
386  tx7.vout[0].nValue = 10 * COIN;
387  uint64_t tx7Size = GetVirtualTransactionSize(CTransaction(tx7));
388 
389  /* set the fee to just below tx2's feerate when including ancestor */
390  CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1;
391 
392  pool.addUnchecked(entry.Fee(fee).FromTx(tx7));
393  BOOST_CHECK_EQUAL(pool.size(), 7U);
394  sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString());
395  CheckSort<ancestor_score>(pool, sortedOrder);
396 
397  /* after tx6 is mined, tx7 should move up in the sort */
398  std::vector<CTransactionRef> vtx;
399  vtx.push_back(MakeTransactionRef(tx6));
400  pool.removeForBlock(vtx, 1);
401 
402  sortedOrder.erase(sortedOrder.begin()+1);
403  // Ties are broken by hash
404  if (tx3.GetHash() < tx6.GetHash())
405  sortedOrder.pop_back();
406  else
407  sortedOrder.erase(sortedOrder.end()-2);
408  sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
409  CheckSort<ancestor_score>(pool, sortedOrder);
410 
411  // High-fee parent, low-fee child
412  // tx7 -> tx8
414  tx8.vin.resize(1);
415  tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
416  tx8.vin[0].scriptSig = CScript() << OP_11;
417  tx8.vout.resize(1);
418  tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
419  tx8.vout[0].nValue = 10*COIN;
420 
421  // Check that we sort by min(feerate, ancestor_feerate):
422  // set the fee so that the ancestor feerate is above tx1/5,
423  // but the transaction's own feerate is lower
424  pool.addUnchecked(entry.Fee(5000LL).FromTx(tx8));
425  sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString());
426  CheckSort<ancestor_score>(pool, sortedOrder);
427 }
428 
429 
430 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
431 {
432  auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
433  LOCK2(cs_main, pool.cs);
435 
437  tx1.vin.resize(1);
438  tx1.vin[0].scriptSig = CScript() << OP_1;
439  tx1.vout.resize(1);
440  tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
441  tx1.vout[0].nValue = 10 * COIN;
442  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
443 
445  tx2.vin.resize(1);
446  tx2.vin[0].scriptSig = CScript() << OP_2;
447  tx2.vout.resize(1);
448  tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
449  tx2.vout[0].nValue = 10 * COIN;
450  pool.addUnchecked(entry.Fee(5000LL).FromTx(tx2));
451 
452  pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
453  BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
454  BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
455 
456  pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
457  BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
458  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
459 
460  pool.addUnchecked(entry.FromTx(tx2));
462  tx3.vin.resize(1);
463  tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
464  tx3.vin[0].scriptSig = CScript() << OP_2;
465  tx3.vout.resize(1);
466  tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
467  tx3.vout[0].nValue = 10 * COIN;
468  pool.addUnchecked(entry.Fee(20000LL).FromTx(tx3));
469 
470  pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
471  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
472  BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
473  BOOST_CHECK(pool.exists(GenTxid::Txid(tx3.GetHash())));
474 
475  pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
476  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
477  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
478  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx3.GetHash())));
479 
481  BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
482 
484  tx4.vin.resize(2);
485  tx4.vin[0].prevout.SetNull();
486  tx4.vin[0].scriptSig = CScript() << OP_4;
487  tx4.vin[1].prevout.SetNull();
488  tx4.vin[1].scriptSig = CScript() << OP_4;
489  tx4.vout.resize(2);
490  tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
491  tx4.vout[0].nValue = 10 * COIN;
492  tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
493  tx4.vout[1].nValue = 10 * COIN;
494 
496  tx5.vin.resize(2);
497  tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
498  tx5.vin[0].scriptSig = CScript() << OP_4;
499  tx5.vin[1].prevout.SetNull();
500  tx5.vin[1].scriptSig = CScript() << OP_5;
501  tx5.vout.resize(2);
502  tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
503  tx5.vout[0].nValue = 10 * COIN;
504  tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
505  tx5.vout[1].nValue = 10 * COIN;
506 
508  tx6.vin.resize(2);
509  tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
510  tx6.vin[0].scriptSig = CScript() << OP_4;
511  tx6.vin[1].prevout.SetNull();
512  tx6.vin[1].scriptSig = CScript() << OP_6;
513  tx6.vout.resize(2);
514  tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
515  tx6.vout[0].nValue = 10 * COIN;
516  tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
517  tx6.vout[1].nValue = 10 * COIN;
518 
520  tx7.vin.resize(2);
521  tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
522  tx7.vin[0].scriptSig = CScript() << OP_5;
523  tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
524  tx7.vin[1].scriptSig = CScript() << OP_6;
525  tx7.vout.resize(2);
526  tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
527  tx7.vout[0].nValue = 10 * COIN;
528  tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
529  tx7.vout[1].nValue = 10 * COIN;
530 
531  pool.addUnchecked(entry.Fee(7000LL).FromTx(tx4));
532  pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
533  pool.addUnchecked(entry.Fee(1100LL).FromTx(tx6));
534  pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
535 
536  // we only require this to remove, at max, 2 txn, because it's not clear what we're really optimizing for aside from that
537  pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
538  BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
539  BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
540  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
541 
542  if (!pool.exists(GenTxid::Txid(tx5.GetHash())))
543  pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
544  pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
545 
546  pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
547  BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
548  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx5.GetHash())));
549  BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
550  BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
551 
552  pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
553  pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
554 
555  std::vector<CTransactionRef> vtx;
556  SetMockTime(42);
558  BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
559  // ... we should keep the same min fee until we get a block
560  pool.removeForBlock(vtx, 1);
562  BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/2.0));
563  // ... then feerate should drop 1/2 each halflife
564 
566  BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/4.0));
567  // ... with a 1/2 halflife when mempool is < 1/2 its target size
568 
570  BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/8.0));
571  // ... with a 1/4 halflife when mempool is < 1/4 its target size
572 
574  BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
575  // ... but feerate should never drop below 1000
576 
578  BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
579  // ... unless it has gone all the way to 0 (after getting past 1000/2)
580 }
581 
582 inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>())
583 {
585  tx.vin.resize(inputs.size());
586  tx.vout.resize(output_values.size());
587  for (size_t i = 0; i < inputs.size(); ++i) {
588  tx.vin[i].prevout.hash = inputs[i]->GetHash();
589  tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
590  }
591  for (size_t i = 0; i < output_values.size(); ++i) {
592  tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
593  tx.vout[i].nValue = output_values[i];
594  }
595  return MakeTransactionRef(tx);
596 }
597 
598 
599 BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
600 {
601  size_t ancestors, descendants;
602 
603  CTxMemPool& pool = *Assert(m_node.mempool);
604  LOCK2(cs_main, pool.cs);
606 
607  /* Base transaction */
608  //
609  // [tx1]
610  //
611  CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN});
612  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
613 
614  // Ancestors / descendants should be 1 / 1 (itself / itself)
615  pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
616  BOOST_CHECK_EQUAL(ancestors, 1ULL);
617  BOOST_CHECK_EQUAL(descendants, 1ULL);
618 
619  /* Child transaction */
620  //
621  // [tx1].0 <- [tx2]
622  //
623  CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1});
624  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx2));
625 
626  // Ancestors / descendants should be:
627  // transaction ancestors descendants
628  // ============ =========== ===========
629  // tx1 1 (tx1) 2 (tx1,2)
630  // tx2 2 (tx1,2) 2 (tx1,2)
631  pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
632  BOOST_CHECK_EQUAL(ancestors, 1ULL);
633  BOOST_CHECK_EQUAL(descendants, 2ULL);
634  pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
635  BOOST_CHECK_EQUAL(ancestors, 2ULL);
636  BOOST_CHECK_EQUAL(descendants, 2ULL);
637 
638  /* Grand-child 1 */
639  //
640  // [tx1].0 <- [tx2].0 <- [tx3]
641  //
642  CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2});
643  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx3));
644 
645  // Ancestors / descendants should be:
646  // transaction ancestors descendants
647  // ============ =========== ===========
648  // tx1 1 (tx1) 3 (tx1,2,3)
649  // tx2 2 (tx1,2) 3 (tx1,2,3)
650  // tx3 3 (tx1,2,3) 3 (tx1,2,3)
651  pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
652  BOOST_CHECK_EQUAL(ancestors, 1ULL);
653  BOOST_CHECK_EQUAL(descendants, 3ULL);
654  pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
655  BOOST_CHECK_EQUAL(ancestors, 2ULL);
656  BOOST_CHECK_EQUAL(descendants, 3ULL);
657  pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
658  BOOST_CHECK_EQUAL(ancestors, 3ULL);
659  BOOST_CHECK_EQUAL(descendants, 3ULL);
660 
661  /* Grand-child 2 */
662  //
663  // [tx1].0 <- [tx2].0 <- [tx3]
664  // |
665  // \---1 <- [tx4]
666  //
667  CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1});
668  pool.addUnchecked(entry.Fee(10000LL).FromTx(tx4));
669 
670  // Ancestors / descendants should be:
671  // transaction ancestors descendants
672  // ============ =========== ===========
673  // tx1 1 (tx1) 4 (tx1,2,3,4)
674  // tx2 2 (tx1,2) 4 (tx1,2,3,4)
675  // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
676  // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
677  pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
678  BOOST_CHECK_EQUAL(ancestors, 1ULL);
679  BOOST_CHECK_EQUAL(descendants, 4ULL);
680  pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
681  BOOST_CHECK_EQUAL(ancestors, 2ULL);
682  BOOST_CHECK_EQUAL(descendants, 4ULL);
683  pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
684  BOOST_CHECK_EQUAL(ancestors, 3ULL);
685  BOOST_CHECK_EQUAL(descendants, 4ULL);
686  pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
687  BOOST_CHECK_EQUAL(ancestors, 3ULL);
688  BOOST_CHECK_EQUAL(descendants, 4ULL);
689 
690  /* Make an alternate branch that is longer and connect it to tx3 */
691  //
692  // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
693  // |
694  // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
695  // |
696  // \---1 <- [tx4]
697  //
698  CTransactionRef ty1, ty2, ty3, ty4, ty5;
699  CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
700  CAmount v = 5 * COIN;
701  for (uint64_t i = 0; i < 5; i++) {
702  CTransactionRef& tyi = *ty[i];
703  tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{});
704  v -= 50 * CENT;
705  pool.addUnchecked(entry.Fee(10000LL).FromTx(tyi));
706  pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants);
707  BOOST_CHECK_EQUAL(ancestors, i+1);
708  BOOST_CHECK_EQUAL(descendants, i+1);
709  }
710  CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5});
711  pool.addUnchecked(entry.Fee(10000LL).FromTx(ty6));
712 
713  // Ancestors / descendants should be:
714  // transaction ancestors descendants
715  // ============ =================== ===========
716  // tx1 1 (tx1) 5 (tx1,2,3,4, ty6)
717  // tx2 2 (tx1,2) 5 (tx1,2,3,4, ty6)
718  // tx3 3 (tx1,2,3) 5 (tx1,2,3,4, ty6)
719  // tx4 3 (tx1,2,4) 5 (tx1,2,3,4, ty6)
720  // ty1 1 (ty1) 6 (ty1,2,3,4,5,6)
721  // ty2 2 (ty1,2) 6 (ty1,2,3,4,5,6)
722  // ty3 3 (ty1,2,3) 6 (ty1,2,3,4,5,6)
723  // ty4 4 (y1234) 6 (ty1,2,3,4,5,6)
724  // ty5 5 (y12345) 6 (ty1,2,3,4,5,6)
725  // ty6 9 (tx123, ty123456) 6 (ty1,2,3,4,5,6)
726  pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
727  BOOST_CHECK_EQUAL(ancestors, 1ULL);
728  BOOST_CHECK_EQUAL(descendants, 5ULL);
729  pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
730  BOOST_CHECK_EQUAL(ancestors, 2ULL);
731  BOOST_CHECK_EQUAL(descendants, 5ULL);
732  pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
733  BOOST_CHECK_EQUAL(ancestors, 3ULL);
734  BOOST_CHECK_EQUAL(descendants, 5ULL);
735  pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
736  BOOST_CHECK_EQUAL(ancestors, 3ULL);
737  BOOST_CHECK_EQUAL(descendants, 5ULL);
738  pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants);
739  BOOST_CHECK_EQUAL(ancestors, 1ULL);
740  BOOST_CHECK_EQUAL(descendants, 6ULL);
741  pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants);
742  BOOST_CHECK_EQUAL(ancestors, 2ULL);
743  BOOST_CHECK_EQUAL(descendants, 6ULL);
744  pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants);
745  BOOST_CHECK_EQUAL(ancestors, 3ULL);
746  BOOST_CHECK_EQUAL(descendants, 6ULL);
747  pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants);
748  BOOST_CHECK_EQUAL(ancestors, 4ULL);
749  BOOST_CHECK_EQUAL(descendants, 6ULL);
750  pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants);
751  BOOST_CHECK_EQUAL(ancestors, 5ULL);
752  BOOST_CHECK_EQUAL(descendants, 6ULL);
753  pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants);
754  BOOST_CHECK_EQUAL(ancestors, 9ULL);
755  BOOST_CHECK_EQUAL(descendants, 6ULL);
756 }
757 
758 BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
759 {
760  size_t ancestors, descendants;
761 
762  CTxMemPool& pool = *Assert(m_node.mempool);
763  LOCK2(::cs_main, pool.cs);
765 
766  /* Ancestors represented more than once ("diamond") */
767  //
768  // [ta].0 <- [tb].0 -----<------- [td].0
769  // | |
770  // \---1 <- [tc].0 --<--/
771  //
772  CTransactionRef ta, tb, tc, td;
773  ta = make_tx(/*output_values=*/{10 * COIN});
774  tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta});
775  tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1});
776  td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0});
777  pool.addUnchecked(entry.Fee(10000LL).FromTx(ta));
778  pool.addUnchecked(entry.Fee(10000LL).FromTx(tb));
779  pool.addUnchecked(entry.Fee(10000LL).FromTx(tc));
780  pool.addUnchecked(entry.Fee(10000LL).FromTx(td));
781 
782  // Ancestors / descendants should be:
783  // transaction ancestors descendants
784  // ============ =================== ===========
785  // ta 1 (ta 4 (ta,tb,tc,td)
786  // tb 2 (ta,tb) 4 (ta,tb,tc,td)
787  // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td)
788  // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td)
789  pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants);
790  BOOST_CHECK_EQUAL(ancestors, 1ULL);
791  BOOST_CHECK_EQUAL(descendants, 4ULL);
792  pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants);
793  BOOST_CHECK_EQUAL(ancestors, 2ULL);
794  BOOST_CHECK_EQUAL(descendants, 4ULL);
795  pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants);
796  BOOST_CHECK_EQUAL(ancestors, 3ULL);
797  BOOST_CHECK_EQUAL(descendants, 4ULL);
798  pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants);
799  BOOST_CHECK_EQUAL(ancestors, 4ULL);
800  BOOST_CHECK_EQUAL(descendants, 4ULL);
801 }
802 
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
node::NodeContext m_node
Definition: bitcoin-gui.cpp:37
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
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
CAmount GetFeePerK() const
Return the fee in satoshis for a vsize of 1000 vbytes.
Definition: feerate.h:65
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
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:288
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:432
CFeeRate GetMinFee() const
The minimum fee to get into the mempool, which may itself not be enough for larger-sized transactions...
Definition: txmempool.h:716
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:521
void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: txmempool.cpp:579
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate=true) 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:605
void GetTransactionAncestry(const uint256 &txid, size_t &ancestors, size_t &descendants, size_t *ancestorsize=nullptr, CAmount *ancestorfees=nullptr) const
Calculate the ancestor and descendant count for the given transaction.
Definition: txmempool.cpp:1177
bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents=true) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Try to calculate all in-mempool ancestors of entry.
Definition: txmempool.cpp:270
static const int ROLLING_FEE_HALFLIFE
Definition: txmempool.h:460
std::set< txiter, CompareIteratorByHash > setEntries
Definition: txmempool.h:527
void removeForBlock(const std::vector< CTransactionRef > &vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs)
Called when a block is connected.
Definition: txmempool.cpp:649
unsigned long size() const
Definition: txmempool.h:749
static GenTxid Txid(const uint256 &hash)
Definition: transaction.h:425
std::string ToString() const
Definition: uint256.cpp:64
BOOST_AUTO_TEST_SUITE_END()
CTransactionRef make_tx(std::vector< CAmount > &&output_values, std::vector< CTransactionRef > &&inputs=std::vector< CTransactionRef >(), std::vector< uint32_t > &&input_indices=std::vector< uint32_t >())
static void CheckSort(CTxMemPool &pool, std::vector< std::string > &sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs)
static constexpr auto REMOVAL_REASON_DUMMY
BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:17
#define BOOST_CHECK(expr)
Definition: object.cpp:16
int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop)
Compute the virtual transaction size (weight reinterpreted as bytes).
Definition: policy.cpp:295
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:415
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:414
const char * name
Definition: rest.cpp:46
@ OP_2
Definition: script.h:81
@ OP_EQUAL
Definition: script.h:142
@ OP_4
Definition: script.h:83
@ OP_1
Definition: script.h:79
@ OP_3
Definition: script.h:82
@ OP_11
Definition: script.h:90
@ OP_6
Definition: script.h:85
@ OP_7
Definition: script.h:86
@ OP_5
Definition: script.h:84
static constexpr CAmount CENT
Definition: setup_common.h:78
A mutable version of CTransaction.
Definition: transaction.h:373
uint256 GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:68
std::vector< CTxOut > vout
Definition: transaction.h:375
std::vector< CTxIn > vin
Definition: transaction.h:374
Definition: setup_common.h:207
int64_t nTime
Definition: setup_common.h:210
CTxMemPoolEntry FromTx(const CMutableTransaction &tx) const
TestMemPoolEntryHelper & Time(int64_t _time)
Definition: setup_common.h:225
TestMemPoolEntryHelper & Fee(CAmount _fee)
Definition: setup_common.h:224
Testing setup that configures a complete environment.
Definition: setup_common.h:109
std::unique_ptr< CTxMemPool > mempool
Definition: context.h:50
#define LOCK2(cs1, cs2)
Definition: sync.h:262
static int count
Definition: tests.c:33
#define EXCLUSIVE_LOCKS_REQUIRED(...)
Definition: threadsafety.h:49
void SetMockTime(int64_t nMockTimeIn)
DEPRECATED Use SetMockTime with chrono type.
Definition: time.cpp:91
MemPoolRemovalReason
Reason why a transaction was removed from the mempool, this is passed to the notification signal.
Definition: txmempool.h:349