1 // Copyright (c) 2015-2020 The Limenka 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 uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
47 bool mutation = false;
48 while (hashes.size() > 1) {
49 if (mutated) {
50 for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
51 if (hashes[pos] == hashes[pos + 1]) {
52 mutation = true;
53 break;
54 }
55 }
56 }
57 if (hashes.size() & 1) {
58 hashes.push_back(hashes.back());
59 }
60 SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
61 hashes.resize(hashes.size() / 2);
62 }
63 if (mutated) *mutated = mutation;
64 if (hashes.size() == 0) return uint256();
65 return hashes[0];
66 }
67 68 69 uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
70 {
71 std::vector<uint256> leaves;
72 leaves.resize(block.vtx.size());
73 for (size_t s = 0; s < block.vtx.size(); s++) {
74 leaves[s] = block.vtx[s]->GetHash();
75 }
76 return ComputeMerkleRoot(std::move(leaves), mutated);
77 }
78 79 uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
80 {
81 std::vector<uint256> leaves;
82 leaves.resize(block.vtx.size());
83 leaves[0].SetNull(); // The witness hash of the coinbase is 0.
84 for (size_t s = 1; s < block.vtx.size(); s++) {
85 leaves[s] = block.vtx[s]->GetWitnessHash();
86 }
87 return ComputeMerkleRoot(std::move(leaves), mutated);
88 }
89 90 /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
91 static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t leaf_pos, std::vector<uint256>* path)
92 {
93 if (path) path->clear();
94 Assume(leaves.size() <= UINT32_MAX);
95 if (leaves.size() == 0) {
96 if (pmutated) *pmutated = false;
97 if (proot) *proot = uint256();
98 return;
99 }
100 bool mutated = false;
101 // count is the number of leaves processed so far.
102 uint32_t count = 0;
103 // inner is an array of eagerly computed subtree hashes, indexed by tree
104 // level (0 being the leaves).
105 // For example, when count is 25 (11001 in binary), inner[4] is the hash of
106 // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
107 // the last leaf. The other inner entries are undefined.
108 uint256 inner[32];
109 // Which position in inner is a hash that depends on the matching leaf.
110 int matchlevel = -1;
111 // First process all leaves into 'inner' values.
112 while (count < leaves.size()) {
113 uint256 h = leaves[count];
114 bool matchh = count == leaf_pos;
115 count++;
116 int level;
117 // For each of the lower bits in count that are 0, do 1 step. Each
118 // corresponds to an inner value that existed before processing the
119 // current leaf, and each needs a hash to combine it.
120 for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
121 if (path) {
122 if (matchh) {
123 path->push_back(inner[level]);
124 } else if (matchlevel == level) {
125 path->push_back(h);
126 matchh = true;
127 }
128 }
129 mutated |= (inner[level] == h);
130 h = Hash(inner[level], h);
131 }
132 // Store the resulting hash at inner position level.
133 inner[level] = h;
134 if (matchh) {
135 matchlevel = level;
136 }
137 }
138 // Do a final 'sweep' over the rightmost branch of the tree to process
139 // odd levels, and reduce everything to a single top value.
140 // Level is the level (counted from the bottom) up to which we've sweeped.
141 int level = 0;
142 // As long as bit number level in count is zero, skip it. It means there
143 // is nothing left at this level.
144 while (!(count & ((uint32_t{1}) << level))) {
145 level++;
146 }
147 uint256 h = inner[level];
148 bool matchh = matchlevel == level;
149 while (count != ((uint32_t{1}) << level)) {
150 // If we reach this point, h is an inner value that is not the top.
151 // We combine it with itself (Limenka's special rule for odd levels in
152 // the tree) to produce a higher level one.
153 if (path && matchh) {
154 path->push_back(h);
155 }
156 h = Hash(h, h);
157 // Increment count to the value it would have if two entries at this
158 // level had existed.
159 count += ((uint32_t{1}) << level);
160 level++;
161 // And propagate the result upwards accordingly.
162 while (!(count & ((uint32_t{1}) << level))) {
163 if (path) {
164 if (matchh) {
165 path->push_back(inner[level]);
166 } else if (matchlevel == level) {
167 path->push_back(h);
168 matchh = true;
169 }
170 }
171 h = Hash(inner[level], h);
172 level++;
173 }
174 }
175 // Return result.
176 if (pmutated) *pmutated = mutated;
177 if (proot) *proot = h;
178 }
179 180 static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
181 std::vector<uint256> ret;
182 MerkleComputation(leaves, nullptr, nullptr, position, &ret);
183 return ret;
184 }
185 186 std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
187 {
188 std::vector<uint256> leaves;
189 leaves.resize(block.vtx.size());
190 for (size_t s = 0; s < block.vtx.size(); s++) {
191 leaves[s] = block.vtx[s]->GetHash();
192 }
193 return ComputeMerklePath(leaves, position);
194 }
195