READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server440 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

21,037 bytes · SHA-256 bffb439c6efe15c9… · View upstream ↗

1// Copyright (c) 2023-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 <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 <ranges>
20#include <utility>
21
22namespace node {
23
24MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
25{
26    LOCK(mempool.cs);
27    // Find which outpoints to calculate bump fees for.
28    // Anything that's spent by the mempool is to-be-replaced
29    // Anything otherwise unavailable just has a bump fee of 0
30    for (const auto& outpoint : outpoints) {
31        if (!mempool.exists(outpoint.hash)) {
32            // This UTXO is either confirmed or not yet submitted to mempool.
33            // If it's confirmed, no bump fee is required.
34            // If it's not yet submitted, we have no information, so return 0.
35            m_bump_fees.emplace(outpoint, 0);
36            continue;
37        }
38
39        // UXTO is created by transaction in mempool, add to map.
40        // Note: This will either create a missing entry or add the outpoint to an existing entry
41        m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
42
43        if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
44            // This outpoint is already being spent by another transaction in the mempool. We
45            // assume that the caller wants to replace this transaction and its descendants. It
46            // would be unusual for the transaction to have descendants as the wallet won’t normally
47            // attempt to replace transactions with descendants. If the outpoint is from a mempool
48            // transaction, we still need to calculate its ancestors bump fees (added to
49            // m_requested_outpoints_by_txid below), but after removing the to-be-replaced entries.
50            //
51            // Note that the descendants of a transaction include the transaction itself. Also note,
52            // that this is only calculating bump fees. RBF fee rules should be handled separately.
53            CTxMemPool::setEntries descendants;
54            mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
55            for (const auto& desc_txiter : descendants) {
56                m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
57            }
58        }
59    }
60
61    // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
62    if (m_requested_outpoints_by_txid.empty()) return;
63
64    // Calculate the cluster and construct the entry map.
65    auto txids_needed{m_requested_outpoints_by_txid | std::views::keys};
66    const auto cluster = mempool.GatherClusters({txids_needed.begin(), txids_needed.end()});
67    if (cluster.empty()) {
68        // An empty cluster means that at least one of the transactions is missing from the mempool
69        // (should not be possible given processing above) or DoS limit was hit.
70        m_ready_to_calculate = false;
71        return;
72    }
73
74    // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
75    for (const auto& txiter : cluster) {
76        if (!m_to_be_replaced.contains(txiter->GetTx().GetHash())) {
77            auto [ancestor_count, ancestor_size, ancestor_fee] = mempool.CalculateAncestorData(*txiter);
78            auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
79                MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
80                                      /*vsize_self=*/txiter->GetTxSize(),
81                                      /*vsize_ancestor=*/int64_t(ancestor_size),
82                                      /*fee_self=*/txiter->GetModifiedFee(),
83                                      /*fee_ancestor=*/ancestor_fee});
84            m_entries.push_back(mapiter);
85        } else {
86            auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
87            if (outpoints_it != m_requested_outpoints_by_txid.end()) {
88                // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
89                // this UTXO is impossible as it will no longer exist after the replacement.
90                for (const auto& outpoint : outpoints_it->second) {
91                    m_bump_fees.emplace(outpoint, 0);
92                }
93                m_requested_outpoints_by_txid.erase(outpoints_it);
94            }
95        }
96    }
97
98    // Build the m_descendant_set_by_txid cache.
99    for (const auto& txiter : cluster) {
100        const auto& txid = txiter->GetTx().GetHash();
101        // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
102        // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
103        std::vector<MockEntryMap::iterator> cached_descendants;
104        const bool remove{m_to_be_replaced.contains(txid)};
105        CTxMemPool::setEntries descendants;
106        mempool.CalculateDescendants(txiter, descendants);
107        Assume(descendants.contains(txiter));
108        for (const auto& desc_txiter : descendants) {
109            const auto txid_desc = desc_txiter->GetTx().GetHash();
110            const bool remove_desc{m_to_be_replaced.contains(txid_desc)};
111            auto desc_it{m_entries_by_txid.find(txid_desc)};
112            Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
113            if (remove) Assume(remove_desc);
114            // It's possible that remove=false but remove_desc=true.
115            if (!remove && !remove_desc) {
116                cached_descendants.push_back(desc_it);
117            }
118        }
119        if (remove) {
120            Assume(cached_descendants.empty());
121        } else {
122            m_descendant_set_by_txid.emplace(txid, cached_descendants);
123        }
124    }
125
126    // Release the mempool lock; we now have all the information we need for a subset of the entries
127    // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
128    Assume(m_in_block.empty());
129    Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
130    SanityCheck();
131}
132
133MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
134                     const std::map<Txid, std::set<Txid>>& descendant_caches)
135{
136    for (const auto& entry : manual_entries) {
137        const auto& txid = entry.GetTx().GetHash();
138        // We need to know the descendant set of every transaction.
139        if (!Assume(descendant_caches.contains(txid))) {
140            m_ready_to_calculate = false;
141            return;
142        }
143        // Just forward these args onto MiniMinerMempoolEntry
144        auto [mapiter, success] = m_entries_by_txid.emplace(txid, entry);
145        // Txids must be unique; this txid shouldn't already be an entry in m_entries_by_txid
146        if (Assume(success)) m_entries.push_back(mapiter);
147    }
148    // Descendant cache is already built, but we need to translate them to m_entries_by_txid iters.
149    for (const auto& [txid, desc_txids] : descendant_caches) {
150        // Descendant cache should include at least the tx itself.
151        if (!Assume(!desc_txids.empty())) {
152            m_ready_to_calculate = false;
153            return;
154        }
155        std::vector<MockEntryMap::iterator> descendants;
156        for (const auto& desc_txid : desc_txids) {
157            auto desc_it{m_entries_by_txid.find(desc_txid)};
158            // Descendants should only include transactions with corresponding entries.
159            if (!Assume(desc_it != m_entries_by_txid.end())) {
160                m_ready_to_calculate = false;
161                return;
162            } else {
163                descendants.emplace_back(desc_it);
164            }
165        }
166        m_descendant_set_by_txid.emplace(txid, descendants);
167    }
168    Assume(m_to_be_replaced.empty());
169    Assume(m_requested_outpoints_by_txid.empty());
170    Assume(m_bump_fees.empty());
171    Assume(m_inclusion_order.empty());
172    SanityCheck();
173}
174
175// Compare by min(ancestor feerate, individual feerate), then txid
176//
177// Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
178// parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
179// transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
180struct AncestorFeerateComparator
181{
182    template<typename I>
183    bool operator()(const I& a, const I& b) const {
184        auto min_feerate = [](const MiniMinerMempoolEntry& e) -> FeeFrac {
185            FeeFrac self_feerate(e.GetModifiedFee(), e.GetTxSize());
186            FeeFrac ancestor_feerate(e.GetModFeesWithAncestors(), e.GetSizeWithAncestors());
187            return std::min<ByRatioNegSize<FeeFrac>>(ancestor_feerate, self_feerate);
188        };
189        FeeFrac a_feerate{min_feerate(a->second)};
190        FeeFrac b_feerate{min_feerate(b->second)};
191        if (a_feerate != b_feerate) {
192            return ByRatioNegSize{a_feerate} > ByRatioNegSize{b_feerate};
193        }
194        // Use txid as tiebreaker for stable sorting
195        return a->first < b->first;
196    }
197};
198
199void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
200{
201    Assume(ancestors.size() >= 1);
202    // "Mine" all transactions in this ancestor set.
203    for (auto& anc : ancestors) {
204        Assume(!m_in_block.contains(anc->first));
205        m_in_block.insert(anc->first);
206        m_total_fees += anc->second.GetModifiedFee();
207        m_total_vsize += anc->second.GetTxSize();
208        auto it = m_descendant_set_by_txid.find(anc->first);
209        // Each entry’s descendant set includes itself
210        Assume(it != m_descendant_set_by_txid.end());
211        for (auto& descendant : it->second) {
212            // If this fails, we must be double-deducting. Don't check fees because negative is possible.
213            Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
214            descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
215        }
216    }
217    // Delete these entries.
218    for (const auto& anc : ancestors) {
219        m_descendant_set_by_txid.erase(anc->first);
220        // The above loop should have deducted each ancestor's size and fees from each of their
221        // respective descendants exactly once.
222        Assume(anc->second.GetModFeesWithAncestors() == 0);
223        Assume(anc->second.GetSizeWithAncestors() == 0);
224        auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
225        Assume(vec_it != m_entries.end());
226        m_entries.erase(vec_it);
227        m_entries_by_txid.erase(anc);
228    }
229}
230
231void MiniMiner::SanityCheck() const
232{
233    // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
234    Assume(m_entries.size() == m_entries_by_txid.size());
235    Assume(m_entries.size() == m_descendant_set_by_txid.size());
236    // Cached ancestor values should be at least as large as the transaction's own size
237    Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
238        return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize();}));
239    // None of the entries should be to-be-replaced transactions
240    Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
241        [&](const auto& txid){ return !m_entries_by_txid.contains(txid); }));
242}
243
244void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
245{
246    const auto num_txns{m_entries_by_txid.size()};
247    uint32_t sequence_num{0};
248    while (!m_entries_by_txid.empty()) {
249        // Sort again, since transaction removal may change some m_entries' ancestor feerates.
250        std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

src/clientversion.cpp

src/common/signmessage.cpp

src/compat/assumptions.h

src/compat/byteswap.h

src/deploymentinfo.cpp

src/deploymentinfo.h

src/deploymentstatus.cpp

src/deploymentstatus.h

src/dummywallet.cpp

src/external_signer.h

src/init/bitcoin-gui.cpp

src/init/bitcoin-node.cpp

src/init/bitcoin-qt.cpp

src/init/bitcoin-wallet.cpp

src/init/bitcoind.cpp

src/init/common.h

src/interfaces/init.h

src/interfaces/ipc.h

src/key_io.h

src/logging/categories.h

src/logging/timer.h

src/mapport.h

src/musig.h

src/net_permissions.h

src/netgroup.h

src/netmessagemaker.h

src/node/chainstatemanager_args.cpp

src/node/connection_types.h

src/node/context.h

src/node/interface_ui.h

src/node/mempool_args.cpp

src/node/mining_args.cpp

src/node/minisketchwrapper.cpp

src/node/txreconciliation.h

src/policy/fees/estimator_args.cpp

src/policy/fees/estimator_args.h

src/policy/fees/estimator_man.cpp

src/policy/fees/estimator_man.h

src/policy/packages.h

src/policy/rbf.h

src/policy/truc_policy.h

src/pow.h

src/primitives/block.cpp

src/randomenv.h

src/rest.h

src/script/keyorigin.h

src/script/parsing.cpp

src/script/parsing.h

src/script/script_error.h

src/script/sigcache.cpp

src/script/sigcache.h

src/script/solver.h

src/script/verify_flags.h

src/semaphore_grant.h

src/signet.h

src/span.h

src/support/allocators/secure.h

src/support/allocators/zeroafterfree.h

src/util/tokenpipe.cpp

src/util/translation.h

src/util/vector.h

src/versionbits.h

src/versionbits_impl.h

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/fees.h

src/wallet/load.h

src/wallet/receive.h

src/wallet/rpc/wallet.h

src/wallet/types.h

src/walletinitinterface.h

src/zmq/zmqabstractnotifier.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.