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                 :     369677 : uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
      46                 :     369677 :     bool mutation = false;
      47         [ +  + ]:     431223 :     while (hashes.size() > 1) {
      48         [ +  + ]:      61546 :         if (mutated) {
      49         [ +  + ]:     594954 :             for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
      50         [ +  + ]:     559031 :                 if (hashes[pos] == hashes[pos + 1]) mutation = true;
      51                 :     559031 :             }
      52                 :      35923 :         }
      53         [ +  + ]:      61546 :         if (hashes.size() & 1) {
      54                 :      21401 :             hashes.push_back(hashes.back());
      55                 :      21401 :         }
      56                 :      61546 :         SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
      57                 :      61546 :         hashes.resize(hashes.size() / 2);
      58                 :            :     }
      59         [ +  + ]:     369677 :     if (mutated) *mutated = mutation;
      60         [ +  + ]:     369677 :     if (hashes.size() == 0) return uint256();
      61                 :     364489 :     return hashes[0];
      62                 :     369677 : }
      63                 :            : 
      64                 :            : 
      65                 :     168488 : uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
      66                 :            : {
      67                 :     168488 :     std::vector<uint256> leaves;
      68         [ +  - ]:     168488 :     leaves.resize(block.vtx.size());
      69         [ +  + ]:    1174550 :     for (size_t s = 0; s < block.vtx.size(); s++) {
      70         [ +  - ]:    1006062 :         leaves[s] = block.vtx[s]->GetHash();
      71                 :    1006062 :     }
      72         [ -  + ]:     168488 :     return ComputeMerkleRoot(std::move(leaves), mutated);
      73                 :     168488 : }
      74                 :            : 
      75                 :     199977 : uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
      76                 :            : {
      77                 :     199977 :     std::vector<uint256> leaves;
      78         [ +  - ]:     199977 :     leaves.resize(block.vtx.size());
      79         [ +  - ]:     199977 :     leaves[0].SetNull(); // The witness hash of the coinbase is 0.
      80         [ +  + ]:     548951 :     for (size_t s = 1; s < block.vtx.size(); s++) {
      81         [ +  - ]:     348974 :         leaves[s] = block.vtx[s]->GetWitnessHash();
      82                 :     348974 :     }
      83         [ -  + ]:     199977 :     return ComputeMerkleRoot(std::move(leaves), mutated);
      84                 :     199977 : }
      85                 :            :