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.

73,047 bytes · SHA-256 fdb2154729005346… · View upstream ↗

1// Copyright (c) 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 <cluster_linearize.h>
6#include <test/fuzz/FuzzedDataProvider.h>
7#include <test/fuzz/fuzz.h>
8#include <test/util/cluster_linearize.h>
9#include <test/util/random.h>
10#include <txgraph.h>
11#include <util/bitset.h>
12#include <util/feefrac.h>
13
14#include <algorithm>
15#include <cstdint>
16#include <iterator>
17#include <map>
18#include <memory>
19#include <ranges>
20#include <set>
21#include <utility>
22
23using namespace cluster_linearize;
24
25namespace {
26
27struct SimTxObject : public TxGraph::Ref
28{
29    // Use random uint64_t as txids for this simulation (0 = empty object).
30    const uint64_t m_txid{0};
31    SimTxObject() noexcept = default;
32    explicit SimTxObject(uint64_t txid) noexcept : m_txid(txid) {}
33};
34
35/** Data type representing a naive simulated TxGraph, keeping all transactions (even from
36 *  disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models
37 *  a single graph, and multiple instances are used to simulate main/staging. */
38struct SimTxGraph
39{
40    /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's
41     *  cluster count, so we can exercise situations with more transactions than fit in one
42     *  cluster. */
43    static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
44    /** Set type to use in the simulation. */
45    using SetType = BitSet<MAX_TRANSACTIONS>;
46    /** Data type for representing positions within SimTxGraph::graph. */
47    using Pos = DepGraphIndex;
48    /** Constant to mean "missing in this graph". */
49    static constexpr auto MISSING = Pos(-1);
50
51    /** The dependency graph (for all transactions in the simulation, regardless of
52     *  connectivity/clustering). */
53    DepGraph<SetType> graph;
54    /** For each position in graph, which SimTxObject it corresponds with (if any). Use shared_ptr
55     *  so that a SimTxGraph can be copied to create a staging one, while sharing Refs with
56     *  the main graph. */
57    std::array<std::shared_ptr<SimTxObject>, MAX_TRANSACTIONS> simmap;
58    /** For each TxGraph::Ref in graph, the position it corresponds with. */
59    std::map<const TxGraph::Ref*, Pos> simrevmap;
60    /** The set of SimTxObject entries that have been removed, but not yet destroyed. */
61    std::vector<std::shared_ptr<SimTxObject>> removed;
62    /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */
63    std::optional<bool> oversized;
64    /** The configured maximum number of transactions per cluster. */
65    DepGraphIndex max_cluster_count;
66    /** Which transactions have been modified in the graph since creation, either directly or by
67     *  being in a cluster which includes modifications. Only relevant for the staging graph. */
68    SetType modified;
69    /** The configured maximum total size of transactions per cluster. */
70    uint64_t max_cluster_size;
71    /** Whether the corresponding real graph is known to be optimally linearized. */
72    bool real_is_optimal{false};
73
74    /** Construct a new SimTxGraph with the specified maximum cluster count and size. */
75    explicit SimTxGraph(DepGraphIndex cluster_count, uint64_t cluster_size) :
76        max_cluster_count(cluster_count), max_cluster_size(cluster_size) {}
77
78    // Permit copying and moving.
79    SimTxGraph(const SimTxGraph&) noexcept = default;
80    SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
81    SimTxGraph(SimTxGraph&&) noexcept = default;
82    SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
83
84    /** Get the connected components within this simulated transaction graph. */
85    std::vector<SetType> GetComponents()
86    {
87        auto todo = graph.Positions();
88        std::vector<SetType> ret;
89        // Iterate over all connected components of the graph.
90        while (todo.Any()) {
91            auto component = graph.FindConnectedComponent(todo);
92            ret.push_back(component);
93            todo -= component;
94        }
95        return ret;
96    }
97
98    /** Check whether this graph is oversized (contains a connected component whose number of
99     *  transactions exceeds max_cluster_count. */
100    bool IsOversized()
101    {
102        if (!oversized.has_value()) {
103            // Only recompute when oversized isn't already known.
104            oversized = false;
105            for (auto component : GetComponents()) {
106                if (component.Count() > max_cluster_count) oversized = true;
107                uint64_t component_size{0};
108                for (auto i : component) component_size += graph.FeeRate(i).size;
109                if (component_size > max_cluster_size) oversized = true;
110            }
111        }
112        return *oversized;
113    }
114
115    void MakeModified(DepGraphIndex index)
116    {
117        modified |= graph.GetConnectedComponent(graph.Positions(), index);
118    }
119
120    /** Determine the number of (non-removed) transactions in the graph. */
121    DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
122
123    /** Get the sum of all fees/sizes in the graph. */
124    FeePerWeight SumAll() const
125    {
126        FeePerWeight ret;
127        for (auto i : graph.Positions()) {
128            ret += graph.FeeRate(i);
129        }
130        return ret;
131    }
132
133    /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */
134    Pos Find(const TxGraph::Ref* ref) const
135    {
136        auto it = simrevmap.find(ref);
137        if (it != simrevmap.end()) return it->second;
138        return MISSING;
139    }
140
141    /** Given a position in this simulated graph, get the corresponding SimTxObject. */
142    SimTxObject* GetRef(Pos pos)
143    {
144        assert(graph.Positions()[pos]);
145        assert(simmap[pos]);
146        return simmap[pos].get();
147    }
148
149    /** Add a new transaction to the simulation and the specified real graph. */
150    void AddTransaction(TxGraph& txgraph, const FeePerWeight& feerate, uint64_t txid)
151    {
152        assert(graph.TxCount() < MAX_TRANSACTIONS);
153        auto simpos = graph.AddTransaction(feerate);
154        real_is_optimal = false;
155        MakeModified(simpos);
156        assert(graph.Positions()[simpos]);
157        simmap[simpos] = std::make_shared<SimTxObject>(txid);
158        txgraph.AddTransaction(*simmap[simpos], feerate);
159        auto ptr = simmap[simpos].get();
160        simrevmap[ptr] = simpos;
161        // This may invalidate our cached oversized value.
162        if (oversized.has_value() && !*oversized) oversized = std::nullopt;
163    }
164
165    /** Add a dependency between two positions in this graph. */
166    void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
167    {
168        auto par_pos = Find(parent);
169        if (par_pos == MISSING) return;
170        auto chl_pos = Find(child);
171        if (chl_pos == MISSING) return;
172        graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
173        MakeModified(par_pos);
174        real_is_optimal = false;
175        // This may invalidate our cached oversized value.
176        if (oversized.has_value() && !*oversized) oversized = std::nullopt;
177    }
178
179    /** Modify the transaction fee of a ref, if it exists. */
180    void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
181    {
182        auto pos = Find(ref);
183        if (pos == MISSING) return;
184        // No need to invoke MakeModified, because this equally affects main and staging.
185        real_is_optimal = false;
186        graph.FeeRate(pos).fee = fee;
187    }
188
189    /** Remove the transaction in the specified position from the graph. */
190    void RemoveTransaction(TxGraph::Ref* ref)
191    {
192        auto pos = Find(ref);
193        if (pos == MISSING) return;
194        MakeModified(pos);
195        real_is_optimal = false;
196        graph.RemoveTransactions(SetType::Singleton(pos));
197        simrevmap.erase(simmap[pos].get());
198        // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
199        // invoked until the simulation explicitly decided to do so.
200        removed.push_back(std::move(simmap[pos]));
201        simmap[pos].reset();
202        // This may invalidate our cached oversized value.
203        if (oversized.has_value() && *oversized) oversized = std::nullopt;
204    }
205
206    /** Destroy the transaction from the graph, including from the removed set. This will
207     *  trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized
208     *  value is cleared (destroying does not clear oversizedness in TxGraph of the main
209     *  graph while staging exists). */
210    void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
211    {
212        auto pos = Find(ref);
213        if (pos == MISSING) {
214            // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
215            // than std::erase because we don't care about the order of the entries that
216            // remain.
217            auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
218            removed.erase(remove, removed.end());
219        } else {
220            MakeModified(pos);
221            graph.RemoveTransactions(SetType::Singleton(pos));
222            real_is_optimal = false;
223            simrevmap.erase(simmap[pos].get());
224            simmap[pos].reset();
225            // This may invalidate our cached oversized value.
226            if (reset_oversize && oversized.has_value() && *oversized) {
227                oversized = std::nullopt;
228            }
229        }
230    }
231
232    /** Construct the set with all positions in this graph corresponding to the specified
233     *  TxGraph::Refs. All of them must occur in this graph and not be removed. */
234    SetType MakeSet(std::span<TxGraph::Ref* const> arg)
235    {
236        SetType ret;
237        for (TxGraph::Ref* ptr : arg) {
238            auto pos = Find(ptr);
239            assert(pos != Pos(-1));
240            ret.Set(pos);
241        }
242        return ret;
243    }
244
245    /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */
246    SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
247    {
248        auto pos = Find(arg);
249        if (pos == MISSING) return {};
250        return desc ? graph.Descendants(pos) : graph.Ancestors(pos);

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.