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.

10,801 bytes · SHA-256 0902477c1f45d153… · View upstream ↗

1// Copyright (c) 2015-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 <consensus/merkle.h>
6#include <test/util/common.h>
7#include <test/util/random.h>
8#include <test/util/setup_common.h>
9
10#include <boost/test/unit_test.hpp>
11
12BOOST_FIXTURE_TEST_SUITE(merkle_tests, BasicTestingSetup)
13
14static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
15    uint256 hash = leaf;
16    for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
17        if (nIndex & 1) {
18            hash = Hash(*it, hash);
19        } else {
20            hash = Hash(hash, *it);
21        }
22        nIndex >>= 1;
23    }
24    return hash;
25}
26
27// Older version of the merkle root computation code, for comparison.
28static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
29{
30    vMerkleTree.clear();
31    vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
32    for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
33        vMerkleTree.push_back((*it)->GetHash().ToUint256());
34    int j = 0;
35    bool mutated = false;
36    for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
37    {
38        for (int i = 0; i < nSize; i += 2)
39        {
40            int i2 = std::min(i+1, nSize-1);
41            if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
42                // Two identical hashes at the end of the list at a particular level.
43                mutated = true;
44            }
45            vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
46        }
47        j += nSize;
48    }
49    if (fMutated) {
50        *fMutated = mutated;
51    }
52    return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
53}
54
55// Older version of the merkle branch computation code, for comparison.
56static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
57{
58    std::vector<uint256> vMerkleBranch;
59    int j = 0;
60    for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
61    {
62        int i = std::min(nIndex^1, nSize-1);
63        vMerkleBranch.push_back(vMerkleTree[j+i]);
64        nIndex >>= 1;
65        j += nSize;
66    }
67    return vMerkleBranch;
68}
69
70static inline int ctz(uint32_t i) {
71    if (i == 0) return 0;
72    int j = 0;
73    while (!(i & 1)) {
74        j++;
75        i >>= 1;
76    }
77    return j;
78}
79
80BOOST_AUTO_TEST_CASE(merkle_test)
81{
82    for (int i = 0; i < 32; i++) {
83        // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
84        int ntx = (i <= 16) ? i : 17 + (m_rng.randrange(4000));
85        // Try up to 3 mutations.
86        for (int mutate = 0; mutate <= 3; mutate++) {
87            int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
88            if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
89            int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
90            int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
91            if (duplicate2 >= ntx1) break;
92            int ntx2 = ntx1 + duplicate2;
93            int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
94            if (duplicate3 >= ntx2) break;
95            int ntx3 = ntx2 + duplicate3;
96            // Build a block with ntx different transactions.
97            CBlock block;
98            block.vtx.resize(ntx);
99            for (int j = 0; j < ntx; j++) {
100                CMutableTransaction mtx;
101                mtx.nLockTime = j;
102                block.vtx[j] = MakeTransactionRef(std::move(mtx));
103            }
104            // Compute the root of the block before mutating it.
105            bool unmutatedMutated = false;
106            uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
107            BOOST_CHECK(unmutatedMutated == false);
108            // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
109            block.vtx.resize(ntx3);
110            for (int j = 0; j < duplicate1; j++) {
111                block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
112            }
113            for (int j = 0; j < duplicate2; j++) {
114                block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
115            }
116            for (int j = 0; j < duplicate3; j++) {
117                block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
118            }
119            // Compute the merkle root and merkle tree using the old mechanism.
120            bool oldMutated = false;
121            std::vector<uint256> merkleTree;
122            uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
123            // Compute the merkle root using the new mechanism.
124            bool newMutated = false;
125            uint256 newRoot = BlockMerkleRoot(block, &newMutated);
126            BOOST_CHECK(oldRoot == newRoot);
127            BOOST_CHECK(newRoot == unmutatedRoot);
128            BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
129            BOOST_CHECK(oldMutated == newMutated);
130            BOOST_CHECK(newMutated == !!mutate);
131            // If no mutation was done (once for every ntx value), try up to 16 branches.
132            if (mutate == 0) {
133                for (int loop = 0; loop < std::min(ntx, 16); loop++) {
134                    // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
135                    int mtx = loop;
136                    if (ntx > 16) {
137                        mtx = m_rng.randrange(ntx);
138                    }
139                    std::vector<uint256> newBranch = TransactionMerklePath(block, mtx);
140                    std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
141                    BOOST_CHECK(oldBranch == newBranch);
142                    BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash().ToUint256(), newBranch, mtx) == oldRoot);
143                }
144            }
145        }
146    }
147}
148
149
150BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
151{
152    bool mutated = false;
153    CBlock block;
154    uint256 root = BlockMerkleRoot(block, &mutated);
155
156    BOOST_CHECK_EQUAL(root.IsNull(), true);
157    BOOST_CHECK_EQUAL(mutated, false);
158
159    // Verify TransactionMerklePath handles empty block correctly
160    // This tests the early-return path in MerkleComputation
161    std::vector<uint256> merkle_path = TransactionMerklePath(block, 0);
162    BOOST_CHECK(merkle_path.empty());
163}
164
165BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
166{
167    bool mutated = false;
168    CBlock block;
169
170    block.vtx.resize(1);
171    CMutableTransaction mtx;
172    mtx.nLockTime = 0;
173    block.vtx[0] = MakeTransactionRef(std::move(mtx));
174    uint256 root = BlockMerkleRoot(block, &mutated);
175    BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash().ToUint256());
176    BOOST_CHECK_EQUAL(mutated, false);
177}
178
179BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
180{
181    bool mutated;
182    CBlock block, blockWithRepeatedLastTx;
183
184    block.vtx.resize(3);
185
186    for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
187        CMutableTransaction mtx;
188        mtx.nLockTime = pos;
189        block.vtx[pos] = MakeTransactionRef(std::move(mtx));
190    }
191
192    blockWithRepeatedLastTx = block;
193    blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
194
195    uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
196    BOOST_CHECK_EQUAL(mutated, false);
197
198    uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
199    BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
200    BOOST_CHECK_EQUAL(mutated, true);
201}
202
203BOOST_AUTO_TEST_CASE(merkle_test_mutated_return_value)
204{
205    // CVE-2012-2459 construction: [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] produce the same root.
206    const std::vector leaves{uint256{1}, uint256{2}, uint256{3}, uint256{4}, uint256{5}, uint256{6}};
207    auto mutated_leaves{leaves};
208    mutated_leaves.insert(mutated_leaves.end(), leaves.end() - 2, leaves.end()); // repeat last two elements
209
210    bool mutated{true};
211    const uint256 unmutated_root{ComputeMerkleRoot(leaves, &mutated)};
212    BOOST_CHECK(!mutated);
213    BOOST_CHECK_EQUAL(unmutated_root, ComputeMerkleRoot(mutated_leaves, &mutated));
214    BOOST_CHECK( mutated);
215
216    const std::vector nontrailing_duplicate_leaves{uint256{1}, uint256{1}, uint256{3}, uint256{4}};
217    mutated = false;
218    const uint256 nontrailing_duplicate_root{ComputeMerkleRoot(nontrailing_duplicate_leaves, &mutated)};
219    BOOST_CHECK(nontrailing_duplicate_root == ComputeMerkleRoot(nontrailing_duplicate_leaves));
220    BOOST_CHECK(mutated);
221}
222
223BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
224{
225    CBlock block, leftSubtreeBlock, rightSubtreeBlock;
226
227    block.vtx.resize(4);
228    std::size_t pos;
229    for (pos = 0; pos < block.vtx.size(); pos++) {
230        CMutableTransaction mtx;
231        mtx.nLockTime = pos;
232        block.vtx[pos] = MakeTransactionRef(std::move(mtx));
233    }
234
235    for (pos = 0; pos < block.vtx.size() / 2; pos++)
236        leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
237
238    for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
239        rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
240
241    uint256 root = BlockMerkleRoot(block);
242    uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
243    uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
244    std::vector<uint256> leftRight;
245    leftRight.push_back(rootOfLeftSubtree);
246    leftRight.push_back(rootOfRightSubtree);
247    uint256 rootOfLR = ComputeMerkleRoot(leftRight);
248
249    BOOST_CHECK_EQUAL(root, rootOfLR);
250}

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.