/root/bitcoin/src/consensus/merkle.cpp

Source
// Copyright (c) 2015-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <consensus/merkle.h>

#include <crypto/sha256.h>
#include <hash.h>
#include <primitives/block.h>
#include <primitives/transaction.h>
#include <util/check.h>

#include <cstddef>
#include <memory>
#include <utility>

/*     WARNING! If you're reading this because you're learning about crypto
       and/or designing a new system that will use merkle trees, keep in mind
       that the following merkle tree algorithm has a serious flaw related to
       duplicate txids, resulting in a vulnerability (CVE-2012-2459).

       The reason is that if the number of hashes in the list at a given level
       is odd, the last one is duplicated before computing the next level (which
       is unusual in Merkle trees). This results in certain sequences of
       transactions leading to the same merkle root. For example, these two
       trees:

                    A               A
                  /  \            /   \
                B     C         B       C
               / \    |        / \     / \
              D   E   F       D   E   F   F
             / \ / \ / \     / \ / \ / \ / \
             1 2 3 4 5 6     1 2 3 4 5 6 5 6

       for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
       6 are repeated) result in the same root hash A (because the hash of both
       of (F) and (F,F) is C).

       The vulnerability results from being able to send a block with such a
       transaction list, with the same merkle root, and the same block hash as
       the original without duplication, resulting in failed validation. If the
       receiving node proceeds to mark that block as permanently invalid
       however, it will fail to accept further unmodified (and thus potentially
       valid) versions of the same block. We defend against this by detecting
       the case where we would hash two identical hashes at the end of the list
       together, and treating that identically to the block having an invalid
       merkle root. Assuming no double-SHA256 collisions, this will detect all
       known ways of changing the transactions without affecting the merkle
       root.
*/
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
    bool mutation = false;
    while (hashes.size() > 1) {
        if (mutated) {
            // Check every level because equal pairs can appear above the leaves,
            // as in the [1,2,3,4,5,6,5,6] construction described above.
            // Continuing after finding one is redundant, but mutated blocks should
            // not propagate through the network anyway, and the total number of
            // comparisons is the same as for an unmutated input of the same length.
            for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
                if (hashes[pos] == hashes[pos + 1]) mutation = true;
            }
        }
        if (hashes.size() & 1) {
            hashes.push_back(hashes.back());
        }
        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
        hashes.resize(hashes.size() / 2);
    }
    if (mutated) *mutated = mutation;
    if (hashes.size() == 0) return uint256();
    return hashes[0];
}


uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
{
    std::vector<uint256> leaves;
    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
    for (size_t s = 0; s < block.vtx.size(); s++) {
        leaves.push_back(block.vtx[s]->GetHash().ToUint256());
    }
    return ComputeMerkleRoot(std::move(leaves), mutated);
}

uint256 BlockWitnessMerkleRoot(const CBlock& block)
{
    std::vector<uint256> leaves;
    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
    leaves.emplace_back(); // The witness hash of the coinbase is 0.
    for (size_t s = 1; s < block.vtx.size(); s++) {
        leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
    }
    return ComputeMerkleRoot(std::move(leaves));
}

/* This implements a constant-space merkle path calculator, limited to 2^32 leaves. */
static void MerkleComputation(const std::vector<uint256>& leaves, uint32_t leaf_pos, std::vector<uint256>& path)
{
    path.clear();
    Assume(leaves.size() <= UINT32_MAX);
    if (leaves.size() == 0) {
        return;
    }
    // count is the number of leaves processed so far.
    uint32_t count = 0;
    // inner is an array of eagerly computed subtree hashes, indexed by tree
    // level (0 being the leaves).
    // For example, when count is 25 (11001 in binary), inner[4] is the hash of
    // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
    // the last leaf. The other inner entries are undefined.
    uint256 inner[32];
    // Which position in inner is a hash that depends on the matching leaf.
    int matchlevel = -1;
    // First process all leaves into 'inner' values.
    while (count < leaves.size()) {
        uint256 h = leaves[count];
        bool matchh = count == leaf_pos;
        count++;
        int level;
        // For each of the lower bits in count that are 0, do 1 step. Each
        // corresponds to an inner value that existed before processing the
        // current leaf, and each needs a hash to combine it.
        for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
            if (matchh) {
                path.push_back(inner[level]);
            } else if (matchlevel == level) {
                path.push_back(h);
                matchh = true;
            }
            h = Hash(inner[level], h);
        }
        // Store the resulting hash at inner position level.
        inner[level] = h;
        if (matchh) {
            matchlevel = level;
        }
    }
    // Do a final 'sweep' over the rightmost branch of the tree to process
    // odd levels, and reduce everything to a single top value.
    // Level is the level (counted from the bottom) up to which we've sweeped.
    int level = 0;
    // As long as bit number level in count is zero, skip it. It means there
    // is nothing left at this level.
    while (!(count & ((uint32_t{1}) << level))) {
        level++;
    }
    uint256 h = inner[level];
    bool matchh = matchlevel == level;
    while (count != ((uint32_t{1}) << level)) {
        // If we reach this point, h is an inner value that is not the top.
        // We combine it with itself (Bitcoin's special rule for odd levels in
        // the tree) to produce a higher level one.
        if (matchh) {
            path.push_back(h);
        }
        h = Hash(h, h);
        // Increment count to the value it would have if two entries at this
        // level had existed.
        count += ((uint32_t{1}) << level);
        level++;
        // And propagate the result upwards accordingly.
        while (!(count & ((uint32_t{1}) << level))) {
            if (matchh) {
                path.push_back(inner[level]);
            } else if (matchlevel == level) {
                path.push_back(h);
                matchh = true;
            }
            h = Hash(inner[level], h);
            level++;
        }
    }
}

