LCOV - code coverage report
Current view: top level - src/node - mini_miner.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 0 232 0.0 %
Date: 2024-01-03 14:57:27 Functions: 0 14 0.0 %
Branches: 0 373 0.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2023 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 <node/mini_miner.h>
       6                 :            : 
       7                 :            : #include <boost/multi_index/detail/hash_index_iterator.hpp>
       8                 :            : #include <boost/operators.hpp>
       9                 :            : #include <consensus/amount.h>
      10                 :            : #include <policy/feerate.h>
      11                 :            : #include <primitives/transaction.h>
      12                 :            : #include <sync.h>
      13                 :            : #include <txmempool.h>
      14                 :            : #include <uint256.h>
      15                 :            : #include <util/check.h>
      16                 :            : 
      17                 :            : #include <algorithm>
      18                 :            : #include <numeric>
      19                 :            : #include <utility>
      20                 :            : 
      21                 :            : namespace node {
      22                 :            : 
      23                 :          0 : MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
      24                 :            : {
      25 [ #  # ][ #  # ]:          0 :     LOCK(mempool.cs);
      26                 :            :     // Find which outpoints to calculate bump fees for.
      27                 :            :     // Anything that's spent by the mempool is to-be-replaced
      28                 :            :     // Anything otherwise unavailable just has a bump fee of 0
      29         [ #  # ]:          0 :     for (const auto& outpoint : outpoints) {
      30 [ #  # ][ #  # ]:          0 :         if (!mempool.exists(GenTxid::Txid(outpoint.hash))) {
         [ #  # ][ #  # ]
      31                 :            :             // This UTXO is either confirmed or not yet submitted to mempool.
      32                 :            :             // If it's confirmed, no bump fee is required.
      33                 :            :             // If it's not yet submitted, we have no information, so return 0.
      34         [ #  # ]:          0 :             m_bump_fees.emplace(outpoint, 0);
      35                 :          0 :             continue;
      36                 :            :         }
      37                 :            : 
      38                 :            :         // UXTO is created by transaction in mempool, add to map.
      39                 :            :         // Note: This will either create a missing entry or add the outpoint to an existing entry
      40 [ #  # ][ #  # ]:          0 :         m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
                 [ #  # ]
      41                 :            : 
      42 [ #  # ][ #  # ]:          0 :         if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
      43                 :            :             // This outpoint is already being spent by another transaction in the mempool. We
      44                 :            :             // assume that the caller wants to replace this transaction and its descendants. It
      45                 :            :             // would be unusual for the transaction to have descendants as the wallet won’t normally
      46                 :            :             // attempt to replace transactions with descendants. If the outpoint is from a mempool
      47                 :            :             // transaction, we still need to calculate its ancestors bump fees (added to
      48                 :            :             // m_requested_outpoints_by_txid below), but after removing the to-be-replaced entries.
      49                 :            :             //
      50                 :            :             // Note that the descendants of a transaction include the transaction itself. Also note,
      51                 :            :             // that this is only calculating bump fees. RBF fee rules should be handled separately.
      52                 :          0 :             CTxMemPool::setEntries descendants;
      53 [ #  # ][ #  # ]:          0 :             mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
         [ #  # ][ #  # ]
                 [ #  # ]
      54         [ #  # ]:          0 :             for (const auto& desc_txiter : descendants) {
      55 [ #  # ][ #  # ]:          0 :                 m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
         [ #  # ][ #  # ]
                 [ #  # ]
      56                 :            :             }
      57                 :          0 :         }
      58                 :            :     }
      59                 :            : 
      60                 :            :     // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
      61         [ #  # ]:          0 :     if (m_requested_outpoints_by_txid.empty()) return;
      62                 :            : 
      63                 :            :     // Calculate the cluster and construct the entry map.
      64                 :          0 :     std::vector<uint256> txids_needed;
      65         [ #  # ]:          0 :     txids_needed.reserve(m_requested_outpoints_by_txid.size());
      66         [ #  # ]:          0 :     for (const auto& [txid, _]: m_requested_outpoints_by_txid) {
      67         [ #  # ]:          0 :         txids_needed.push_back(txid);
      68                 :            :     }
      69         [ #  # ]:          0 :     const auto cluster = mempool.GatherClusters(txids_needed);
      70         [ #  # ]:          0 :     if (cluster.empty()) {
      71                 :            :         // An empty cluster means that at least one of the transactions is missing from the mempool
      72                 :            :         // (should not be possible given processing above) or DoS limit was hit.
      73                 :          0 :         m_ready_to_calculate = false;
      74                 :          0 :         return;
      75                 :            :     }
      76                 :            : 
      77                 :            :     // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
      78         [ #  # ]:          0 :     for (const auto& txiter : cluster) {
      79 [ #  # ][ #  # ]:          0 :         if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
      80 [ #  # ][ #  # ]:          0 :             auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
         [ #  # ][ #  # ]
      81 [ #  # ][ #  # ]:          0 :                 MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
                 [ #  # ]
      82 [ #  # ][ #  # ]:          0 :                                       /*vsize_self=*/txiter->GetTxSize(),
      83 [ #  # ][ #  # ]:          0 :                                       /*vsize_ancestor=*/txiter->GetSizeWithAncestors(),
      84 [ #  # ][ #  # ]:          0 :                                       /*fee_self=*/txiter->GetModifiedFee(),
      85 [ #  # ][ #  # ]:          0 :                                       /*fee_ancestor=*/txiter->GetModFeesWithAncestors()});
      86 [ #  # ][ #  # ]:          0 :             m_entries.push_back(mapiter);
      87                 :          0 :         } else {
      88 [ #  # ][ #  # ]:          0 :             auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
         [ #  # ][ #  # ]
                 [ #  # ]
      89         [ #  # ]:          0 :             if (outpoints_it != m_requested_outpoints_by_txid.end()) {
      90                 :            :                 // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
      91                 :            :                 // this UTXO is impossible as it will no longer exist after the replacement.
      92         [ #  # ]:          0 :                 for (const auto& outpoint : outpoints_it->second) {
      93         [ #  # ]:          0 :                     m_bump_fees.emplace(outpoint, 0);
      94                 :            :                 }
      95         [ #  # ]:          0 :                 m_requested_outpoints_by_txid.erase(outpoints_it);
      96                 :          0 :             }
      97                 :            :         }
      98                 :            :     }
      99                 :            : 
     100                 :            :     // Build the m_descendant_set_by_txid cache.
     101         [ #  # ]:          0 :     for (const auto& txiter : cluster) {
     102 [ #  # ][ #  # ]:          0 :         const auto& txid = txiter->GetTx().GetHash();
                 [ #  # ]
     103                 :            :         // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
     104                 :          0 :         // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
     105                 :          0 :         std::vector<MockEntryMap::iterator> cached_descendants;
     106 [ #  # ][ #  # ]:          0 :         const bool remove{m_to_be_replaced.count(txid) > 0};
     107                 :          0 :         CTxMemPool::setEntries descendants;
     108         [ #  # ]:          0 :         mempool.CalculateDescendants(txiter, descendants);
     109 [ #  # ][ #  # ]:          0 :         Assume(descendants.count(txiter) > 0);
     110         [ #  # ]:          0 :         for (const auto& desc_txiter : descendants) {
     111 [ #  # ][ #  # ]:          0 :             const auto txid_desc = desc_txiter->GetTx().GetHash();
                 [ #  # ]
     112 [ #  # ][ #  # ]:          0 :             const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
     113 [ #  # ][ #  # ]:          0 :             auto desc_it{m_entries_by_txid.find(txid_desc)};
     114         [ #  # ]:          0 :             Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
     115 [ #  # ][ #  # ]:          0 :             if (remove) Assume(remove_desc);
     116                 :            :             // It's possible that remove=false but remove_desc=true.
     117 [ #  # ][ #  # ]:          0 :             if (!remove && !remove_desc) {
     118         [ #  # ]:          0 :                 cached_descendants.push_back(desc_it);
     119                 :          0 :             }
     120                 :            :         }
     121         [ #  # ]:          0 :         if (remove) {
     122         [ #  # ]:          0 :             Assume(cached_descendants.empty());
     123                 :          0 :         } else {
     124         [ #  # ]:          0 :             m_descendant_set_by_txid.emplace(txid, cached_descendants);
     125                 :            :         }
     126                 :          0 :     }
     127                 :            : 
     128                 :            :     // Release the mempool lock; we now have all the information we need for a subset of the entries
     129                 :            :     // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
     130         [ #  # ]:          0 :     Assume(m_in_block.empty());
     131         [ #  # ]:          0 :     Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
     132         [ #  # ]:          0 :     SanityCheck();
     133         [ #  # ]:          0 : }
     134                 :            : 
     135                 :          0 : MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
     136                 :            :                      const std::map<Txid, std::set<Txid>>& descendant_caches)
     137                 :            : {
     138         [ #  # ]:          0 :     for (const auto& entry : manual_entries) {
     139 [ #  # ][ #  # ]:          0 :         const auto& txid = entry.GetTx().GetHash();
     140                 :            :         // We need to know the descendant set of every transaction.
     141 [ #  # ][ #  # ]:          0 :         if (!Assume(descendant_caches.count(txid) > 0)) {
                 [ #  # ]
     142                 :          0 :             m_ready_to_calculate = false;
     143                 :          0 :             return;
     144                 :            :         }
     145                 :            :         // Just forward these args onto MiniMinerMempoolEntry
     146         [ #  # ]:          0 :         auto [mapiter, success] = m_entries_by_txid.emplace(txid, entry);
     147                 :            :         // Txids must be unique; this txid shouldn't already be an entry in m_entries_by_txid
     148 [ #  # ][ #  # ]:          0 :         if (Assume(success)) m_entries.push_back(mapiter);
         [ #  # ][ #  # ]
     149                 :            :     }
     150                 :            :     // Descendant cache is already built, but we need to translate them to m_entries_by_txid iters.
     151         [ #  # ]:          0 :     for (const auto& [txid, desc_txids] : descendant_caches) {
     152                 :            :         // Descendant cache should include at least the tx itself.
     153 [ #  # ][ #  # ]:          0 :         if (!Assume(!desc_txids.empty())) {
     154                 :          0 :             m_ready_to_calculate = false;
     155                 :          0 :             return;
     156                 :            :         }
     157                 :          0 :         std::vector<MockEntryMap::iterator> descendants;
     158         [ #  # ]:          0 :         for (const auto& desc_txid : desc_txids) {
     159 [ #  # ][ #  # ]:          0 :             auto desc_it{m_entries_by_txid.find(desc_txid)};
     160                 :            :             // Descendants should only include transactions with corresponding entries.
     161 [ #  # ][ #  # ]:          0 :             if (!Assume(desc_it != m_entries_by_txid.end())) {
     162                 :          0 :                 m_ready_to_calculate = false;
     163                 :          0 :                 return;
     164                 :            :             } else {
     165         [ #  # ]:          0 :                 descendants.emplace_back(desc_it);
     166                 :            :             }
     167                 :            :         }
     168 [ #  # ][ #  # ]:          0 :         m_descendant_set_by_txid.emplace(txid, descendants);
     169      [ #  #  # ]:          0 :     }
     170         [ #  # ]:          0 :     Assume(m_to_be_replaced.empty());
     171         [ #  # ]:          0 :     Assume(m_requested_outpoints_by_txid.empty());
     172         [ #  # ]:          0 :     Assume(m_bump_fees.empty());
     173         [ #  # ]:          0 :     Assume(m_inclusion_order.empty());
     174         [ #  # ]:          0 :     SanityCheck();
     175                 :          0 : }
     176                 :            : 
     177                 :            : // Compare by min(ancestor feerate, individual feerate), then iterator
     178                 :            : //
     179                 :            : // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
     180                 :            : // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
     181                 :            : // transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
     182                 :            : struct AncestorFeerateComparator
     183                 :            : {
     184                 :            :     template<typename I>
     185                 :          0 :     bool operator()(const I& a, const I& b) const {
     186                 :          0 :         auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
     187                 :          0 :             const CAmount ancestor_fee{e.GetModFeesWithAncestors()};
     188                 :          0 :             const int64_t ancestor_size{e.GetSizeWithAncestors()};
     189                 :          0 :             const CAmount tx_fee{e.GetModifiedFee()};
     190                 :          0 :             const int64_t tx_size{e.GetTxSize()};
     191                 :            :             // Comparing ancestor feerate with individual feerate:
     192                 :            :             //     ancestor_fee / ancestor_size <= tx_fee / tx_size
     193                 :            :             // Avoid division and possible loss of precision by
     194                 :            :             // multiplying both sides by the sizes:
     195         [ #  # ]:          0 :             return ancestor_fee * tx_size < tx_fee * ancestor_size ?
     196                 :          0 :                        CFeeRate(ancestor_fee, ancestor_size) :
     197                 :          0 :                        CFeeRate(tx_fee, tx_size);
     198                 :            :         };
     199                 :          0 :         CFeeRate a_feerate{min_feerate(a->second)};
     200                 :          0 :         CFeeRate b_feerate{min_feerate(b->second)};
     201         [ #  # ]:          0 :         if (a_feerate != b_feerate) {
     202                 :          0 :             return a_feerate > b_feerate;
     203                 :            :         }
     204                 :            :         // Use txid as tiebreaker for stable sorting
     205                 :          0 :         return a->first < b->first;
     206                 :          0 :     }
     207                 :            : };
     208                 :            : 
     209                 :          0 : void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
     210                 :            : {
     211                 :          0 :     Assume(ancestors.size() >= 1);
     212                 :            :     // "Mine" all transactions in this ancestor set.
     213         [ #  # ]:          0 :     for (auto& anc : ancestors) {
     214                 :          0 :         Assume(m_in_block.count(anc->first) == 0);
     215                 :          0 :         m_in_block.insert(anc->first);
     216                 :          0 :         m_total_fees += anc->second.GetModifiedFee();
     217                 :          0 :         m_total_vsize += anc->second.GetTxSize();
     218                 :          0 :         auto it = m_descendant_set_by_txid.find(anc->first);
     219                 :            :         // Each entry’s descendant set includes itself
     220                 :          0 :         Assume(it != m_descendant_set_by_txid.end());
     221         [ #  # ]:          0 :         for (auto& descendant : it->second) {
     222                 :            :             // If these fail, we must be double-deducting.
     223                 :          0 :             Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
     224                 :          0 :             Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
     225                 :          0 :             descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
     226                 :            :         }
     227                 :            :     }
     228                 :            :     // Delete these entries.
     229         [ #  # ]:          0 :     for (const auto& anc : ancestors) {
     230                 :          0 :         m_descendant_set_by_txid.erase(anc->first);
     231                 :            :         // The above loop should have deducted each ancestor's size and fees from each of their
     232                 :            :         // respective descendants exactly once.
     233                 :          0 :         Assume(anc->second.GetModFeesWithAncestors() == 0);
     234                 :          0 :         Assume(anc->second.GetSizeWithAncestors() == 0);
     235                 :          0 :         auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
     236                 :          0 :         Assume(vec_it != m_entries.end());
     237                 :          0 :         m_entries.erase(vec_it);
     238                 :          0 :         m_entries_by_txid.erase(anc);
     239                 :            :     }
     240                 :          0 : }
     241                 :            : 
     242                 :          0 : void MiniMiner::SanityCheck() const
     243                 :            : {
     244                 :            :     // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
     245                 :          0 :     Assume(m_entries.size() == m_entries_by_txid.size());
     246                 :          0 :     Assume(m_entries.size() == m_descendant_set_by_txid.size());
     247                 :            :     // Cached ancestor values should be at least as large as the transaction's own fee and size
     248         [ #  # ]:          0 :     Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
     249                 :            :         return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
     250                 :            :                entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
     251                 :            :     // None of the entries should be to-be-replaced transactions
     252                 :          0 :     Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
     253                 :            :         [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
     254                 :          0 : }
     255                 :            : 
     256                 :          0 : void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
     257                 :            : {
     258                 :          0 :     const auto num_txns{m_entries_by_txid.size()};
     259                 :          0 :     uint32_t sequence_num{0};
     260         [ #  # ]:          0 :     while (!m_entries_by_txid.empty()) {
     261                 :            :         // Sort again, since transaction removal may change some m_entries' ancestor feerates.
     262                 :          0 :         std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
     263                 :            : 
     264                 :            :         // Pick highest ancestor feerate entry.
     265                 :          0 :         auto best_iter = m_entries.begin();
     266                 :          0 :         Assume(best_iter != m_entries.end());
     267                 :          0 :         const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
     268                 :          0 :         const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
     269                 :            :         // Stop here. Everything that didn't "make it into the block" has bumpfee.
     270 [ #  # ][ #  # ]:          0 :         if (target_feerate.has_value() &&
     271                 :          0 :             ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) {
     272                 :          0 :             break;
     273                 :            :         }
     274                 :            : 
     275                 :            :         // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
     276                 :            :         // change at every iteration, so this is more efficient than maintaining a cache.
     277                 :          0 :         std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
     278                 :            :         {
     279                 :          0 :             std::set<MockEntryMap::iterator, IteratorComparator> to_process;
     280         [ #  # ]:          0 :             to_process.insert(*best_iter);
     281         [ #  # ]:          0 :             while (!to_process.empty()) {
     282                 :          0 :                 auto iter = to_process.begin();
     283         [ #  # ]:          0 :                 Assume(iter != to_process.end());
     284         [ #  # ]:          0 :                 ancestors.insert(*iter);
     285 [ #  # ][ #  # ]:          0 :                 for (const auto& input : (*iter)->second.GetTx().vin) {
     286 [ #  # ][ #  # ]:          0 :                     if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
                 [ #  # ]
     287 [ #  # ][ #  # ]:          0 :                         if (ancestors.count(parent_it) == 0) {
     288         [ #  # ]:          0 :                             to_process.insert(parent_it);
     289                 :          0 :                         }
     290                 :          0 :                     }
     291                 :            :                 }
     292         [ #  # ]:          0 :                 to_process.erase(iter);
     293                 :            :             }
     294                 :          0 :         }
     295                 :            :         // Track the order in which transactions were selected.
     296         [ #  # ]:          0 :         for (const auto& ancestor : ancestors) {
     297 [ #  # ][ #  # ]:          0 :             m_inclusion_order.emplace(Txid::FromUint256(ancestor->first), sequence_num);
     298                 :            :         }
     299         [ #  # ]:          0 :         DeleteAncestorPackage(ancestors);
     300         [ #  # ]:          0 :         SanityCheck();
     301                 :          0 :         ++sequence_num;
     302                 :          0 :     }
     303         [ #  # ]:          0 :     if (!target_feerate.has_value()) {
     304                 :          0 :         Assume(m_in_block.size() == num_txns);
     305                 :          0 :     } else {
     306         [ #  # ]:          0 :         Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize));
     307                 :            :     }
     308         [ #  # ]:          0 :     Assume(m_in_block.empty() || sequence_num > 0);
     309                 :          0 :     Assume(m_in_block.size() == m_inclusion_order.size());
     310                 :            :     // Do not try to continue building the block template with a different feerate.
     311                 :          0 :     m_ready_to_calculate = false;
     312                 :          0 : }
     313                 :            : 
     314                 :            : 
     315                 :          0 : std::map<Txid, uint32_t> MiniMiner::Linearize()
     316                 :            : {
     317                 :          0 :     BuildMockTemplate(std::nullopt);
     318                 :          0 :     return m_inclusion_order;
     319                 :            : }
     320                 :            : 
     321                 :          0 : std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
     322                 :            : {
     323         [ #  # ]:          0 :     if (!m_ready_to_calculate) return {};
     324                 :            :     // Build a block template until the target feerate is hit.
     325                 :          0 :     BuildMockTemplate(target_feerate);
     326                 :            : 
     327                 :            :     // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
     328                 :            :     // ancestor package with at least the target feerate and don't need to be bumped.
     329         [ #  # ]:          0 :     for (const auto& txid : m_in_block) {
     330                 :            :         // Not all of the block transactions were necessarily requested.
     331                 :          0 :         auto it = m_requested_outpoints_by_txid.find(txid);
     332         [ #  # ]:          0 :         if (it != m_requested_outpoints_by_txid.end()) {
     333         [ #  # ]:          0 :             for (const auto& outpoint : it->second) {
     334                 :          0 :                 m_bump_fees.emplace(outpoint, 0);
     335                 :            :             }
     336                 :          0 :             m_requested_outpoints_by_txid.erase(it);
     337                 :          0 :         }
     338                 :            :     }
     339                 :            : 
     340                 :            :     // A transactions and its ancestors will only be picked into a block when
     341                 :            :     // both the ancestor set feerate and the individual feerate meet the target
     342                 :            :     // feerate.
     343                 :            :     //
     344                 :            :     // We had to convince ourselves that after running the mini miner and
     345                 :            :     // picking all eligible transactions into our MockBlockTemplate, there
     346                 :            :     // could still be transactions remaining that have a lower individual
     347                 :            :     // feerate than their ancestor feerate. So here is an example:
     348                 :            :     //
     349                 :            :     //               ┌─────────────────┐
     350                 :            :     //               │                 │
     351                 :            :     //               │   Grandparent   │
     352                 :            :     //               │    1700 vB      │
     353                 :            :     //               │    1700 sats    │                    Target feerate: 10    s/vB
     354                 :            :     //               │       1 s/vB    │    GP Ancestor Set Feerate (ASFR):  1    s/vB
     355                 :            :     //               │                 │                           P1_ASFR:  9.84 s/vB
     356                 :            :     //               └──────▲───▲──────┘                           P2_ASFR:  2.47 s/vB
     357                 :            :     //                      │   │                                   C_ASFR: 10.27 s/vB
     358                 :            :     // ┌───────────────┐    │   │    ┌──────────────┐
     359                 :            :     // │               ├────┘   └────┤              │             ⇒ C_FR < TFR < C_ASFR
     360                 :            :     // │   Parent 1    │             │   Parent 2   │
     361                 :            :     // │    200 vB     │             │    200 vB    │
     362                 :            :     // │  17000 sats   │             │   3000 sats  │
     363                 :            :     // │     85 s/vB   │             │     15 s/vB  │
     364                 :            :     // │               │             │              │
     365                 :            :     // └───────────▲───┘             └───▲──────────┘
     366                 :            :     //             │                     │
     367                 :            :     //             │    ┌───────────┐    │
     368                 :            :     //             └────┤           ├────┘
     369                 :            :     //                  │   Child   │
     370                 :            :     //                  │  100 vB   │
     371                 :            :     //                  │  900 sats │
     372                 :            :     //                  │    9 s/vB │
     373                 :            :     //                  │           │
     374                 :            :     //                  └───────────┘
     375                 :            :     //
     376                 :            :     // We therefore calculate both the bump fee that is necessary to elevate
     377                 :            :     // the individual transaction to the target feerate:
     378                 :            :     //         target_feerate × tx_size - tx_fees
     379                 :            :     // and the bump fee that is necessary to bump the entire ancestor set to
     380                 :            :     // the target feerate:
     381                 :            :     //         target_feerate × ancestor_set_size - ancestor_set_fees
     382                 :            :     // By picking the maximum from the two, we ensure that a transaction meets
     383                 :            :     // both criteria.
     384         [ #  # ]:          0 :     for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
     385                 :          0 :         auto it = m_entries_by_txid.find(txid);
     386                 :          0 :         Assume(it != m_entries_by_txid.end());
     387         [ #  # ]:          0 :         if (it != m_entries_by_txid.end()) {
     388                 :          0 :             Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
     389                 :          0 :             CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
     390                 :          0 :             CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
     391                 :          0 :             const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
     392                 :          0 :             Assume(bump_fee >= 0);
     393         [ #  # ]:          0 :             for (const auto& outpoint : outpoints) {
     394                 :          0 :                 m_bump_fees.emplace(outpoint, bump_fee);
     395                 :            :             }
     396                 :          0 :         }
     397                 :            :     }
     398                 :          0 :     return m_bump_fees;
     399                 :          0 : }
     400                 :            : 
     401                 :          0 : std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
     402                 :            : {
     403         [ #  # ]:          0 :     if (!m_ready_to_calculate) return std::nullopt;
     404                 :            :     // Build a block template until the target feerate is hit.
     405                 :          0 :     BuildMockTemplate(target_feerate);
     406                 :            : 
     407                 :            :     // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
     408                 :          0 :     std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
     409                 :          0 :     std::set<MockEntryMap::iterator, IteratorComparator> to_process;
     410         [ #  # ]:          0 :     for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
     411                 :            :         // Skip any ancestors that already have a miner score higher than the target feerate
     412                 :            :         // (already "made it" into the block)
     413 [ #  # ][ #  # ]:          0 :         if (m_in_block.count(txid)) continue;
                 [ #  # ]
     414 [ #  # ][ #  # ]:          0 :         auto iter = m_entries_by_txid.find(txid);
     415         [ #  # ]:          0 :         if (iter == m_entries_by_txid.end()) continue;
     416         [ #  # ]:          0 :         to_process.insert(iter);
     417         [ #  # ]:          0 :         ancestors.insert(iter);
     418                 :            :     }
     419                 :            : 
     420                 :          0 :     std::set<uint256> has_been_processed;
     421         [ #  # ]:          0 :     while (!to_process.empty()) {
     422                 :          0 :         auto iter = to_process.begin();
     423         [ #  # ]:          0 :         const CTransaction& tx = (*iter)->second.GetTx();
     424         [ #  # ]:          0 :         for (const auto& input : tx.vin) {
     425 [ #  # ][ #  # ]:          0 :             if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
                 [ #  # ]
     426 [ #  # ][ #  # ]:          0 :                 if (!has_been_processed.count(input.prevout.hash)) {
                 [ #  # ]
     427         [ #  # ]:          0 :                     to_process.insert(parent_it);
     428                 :          0 :                 }
     429         [ #  # ]:          0 :                 ancestors.insert(parent_it);
     430                 :          0 :             }
     431                 :            :         }
     432 [ #  # ][ #  # ]:          0 :         has_been_processed.insert(tx.GetHash());
                 [ #  # ]
     433         [ #  # ]:          0 :         to_process.erase(iter);
     434                 :            :     }
     435         [ #  # ]:          0 :     const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
     436                 :          0 :         [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
     437         [ #  # ]:          0 :     const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
     438                 :          0 :         [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
     439         [ #  # ]:          0 :     return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
     440                 :          0 : }
     441                 :            : } // namespace node

Generated by: LCOV version 1.14