1// Copyright (c) 2015-present 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
7#include <crypto/sha256.h>
8#include <hash.h>
9#include <primitives/block.h>
10#include <primitives/transaction.h>
11#include <util/check.h>
12
13#include <cstddef>
14#include <utility>
15
16/*     WARNING! If you're reading this because you're learning about crypto
17       and/or designing a new system that will use merkle trees, keep in mind
18       that the following merkle tree algorithm has a serious flaw related to
19       duplicate txids, resulting in a vulnerability (CVE-2012-2459).
20
21       The reason is that if the number of hashes in the list at a given level
22       is odd, the last one is duplicated before computing the next level (which
23       is unusual in Merkle trees). This results in certain sequences of
24       transactions leading to the same merkle root. For example, these two
25       trees:
26
27                    A               A
28                  /  \            /   \
29                B     C         B       C
30               / \    |        / \     / \
31              D   E   F       D   E   F   F
32             / \ / \ / \     / \ / \ / \ / \
33             1 2 3 4 5 6     1 2 3 4 5 6 5 6
34
35       for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
36       6 are repeated) result in the same root hash A (because the hash of both
37       of (F) and (F,F) is C).
38
39       The vulnerability results from being able to send a block with such a
40       transaction list, with the same merkle root, and the same block hash as
41       the original without duplication, resulting in failed validation. If the
42       receiving node proceeds to mark that block as permanently invalid
43       however, it will fail to accept further unmodified (and thus potentially
44       valid) versions of the same block. We defend against this by detecting
45       the case where we would hash two identical hashes at the end of the list
46       together, and treating that identically to the block having an invalid
47       merkle root. Assuming no double-SHA256 collisions, this will detect all
48       known ways of changing the transactions without affecting the merkle
49       root.
50*/
51uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
52    bool mutation = false;
53    while (hashes.size() > 1) {
54        if (mutated) {
55            // Check every level because equal pairs can appear above the leaves,
56            // as in the [1,2,3,4,5,6,5,6] construction described above.
57            // Continuing after finding one is redundant, but mutated blocks should
58            // not propagate through the network anyway, and the total number of
59            // comparisons is the same as for an unmutated input of the same length.
60            for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
61                if (hashes[pos] == hashes[pos + 1]) mutation = true;
62            }
63        }
64        if (hashes.size() & 1) {
65            hashes.push_back(hashes.back());
66        }
67        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
68        hashes.resize(hashes.size() / 2);
69    }
70    if (mutated) *mutated = mutation;
71    if (hashes.size() == 0) return uint256();
72    return hashes[0];
73}
74
75
76uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
77{
78    std::vector<uint256> leaves;
79    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
80    for (size_t s = 0; s < block.vtx.size(); s++) {
81        leaves.push_back(block.vtx[s]->GetHash().ToUint256());
82    }
83    return ComputeMerkleRoot(std::move(leaves), mutated);
84}
85
86uint256 BlockWitnessMerkleRoot(const CBlock& block)
87{
88    std::vector<uint256> leaves;
89    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
90    leaves.emplace_back(); // The witness hash of the coinbase is 0.
91    for (size_t s = 1; s < block.vtx.size(); s++) {
92        leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
93    }
94    return ComputeMerkleRoot(std::move(leaves));
95}
96
97/* This implements a constant-space merkle path calculator, limited to 2^32 leaves. */
98static void MerkleComputation(const std::vector<uint256>& leaves, uint32_t leaf_pos, std::vector<uint256>& path)
99{
100    path.clear();
101    Assume(leaves.size() <= UINT32_MAX);
102    if (leaves.size() == 0) {
103        return;
104    }
105    // count is the number of leaves processed so far.
106    uint32_t count = 0;
107    // inner is an array of eagerly computed subtree hashes, indexed by tree
108    // level (0 being the leaves).
109    // For example, when count is 25 (11001 in binary), inner[4] is the hash of
110    // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
111    // the last leaf. The other inner entries are undefined.
112    uint256 inner[32];
113    // Which position in inner is a hash that depends on the matching leaf.
114    int matchlevel = -1;
115    // First process all leaves into 'inner' values.
116    while (count < leaves.size()) {
117        uint256 h = leaves[count];
118        bool matchh = count == leaf_pos;
119        count++;
120        int level;
121        // For each of the lower bits in count that are 0, do 1 step. Each
122        // corresponds to an inner value that existed before processing the
123        // current leaf, and each needs a hash to combine it.
124        for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
125            if (matchh) {
126                path.push_back(inner[level]);
127            } else if (matchlevel == level) {
128                path.push_back(h);
129                matchh = true;
130            }
131            h = Hash(inner[level], h);
132        }
133        // Store the resulting hash at inner position level.
134        inner[level] = h;
135        if (matchh) {
136            matchlevel = level;
137        }
138    }
139    // Do a final 'sweep' over the rightmost branch of the tree to process
140    // odd levels, and reduce everything to a single top value.
141    // Level is the level (counted from the bottom) up to which we've sweeped.
142    int level = 0;
143    // As long as bit number level in count is zero, skip it. It means there
144    // is nothing left at this level.
145    while (!(count & ((uint32_t{1}) << level))) {
146        level++;
147    }
148    uint256 h = inner[level];
149    bool matchh = matchlevel == level;
150    while (count != ((uint32_t{1}) << level)) {
151        // If we reach this point, h is an inner value that is not the top.
152        // We combine it with itself (Bitcoin's special rule for odd levels in
153        // the tree) to produce a higher level one.
154        if (matchh) {
155            path.push_back(h);
156        }
157        h = Hash(h, h);
158        // Increment count to the value it would have if two entries at this
159        // level had existed.
160        count += ((uint32_t{1}) << level);
161        level++;
162        // And propagate the result upwards accordingly.
163        while (!(count & ((uint32_t{1}) << level))) {
164            if (matchh) {
165                path.push_back(inner[level]);
166            } else if (matchlevel == level) {
167                path.push_back(h);
168                matchh = true;
169            }
170            h = Hash(inner[level], h);
171            level++;
172        }
173    }
174}
175
176static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
177    std::vector<uint256> ret;
178    MerkleComputation(leaves, position, ret);
179    return ret;
180}
181
182std::vector<uint256> TransactionMerklePath(const CBlock& block, uint32_t position)
183{
184    std::vector<uint256> leaves;
185    leaves.resize(block.vtx.size());
186    for (size_t s = 0; s < block.vtx.size(); s++) {
187        leaves[s] = block.vtx[s]->GetHash().ToUint256();
188    }
189    return ComputeMerklePath(leaves, position);
190}
191