Inside Bitcoin

251        const CFeeRate tx4_feerate = CFeeRate(tx4_dimensions.mod_fee + tx5_dimensions.mod_fee, tx4_dimensions.vsize + tx5_dimensions.vsize);
252        CAmount bumpfee4 = Find(bump_fees, COutPoint{tx4->GetHash(), 1});
253        if (target_feerate <= tx4_feerate) {
254            // As long as target feerate is below tx5's ancestor feerate, there is no bump fee.
255            BOOST_CHECK_EQUAL(bumpfee4, 0);
256        } else {
257            // Difference is fee to bump tx4 from current to target feerate, without tx5.
258            BOOST_CHECK_EQUAL(bumpfee4, target_feerate.GetFee(tx4_dimensions.vsize) - tx4_dimensions.mod_fee);
259        }
260    }
261    // Spent outpoints should usually not be requested as they would not be
262    // considered available. However, when they are explicitly requested, we
263    // can calculate their bumpfee to facilitate RBF-replacements
264    for (const auto& target_feerate : various_normal_feerates) {
265        node::MiniMiner mini_miner_all_spent(pool, all_spent_outpoints);
266        BOOST_CHECK(mini_miner_all_spent.IsReadyToCalculate());
267        auto bump_fees_all_spent = mini_miner_all_spent.CalculateBumpFees(target_feerate);
268        BOOST_CHECK(!mini_miner_all_spent.IsReadyToCalculate());
269        BOOST_CHECK_EQUAL(bump_fees_all_spent.size(), all_spent_outpoints.size());
270        node::MiniMiner mini_miner_all_parents(pool, all_parent_outputs);
271        BOOST_CHECK(mini_miner_all_parents.IsReadyToCalculate());
272        auto bump_fees_all_parents = mini_miner_all_parents.CalculateBumpFees(target_feerate);
273        BOOST_CHECK(!mini_miner_all_parents.IsReadyToCalculate());
274        BOOST_CHECK_EQUAL(bump_fees_all_parents.size(), all_parent_outputs.size());
275        for (auto& bump_fees : {bump_fees_all_parents, bump_fees_all_spent}) {
276            // For all_parents case, both outputs from the parent should have the same bump fee,
277            // even though only one of them is in a to-be-replaced transaction.
278            BOOST_CHECK(sanity_check(all_transactions, bump_fees));
279
280            // Check tx0 bumpfee: no other bumper.
281            const TxDimensions& tx0_dimensions = tx_dims.find(tx0->GetHash())->second;
282            CAmount it0_spent = Find(bump_fees, COutPoint{tx0->GetHash(), 0});
283            if (target_feerate <= tx0_dimensions.feerate) {
284                BOOST_CHECK_EQUAL(it0_spent, 0);
285            } else {
286                // Difference is fee to bump tx0 from current to target feerate.
287                BOOST_CHECK_EQUAL(it0_spent, target_feerate.GetFee(tx0_dimensions.vsize) - tx0_dimensions.mod_fee);
288            }
289
290            // Check tx2 bumpfee: no other bumper, because tx3 is to-be-replaced.
291            const TxDimensions& tx2_dimensions = tx_dims.find(tx2->GetHash())->second;
292            const CFeeRate tx2_feerate_unbumped = tx2_dimensions.feerate;
293            auto it2_spent = Find(bump_fees, COutPoint{tx2->GetHash(), 0});
294            if (target_feerate <= tx2_feerate_unbumped) {
295                BOOST_CHECK_EQUAL(it2_spent, 0);
296            } else {
297                // Difference is fee to bump tx2 from current to target feerate, without tx3.
298                BOOST_CHECK_EQUAL(it2_spent, target_feerate.GetFee(tx2_dimensions.vsize) - tx2_dimensions.mod_fee);
299            }
300
301            // Check tx4 bumpfee: no other bumper, because tx5 is to-be-replaced.
302            const TxDimensions& tx4_dimensions = tx_dims.find(tx4->GetHash())->second;
303            const CFeeRate tx4_feerate_unbumped = tx4_dimensions.feerate;
304            auto it4_spent = Find(bump_fees, COutPoint{tx4->GetHash(), 0});
305            if (target_feerate <= tx4_feerate_unbumped) {
306                BOOST_CHECK_EQUAL(it4_spent, 0);
307            } else {
308                // Difference is fee to bump tx4 from current to target feerate, without tx5.
309                BOOST_CHECK_EQUAL(it4_spent, target_feerate.GetFee(tx4_dimensions.vsize) - tx4_dimensions.mod_fee);
310            }
311        }
312    }
313
314    // Check m_inclusion_order for equivalent mempool- and manually-constructed MiniMiners.
315    // (We cannot check bump fees in manually-constructed MiniMiners because it doesn't know what
316    // outpoints are requested).
317    std::vector<node::MiniMinerMempoolEntry> miniminer_info;
318    {
319        const int32_t tx0_vsize{tx_dims.at(tx0->GetHash()).vsize};
320        const int32_t tx1_vsize{tx_dims.at(tx1->GetHash()).vsize};
321        const int32_t tx2_vsize{tx_dims.at(tx2->GetHash()).vsize};
322        const int32_t tx3_vsize{tx_dims.at(tx3->GetHash()).vsize};
323        const int32_t tx4_vsize{tx_dims.at(tx4->GetHash()).vsize};
324        const int32_t tx5_vsize{tx_dims.at(tx5->GetHash()).vsize};
325        const int32_t tx6_vsize{tx_dims.at(tx6->GetHash()).vsize};
326        const int32_t tx7_vsize{tx_dims.at(tx7->GetHash()).vsize};
327
328        miniminer_info.emplace_back(tx0,/*vsize_self=*/tx0_vsize,/*vsize_ancestor=*/tx0_vsize,/*fee_self=*/med_fee,/*fee_ancestor=*/med_fee);
329        miniminer_info.emplace_back(tx1,               tx1_vsize,       tx0_vsize + tx1_vsize,             med_fee,               2*med_fee);
330        miniminer_info.emplace_back(tx2,               tx2_vsize,                   tx2_vsize,             low_fee,                 low_fee);
331        miniminer_info.emplace_back(tx3,               tx3_vsize,       tx2_vsize + tx3_vsize,            high_fee,      low_fee + high_fee);
332        miniminer_info.emplace_back(tx4,               tx4_vsize,                   tx4_vsize,             low_fee,                 low_fee);
333        miniminer_info.emplace_back(tx5,               tx5_vsize,       tx4_vsize + tx5_vsize,         tx5_mod_fee,   low_fee + tx5_mod_fee);
334        miniminer_info.emplace_back(tx6,               tx6_vsize,                   tx6_vsize,            high_fee,                high_fee);
335        miniminer_info.emplace_back(tx7,               tx7_vsize,       tx6_vsize + tx7_vsize,             low_fee,      high_fee + low_fee);
336    }
337    std::map<Txid, std::set<Txid>> descendant_caches;
338    descendant_caches.emplace(tx0->GetHash(), std::set<Txid>{tx0->GetHash(), tx1->GetHash()});
339    descendant_caches.emplace(tx1->GetHash(), std::set<Txid>{tx1->GetHash()});
340    descendant_caches.emplace(tx2->GetHash(), std::set<Txid>{tx2->GetHash(), tx3->GetHash()});
341    descendant_caches.emplace(tx3->GetHash(), std::set<Txid>{tx3->GetHash()});
342    descendant_caches.emplace(tx4->GetHash(), std::set<Txid>{tx4->GetHash(), tx5->GetHash()});
343    descendant_caches.emplace(tx5->GetHash(), std::set<Txid>{tx5->GetHash()});
344    descendant_caches.emplace(tx6->GetHash(), std::set<Txid>{tx6->GetHash(), tx7->GetHash()});
345    descendant_caches.emplace(tx7->GetHash(), std::set<Txid>{tx7->GetHash()});
346
347    node::MiniMiner miniminer_manual(miniminer_info, descendant_caches);
348    // Use unspent outpoints to avoid entries being omitted.
349    node::MiniMiner miniminer_pool(pool, all_unspent_outpoints);
350    BOOST_CHECK(miniminer_manual.IsReadyToCalculate());
351    BOOST_CHECK(miniminer_pool.IsReadyToCalculate());
352    for (const auto& sequences : {miniminer_manual.Linearize(), miniminer_pool.Linearize()}) {
353        // tx6 is selected first: high feerate with no parents to bump
354        BOOST_CHECK_EQUAL(Find(sequences, tx6->GetHash()), 0);
355
356        // tx2 + tx3 CPFP are selected next
357        BOOST_CHECK_EQUAL(Find(sequences, tx2->GetHash()), 1);
358        BOOST_CHECK_EQUAL(Find(sequences, tx3->GetHash()), 1);
359
360        // tx4 + prioritised tx5 CPFP
361        BOOST_CHECK_EQUAL(Find(sequences, tx4->GetHash()), 2);
362        BOOST_CHECK_EQUAL(Find(sequences, tx5->GetHash()), 2);
363
364        BOOST_CHECK_EQUAL(Find(sequences, tx0->GetHash()), 3);
365        BOOST_CHECK_EQUAL(Find(sequences, tx1->GetHash()), 3);
366
367
368        // tx7 is selected last: low feerate with no children
369        BOOST_CHECK_EQUAL(Find(sequences, tx7->GetHash()), 4);
370    }
371}
372
373BOOST_FIXTURE_TEST_CASE(miniminer_overlap, TestChain100Setup)
374{
375/*      Tx graph for `miniminer_overlap` unit test:
376 *
377 *     coinbase_tx [mined]        ... block-chain
378 *  -------------------------------------------------
379 *      /   |   \          \      ... mempool
380 *     /    |    \         |
381 *   tx0   tx1   tx2      tx4
382 *  [low] [med] [high]   [high]
383 *     \    |    /         |
384 *      \   |   /         tx5
385 *       \  |  /         [low]
386 *         tx3          /     \
387 *        [high]       tx6    tx7
388 *                    [med]  [high]
389 *
390 *  NOTE:
391 *  -> "low"/"med"/"high" denote the _absolute_ fee of each tx
392 *  -> tx3 has 3 inputs and 3 outputs, all other txs have 1 input and 2 outputs
393 *  -> tx3's feerate is lower than tx2's, as tx3 has more weight (due to having more inputs and outputs)
394 *
395 *  -> tx2_FR = high / tx2_vsize
396 *  -> tx3_FR = high / tx3_vsize
397 *  -> tx3_ASFR = (low+med+high+high) / (tx0_vsize + tx1_vsize + tx2_vsize + tx3_vsize)
398 *  -> tx4_FR = high / tx4_vsize
399 *  -> tx6_ASFR = (high+low+med) / (tx4_vsize + tx5_vsize + tx6_vsize)
400 *  -> tx7_ASFR = (high+low+high) / (tx4_vsize + tx5_vsize + tx7_vsize) */
401
402    CTxMemPool& pool = *Assert(m_node.mempool);
403    LOCK2(::cs_main, pool.cs);
404    TestMemPoolEntryHelper entry;
405
406    // Create 3 parents of different feerates, and 1 child spending outputs from all 3 parents.
407    const auto tx0 = make_tx({COutPoint{m_coinbase_txns[0]->GetHash(), 0}}, /*num_outputs=*/2);
408    TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx0));
409    const auto tx1 = make_tx({COutPoint{m_coinbase_txns[1]->GetHash(), 0}}, /*num_outputs=*/2);
410    TryAddToMempool(pool, entry.Fee(med_fee).FromTx(tx1));
411    const auto tx2 = make_tx({COutPoint{m_coinbase_txns[2]->GetHash(), 0}}, /*num_outputs=*/2);
412    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx2));
413    const auto tx3 = make_tx({COutPoint{tx0->GetHash(), 0}, COutPoint{tx1->GetHash(), 0}, COutPoint{tx2->GetHash(), 0}}, /*num_outputs=*/3);
414    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx3));
415
416    // Create 1 grandparent and 1 parent, then 2 children.
417    const auto tx4 = make_tx({COutPoint{m_coinbase_txns[3]->GetHash(), 0}}, /*num_outputs=*/2);
418    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx4));
419    const auto tx5 = make_tx({COutPoint{tx4->GetHash(), 0}}, /*num_outputs=*/3);
420    TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx5));
421    const auto tx6 = make_tx({COutPoint{tx5->GetHash(), 0}}, /*num_outputs=*/2);
422    TryAddToMempool(pool, entry.Fee(med_fee).FromTx(tx6));
423    const auto tx7 = make_tx({COutPoint{tx5->GetHash(), 1}}, /*num_outputs=*/2);
424    TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx7));
425
426    std::vector<CTransactionRef> all_transactions{tx0, tx1, tx2, tx3, tx4, tx5, tx6, tx7};
427    std::vector<int64_t> tx_vsizes;
428    tx_vsizes.reserve(all_transactions.size());
429    for (const auto& tx : all_transactions) tx_vsizes.push_back(GetVirtualTransactionSize(*tx));
430
431    std::vector<COutPoint> all_unspent_outpoints({
432        COutPoint{tx0->GetHash(), 1},
433        COutPoint{tx1->GetHash(), 1},
434        COutPoint{tx2->GetHash(), 1},
435        COutPoint{tx3->GetHash(), 0},
436        COutPoint{tx3->GetHash(), 1},
437        COutPoint{tx3->GetHash(), 2},
438        COutPoint{tx4->GetHash(), 1},
439        COutPoint{tx5->GetHash(), 2},
440        COutPoint{tx6->GetHash(), 0},
441        COutPoint{tx7->GetHash(), 0}
442    });
443    for (const auto& outpoint : all_unspent_outpoints) BOOST_CHECK(!pool.isSpent(outpoint));
444
445    const auto tx2_feerate = CFeeRate(high_fee, tx_vsizes[2]);
446    const auto tx3_feerate = CFeeRate(high_fee, tx_vsizes[3]);
447    // tx3's feerate is lower than tx2's. same fee, different weight.
448    BOOST_CHECK(tx2_feerate > tx3_feerate);
449    const auto tx3_anc_feerate = CFeeRate(low_fee + med_fee + high_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]);
450    const auto& tx3_entry{*Assert(pool.GetEntry(tx3->GetHash()))};
451
452    // Check that ancestor feerate is calculated correctly.
453    auto [dummy_count, ancestor_vsize, mod_fees] = pool.CalculateAncestorData(tx3_entry);
454    BOOST_CHECK(tx3_anc_feerate == CFeeRate(mod_fees, ancestor_vsize));
455
456    const auto tx4_feerate = CFeeRate(high_fee, tx_vsizes[4]);
457    const auto tx6_anc_feerate = CFeeRate(high_fee + low_fee + med_fee, tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6]);
458    const auto& tx6_entry{*Assert(pool.GetEntry(tx6->GetHash()))};
459
460    std::tie(std::ignore, ancestor_vsize, mod_fees) = pool.CalculateAncestorData(tx6_entry);
461    BOOST_CHECK(tx6_anc_feerate == CFeeRate(mod_fees, ancestor_vsize));
462    const auto tx7_anc_feerate = CFeeRate(high_fee + low_fee + high_fee, tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[7]);
463    const auto& tx7_entry{*Assert(pool.GetEntry(tx7->GetHash()))};
464
465    std::tie(std::ignore, ancestor_vsize, mod_fees) = pool.CalculateAncestorData(tx7_entry);
466    BOOST_CHECK(tx7_anc_feerate == CFeeRate(mod_fees, ancestor_vsize));
467    BOOST_CHECK(tx4_feerate > tx6_anc_feerate);
468    BOOST_CHECK(tx4_feerate > tx7_anc_feerate);
469
470    // Extremely high feerate: everybody's bumpfee is from their full ancestor set.
471    {
472        node::MiniMiner mini_miner(pool, all_unspent_outpoints);
473        const CFeeRate very_high_feerate(COIN);
474        BOOST_CHECK(tx3_anc_feerate < very_high_feerate);
475        BOOST_CHECK(mini_miner.IsReadyToCalculate());
476        auto bump_fees = mini_miner.CalculateBumpFees(very_high_feerate);
477        BOOST_CHECK_EQUAL(bump_fees.size(), all_unspent_outpoints.size());
478        BOOST_CHECK(!mini_miner.IsReadyToCalculate());
479        BOOST_CHECK(sanity_check(all_transactions, bump_fees));
480        const auto tx0_bumpfee = bump_fees.find(COutPoint{tx0->GetHash(), 1});
481        BOOST_CHECK(tx0_bumpfee != bump_fees.end());
482        BOOST_CHECK_EQUAL(tx0_bumpfee->second, very_high_feerate.GetFee(tx_vsizes[0]) - low_fee);
483        const auto tx3_bumpfee = bump_fees.find(COutPoint{tx3->GetHash(), 0});
484        BOOST_CHECK(tx3_bumpfee != bump_fees.end());
485        BOOST_CHECK_EQUAL(tx3_bumpfee->second,
486            very_high_feerate.GetFee(tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]) - (low_fee + med_fee + high_fee + high_fee));
487        const auto tx6_bumpfee = bump_fees.find(COutPoint{tx6->GetHash(), 0});
488        BOOST_CHECK(tx6_bumpfee != bump_fees.end());
489        BOOST_CHECK_EQUAL(tx6_bumpfee->second,
490            very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[6]) - (high_fee + low_fee + med_fee));
491        const auto tx7_bumpfee = bump_fees.find(COutPoint{tx7->GetHash(), 0});
492        BOOST_CHECK(tx7_bumpfee != bump_fees.end());
493        BOOST_CHECK_EQUAL(tx7_bumpfee->second,
494            very_high_feerate.GetFee(tx_vsizes[4] + tx_vsizes[5] + tx_vsizes[7]) - (high_fee + low_fee + high_fee));
495        // Total fees: if spending multiple outputs from tx3 don't double-count fees.
496        node::MiniMiner mini_miner_total_tx3(pool, {COutPoint{tx3->GetHash(), 0}, COutPoint{tx3->GetHash(), 1}});
497        BOOST_CHECK(mini_miner_total_tx3.IsReadyToCalculate());
498        const auto tx3_bump_fee = mini_miner_total_tx3.CalculateTotalBumpFees(very_high_feerate);
499        BOOST_CHECK(!mini_miner_total_tx3.IsReadyToCalculate());
500        BOOST_CHECK(tx3_bump_fee.has_value());