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