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 : 231813 : uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
# 46 : 231813 : bool mutation = false;
# 47 [ + + ]: 272801 : while (hashes.size() > 1) {
# 48 [ + + ]: 40988 : if (mutated) {
# 49 [ + + ]: 502409 : for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
# 50 [ + + ]: 465827 : if (hashes[pos] == hashes[pos + 1]) mutation = true;
# 51 : 465827 : }
# 52 : 36582 : }
# 53 [ + + ]: 40988 : if (hashes.size() & 1) {
# 54 : 7160 : hashes.push_back(hashes.back());
# 55 : 7160 : }
# 56 : 40988 : SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
# 57 : 40988 : hashes.resize(hashes.size() / 2);
# 58 : 40988 : }
# 59 [ + + ]: 231813 : if (mutated) *mutated = mutation;
# 60 [ + + ]: 231813 : if (hashes.size() == 0) return uint256();
# 61 : 231810 : return hashes[0];
# 62 : 231813 : }
# 63 : :
# 64 : :
# 65 : : uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
# 66 : 113319 : {
# 67 : 113319 : std::vector<uint256> leaves;
# 68 : 113319 : leaves.resize(block.vtx.size());
# 69 [ + + ]: 677155 : for (size_t s = 0; s < block.vtx.size(); s++) {
# 70 : 563836 : leaves[s] = block.vtx[s]->GetHash();
# 71 : 563836 : }
# 72 : 113319 : return ComputeMerkleRoot(std::move(leaves), mutated);
# 73 : 113319 : }
# 74 : :
# 75 : : uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
# 76 : 118467 : {
# 77 : 118467 : std::vector<uint256> leaves;
# 78 : 118467 : leaves.resize(block.vtx.size());
# 79 : 118467 : leaves[0].SetNull(); // The witness hash of the coinbase is 0.
# 80 [ + + ]: 167171 : for (size_t s = 1; s < block.vtx.size(); s++) {
# 81 : 48704 : leaves[s] = block.vtx[s]->GetWitnessHash();
# 82 : 48704 : }
# 83 : 118467 : return ComputeMerkleRoot(std::move(leaves), mutated);
# 84 : 118467 : }
# 85 : :
|