static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
    std::vector<uint256> ret;
    MerkleComputation(leaves, position, ret);
    return ret;
}

std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
{
    std::vector<uint256> leaves;
    leaves.resize(block.vtx.size());
    for (size_t s = 0; s < block.vtx.size(); s++) {
        leaves[s] = block.vtx[s]->GetHash().ToUint256();
    }
    return ComputeMerklePath(leaves, position);
}

Line	Count	Source
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
7		#include <crypto/sha256.h>
8		#include <hash.h>
9		#include <primitives/block.h>
10		#include <primitives/transaction.h>
11		#include <util/check.h>
12
13		#include <cstddef>
14		#include <memory>
15		#include <utility>
16
17		/* WARNING! If you're reading this because you're learning about crypto
18		and/or designing a new system that will use merkle trees, keep in mind
19		that the following merkle tree algorithm has a serious flaw related to
20		duplicate txids, resulting in a vulnerability (CVE-2012-2459).
21
22		The reason is that if the number of hashes in the list at a given level
23		is odd, the last one is duplicated before computing the next level (which
24		is unusual in Merkle trees). This results in certain sequences of
25		transactions leading to the same merkle root. For example, these two
26		trees:
27
28		A A
29		/ \ / \
30		B C B C
31		/ \ \| / \ / \
32		D E F D E F F
33		/ \ / \ / \ / \ / \ / \ / \
34		1 2 3 4 5 6 1 2 3 4 5 6 5 6
35
36		for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
37		6 are repeated) result in the same root hash A (because the hash of both
38		of (F) and (F,F) is C).
39
40		The vulnerability results from being able to send a block with such a
41		transaction list, with the same merkle root, and the same block hash as
42		the original without duplication, resulting in failed validation. If the
43		receiving node proceeds to mark that block as permanently invalid
44		however, it will fail to accept further unmodified (and thus potentially
45		valid) versions of the same block. We defend against this by detecting
46		the case where we would hash two identical hashes at the end of the list
47		together, and treating that identically to the block having an invalid
48		merkle root. Assuming no double-SHA256 collisions, this will detect all
49		known ways of changing the transactions without affecting the merkle
50		root.
51		*/
52	2.86M	uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
53	2.86M	bool mutation = false;
54	3.29M	while (hashes.size() > 1) { Branch (54:12): [True: 435k, False: 2.86M]
55	435k	if (mutated) { Branch (55:13): [True: 199k, False: 236k]
56		// Check every level because equal pairs can appear above the leaves,
57		// as in the [1,2,3,4,5,6,5,6] construction described above.
58		// Continuing after finding one is redundant, but mutated blocks should
59		// not propagate through the network anyway, and the total number of
60		// comparisons is the same as for an unmutated input of the same length.
61	6.17M	for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) { Branch (61:34): [True: 5.97M, False: 199k]
62	5.97M	if (hashes[pos] == hashes[pos + 1]) mutation = true; Branch (62:21): [True: 5.41M, False: 560k]
63	5.97M	}
64	199k	}
65	435k	if (hashes.size() & 1) { Branch (65:13): [True: 192k, False: 242k]
66	192k	hashes.push_back(hashes.back());
67	192k	}
68	435k	SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
69	435k	hashes.resize(hashes.size() / 2);
70	435k	}
71	2.86M	if (mutated) *mutated = mutation; Branch (71:9): [True: 663k, False: 2.19M]
72	2.86M	if (hashes.size() == 0) return uint256(); Branch (72:9): [True: 10.2k, False: 2.85M]
73	2.85M	return hashes[0];
74	2.86M	}
75
76
77		uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
78	1.44M	{
79	1.44M	std::vector<uint256> leaves;
80	1.44M	leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
81	9.94M	for (size_t s = 0; s < block.vtx.size(); s++) { Branch (81:24): [True: 8.49M, False: 1.44M]
82	8.49M	leaves.push_back(block.vtx[s]->GetHash().ToUint256());
83	8.49M	}
84	1.44M	return ComputeMerkleRoot(std::move(leaves), mutated);
85	1.44M	}
86
87		uint256 BlockWitnessMerkleRoot(const CBlock& block)
88	1.41M	{
89	1.41M	std::vector<uint256> leaves;
90	1.41M	leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
91	1.41M	leaves.emplace_back(); // The witness hash of the coinbase is 0.
92	5.62M	for (size_t s = 1; s < block.vtx.size(); s++) { Branch (92:24): [True: 4.21M, False: 1.41M]
93	4.21M	leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
94	4.21M	}
95	1.41M	return ComputeMerkleRoot(std::move(leaves));
96	1.41M	}
97
98		/* This implements a constant-space merkle path calculator, limited to 2^32 leaves. */
99		static void MerkleComputation(const std::vector<uint256>& leaves, uint32_t leaf_pos, std::vector<uint256>& path)
100	296	{
101	296	path.clear();
102	296	Assume(leaves.size() <= UINT32_MAX);
103	296	if (leaves.size() == 0) { Branch (103:9): [True: 5, False: 291]
104	5	return;
105	5	}
106		// count is the number of leaves processed so far.
107	291	uint32_t count = 0;
108		// inner is an array of eagerly computed subtree hashes, indexed by tree
109		// level (0 being the leaves).
110		// For example, when count is 25 (11001 in binary), inner[4] is the hash of
111		// the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
112		// the last leaf. The other inner entries are undefined.
113	291	uint256 inner[32];
114		// Which position in inner is a hash that depends on the matching leaf.
115	291	int matchlevel = -1;
116		// First process all leaves into 'inner' values.
117	2.32M	while (count < leaves.size()) { Branch (117:12): [True: 2.32M, False: 291]
118	2.32M	uint256 h = leaves[count];
119	2.32M	bool matchh = count == leaf_pos;
120	2.32M	count++;
121	2.32M	int level;
122		// For each of the lower bits in count that are 0, do 1 step. Each
123		// corresponds to an inner value that existed before processing the
124		// current leaf, and each needs a hash to combine it.
125	4.64M	for (level = 0; !(count & ((uint32_t{1}) << level)); level++) { Branch (125:25): [True: 2.31M, False: 2.32M]
126	2.31M	if (matchh) { Branch (126:17): [True: 307, False: 2.31M]
127	307	path.push_back(inner[level]);
128	2.31M	} else if (matchlevel == level) { Branch (128:24): [True: 1.23k, False: 2.31M]
129	1.23k	path.push_back(h);
130	1.23k	matchh = true;
131	1.23k	}
132	2.31M	h = Hash(inner[level], h);
133	2.31M	}
134		// Store the resulting hash at inner position level.
135	2.32M	inner[level] = h;
136	2.32M	if (matchh) { Branch (136:13): [True: 1.52k, False: 2.31M]
137	1.52k	matchlevel = level;
138	1.52k	}
139	2.32M	}
140		// Do a final 'sweep' over the rightmost branch of the tree to process
141		// odd levels, and reduce everything to a single top value.
142		// Level is the level (counted from the bottom) up to which we've sweeped.
143	291	int level = 0;
144		// As long as bit number level in count is zero, skip it. It means there
145		// is nothing left at this level.
146	595	while (!(count & ((uint32_t{1}) << level))) { Branch (146:12): [True: 304, False: 291]
147	304	level++;
148	304	}
149	291	uint256 h = inner[level];
150	291	bool matchh = matchlevel == level;
151	1.26k	while (count != ((uint32_t{1}) << level)) { Branch (151:12): [True: 971, False: 291]
152		// If we reach this point, h is an inner value that is not the top.
153		// We combine it with itself (Bitcoin's special rule for odd levels in
154		// the tree) to produce a higher level one.
155	971	if (matchh) { Branch (155:13): [True: 187, False: 784]
156	187	path.push_back(h);
157	187	}
158	971	h = Hash(h, h);
159		// Increment count to the value it would have if two entries at this
160		// level had existed.
161	971	count += ((uint32_t{1}) << level);
162	971	level++;
163		// And propagate the result upwards accordingly.
164	1.78k	while (!(count & ((uint32_t{1}) << level))) { Branch (164:16): [True: 810, False: 971]
165	810	if (matchh) { Branch (165:17): [True: 167, False: 643]
166	167	path.push_back(inner[level]);
167	643	} else if (matchlevel == level) { Branch (167:24): [True: 186, False: 457]
168	186	path.push_back(h);
169	186	matchh = true;
170	186	}
171	810	h = Hash(inner[level], h);
172	810	level++;
173	810	}
174	971	}
175	291	}
176
177	296	static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
178	296	std::vector<uint256> ret;
179	296	MerkleComputation(leaves, position, ret);
180	296	return ret;
181	296	}
182
183		std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
184	296	{
185	296	std::vector<uint256> leaves;
186	296	leaves.resize(block.vtx.size());
187	2.32M	for (size_t s = 0; s < block.vtx.size(); s++) { Branch (187:24): [True: 2.32M, False: 296]
188	2.32M	leaves[s] = block.vtx[s]->GetHash().ToUint256();
189	2.32M	}
190	296	return ComputeMerklePath(leaves, position);
191	296	}

Coverage Report

Created: 2026-08-25 19:22