1 // Copyright (c) 2011-2018 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
9 #include <test/test_bitcoin.h>
10
11 #include <boost/test/unit_test.hpp>
12 #include <list>
13 #include <vector>
14
BOOST_FIXTURE_TEST_SUITE(mempool_tests,TestingSetup)15 BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
16
17 BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
18 {
19 // Test CTxMemPool::remove functionality
20
21 TestMemPoolEntryHelper entry;
22 // Parent transaction with three children,
23 // and three grand-children:
24 CMutableTransaction txParent;
25 txParent.vin.resize(1);
26 txParent.vin[0].scriptSig = CScript() << OP_11;
27 txParent.vout.resize(3);
28 for (int i = 0; i < 3; i++)
29 {
30 txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
31 txParent.vout[i].nValue = 33000LL;
32 }
33 CMutableTransaction txChild[3];
34 for (int i = 0; i < 3; i++)
35 {
36 txChild[i].vin.resize(1);
37 txChild[i].vin[0].scriptSig = CScript() << OP_11;
38 txChild[i].vin[0].prevout.hash = txParent.GetHash();
39 txChild[i].vin[0].prevout.n = i;
40 txChild[i].vout.resize(1);
41 txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
42 txChild[i].vout[0].nValue = 11000LL;
43 }
44 CMutableTransaction txGrandChild[3];
45 for (int i = 0; i < 3; i++)
46 {
47 txGrandChild[i].vin.resize(1);
48 txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
49 txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
50 txGrandChild[i].vin[0].prevout.n = 0;
51 txGrandChild[i].vout.resize(1);
52 txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
53 txGrandChild[i].vout[0].nValue = 11000LL;
54 }
55
56
57 CTxMemPool testPool;
58 LOCK2(cs_main, testPool.cs);
59
60 // Nothing in pool, remove should do nothing:
61 unsigned int poolSize = testPool.size();
62 testPool.removeRecursive(CTransaction(txParent));
63 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
64
65 // Just the parent:
66 testPool.addUnchecked(entry.FromTx(txParent));
67 poolSize = testPool.size();
68 testPool.removeRecursive(CTransaction(txParent));
69 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
70
71 // Parent, children, grandchildren:
72 testPool.addUnchecked(entry.FromTx(txParent));
73 for (int i = 0; i < 3; i++)
74 {
75 testPool.addUnchecked(entry.FromTx(txChild[i]));
76 testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
77 }
78 // Remove Child[0], GrandChild[0] should be removed:
79 poolSize = testPool.size();
80 testPool.removeRecursive(CTransaction(txChild[0]));
81 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
82 // ... make sure grandchild and child are gone:
83 poolSize = testPool.size();
84 testPool.removeRecursive(CTransaction(txGrandChild[0]));
85 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
86 poolSize = testPool.size();
87 testPool.removeRecursive(CTransaction(txChild[0]));
88 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
89 // Remove parent, all children/grandchildren should go:
90 poolSize = testPool.size();
91 testPool.removeRecursive(CTransaction(txParent));
92 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
93 BOOST_CHECK_EQUAL(testPool.size(), 0U);
94
95 // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
96 for (int i = 0; i < 3; i++)
97 {
98 testPool.addUnchecked(entry.FromTx(txChild[i]));
99 testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
100 }
101 // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
102 // put into the mempool (maybe because it is non-standard):
103 poolSize = testPool.size();
104 testPool.removeRecursive(CTransaction(txParent));
105 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
106 BOOST_CHECK_EQUAL(testPool.size(), 0U);
107 }
108
109 template<typename name>
CheckSort(CTxMemPool & pool,std::vector<std::string> & sortedOrder)110 static void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs)
111 {
112 BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
113 typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin();
114 int count=0;
115 for (; it != pool.mapTx.get<name>().end(); ++it, ++count) {
116 BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
117 }
118 }
119
BOOST_AUTO_TEST_CASE(MempoolIndexingTest)120 BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
121 {
122 CTxMemPool pool;
123 LOCK2(cs_main, pool.cs);
124 TestMemPoolEntryHelper entry;
125
126 /* 3rd highest fee */
127 CMutableTransaction tx1 = CMutableTransaction();
128 tx1.vout.resize(1);
129 tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
130 tx1.vout[0].nValue = 10 * COIN;
131 pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
132
133 /* highest fee */
134 CMutableTransaction tx2 = CMutableTransaction();
135 tx2.vout.resize(1);
136 tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
137 tx2.vout[0].nValue = 2 * COIN;
138 pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
139
140 /* lowest fee */
141 CMutableTransaction tx3 = CMutableTransaction();
142 tx3.vout.resize(1);
143 tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
144 tx3.vout[0].nValue = 5 * COIN;
145 pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
146
147 /* 2nd highest fee */
148 CMutableTransaction tx4 = CMutableTransaction();
149 tx4.vout.resize(1);
150 tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
151 tx4.vout[0].nValue = 6 * COIN;
152 pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
153
154 /* equal fee rate to tx1, but newer */
155 CMutableTransaction tx5 = CMutableTransaction();
156 tx5.vout.resize(1);
157 tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
158 tx5.vout[0].nValue = 11 * COIN;
159 entry.nTime = 1;
160 pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
161 BOOST_CHECK_EQUAL(pool.size(), 5U);
162
163 std::vector<std::string> sortedOrder;
164 sortedOrder.resize(5);
165 sortedOrder[0] = tx3.GetHash().ToString(); // 0
166 sortedOrder[1] = tx5.GetHash().ToString(); // 10000
167 sortedOrder[2] = tx1.GetHash().ToString(); // 10000
168 sortedOrder[3] = tx4.GetHash().ToString(); // 15000
169 sortedOrder[4] = tx2.GetHash().ToString(); // 20000
170 CheckSort<descendant_score>(pool, sortedOrder);
171
172 /* low fee but with high fee child */
173 /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
174 CMutableTransaction tx6 = CMutableTransaction();
175 tx6.vout.resize(1);
176 tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
177 tx6.vout[0].nValue = 20 * COIN;
178 pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
179 BOOST_CHECK_EQUAL(pool.size(), 6U);
180 // Check that at this point, tx6 is sorted low
181 sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
182 CheckSort<descendant_score>(pool, sortedOrder);
183
184 CTxMemPool::setEntries setAncestors;
185 setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
186 CMutableTransaction tx7 = CMutableTransaction();
187 tx7.vin.resize(1);
188 tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
189 tx7.vin[0].scriptSig = CScript() << OP_11;
190 tx7.vout.resize(2);
191 tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
192 tx7.vout[0].nValue = 10 * COIN;
193 tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
194 tx7.vout[1].nValue = 1 * COIN;
195
196 CTxMemPool::setEntries setAncestorsCalculated;
197 std::string dummy;
198 BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
199 BOOST_CHECK(setAncestorsCalculated == setAncestors);
200
201 pool.addUnchecked(entry.FromTx(tx7), setAncestors);
202 BOOST_CHECK_EQUAL(pool.size(), 7U);
203
204 // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
205 sortedOrder.erase(sortedOrder.begin());
206 sortedOrder.push_back(tx6.GetHash().ToString());
207 sortedOrder.push_back(tx7.GetHash().ToString());
208 CheckSort<descendant_score>(pool, sortedOrder);
209
210 /* low fee child of tx7 */
211 CMutableTransaction tx8 = CMutableTransaction();
212 tx8.vin.resize(1);
213 tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
214 tx8.vin[0].scriptSig = CScript() << OP_11;
215 tx8.vout.resize(1);
216 tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
217 tx8.vout[0].nValue = 10 * COIN;
218 setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
219 pool.addUnchecked(entry.Fee(0LL).Time(2).FromTx(tx8), setAncestors);
220
221 // Now tx8 should be sorted low, but tx6/tx both high
222 sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
223 CheckSort<descendant_score>(pool, sortedOrder);
224
225 /* low fee child of tx7 */
226 CMutableTransaction tx9 = CMutableTransaction();
227 tx9.vin.resize(1);
228 tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
229 tx9.vin[0].scriptSig = CScript() << OP_11;
230 tx9.vout.resize(1);
231 tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
232 tx9.vout[0].nValue = 1 * COIN;
233 pool.addUnchecked(entry.Fee(0LL).Time(3).FromTx(tx9), setAncestors);
234
235 // tx9 should be sorted low
236 BOOST_CHECK_EQUAL(pool.size(), 9U);
237 sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
238 CheckSort<descendant_score>(pool, sortedOrder);
239
240 std::vector<std::string> snapshotOrder = sortedOrder;
241
242 setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
243 setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
244 /* tx10 depends on tx8 and tx9 and has a high fee*/
245 CMutableTransaction tx10 = CMutableTransaction();
246 tx10.vin.resize(2);
247 tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
248 tx10.vin[0].scriptSig = CScript() << OP_11;
249 tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
250 tx10.vin[1].scriptSig = CScript() << OP_11;
251 tx10.vout.resize(1);
252 tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
253 tx10.vout[0].nValue = 10 * COIN;
254
255 setAncestorsCalculated.clear();
256 BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(4).FromTx(tx10), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
257 BOOST_CHECK(setAncestorsCalculated == setAncestors);
258
259 pool.addUnchecked(entry.FromTx(tx10), setAncestors);
260
261 /**
262 * tx8 and tx9 should both now be sorted higher
263 * Final order after tx10 is added:
264 *
265 * tx3 = 0 (1)
266 * tx5 = 10000 (1)
267 * tx1 = 10000 (1)
268 * tx4 = 15000 (1)
269 * tx2 = 20000 (1)
270 * tx9 = 200k (2 txs)
271 * tx8 = 200k (2 txs)
272 * tx10 = 200k (1 tx)
273 * tx6 = 2.2M (5 txs)
274 * tx7 = 2.2M (4 txs)
275 */
276 sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
277 sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
278 sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
279 sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
280 CheckSort<descendant_score>(pool, sortedOrder);
281
282 // there should be 10 transactions in the mempool
283 BOOST_CHECK_EQUAL(pool.size(), 10U);
284
285 // Now try removing tx10 and verify the sort order returns to normal
286 pool.removeRecursive(pool.mapTx.find(tx10.GetHash())->GetTx());
287 CheckSort<descendant_score>(pool, snapshotOrder);
288
289 pool.removeRecursive(pool.mapTx.find(tx9.GetHash())->GetTx());
290 pool.removeRecursive(pool.mapTx.find(tx8.GetHash())->GetTx());
291 }
292
BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)293 BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)
294 {
295 CTxMemPool pool;
296 LOCK2(cs_main, pool.cs);
297 TestMemPoolEntryHelper entry;
298
299 /* 3rd highest fee */
300 CMutableTransaction tx1 = CMutableTransaction();
301 tx1.vout.resize(1);
302 tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
303 tx1.vout[0].nValue = 10 * COIN;
304 pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
305
306 /* highest fee */
307 CMutableTransaction tx2 = CMutableTransaction();
308 tx2.vout.resize(1);
309 tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
310 tx2.vout[0].nValue = 2 * COIN;
311 pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
312 uint64_t tx2Size = GetVirtualTransactionSize(CTransaction(tx2));
313
314 /* lowest fee */
315 CMutableTransaction tx3 = CMutableTransaction();
316 tx3.vout.resize(1);
317 tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
318 tx3.vout[0].nValue = 5 * COIN;
319 pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
320
321 /* 2nd highest fee */
322 CMutableTransaction tx4 = CMutableTransaction();
323 tx4.vout.resize(1);
324 tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
325 tx4.vout[0].nValue = 6 * COIN;
326 pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
327
328 /* equal fee rate to tx1, but newer */
329 CMutableTransaction tx5 = CMutableTransaction();
330 tx5.vout.resize(1);
331 tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
332 tx5.vout[0].nValue = 11 * COIN;
333 pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
334 BOOST_CHECK_EQUAL(pool.size(), 5U);
335
336 std::vector<std::string> sortedOrder;
337 sortedOrder.resize(5);
338 sortedOrder[0] = tx2.GetHash().ToString(); // 20000
339 sortedOrder[1] = tx4.GetHash().ToString(); // 15000
340 // tx1 and tx5 are both 10000
341 // Ties are broken by hash, not timestamp, so determine which
342 // hash comes first.
343 if (tx1.GetHash() < tx5.GetHash()) {
344 sortedOrder[2] = tx1.GetHash().ToString();
345 sortedOrder[3] = tx5.GetHash().ToString();
346 } else {
347 sortedOrder[2] = tx5.GetHash().ToString();
348 sortedOrder[3] = tx1.GetHash().ToString();
349 }
350 sortedOrder[4] = tx3.GetHash().ToString(); // 0
351
352 CheckSort<ancestor_score>(pool, sortedOrder);
353
354 /* low fee parent with high fee child */
355 /* tx6 (0) -> tx7 (high) */
356 CMutableTransaction tx6 = CMutableTransaction();
357 tx6.vout.resize(1);
358 tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
359 tx6.vout[0].nValue = 20 * COIN;
360 uint64_t tx6Size = GetVirtualTransactionSize(CTransaction(tx6));
361
362 pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
363 BOOST_CHECK_EQUAL(pool.size(), 6U);
364 // Ties are broken by hash
365 if (tx3.GetHash() < tx6.GetHash())
366 sortedOrder.push_back(tx6.GetHash().ToString());
367 else
368 sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString());
369
370 CheckSort<ancestor_score>(pool, sortedOrder);
371
372 CMutableTransaction tx7 = CMutableTransaction();
373 tx7.vin.resize(1);
374 tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
375 tx7.vin[0].scriptSig = CScript() << OP_11;
376 tx7.vout.resize(1);
377 tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
378 tx7.vout[0].nValue = 10 * COIN;
379 uint64_t tx7Size = GetVirtualTransactionSize(CTransaction(tx7));
380
381 /* set the fee to just below tx2's feerate when including ancestor */
382 CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1;
383
384 pool.addUnchecked(entry.Fee(fee).FromTx(tx7));
385 BOOST_CHECK_EQUAL(pool.size(), 7U);
386 sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString());
387 CheckSort<ancestor_score>(pool, sortedOrder);
388
389 /* after tx6 is mined, tx7 should move up in the sort */
390 std::vector<CTransactionRef> vtx;
391 vtx.push_back(MakeTransactionRef(tx6));
392 pool.removeForBlock(vtx, 1);
393
394 sortedOrder.erase(sortedOrder.begin()+1);
395 // Ties are broken by hash
396 if (tx3.GetHash() < tx6.GetHash())
397 sortedOrder.pop_back();
398 else
399 sortedOrder.erase(sortedOrder.end()-2);
400 sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
401 CheckSort<ancestor_score>(pool, sortedOrder);
402
403 // High-fee parent, low-fee child
404 // tx7 -> tx8
405 CMutableTransaction tx8 = CMutableTransaction();
406 tx8.vin.resize(1);
407 tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
408 tx8.vin[0].scriptSig = CScript() << OP_11;
409 tx8.vout.resize(1);
410 tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
411 tx8.vout[0].nValue = 10*COIN;
412
413 // Check that we sort by min(feerate, ancestor_feerate):
414 // set the fee so that the ancestor feerate is above tx1/5,
415 // but the transaction's own feerate is lower
416 pool.addUnchecked(entry.Fee(5000LL).FromTx(tx8));
417 sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString());
418 CheckSort<ancestor_score>(pool, sortedOrder);
419 }
420
421
BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)422 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
423 {
424 CTxMemPool pool;
425 LOCK2(cs_main, pool.cs);
426 TestMemPoolEntryHelper entry;
427
428 CMutableTransaction tx1 = CMutableTransaction();
429 tx1.vin.resize(1);
430 tx1.vin[0].scriptSig = CScript() << OP_1;
431 tx1.vout.resize(1);
432 tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
433 tx1.vout[0].nValue = 10 * COIN;
434 pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
435
436 CMutableTransaction tx2 = CMutableTransaction();
437 tx2.vin.resize(1);
438 tx2.vin[0].scriptSig = CScript() << OP_2;
439 tx2.vout.resize(1);
440 tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
441 tx2.vout[0].nValue = 10 * COIN;
442 pool.addUnchecked(entry.Fee(5000LL).FromTx(tx2));
443
444 pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
445 BOOST_CHECK(pool.exists(tx1.GetHash()));
446 BOOST_CHECK(pool.exists(tx2.GetHash()));
447
448 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
449 BOOST_CHECK(pool.exists(tx1.GetHash()));
450 BOOST_CHECK(!pool.exists(tx2.GetHash()));
451
452 pool.addUnchecked(entry.FromTx(tx2));
453 CMutableTransaction tx3 = CMutableTransaction();
454 tx3.vin.resize(1);
455 tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
456 tx3.vin[0].scriptSig = CScript() << OP_2;
457 tx3.vout.resize(1);
458 tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
459 tx3.vout[0].nValue = 10 * COIN;
460 pool.addUnchecked(entry.Fee(20000LL).FromTx(tx3));
461
462 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
463 BOOST_CHECK(!pool.exists(tx1.GetHash()));
464 BOOST_CHECK(pool.exists(tx2.GetHash()));
465 BOOST_CHECK(pool.exists(tx3.GetHash()));
466
467 pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
468 BOOST_CHECK(!pool.exists(tx1.GetHash()));
469 BOOST_CHECK(!pool.exists(tx2.GetHash()));
470 BOOST_CHECK(!pool.exists(tx3.GetHash()));
471
472 CFeeRate maxFeeRateRemoved(25000, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2)));
473 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
474
475 CMutableTransaction tx4 = CMutableTransaction();
476 tx4.vin.resize(2);
477 tx4.vin[0].prevout.SetNull();
478 tx4.vin[0].scriptSig = CScript() << OP_4;
479 tx4.vin[1].prevout.SetNull();
480 tx4.vin[1].scriptSig = CScript() << OP_4;
481 tx4.vout.resize(2);
482 tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
483 tx4.vout[0].nValue = 10 * COIN;
484 tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
485 tx4.vout[1].nValue = 10 * COIN;
486
487 CMutableTransaction tx5 = CMutableTransaction();
488 tx5.vin.resize(2);
489 tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
490 tx5.vin[0].scriptSig = CScript() << OP_4;
491 tx5.vin[1].prevout.SetNull();
492 tx5.vin[1].scriptSig = CScript() << OP_5;
493 tx5.vout.resize(2);
494 tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
495 tx5.vout[0].nValue = 10 * COIN;
496 tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
497 tx5.vout[1].nValue = 10 * COIN;
498
499 CMutableTransaction tx6 = CMutableTransaction();
500 tx6.vin.resize(2);
501 tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
502 tx6.vin[0].scriptSig = CScript() << OP_4;
503 tx6.vin[1].prevout.SetNull();
504 tx6.vin[1].scriptSig = CScript() << OP_6;
505 tx6.vout.resize(2);
506 tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
507 tx6.vout[0].nValue = 10 * COIN;
508 tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
509 tx6.vout[1].nValue = 10 * COIN;
510
511 CMutableTransaction tx7 = CMutableTransaction();
512 tx7.vin.resize(2);
513 tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
514 tx7.vin[0].scriptSig = CScript() << OP_5;
515 tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
516 tx7.vin[1].scriptSig = CScript() << OP_6;
517 tx7.vout.resize(2);
518 tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
519 tx7.vout[0].nValue = 10 * COIN;
520 tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
521 tx7.vout[1].nValue = 10 * COIN;
522
523 pool.addUnchecked(entry.Fee(7000LL).FromTx(tx4));
524 pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
525 pool.addUnchecked(entry.Fee(1100LL).FromTx(tx6));
526 pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
527
528 // we only require this to remove, at max, 2 txn, because it's not clear what we're really optimizing for aside from that
529 pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
530 BOOST_CHECK(pool.exists(tx4.GetHash()));
531 BOOST_CHECK(pool.exists(tx6.GetHash()));
532 BOOST_CHECK(!pool.exists(tx7.GetHash()));
533
534 if (!pool.exists(tx5.GetHash()))
535 pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
536 pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
537
538 pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
539 BOOST_CHECK(pool.exists(tx4.GetHash()));
540 BOOST_CHECK(!pool.exists(tx5.GetHash()));
541 BOOST_CHECK(pool.exists(tx6.GetHash()));
542 BOOST_CHECK(!pool.exists(tx7.GetHash()));
543
544 pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
545 pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
546
547 std::vector<CTransactionRef> vtx;
548 SetMockTime(42);
549 SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
550 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
551 // ... we should keep the same min fee until we get a block
552 pool.removeForBlock(vtx, 1);
553 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
554 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/2.0));
555 // ... then feerate should drop 1/2 each halflife
556
557 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
558 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/4.0));
559 // ... with a 1/2 halflife when mempool is < 1/2 its target size
560
561 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
562 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/8.0));
563 // ... with a 1/4 halflife when mempool is < 1/4 its target size
564
565 SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
566 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
567 // ... but feerate should never drop below 1000
568
569 SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
570 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
571 // ... unless it has gone all the way to 0 (after getting past 1000/2)
572
573 SetMockTime(0);
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
752 BOOST_AUTO_TEST_SUITE_END()
753