mempool_tests.cpp raw
1 // Copyright (c) 2011-present 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 <common/system.h>
6 #include <policy/policy.h>
7 #include <test/util/time.h>
8 #include <test/util/txmempool.h>
9 #include <txmempool.h>
10 #include <util/time.h>
11
12 #include <test/util/setup_common.h>
13
14 #include <boost/test/unit_test.hpp>
15 #include <vector>
16
17 BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
18
19 static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED;
20
21 class MemPoolTest final : public CTxMemPool
22 {
23 public:
24 using CTxMemPool::GetMinFee;
25 };
26
27 BOOST_AUTO_TEST_CASE(MempoolLookupTest)
28 {
29 auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
30 LOCK2(cs_main, pool.cs);
31 TestMemPoolEntryHelper entry;
32
33 CMutableTransaction tx = CMutableTransaction();
34 tx.vin.resize(1);
35 tx.vin[0].scriptSig = CScript() << OP_1;
36 tx.vout.resize(1);
37 tx.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
38 tx.vout[0].nValue = 10 * COIN;
39
40 // Not in the mempool, so can't find it by txid or wtxid
41 BOOST_CHECK(!pool.get(tx.GetHash()));
42 BOOST_CHECK(!pool.get(CTransaction(tx).GetWitnessHash()));
43
44 TryAddToMempool(pool, entry.Fee(1000LL).FromTx(tx));
45
46 // Lookup by Txid
47 BOOST_CHECK(pool.get(tx.GetHash()));
48
49 // Lookup by Wtxid
50 BOOST_CHECK(pool.get(CTransaction(tx).GetWitnessHash()));
51 }
52
53 BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
54 {
55 // Test CTxMemPool::remove functionality
56
57 TestMemPoolEntryHelper entry;
58 // Parent transaction with three children,
59 // and three grand-children:
60 CMutableTransaction txParent;
61 txParent.vin.resize(1);
62 txParent.vin[0].scriptSig = CScript() << OP_11;
63 txParent.vout.resize(3);
64 for (int i = 0; i < 3; i++)
65 {
66 txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
67 txParent.vout[i].nValue = 33000LL;
68 }
69 CMutableTransaction txChild[3];
70 for (int i = 0; i < 3; i++)
71 {
72 txChild[i].vin.resize(1);
73 txChild[i].vin[0].scriptSig = CScript() << OP_11;
74 txChild[i].vin[0].prevout.hash = txParent.GetHash();
75 txChild[i].vin[0].prevout.n = i;
76 txChild[i].vout.resize(1);
77 txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
78 txChild[i].vout[0].nValue = 11000LL;
79 }
80 CMutableTransaction txGrandChild[3];
81 for (int i = 0; i < 3; i++)
82 {
83 txGrandChild[i].vin.resize(1);
84 txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
85 txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
86 txGrandChild[i].vin[0].prevout.n = 0;
87 txGrandChild[i].vout.resize(1);
88 txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
89 txGrandChild[i].vout[0].nValue = 11000LL;
90 }
91
92
93 CTxMemPool& testPool = *Assert(m_node.mempool);
94 LOCK2(::cs_main, testPool.cs);
95
96 // Nothing in pool, remove should do nothing:
97 unsigned int poolSize = testPool.size();
98 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
99 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
100
101 // Just the parent:
102 TryAddToMempool(testPool, entry.FromTx(txParent));
103 poolSize = testPool.size();
104 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
105 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
106
107 // Parent, children, grandchildren:
108 TryAddToMempool(testPool, entry.FromTx(txParent));
109 for (int i = 0; i < 3; i++)
110 {
111 TryAddToMempool(testPool, entry.FromTx(txChild[i]));
112 TryAddToMempool(testPool, entry.FromTx(txGrandChild[i]));
113 }
114 // Remove Child[0], GrandChild[0] should be removed:
115 poolSize = testPool.size();
116 testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
117 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
118 // ... make sure grandchild and child are gone:
119 poolSize = testPool.size();
120 testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY);
121 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
122 poolSize = testPool.size();
123 testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
124 BOOST_CHECK_EQUAL(testPool.size(), poolSize);
125 // Remove parent, all children/grandchildren should go:
126 poolSize = testPool.size();
127 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
128 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
129 BOOST_CHECK_EQUAL(testPool.size(), 0U);
130
131 // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
132 for (int i = 0; i < 3; i++)
133 {
134 TryAddToMempool(testPool, entry.FromTx(txChild[i]));
135 TryAddToMempool(testPool, entry.FromTx(txGrandChild[i]));
136 }
137 // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
138 // put into the mempool (maybe because it is non-standard):
139 poolSize = testPool.size();
140 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
141 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
142 BOOST_CHECK_EQUAL(testPool.size(), 0U);
143 }
144
145 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
146 {
147 auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
148 LOCK2(cs_main, pool.cs);
149 TestMemPoolEntryHelper entry;
150
151 CMutableTransaction tx1 = CMutableTransaction();
152 tx1.vin.resize(1);
153 tx1.vin[0].scriptSig = CScript() << OP_1;
154 tx1.vout.resize(1);
155 tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
156 tx1.vout[0].nValue = 10 * COIN;
157 TryAddToMempool(pool, entry.Fee(1000LL).FromTx(tx1));
158
159 CMutableTransaction tx2 = CMutableTransaction();
160 tx2.vin.resize(1);
161 tx2.vin[0].scriptSig = CScript() << OP_2;
162 tx2.vout.resize(1);
163 tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
164 tx2.vout[0].nValue = 10 * COIN;
165 TryAddToMempool(pool, entry.Fee(500LL).FromTx(tx2));
166
167 pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
168 BOOST_CHECK(pool.exists(tx1.GetHash()));
169 BOOST_CHECK(pool.exists(tx2.GetHash()));
170
171 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
172 BOOST_CHECK(pool.exists(tx1.GetHash()));
173 BOOST_CHECK(!pool.exists(tx2.GetHash()));
174
175 TryAddToMempool(pool, entry.FromTx(tx2));
176 CMutableTransaction tx3 = CMutableTransaction();
177 tx3.vin.resize(1);
178 tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
179 tx3.vin[0].scriptSig = CScript() << OP_2;
180 tx3.vout.resize(1);
181 tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
182 tx3.vout[0].nValue = 10 * COIN;
183 TryAddToMempool(pool, entry.Fee(2000LL).FromTx(tx3));
184
185 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
186 BOOST_CHECK(!pool.exists(tx1.GetHash()));
187 BOOST_CHECK(pool.exists(tx2.GetHash()));
188 BOOST_CHECK(pool.exists(tx3.GetHash()));
189
190 pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
191 BOOST_CHECK(!pool.exists(tx1.GetHash()));
192 BOOST_CHECK(!pool.exists(tx2.GetHash()));
193 BOOST_CHECK(!pool.exists(tx3.GetHash()));
194
195 CFeeRate maxFeeRateRemoved(2500, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2)));
196 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE);
197
198 CMutableTransaction tx4 = CMutableTransaction();
199 tx4.vin.resize(2);
200 tx4.vin[0].prevout.SetNull();
201 tx4.vin[0].scriptSig = CScript() << OP_4;
202 tx4.vin[1].prevout.SetNull();
203 tx4.vin[1].scriptSig = CScript() << OP_4;
204 tx4.vout.resize(2);
205 tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
206 tx4.vout[0].nValue = 10 * COIN;
207 tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
208 tx4.vout[1].nValue = 10 * COIN;
209
210 CMutableTransaction tx5 = CMutableTransaction();
211 tx5.vin.resize(2);
212 tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
213 tx5.vin[0].scriptSig = CScript() << OP_4;
214 tx5.vin[1].prevout.SetNull();
215 tx5.vin[1].scriptSig = CScript() << OP_5;
216 tx5.vout.resize(2);
217 tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
218 tx5.vout[0].nValue = 10 * COIN;
219 tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
220 tx5.vout[1].nValue = 10 * COIN;
221
222 CMutableTransaction tx6 = CMutableTransaction();
223 tx6.vin.resize(2);
224 tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
225 tx6.vin[0].scriptSig = CScript() << OP_4;
226 tx6.vin[1].prevout.SetNull();
227 tx6.vin[1].scriptSig = CScript() << OP_6;
228 tx6.vout.resize(2);
229 tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
230 tx6.vout[0].nValue = 10 * COIN;
231 tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
232 tx6.vout[1].nValue = 10 * COIN;
233
234 CMutableTransaction tx7 = CMutableTransaction();
235 tx7.vin.resize(2);
236 tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
237 tx7.vin[0].scriptSig = CScript() << OP_5;
238 tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
239 tx7.vin[1].scriptSig = CScript() << OP_6;
240 tx7.vout.resize(2);
241 tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
242 tx7.vout[0].nValue = 10 * COIN;
243 tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
244 tx7.vout[1].nValue = 10 * COIN;
245
246 TryAddToMempool(pool, entry.Fee(700LL).FromTx(tx4));
247 auto usage_with_tx4_only = pool.DynamicMemoryUsage();
248 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
249 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
250 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
251
252 // From the topology above, tx7 must be sorted last, so it should
253 // definitely evicted first if we must trim. tx4 should definitely remain
254 // in the mempool since it has a higher feerate than its descendants and
255 // should be in its own chunk.
256 pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
257 BOOST_CHECK(pool.exists(tx4.GetHash()));
258 BOOST_CHECK(!pool.exists(tx7.GetHash()));
259
260 // Tx5 and Tx6 may be removed as well because they're in the same chunk as
261 // tx7, but this behavior need not be guaranteed.
262
263 if (!pool.exists(tx5.GetHash()))
264 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
265 if (!pool.exists(tx6.GetHash()))
266 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
267 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
268
269 // If we trim sufficiently, everything but tx4 should be removed.
270 pool.TrimToSize(usage_with_tx4_only + 1);
271 BOOST_CHECK(pool.exists(tx4.GetHash()));
272 BOOST_CHECK(!pool.exists(tx5.GetHash()));
273 BOOST_CHECK(!pool.exists(tx6.GetHash()));
274 BOOST_CHECK(!pool.exists(tx7.GetHash()));
275
276 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
277 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
278 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
279
280 std::vector<CTransactionRef> vtx;
281 FakeNodeClock clock{42s};
282 constexpr std::chrono::seconds HALFLIFE{CTxMemPool::ROLLING_FEE_HALFLIFE};
283 clock += HALFLIFE;
284 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE);
285 // ... we should keep the same min fee until we get a block
286 pool.removeForBlock(vtx, 1);
287 clock += HALFLIFE;
288 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/2.0));
289 // ... then feerate should drop 1/2 each halflife
290
291 clock += HALFLIFE / 2;
292 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/4.0));
293 // ... with a 1/2 halflife when mempool is < 1/2 its target size
294
295 clock += HALFLIFE / 4;
296 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/8.0));
297 // ... with a 1/4 halflife when mempool is < 1/4 its target size
298
299 clock += 5 * HALFLIFE;
300 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), DEFAULT_INCREMENTAL_RELAY_FEE);
301 // ... but feerate should never drop below DEFAULT_INCREMENTAL_RELAY_FEE
302
303 clock += HALFLIFE;
304 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
305 // ... unless it has gone all the way to 0 (after getting past DEFAULT_INCREMENTAL_RELAY_FEE/2)
306 }
307
308 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>())
309 {
310 CMutableTransaction tx = CMutableTransaction();
311 tx.vin.resize(inputs.size());
312 tx.vout.resize(output_values.size());
313 for (size_t i = 0; i < inputs.size(); ++i) {
314 tx.vin[i].prevout.hash = inputs[i]->GetHash();
315 tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
316 }
317 for (size_t i = 0; i < output_values.size(); ++i) {
318 tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
319 tx.vout[i].nValue = output_values[i];
320 }
321 return MakeTransactionRef(tx);
322 }
323
324
325 BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
326 {
327 size_t ancestors, clustersize;
328
329 CTxMemPool& pool = *Assert(m_node.mempool);
330 LOCK2(cs_main, pool.cs);
331 TestMemPoolEntryHelper entry;
332
333 /* Base transaction */
334 //
335 // [tx1]
336 //
337 CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN});
338 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx1));
339
340 // Ancestors / clustersize should be 1 / 1 (itself / itself)
341 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
342 BOOST_CHECK_EQUAL(ancestors, 1ULL);
343 BOOST_CHECK_EQUAL(clustersize, 1ULL);
344
345 /* Child transaction */
346 //
347 // [tx1].0 <- [tx2]
348 //
349 CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1});
350 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx2));
351
352 // Ancestors / clustersize should be:
353 // transaction ancestors clustersize
354 // ============ =========== ===========
355 // tx1 1 (tx1) 2 (tx1,2)
356 // tx2 2 (tx1,2) 2 (tx1,2)
357 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
358 BOOST_CHECK_EQUAL(ancestors, 1ULL);
359 BOOST_CHECK_EQUAL(clustersize, 2ULL);
360 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
361 BOOST_CHECK_EQUAL(ancestors, 2ULL);
362 BOOST_CHECK_EQUAL(clustersize, 2ULL);
363
364 /* Grand-child 1 */
365 //
366 // [tx1].0 <- [tx2].0 <- [tx3]
367 //
368 CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2});
369 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx3));
370
371 // Ancestors / clustersize should be:
372 // transaction ancestors clustersize
373 // ============ =========== ===========
374 // tx1 1 (tx1) 3 (tx1,2,3)
375 // tx2 2 (tx1,2) 3 (tx1,2,3)
376 // tx3 3 (tx1,2,3) 3 (tx1,2,3)
377 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
378 BOOST_CHECK_EQUAL(ancestors, 1ULL);
379 BOOST_CHECK_EQUAL(clustersize, 3ULL);
380 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
381 BOOST_CHECK_EQUAL(ancestors, 2ULL);
382 BOOST_CHECK_EQUAL(clustersize, 3ULL);
383 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
384 BOOST_CHECK_EQUAL(ancestors, 3ULL);
385 BOOST_CHECK_EQUAL(clustersize, 3ULL);
386
387 /* Grand-child 2 */
388 //
389 // [tx1].0 <- [tx2].0 <- [tx3]
390 // |
391 // \---1 <- [tx4]
392 //
393 CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1});
394 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx4));
395
396 // Ancestors / clustersize should be:
397 // transaction ancestors clustersize
398 // ============ =========== ===========
399 // tx1 1 (tx1) 4 (tx1,2,3,4)
400 // tx2 2 (tx1,2) 4 (tx1,2,3,4)
401 // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
402 // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
403 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
404 BOOST_CHECK_EQUAL(ancestors, 1ULL);
405 BOOST_CHECK_EQUAL(clustersize, 4ULL);
406 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
407 BOOST_CHECK_EQUAL(ancestors, 2ULL);
408 BOOST_CHECK_EQUAL(clustersize, 4ULL);
409 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
410 BOOST_CHECK_EQUAL(ancestors, 3ULL);
411 BOOST_CHECK_EQUAL(clustersize, 4ULL);
412 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize);
413 BOOST_CHECK_EQUAL(ancestors, 3ULL);
414 BOOST_CHECK_EQUAL(clustersize, 4ULL);
415
416 /* Make an alternate branch that is longer and connect it to tx3 */
417 //
418 // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
419 // |
420 // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
421 // |
422 // \---1 <- [tx4]
423 //
424 CTransactionRef ty1, ty2, ty3, ty4, ty5;
425 CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
426 CAmount v = 5 * COIN;
427 for (uint64_t i = 0; i < 5; i++) {
428 CTransactionRef& tyi = *ty[i];
429 tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{});
430 v -= 50 * CENT;
431 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tyi));
432 pool.GetTransactionAncestry(tyi->GetHash(), ancestors, clustersize);
433 BOOST_CHECK_EQUAL(ancestors, i+1);
434 BOOST_CHECK_EQUAL(clustersize, i+1);
435 }
436 CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5});
437 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ty6));
438
439 // Ancestors / clustersize should be:
440 // transaction ancestors clustersize
441 // ============ =================== ===========
442 // tx1 1 (tx1) 10 (tx1-5, ty1-5)
443 // tx2 2 (tx1,2) 10
444 // tx3 3 (tx1,2,3) 10
445 // tx4 3 (tx1,2,4) 10
446 // ty1 1 (ty1) 10
447 // ty2 2 (ty1,2) 10
448 // ty3 3 (ty1,2,3) 10
449 // ty4 4 (y1234) 10
450 // ty5 5 (y12345) 10
451 // ty6 9 (tx123, ty123456) 10
452 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
453 BOOST_CHECK_EQUAL(ancestors, 1ULL);
454 BOOST_CHECK_EQUAL(clustersize, 10ULL);
455 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
456 BOOST_CHECK_EQUAL(ancestors, 2ULL);
457 BOOST_CHECK_EQUAL(clustersize, 10ULL);
458 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
459 BOOST_CHECK_EQUAL(ancestors, 3ULL);
460 BOOST_CHECK_EQUAL(clustersize, 10ULL);
461 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize);
462 BOOST_CHECK_EQUAL(ancestors, 3ULL);
463 BOOST_CHECK_EQUAL(clustersize, 10ULL);
464 pool.GetTransactionAncestry(ty1->GetHash(), ancestors, clustersize);
465 BOOST_CHECK_EQUAL(ancestors, 1ULL);
466 BOOST_CHECK_EQUAL(clustersize, 10ULL);
467 pool.GetTransactionAncestry(ty2->GetHash(), ancestors, clustersize);
468 BOOST_CHECK_EQUAL(ancestors, 2ULL);
469 BOOST_CHECK_EQUAL(clustersize, 10ULL);
470 pool.GetTransactionAncestry(ty3->GetHash(), ancestors, clustersize);
471 BOOST_CHECK_EQUAL(ancestors, 3ULL);
472 BOOST_CHECK_EQUAL(clustersize, 10ULL);
473 pool.GetTransactionAncestry(ty4->GetHash(), ancestors, clustersize);
474 BOOST_CHECK_EQUAL(ancestors, 4ULL);
475 BOOST_CHECK_EQUAL(clustersize, 10ULL);
476 pool.GetTransactionAncestry(ty5->GetHash(), ancestors, clustersize);
477 BOOST_CHECK_EQUAL(ancestors, 5ULL);
478 BOOST_CHECK_EQUAL(clustersize, 10ULL);
479 pool.GetTransactionAncestry(ty6->GetHash(), ancestors, clustersize);
480 BOOST_CHECK_EQUAL(ancestors, 9ULL);
481 BOOST_CHECK_EQUAL(clustersize, 10ULL);
482 }
483
484 BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
485 {
486 size_t ancestors, descendants;
487
488 CTxMemPool& pool = *Assert(m_node.mempool);
489 LOCK2(::cs_main, pool.cs);
490 TestMemPoolEntryHelper entry;
491
492 /* Ancestors represented more than once ("diamond") */
493 //
494 // [ta].0 <- [tb].0 -----<------- [td].0
495 // | |
496 // \---1 <- [tc].0 --<--/
497 //
498 CTransactionRef ta, tb, tc, td;
499 ta = make_tx(/*output_values=*/{10 * COIN});
500 tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta});
501 tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1});
502 td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0});
503 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ta));
504 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tb));
505 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tc));
506 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(td));
507
508 // Ancestors / descendants should be:
509 // transaction ancestors descendants
510 // ============ =================== ===========
511 // ta 1 (ta 4 (ta,tb,tc,td)
512 // tb 2 (ta,tb) 4 (ta,tb,tc,td)
513 // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td)
514 // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td)
515 pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants);
516 BOOST_CHECK_EQUAL(ancestors, 1ULL);
517 BOOST_CHECK_EQUAL(descendants, 4ULL);
518 pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants);
519 BOOST_CHECK_EQUAL(ancestors, 2ULL);
520 BOOST_CHECK_EQUAL(descendants, 4ULL);
521 pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants);
522 BOOST_CHECK_EQUAL(ancestors, 3ULL);
523 BOOST_CHECK_EQUAL(descendants, 4ULL);
524 pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants);
525 BOOST_CHECK_EQUAL(ancestors, 4ULL);
526 BOOST_CHECK_EQUAL(descendants, 4ULL);
527 }
528
529 BOOST_AUTO_TEST_SUITE_END()
530