Inside Bitcoin

501        BOOST_CHECK_EQUAL(tx3_bump_fee.value(),
502            very_high_feerate.GetFee(tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]) - (low_fee + med_fee + high_fee + high_fee));
503        // Total fees: if spending both tx6 and tx7, don't double-count fees.
504        node::MiniMiner mini_miner_tx6_tx7(pool, {COutPoint{tx6->GetHash(), 0}, COutPoint{tx7->GetHash(), 0}});
505        BOOST_CHECK(mini_miner_tx6_tx7.IsReadyToCalculate());
506        const auto tx6_tx7_bumpfee = mini_miner_tx6_tx7.CalculateTotalBumpFees(very_high_feerate);
507        BOOST_CHECK(!mini_miner_tx6_tx7.IsReadyToCalculate());
508        BOOST_CHECK(tx6_tx7_bumpfee.has_value());
509        BOOST_CHECK_EQUAL(tx6_tx7_bumpfee.value(),
510            very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6] + tx_vsizes[7]) - (high_fee + low_fee + med_fee + high_fee));
511    }
512    // Feerate just below tx4: tx6 and tx7 have different bump fees.
513    {
514        const auto just_below_tx4 = CFeeRate(tx4_feerate.GetFeePerK() - 5);
515        node::MiniMiner mini_miner(pool, all_unspent_outpoints);
516        BOOST_CHECK(mini_miner.IsReadyToCalculate());
517        auto bump_fees = mini_miner.CalculateBumpFees(just_below_tx4);
518        BOOST_CHECK(!mini_miner.IsReadyToCalculate());
519        BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size());
520        BOOST_CHECK(sanity_check(all_transactions, bump_fees));
521        const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0});
522        BOOST_CHECK(tx6_bumpfee != bump_fees.end());
523        BOOST_CHECK_EQUAL(tx6_bumpfee->second, just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee));
524        const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0});
525        BOOST_CHECK(tx7_bumpfee != bump_fees.end());
526        BOOST_CHECK_EQUAL(tx7_bumpfee->second, just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[7]) - (low_fee + high_fee));
527        // Total fees: if spending both tx6 and tx7, don't double-count fees.
528        node::MiniMiner mini_miner_tx6_tx7(pool, {COutPoint{tx6->GetHash(), 0}, COutPoint{tx7->GetHash(), 0}});
529        BOOST_CHECK(mini_miner_tx6_tx7.IsReadyToCalculate());
530        const auto tx6_tx7_bumpfee = mini_miner_tx6_tx7.CalculateTotalBumpFees(just_below_tx4);
531        BOOST_CHECK(!mini_miner_tx6_tx7.IsReadyToCalculate());
532        BOOST_CHECK(tx6_tx7_bumpfee.has_value());
533        BOOST_CHECK_EQUAL(tx6_tx7_bumpfee.value(), just_below_tx4.GetFee(tx_vsizes[5] + tx_vsizes[6]) - (low_fee + med_fee));
534    }
535    // Feerate between tx6 and tx7's ancestor feerates: don't need to bump tx5 because tx7 already does.
536    {
537        const auto just_above_tx6 = CFeeRate(med_fee + 10, tx_vsizes[6]);
538        BOOST_CHECK(just_above_tx6 <= CFeeRate(low_fee + high_fee, tx_vsizes[5] + tx_vsizes[7]));
539        node::MiniMiner mini_miner(pool, all_unspent_outpoints);
540        BOOST_CHECK(mini_miner.IsReadyToCalculate());
541        auto bump_fees = mini_miner.CalculateBumpFees(just_above_tx6);
542        BOOST_CHECK(!mini_miner.IsReadyToCalculate());
543        BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size());
544        BOOST_CHECK(sanity_check(all_transactions, bump_fees));
545        const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0});
546        BOOST_CHECK(tx6_bumpfee != bump_fees.end());
547        BOOST_CHECK_EQUAL(tx6_bumpfee->second, just_above_tx6.GetFee(tx_vsizes[6]) - (med_fee));
548        const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0});
549        BOOST_CHECK(tx7_bumpfee != bump_fees.end());
550        BOOST_CHECK_EQUAL(tx7_bumpfee->second, 0);
551    }
552    // Check linearization order
553    std::vector<node::MiniMinerMempoolEntry> miniminer_info;
554    miniminer_info.emplace_back(tx0,/*vsize_self=*/tx_vsizes[0],                     /*vsize_ancestor=*/tx_vsizes[0], /*fee_self=*/low_fee,   /*fee_ancestor=*/low_fee);
555    miniminer_info.emplace_back(tx1,               tx_vsizes[1],                                        tx_vsizes[1],              med_fee,                    med_fee);
556    miniminer_info.emplace_back(tx2,               tx_vsizes[2],                                        tx_vsizes[2],             high_fee,                   high_fee);
557    miniminer_info.emplace_back(tx3,               tx_vsizes[3], tx_vsizes[0]+tx_vsizes[1]+tx_vsizes[2]+tx_vsizes[3],             high_fee, low_fee+med_fee+2*high_fee);
558    miniminer_info.emplace_back(tx4,               tx_vsizes[4],                                        tx_vsizes[4],             high_fee,                   high_fee);
559    miniminer_info.emplace_back(tx5,               tx_vsizes[5],                           tx_vsizes[4]+tx_vsizes[5],              low_fee,         low_fee + high_fee);
560    miniminer_info.emplace_back(tx6,               tx_vsizes[6],              tx_vsizes[4]+tx_vsizes[5]+tx_vsizes[6],              med_fee,   high_fee+low_fee+med_fee);
561    miniminer_info.emplace_back(tx7,               tx_vsizes[7],              tx_vsizes[4]+tx_vsizes[5]+tx_vsizes[7],             high_fee,  high_fee+low_fee+high_fee);
562
563    std::map<Txid, std::set<Txid>> descendant_caches;
564    descendant_caches.emplace(tx0->GetHash(), std::set<Txid>{tx0->GetHash(), tx3->GetHash()});
565    descendant_caches.emplace(tx1->GetHash(), std::set<Txid>{tx1->GetHash(), tx3->GetHash()});
566    descendant_caches.emplace(tx2->GetHash(), std::set<Txid>{tx2->GetHash(), tx3->GetHash()});
567    descendant_caches.emplace(tx3->GetHash(), std::set<Txid>{tx3->GetHash()});
568    descendant_caches.emplace(tx4->GetHash(), std::set<Txid>{tx4->GetHash(), tx5->GetHash(), tx6->GetHash(), tx7->GetHash()});
569    descendant_caches.emplace(tx5->GetHash(), std::set<Txid>{tx5->GetHash(), tx6->GetHash(), tx7->GetHash()});
570    descendant_caches.emplace(tx6->GetHash(), std::set<Txid>{tx6->GetHash()});
571    descendant_caches.emplace(tx7->GetHash(), std::set<Txid>{tx7->GetHash()});
572
573    node::MiniMiner miniminer_manual(miniminer_info, descendant_caches);
574    // Use unspent outpoints to avoid entries being omitted.
575    node::MiniMiner miniminer_pool(pool, all_unspent_outpoints);
576    BOOST_CHECK(miniminer_manual.IsReadyToCalculate());
577    BOOST_CHECK(miniminer_pool.IsReadyToCalculate());
578    for (const auto& sequences : {miniminer_manual.Linearize(), miniminer_pool.Linearize()}) {
579        // tx2 and tx4 selected first: high feerate with nothing to bump
580        BOOST_CHECK_EQUAL(Find(sequences, tx4->GetHash()), 0);
581        BOOST_CHECK_EQUAL(Find(sequences, tx2->GetHash()), 1);
582
583        // tx5 + tx7 CPFP
584        BOOST_CHECK_EQUAL(Find(sequences, tx5->GetHash()), 2);
585        BOOST_CHECK_EQUAL(Find(sequences, tx7->GetHash()), 2);
586
587        // tx0 and tx1 CPFP'd by tx3
588        BOOST_CHECK_EQUAL(Find(sequences, tx0->GetHash()), 3);
589        BOOST_CHECK_EQUAL(Find(sequences, tx1->GetHash()), 3);
590        BOOST_CHECK_EQUAL(Find(sequences, tx3->GetHash()), 3);
591
592        // tx6 at medium feerate
593        BOOST_CHECK_EQUAL(Find(sequences, tx6->GetHash()), 4);
594    }
595}
596BOOST_FIXTURE_TEST_CASE(calculate_cluster, TestChain100Setup)
597{
598    CTxMemPool& pool = *Assert(m_node.mempool);
599    LOCK2(cs_main, pool.cs);
600
601    // Add 500 transactions in 10 clusters
602    std::vector<Txid> last_txs;
603    std::vector<Txid> chain_txids;
604    auto& lasttx = m_coinbase_txns[0];
605    TestMemPoolEntryHelper entry;
606    for (int cluster_count=0; cluster_count < 10; ++cluster_count) {
607        // Add chain of size 50
608        lasttx = m_coinbase_txns[cluster_count];
609        for (auto i{0}; i < 50; ++i) {
610            const auto tx = make_tx({COutPoint{lasttx->GetHash(), 0}}, /*num_outputs=*/1);
611            TryAddToMempool(pool, entry.Fee(CENT).FromTx(tx));
612            chain_txids.push_back(tx->GetHash());
613            lasttx = tx;
614        }
615        last_txs.emplace_back(lasttx->GetHash());
616    }
617    const auto cluster_500tx = pool.GatherClusters(last_txs);
618    CTxMemPool::setEntries cluster_500tx_set{cluster_500tx.begin(), cluster_500tx.end()};
619    BOOST_CHECK_EQUAL(cluster_500tx.size(), cluster_500tx_set.size());
620    const auto vec_iters_500 = pool.GetIterVec(chain_txids);
621    for (const auto& iter : vec_iters_500) BOOST_CHECK(cluster_500tx_set.count(iter));
622
623    // GatherClusters stops at 500 transactions.
624    const auto tx_501 = make_tx({COutPoint{lasttx->GetHash(), 0}}, /*num_outputs=*/1);
625    TryAddToMempool(pool, entry.Fee(CENT).FromTx(tx_501));
626    const auto cluster_501 = pool.GatherClusters(last_txs);
627    BOOST_CHECK_EQUAL(cluster_501.size(), 0);
628
629    /* Zig Zag cluster:
630     * txp0     txp1     txp2    ...  txp30  txp31
631     *    \    /    \   /   \            \   /
632     *     txc0     txc1    txc2  ...    txc30
633     * Note that each transaction's ancestor size is 1 or 3, and each descendant size is 1, 2 or 3.
634     * However, all of these transactions are in the same cluster. */
635    std::vector<Txid> zigzag_txids;
636    for (auto p{0}; p < 32; ++p) {
637        const auto txp = make_tx({COutPoint{Txid::FromUint256(GetRandHash()), 0}}, /*num_outputs=*/2);
638        TryAddToMempool(pool, entry.Fee(CENT).FromTx(txp));
639        zigzag_txids.push_back(txp->GetHash());
640    }
641    for (auto c{0}; c < 31; ++c) {
642        const auto txc = make_tx({COutPoint{zigzag_txids[c], 1}, COutPoint{zigzag_txids[c+1], 0}}, /*num_outputs=*/1);
643        TryAddToMempool(pool, entry.Fee(CENT).FromTx(txc));
644        zigzag_txids.push_back(txc->GetHash());
645    }
646    const auto vec_iters_zigzag = pool.GetIterVec(zigzag_txids);
647    // It doesn't matter which tx we calculate cluster for, everybody is in it.
648    const std::vector<size_t> indices{0, 22, 52, zigzag_txids.size() - 1};
649    for (const auto index : indices) {
650        const auto cluster = pool.GatherClusters({zigzag_txids[index]});
651        BOOST_CHECK_EQUAL(cluster.size(), zigzag_txids.size());
652        CTxMemPool::setEntries clusterset{cluster.begin(), cluster.end()};
653        BOOST_CHECK_EQUAL(cluster.size(), clusterset.size());
654        for (const auto& iter : vec_iters_zigzag) BOOST_CHECK(clusterset.count(iter));
655    }
656}
657
658BOOST_FIXTURE_TEST_CASE(manual_ctor, TestChain100Setup)
659{
660    CTxMemPool& pool = *Assert(m_node.mempool);
661    LOCK2(cs_main, pool.cs);
662    {
663        // 3 pairs of grandparent + fee-bumping parent, plus 1 low-feerate child.
664        // 0 fee + high fee
665        auto grandparent_zero_fee = make_tx({{m_coinbase_txns.at(0)->GetHash(), 0}}, 1);
666        auto parent_high_feerate = make_tx({{grandparent_zero_fee->GetHash(), 0}}, 1);
667        // double low fee + med fee
668        auto grandparent_double_low_feerate = make_tx({{m_coinbase_txns.at(2)->GetHash(), 0}}, 1);
669        auto parent_med_feerate = make_tx({{grandparent_double_low_feerate->GetHash(), 0}}, 1);
670        // low fee + double low fee
671        auto grandparent_low_feerate = make_tx({{m_coinbase_txns.at(1)->GetHash(), 0}}, 1);
672        auto parent_double_low_feerate = make_tx({{grandparent_low_feerate->GetHash(), 0}}, 1);
673        // child is below the cpfp package feerates because it is larger than everything else
674        auto child = make_tx({{parent_high_feerate->GetHash(), 0}, {parent_double_low_feerate->GetHash(), 0}, {parent_med_feerate->GetHash(), 0}}, 1);
675
676        // We artificially record each transaction (except the child) with a uniform vsize of 100vB.
677        const int64_t tx_vsize{100};
678        const int64_t child_vsize{1000};
679
680        std::vector<node::MiniMinerMempoolEntry> miniminer_info;
681        miniminer_info.emplace_back(grandparent_zero_fee,          /*vsize_self=*/tx_vsize,/*vsize_ancestor=*/tx_vsize, /*fee_self=*/0,/*fee_ancestor=*/0);
682        miniminer_info.emplace_back(parent_high_feerate,                          tx_vsize,                 2*tx_vsize, high_fee,      high_fee);
683        miniminer_info.emplace_back(grandparent_double_low_feerate,               tx_vsize,                   tx_vsize, 2*low_fee,     2*low_fee);
684        miniminer_info.emplace_back(parent_med_feerate,                           tx_vsize,                 2*tx_vsize, med_fee,       2*low_fee+med_fee);
685        miniminer_info.emplace_back(grandparent_low_feerate,                      tx_vsize,                   tx_vsize, low_fee,       low_fee);
686        miniminer_info.emplace_back(parent_double_low_feerate,                    tx_vsize,                 2*tx_vsize, 2*low_fee,     3*low_fee);
687        miniminer_info.emplace_back(child,                                     child_vsize,     6*tx_vsize+child_vsize, low_fee,       high_fee+med_fee+6*low_fee);
688        std::map<Txid, std::set<Txid>> descendant_caches;
689        descendant_caches.emplace(grandparent_zero_fee->GetHash(), std::set<Txid>{grandparent_zero_fee->GetHash(), parent_high_feerate->GetHash(), child->GetHash()});
690        descendant_caches.emplace(grandparent_low_feerate->GetHash(), std::set<Txid>{grandparent_low_feerate->GetHash(), parent_double_low_feerate->GetHash(), child->GetHash()});
691        descendant_caches.emplace(grandparent_double_low_feerate->GetHash(), std::set<Txid>{grandparent_double_low_feerate->GetHash(), parent_med_feerate->GetHash(), child->GetHash()});
692        descendant_caches.emplace(parent_high_feerate->GetHash(), std::set<Txid>{parent_high_feerate->GetHash(), child->GetHash()});
693        descendant_caches.emplace(parent_med_feerate->GetHash(), std::set<Txid>{parent_med_feerate->GetHash(), child->GetHash()});
694        descendant_caches.emplace(parent_double_low_feerate->GetHash(), std::set<Txid>{parent_double_low_feerate->GetHash(), child->GetHash()});
695        descendant_caches.emplace(child->GetHash(), std::set<Txid>{child->GetHash()});
696
697        node::MiniMiner miniminer_manual(miniminer_info, descendant_caches);
698        BOOST_CHECK(miniminer_manual.IsReadyToCalculate());
699        const auto sequences{miniminer_manual.Linearize()};
700
701        // CPFP zero + high
702        BOOST_CHECK_EQUAL(sequences.at(grandparent_zero_fee->GetHash()), 0);
703        BOOST_CHECK_EQUAL(sequences.at(parent_high_feerate->GetHash()), 0);
704
705        // CPFP double low + med
706        BOOST_CHECK_EQUAL(sequences.at(grandparent_double_low_feerate->GetHash()), 1);
707        BOOST_CHECK_EQUAL(sequences.at(parent_med_feerate->GetHash()), 1);
708
709        // CPFP low + double low
710        BOOST_CHECK_EQUAL(sequences.at(grandparent_low_feerate->GetHash()), 2);
711        BOOST_CHECK_EQUAL(sequences.at(parent_double_low_feerate->GetHash()), 2);
712
713        // Child at the end
714        BOOST_CHECK_EQUAL(sequences.at(child->GetHash()), 3);
715    }
716}
717
718BOOST_AUTO_TEST_SUITE_END()
719