Branch data Line data Source code
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 : 50530 : uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
53 : 50530 : bool mutation = false;
54 [ - + + + ]: 52625 : while (hashes.size() > 1) {
55 [ + + ]: 2095 : if (mutated) {
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 [ + + ]: 235662 : for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
62 [ + + ]: 234001 : if (hashes[pos] == hashes[pos + 1]) mutation = true;
63 : : }
64 : : }
65 [ + + ]: 2095 : if (hashes.size() & 1) {
66 : 706 : hashes.push_back(hashes.back());
67 : : }
68 [ - + ]: 2095 : SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
69 [ - + ]: 2095 : hashes.resize(hashes.size() / 2);
70 : : }
71 [ + + ]: 50530 : if (mutated) *mutated = mutation;
72 [ - + + + ]: 50530 : if (hashes.size() == 0) return uint256();
73 : 50527 : return hashes[0];
74 : : }
75 : :
76 : :
77 : 23776 : uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
78 : : {
79 : 23776 : std::vector<uint256> leaves;
80 [ - + + - ]: 23776 : leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
81 [ - + + + ]: 288100 : for (size_t s = 0; s < block.vtx.size(); s++) {
82 [ + - ]: 264324 : leaves.push_back(block.vtx[s]->GetHash().ToUint256());
83 : : }
84 [ + - ]: 47552 : return ComputeMerkleRoot(std::move(leaves), mutated);
85 : 23776 : }
86 : :
87 : 26742 : uint256 BlockWitnessMerkleRoot(const CBlock& block)
88 : : {
89 : 26742 : std::vector<uint256> leaves;
90 [ - + + - ]: 26742 : leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
91 [ + - ]: 26742 : leaves.emplace_back(); // The witness hash of the coinbase is 0.
92 [ - + + + ]: 67419 : for (size_t s = 1; s < block.vtx.size(); s++) {
93 [ + - ]: 40677 : leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
94 : : }
95 [ + - ]: 53484 : return ComputeMerkleRoot(std::move(leaves));
96 : 26742 : }
97 : :
98 : : /* This implements a constant-space merkle path calculator, limited to 2^32 leaves. */
99 : 377 : static void MerkleComputation(const std::vector<uint256>& leaves, uint32_t leaf_pos, std::vector<uint256>& path)
100 : : {
101 [ - + ]: 377 : path.clear();
102 [ - + + + ]: 377 : Assume(leaves.size() <= UINT32_MAX);
103 [ + + ]: 377 : if (leaves.size() == 0) {
104 : : return;
105 : : }
106 : : // count is the number of leaves processed so far.
107 : 376 : 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 : 376 : uint256 inner[32];
114 : : // Which position in inner is a hash that depends on the matching leaf.
115 : 376 : int matchlevel = -1;
116 : : // First process all leaves into 'inner' values.
117 [ - + + + ]: 474736 : while (count < leaves.size()) {
118 : 474360 : uint256 h = leaves[count];
119 : 474360 : bool matchh = count == leaf_pos;
120 : 474360 : count++;
121 : 474360 : 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 [ + + ]: 947060 : for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
126 [ + + ]: 472700 : if (matchh) {
127 : 1252 : path.push_back(inner[level]);
128 [ + + ]: 471448 : } else if (matchlevel == level) {
129 : 1332 : path.push_back(h);
130 : 1332 : matchh = true;
131 : : }
132 : 472700 : h = Hash(inner[level], h);
133 : : }
134 : : // Store the resulting hash at inner position level.
135 : 474360 : inner[level] = h;
136 [ + + ]: 474360 : if (matchh) {
137 : 1708 : matchlevel = level;
138 : : }
139 : : }
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 : : 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 [ + + ]: 880 : while (!(count & ((uint32_t{1}) << level))) {
147 : 504 : level++;
148 : : }
149 : 376 : uint256 h = inner[level];
150 : 376 : bool matchh = matchlevel == level;
151 [ + + ]: 1706 : while (count != ((uint32_t{1}) << level)) {
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 [ + + ]: 1330 : if (matchh) {
156 : 64 : path.push_back(h);
157 : : }
158 : 1330 : h = Hash(h, h);
159 : : // Increment count to the value it would have if two entries at this
160 : : // level had existed.
161 : 1330 : count += ((uint32_t{1}) << level);
162 : 1330 : level++;
163 : : // And propagate the result upwards accordingly.
164 [ + + ]: 2614 : while (!(count & ((uint32_t{1}) << level))) {
165 [ + + ]: 1284 : if (matchh) {
166 : 148 : path.push_back(inner[level]);
167 [ + + ]: 1136 : } else if (matchlevel == level) {
168 : 322 : path.push_back(h);
169 : 322 : matchh = true;
170 : : }
171 : 1284 : h = Hash(inner[level], h);
172 : 1284 : level++;
173 : : }
174 : : }
175 : : }
176 : :
177 : 377 : static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
178 : 377 : std::vector<uint256> ret;
179 [ + - ]: 377 : MerkleComputation(leaves, position, ret);
180 : 377 : return ret;
181 : 0 : }
182 : :
183 : 377 : std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
184 : : {
185 : 377 : std::vector<uint256> leaves;
186 [ - + + - ]: 377 : leaves.resize(block.vtx.size());
187 [ - + + + ]: 474737 : for (size_t s = 0; s < block.vtx.size(); s++) {
188 : 474360 : leaves[s] = block.vtx[s]->GetHash().ToUint256();
189 : : }
190 [ + - ]: 377 : return ComputeMerklePath(leaves, position);
191 : 377 : }
|
