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  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]) mutation = true;
 52              }
 53          }
 54          if (hashes.size() & 1) {
 55              hashes.push_back(hashes.back());
 56          }
 57          SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
 58          hashes.resize(hashes.size() / 2);
 59      }
 60      if (mutated) *mutated = mutation;
 61      if (hashes.size() == 0) return uint256();
 62      return hashes[0];
 63  }
 64  
 65  
 66  uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
 67  {
 68      std::vector<uint256> leaves;
 69      leaves.resize(block.vtx.size());
 70      for (size_t s = 0; s < block.vtx.size(); s++) {
 71          leaves[s] = block.vtx[s]->GetHash();
 72      }
 73      return ComputeMerkleRoot(std::move(leaves), mutated);
 74  }
 75  
 76  uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
 77  {
 78      std::vector<uint256> leaves;
 79      leaves.resize(block.vtx.size());
 80      leaves[0].SetNull(); // The witness hash of the coinbase is 0.
 81      for (size_t s = 1; s < block.vtx.size(); s++) {
 82          leaves[s] = block.vtx[s]->GetWitnessHash();
 83      }
 84      return ComputeMerkleRoot(std::move(leaves), mutated);
 85  }
 86  
 87  /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
 88  static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t leaf_pos, std::vector<uint256>* path)
 89  {
 90      if (path) path->clear();
 91      Assume(leaves.size() <= UINT32_MAX);
 92      if (leaves.size() == 0) {
 93          if (pmutated) *pmutated = false;
 94          if (proot) *proot = uint256();
 95          return;
 96      }
 97      bool mutated = false;
 98      // count is the number of leaves processed so far.
 99      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      uint256 inner[32];
106      // Which position in inner is a hash that depends on the matching leaf.
107      int matchlevel = -1;
108      // First process all leaves into 'inner' values.
109      while (count < leaves.size()) {
110          uint256 h = leaves[count];
111          bool matchh = count == leaf_pos;
112          count++;
113          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          for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
118              if (path) {
119                  if (matchh) {
120                      path->push_back(inner[level]);
121                  } else if (matchlevel == level) {
122                      path->push_back(h);
123                      matchh = true;
124                  }
125              }
126              mutated |= (inner[level] == h);
127              h = Hash(inner[level], h);
128          }
129          // Store the resulting hash at inner position level.
130          inner[level] = h;
131          if (matchh) {
132              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      while (!(count & ((uint32_t{1}) << level))) {
142          level++;
143      }
144      uint256 h = inner[level];
145      bool matchh = matchlevel == level;
146      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          if (path && matchh) {
151              path->push_back(h);
152          }
153          h = Hash(h, h);
154          // Increment count to the value it would have if two entries at this
155          // level had existed.
156          count += ((uint32_t{1}) << level);
157          level++;
158          // And propagate the result upwards accordingly.
159          while (!(count & ((uint32_t{1}) << level))) {
160              if (path) {
161                  if (matchh) {
162                      path->push_back(inner[level]);
163                  } else if (matchlevel == level) {
164                      path->push_back(h);
165                      matchh = true;
166                  }
167              }
168              h = Hash(inner[level], h);
169              level++;
170          }
171      }
172      // Return result.
173      if (pmutated) *pmutated = mutated;
174      if (proot) *proot = h;
175  }
176  
177  static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
178      std::vector<uint256> ret;
179      MerkleComputation(leaves, nullptr, nullptr, position, &ret);
180      return ret;
181  }
182  
183  std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
184  {
185      std::vector<uint256> leaves;
186      leaves.resize(block.vtx.size());
187      for (size_t s = 0; s < block.vtx.size(); s++) {
188          leaves[s] = block.vtx[s]->GetHash();
189      }
190      return ComputeMerklePath(leaves, position);
191  }