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