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 : 40619 : uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
46 : 40619 : bool mutation = false;
47 [ + + ]: 42486 : while (hashes.size() > 1) {
48 [ + + ]: 1867 : if (mutated) {
49 [ + + ]: 229074 : for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
50 [ + + ]: 227500 : if (hashes[pos] == hashes[pos + 1]) mutation = true;
51 : : }
52 : : }
53 [ + + ]: 1867 : if (hashes.size() & 1) {
54 : 660 : hashes.push_back(hashes.back());
55 : : }
56 : 1867 : SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
57 : 1867 : hashes.resize(hashes.size() / 2);
58 : : }
59 [ + + ]: 40619 : if (mutated) *mutated = mutation;
60 [ + + ]: 40619 : if (hashes.size() == 0) return uint256();
61 : 40616 : return hashes[0];
62 : : }
63 : :
64 : :
65 : 19270 : uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
66 : : {
67 : 19270 : std::vector<uint256> leaves;
68 [ + - ]: 19270 : leaves.resize(block.vtx.size());
69 [ + + ]: 272590 : for (size_t s = 0; s < block.vtx.size(); s++) {
70 : 253320 : leaves[s] = block.vtx[s]->GetHash();
71 : : }
72 [ + - ]: 38540 : return ComputeMerkleRoot(std::move(leaves), mutated);
73 : 19270 : }
74 : :
75 : 21341 : uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
76 : : {
77 : 21341 : std::vector<uint256> leaves;
78 [ + - ]: 21341 : leaves.resize(block.vtx.size());
79 : 21341 : leaves[0].SetNull(); // The witness hash of the coinbase is 0.
80 [ + + ]: 23557 : for (size_t s = 1; s < block.vtx.size(); s++) {
81 : 2216 : leaves[s] = block.vtx[s]->GetWitnessHash();
82 : : }
83 [ + - ]: 42682 : return ComputeMerkleRoot(std::move(leaves), mutated);
84 : 21341 : }
85 : :
|
