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