Line data Source code
1 : // Copyright (c) 2015 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 "merkle.h"
6 : #include "hash.h"
7 : #include "utilstrencodings.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 : The reason is that if the number of hashes in the list at a given time
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 : A A
19 : / \ / \
20 : B C B C
21 : / \ | / \ / \
22 : D E F D E F F
23 : / \ / \ / \ / \ / \ / \ / \
24 : 1 2 3 4 5 6 1 2 3 4 5 6 5 6
25 : for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
26 : 6 are repeated) result in the same root hash A (because the hash of both
27 : of (F) and (F,F) is C).
28 : The vulnerability results from being able to send a block with such a
29 : transaction list, with the same merkle root, and the same block hash as
30 : the original without duplication, resulting in failed validation. If the
31 : receiving node proceeds to mark that block as permanently invalid
32 : however, it will fail to accept further unmodified (and thus potentially
33 : valid) versions of the same block. We defend against this by detecting
34 : the case where we would hash two identical hashes at the end of the list
35 : together, and treating that identically to the block having an invalid
36 : merkle root. Assuming no double-SHA256 collisions, this will detect all
37 : known ways of changing the transactions without affecting the merkle
38 : root.
39 : */
40 :
41 : /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
42 70225 : static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
43 70225 : if (pbranch) pbranch->clear();
44 70225 : if (leaves.size() == 0) {
45 1 : if (pmutated) *pmutated = false;
46 2 : if (proot) *proot = uint256();
47 1 : return;
48 : }
49 2317391 : bool mutated = false;
50 : // count is the number of leaves processed so far.
51 2317391 : uint32_t count = 0;
52 : // inner is an array of eagerly computed subtree hashes, indexed by tree
53 : // level (0 being the leaves).
54 : // For example, when count is 25 (11001 in binary), inner[4] is the hash of
55 : // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
56 : // the last leaf. The other inner entries are undefined.
57 2317391 : uint256 inner[32];
58 : // Which position in inner is a hash that depends on the matching leaf.
59 : int matchlevel = -1;
60 : // First process all leaves into 'inner' values.
61 1336723 : while (count < leaves.size()) {
62 1266499 : uint256 h = leaves[count];
63 1266499 : bool matchh = count == branchpos;
64 1266499 : count++;
65 1266499 : int level;
66 : // For each of the lower bits in count that are 0, do 1 step. Each
67 : // corresponds to an inner value that existed before processing the
68 : // current leaf, and each needs a hash to combine it.
69 2457610 : for (level = 0; !(count & (((uint32_t)1) << level)); level++) {
70 1191113 : if (pbranch) {
71 475132 : if (matchh) {
72 1272 : pbranch->push_back(inner[level]);
73 473860 : } else if (matchlevel == level) {
74 1280 : pbranch->push_back(h);
75 : matchh = true;
76 : }
77 : }
78 1191113 : mutated |= (inner[level] == h);
79 1191113 : CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
80 : }
81 : // Store the resulting hash at inner position level.
82 1266499 : inner[level] = h;
83 1266499 : if (matchh) {
84 1656 : matchlevel = level;
85 : }
86 : }
87 : // Do a final 'sweep' over the rightmost branch of the tree to process
88 : // odd levels, and reduce everything to a single top value.
89 : // Level is the level (counted from the bottom) up to which we've sweeped.
90 : int level = 0;
91 : // As long as bit number level in count is zero, skip it. It means there
92 : // is nothing left at this level.
93 81939 : while (!(count & (((uint32_t)1) << level))) {
94 11715 : level++;
95 : }
96 70224 : uint256 h = inner[level];
97 70224 : bool matchh = matchlevel == level;
98 76070 : while (count != (((uint32_t)1) << level)) {
99 : // If we reach this point, h is an inner value that is not the top.
100 : // We combine it with itself (Bitcoin's special rule for odd levels in
101 : // the tree) to produce a higher level one.
102 5846 : if (pbranch && matchh) {
103 67 : pbranch->push_back(h);
104 : }
105 5846 : CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
106 : // Increment count to the value it would have if two entries at this
107 : // level had existed.
108 5846 : count += (((uint32_t)1) << level);
109 5846 : level++;
110 : // And propagate the result upwards accordingly.
111 11008 : while (!(count & (((uint32_t)1) << level))) {
112 5162 : if (pbranch) {
113 1300 : if (matchh) {
114 155 : pbranch->push_back(inner[level]);
115 1145 : } else if (matchlevel == level) {
116 328 : pbranch->push_back(h);
117 : matchh = true;
118 : }
119 : }
120 5162 : CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
121 5162 : level++;
122 : }
123 : }
124 : // Return result.
125 70224 : if (pmutated) *pmutated = mutated;
126 70224 : if (proot) *proot = h;
127 : }
128 :
129 69849 : uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated) {
130 69849 : uint256 hash;
131 69849 : MerkleComputation(leaves, &hash, mutated, -1, nullptr);
132 69849 : return hash;
133 : }
134 :
135 376 : std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
136 376 : std::vector<uint256> ret;
137 376 : MerkleComputation(leaves, nullptr, nullptr, position, &ret);
138 376 : return ret;
139 : }
140 :
141 376 : uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
142 376 : uint256 hash = leaf;
143 3478 : for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
144 3102 : if (nIndex & 1) {
145 1427 : hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
146 : } else {
147 1675 : hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
148 : }
149 3102 : nIndex >>= 1;
150 : }
151 376 : return hash;
152 : }
153 :
154 69849 : uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
155 : {
156 69849 : std::vector<uint256> leaves;
157 69849 : leaves.resize(block.vtx.size());
158 859540 : for (size_t s = 0; s < block.vtx.size(); s++) {
159 789691 : leaves[s] = block.vtx[s]->GetHash();
160 : }
161 139698 : return ComputeMerkleRoot(leaves, mutated);
162 : }
163 :
164 376 : std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
165 : {
166 376 : std::vector<uint256> leaves;
167 376 : leaves.resize(block.vtx.size());
168 477184 : for (size_t s = 0; s < block.vtx.size(); s++) {
169 476808 : leaves[s] = block.vtx[s]->GetHash();
170 : }
171 752 : return ComputeMerkleBranch(leaves, position);
172 : }
|
