Inside Bitcoin

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);
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
308inline 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
325BOOST_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
484BOOST_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});