Bitcoin Core  22.99.0
P2P Digital Currency
merkle.cpp
Go to the documentation of this file.
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 uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
46  bool mutation = false;
47  while (hashes.size() > 1) {
48  if (mutated) {
49  for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
50  if (hashes[pos] == hashes[pos + 1]) mutation = true;
51  }
52  }
53  if (hashes.size() & 1) {
54  hashes.push_back(hashes.back());
55  }
56  SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
57  hashes.resize(hashes.size() / 2);
58  }
59  if (mutated) *mutated = mutation;
60  if (hashes.size() == 0) return uint256();
61  return hashes[0];
62 }
63 
64 
65 uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
66 {
67  std::vector<uint256> leaves;
68  leaves.resize(block.vtx.size());
69  for (size_t s = 0; s < block.vtx.size(); s++) {
70  leaves[s] = block.vtx[s]->GetHash();
71  }
72  return ComputeMerkleRoot(std::move(leaves), mutated);
73 }
74 
76 {
77  std::vector<uint256> leaves;
78  leaves.resize(block.vtx.size());
79  leaves[0].SetNull(); // The witness hash of the coinbase is 0.
80  for (size_t s = 1; s < block.vtx.size(); s++) {
81  leaves[s] = block.vtx[s]->GetWitnessHash();
82  }
83  return ComputeMerkleRoot(std::move(leaves), mutated);
84 }
85 
ComputeMerkleRoot
uint256 ComputeMerkleRoot(std::vector< uint256 > hashes, bool *mutated)
Definition: merkle.cpp:45
base_blob::SetNull
void SetNull()
Definition: uint256.h:39
SHA256D64
void SHA256D64(unsigned char *out, const unsigned char *in, size_t blocks)
Compute multiple double-SHA256's of 64-byte blobs.
Definition: sha256.cpp:687
mutated
bool mutated
Definition: deserialize.cpp:187
uint256
256-bit opaque blob.
Definition: uint256.h:124
merkle.h
BlockWitnessMerkleRoot
uint256 BlockWitnessMerkleRoot(const CBlock &block, bool *mutated)
Definition: merkle.cpp:75
CBlock
Definition: block.h:62
CBlock::vtx
std::vector< CTransactionRef > vtx
Definition: block.h:66
BlockMerkleRoot
uint256 BlockMerkleRoot(const CBlock &block, bool *mutated)
Definition: merkle.cpp:65