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