Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2014 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include "primitives/block.h"
       7             : 
       8             : #include "hash.h"
       9             : #include "tinyformat.h"
      10             : #include "utilstrencodings.h"
      11             : #include "crypto/common.h"
      12             : 
      13      318371 : uint256 CBlockHeader::GetHash() const
      14             : {
      15      318371 :     return SerializeHash(*this);
      16             : }
      17             : 
      18       19571 : uint256 CBlock::ComputeMerkleRoot(bool* fMutated) const
      19             : {
      20             :     /* WARNING! If you're reading this because you're learning about crypto
      21             :        and/or designing a new system that will use merkle trees, keep in mind
      22             :        that the following merkle tree algorithm has a serious flaw related to
      23             :        duplicate txids, resulting in a vulnerability (CVE-2012-2459).
      24             : 
      25             :        The reason is that if the number of hashes in the list at a given time
      26             :        is odd, the last one is duplicated before computing the next level (which
      27             :        is unusual in Merkle trees). This results in certain sequences of
      28             :        transactions leading to the same merkle root. For example, these two
      29             :        trees:
      30             : 
      31             :                     A               A
      32             :                   /  \            /   \
      33             :                 B     C         B       C
      34             :                / \    |        / \     / \
      35             :               D   E   F       D   E   F   F
      36             :              / \ / \ / \     / \ / \ / \ / \
      37             :              1 2 3 4 5 6     1 2 3 4 5 6 5 6
      38             : 
      39             :        for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
      40             :        6 are repeated) result in the same root hash A (because the hash of both
      41             :        of (F) and (F,F) is C).
      42             : 
      43             :        The vulnerability results from being able to send a block with such a
      44             :        transaction list, with the same merkle root, and the same block hash as
      45             :        the original without duplication, resulting in failed validation. If the
      46             :        receiving node proceeds to mark that block as permanently invalid
      47             :        however, it will fail to accept further unmodified (and thus potentially
      48             :        valid) versions of the same block. We defend against this by detecting
      49             :        the case where we would hash two identical hashes at the end of the list
      50             :        together, and treating that identically to the block having an invalid
      51             :        merkle root. Assuming no double-SHA256 collisions, this will detect all
      52             :        known ways of changing the transactions without affecting the merkle
      53             :        root.
      54             :     */
      55             :     std::vector<uint256> vMerkleTree;
      56       39142 :     vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
      57      179653 :     for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
      58       54532 :         vMerkleTree.push_back(it->GetHash());
      59       19571 :     int j = 0;
      60       19571 :     bool mutated = false;
      61       40092 :     for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
      62             :     {
      63        7978 :         for (int i = 0; i < nSize; i += 2)
      64             :         {
      65       15956 :             int i2 = std::min(i+1, nSize-1);
      66        9979 :             if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
      67             :                 // Two identical hashes at the end of the list at a particular level.
      68           0 :                 mutated = true;
      69             :             }
      70       15956 :             vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
      71       31912 :                                        BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
      72             :         }
      73         950 :         j += nSize;
      74             :     }
      75       19571 :     if (fMutated) {
      76       17779 :         *fMutated = mutated;
      77             :     }
      78       58713 :     return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
      79             : }
      80             : 
      81           0 : std::string CBlock::ToString() const
      82             : {
      83           0 :     std::stringstream s;
      84             :     s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%u)\n",
      85           0 :         GetHash().ToString(),
      86             :         nVersion,
      87             :         hashPrevBlock.ToString(),
      88             :         hashMerkleRoot.ToString(),
      89             :         nTime, nBits, nNonce,
      90           0 :         vtx.size());
      91           0 :     for (unsigned int i = 0; i < vtx.size(); i++)
      92             :     {
      93           0 :         s << "  " << vtx[i].ToString() << "\n";
      94             :     }
      95           0 :     return s.str();
      96         330 : }