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.

55,143 bytes · SHA-256 e5cec8c287fd331a… · 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 <random.h>
7#include <serialize.h>
8#include <streams.h>
9#include <test/fuzz/FuzzedDataProvider.h>
10#include <test/fuzz/fuzz.h>
11#include <test/util/cluster_linearize.h>
12#include <util/bitset.h>
13#include <util/feefrac.h>
14
15#include <algorithm>
16#include <cstdint>
17#include <utility>
18#include <vector>
19
20/*
21 * The tests in this file primarily cover the candidate finder classes and linearization algorithms.
22 *
23 *   <----: An implementation (at the start of the line --) is tested in the test marked with *,
24 *          possibly by comparison with other implementations (at the end of the line ->).
25 *   <<---: The right side is implemented using the left side.
26 *
27 *   +---------------------+                        +-----------+
28 *   | SpanningForestState | <<-------------------- | Linearize |
29 *   +---------------------+                        +-----------+
30 *               |                                       |
31 *               |                                       |        ^^  PRODUCTION CODE
32 *               |                                       |        ||
33 *  ==============================================================================================
34 *               |                                       |        ||
35 *               |-clusterlin_sfl*                       |        vv  TEST CODE
36 *               |                                       |
37 *               \------------------------------------\  |-clusterlin_linearize*
38 *                                                    |  |
39 *                                                    v  v
40 *   +-----------------------+                      +-----------------+
41 *   | SimpleCandidateFinder | <<-------------------| SimpleLinearize |
42 *   +-----------------------+                      +-----------------+
43 *                  |                                    |
44 *                  |-clusterlin_simple_finder*          |-clusterlin_simple_linearize*
45 *                  v                                    v
46 *   +---------------------------+                  +---------------------+
47 *   | ExhaustiveCandidateFinder |                  | ExhaustiveLinearize |
48 *   +---------------------------+                  +---------------------+
49 *
50 * More tests are included for lower-level and related functions and classes:
51 * - DepGraph tests:
52 *   - clusterlin_depgraph_sim
53 *   - clusterlin_depgraph_serialization
54 *   - clusterlin_components
55 * - ChunkLinearization and ChunkLinearizationInfo tests:
56 *   - clusterlin_chunking
57 * - PostLinearize tests:
58 *   - clusterlin_postlinearize
59 *   - clusterlin_postlinearize_tree
60 *   - clusterlin_postlinearize_moved_leaf
61 * - MakeConnected tests (a test-only function):
62 *   - clusterlin_make_connected
63 */
64
65using namespace cluster_linearize;
66
67namespace {
68
69/** A simple finder class for candidate sets (topologically-valid subsets with high feerate), only
70 *  used by SimpleLinearize below. */
71template<typename SetType>
72class SimpleCandidateFinder
73{
74    /** Internal dependency graph. */
75    const DepGraph<SetType>& m_depgraph;
76    /** Which transaction are left to include. */
77    SetType m_todo;
78
79public:
80    /** Construct an SimpleCandidateFinder for a given graph. */
81    SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
82        m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
83
84    /** Remove a set of transactions from the set of to-be-linearized ones. */
85    void MarkDone(SetType select) noexcept { m_todo -= select; }
86
87    /** Determine whether unlinearized transactions remain. */
88    bool AllDone() const noexcept { return m_todo.None(); }
89
90    /** Find a candidate set using at most max_iterations iterations, and the number of iterations
91     *  actually performed. If that number is less than max_iterations, then the result is optimal.
92     *
93     * Always returns a connected set of transactions.
94     *
95     * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
96     *             That number is bounded by M <= 2^(N-1).
97     */
98    std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
99    {
100        uint64_t iterations_left = max_iterations;
101        // Queue of work units. Each consists of:
102        // - inc: set of transactions definitely included
103        // - und: set of transactions that can be added to inc still
104        std::vector<std::pair<SetType, SetType>> queue;
105        // Initially we have just one queue element, with the entire graph in und.
106        queue.emplace_back(SetType{}, m_todo);
107        // Best solution so far. Initialize with the remaining ancestors of the first remaining
108        // transaction.
109        SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
110        // Process the queue.
111        while (!queue.empty() && iterations_left) {
112            // Pop top element of the queue.
113            auto [inc, und] = queue.back();
114            queue.pop_back();
115            // Look for a transaction to consider adding/removing.
116            bool inc_none = inc.None();
117            for (auto split : und) {
118                // If inc is empty, consider any split transaction. Otherwise only consider
119                // transactions that share ancestry with inc so far (which means only connected
120                // sets will be considered).
121                if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
122                    --iterations_left;
123                    // Add a queue entry with split included.
124                    SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
125                    queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
126                    // Add a queue entry with split excluded.
127                    queue.emplace_back(inc, und - m_depgraph.Descendants(split));
128                    // Update statistics to account for the candidate new_inc.
129                    if (ByRatioNegSize{new_inc.feerate} > ByRatioNegSize{best.feerate}) best = new_inc;
130                    break;
131                }
132            }
133        }
134        return {std::move(best), max_iterations - iterations_left};
135    }
136};
137
138/** A very simple finder class for optimal candidate sets, which tries every subset.
139 *
140 * It is even simpler than SimpleCandidateFinder, and exists just to help test the correctness of
141 * SimpleCandidateFinder, so that it can be used in SimpleLinearize, which is then used to test the
142 * correctness of Linearize.
143 */
144template<typename SetType>
145class ExhaustiveCandidateFinder
146{
147    /** Internal dependency graph. */
148    const DepGraph<SetType>& m_depgraph;
149    /** Which transaction are left to include. */
150    SetType m_todo;
151
152public:
153    /** Construct an ExhaustiveCandidateFinder for a given graph. */
154    ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
155        m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
156
157    /** Remove a set of transactions from the set of to-be-linearized ones. */
158    void MarkDone(SetType select) noexcept { m_todo -= select; }
159
160    /** Determine whether unlinearized transactions remain. */
161    bool AllDone() const noexcept { return m_todo.None(); }
162
163    /** Find the optimal remaining candidate set.
164     *
165     * Complexity: O(N * 2^N).
166     */
167    SetInfo<SetType> FindCandidateSet() const noexcept
168    {
169        // Best solution so far.
170        SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
171        // The number of combinations to try.
172        uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
173        // Try the transitive closure of every non-empty subset of m_todo.
174        for (uint64_t x = 1; x < limit; ++x) {
175            // If bit number b is set in x, then the remaining ancestors of the b'th remaining
176            // transaction in m_todo are included.
177            SetType txn;
178            auto x_shifted{x};
179            for (auto i : m_todo) {
180                if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
181                x_shifted >>= 1;
182            }
183            SetInfo cur(m_depgraph, txn & m_todo);
184            if (ByRatioNegSize{cur.feerate} > ByRatioNegSize{best.feerate}) best = cur;
185        }
186        return best;
187    }
188};
189
190/** A simple linearization algorithm.
191 *
192 * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
193 * the ability to pass in an existing linearization, and linearizing by simply finding the
194 * consecutive remaining highest-feerate topological subset using SimpleCandidateFinder.
195 */
196template<typename SetType>
197std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
198{
199    std::vector<DepGraphIndex> linearization;
200    SimpleCandidateFinder finder(depgraph);
201    SetType todo = depgraph.Positions();
202    bool optimal = true;
203    while (todo.Any()) {
204        auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
205        if (iterations_done == max_iterations) optimal = false;
206        depgraph.AppendTopo(linearization, candidate.transactions);
207        todo -= candidate.transactions;
208        finder.MarkDone(candidate.transactions);
209        max_iterations -= iterations_done;
210    }
211    return {std::move(linearization), optimal};
212}
213
214/** An even simpler linearization algorithm that tries all permutations.
215 *
216 * This roughly matches SimpleLinearize() (and Linearize) in interface and behavior, but always
217 * tries all topologically-valid transaction orderings, has no way to bound how much work it does,
218 * and always finds the optimal. With an O(n!) complexity, it should only be used for small
219 * clusters.
220 */
221template<typename SetType>
222std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
223{
224    // The best linearization so far, and its chunking.
225    std::vector<DepGraphIndex> linearization;
226    std::vector<FeeFrac> chunking;
227
228    std::vector<DepGraphIndex> perm_linearization;
229    // Initialize with the lexicographically-first linearization.
230    for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
231    // Iterate over all valid permutations.
232    do {
233        /** What prefix of perm_linearization is topological. */
234        DepGraphIndex topo_length{0};
235        TestBitSet perm_done;
236        while (topo_length < perm_linearization.size()) {
237            auto i = perm_linearization[topo_length];
238            perm_done.Set(i);
239            if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
240            ++topo_length;
241        }
242        if (topo_length == perm_linearization.size()) {
243            // If all of perm_linearization is topological, check if it is perhaps our best
244            // linearization so far.
245            auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
246            auto cmp = CompareChunks(perm_chunking, chunking);
247            // If the diagram is better, or if it is equal but with more chunks (because we
248            // prefer minimal chunks), consider this better.
249            if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
250                linearization = perm_linearization;

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.