src/primitives/block.cpp

   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 uint256 CBlockHeader::GetHash() const
  14 {
  15     return SerializeHash(*this);
  16 }
  17
  18 uint256 CBlock::BuildMerkleTree(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     vMerkleTree.clear();
  56     vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
  57     for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
  58         vMerkleTree.push_back(it->GetHash());
  59     int j = 0;
  60     bool mutated = false;
  61     for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
  62     {
  63         for (int i = 0; i < nSize; i += 2)
  64         {
  65             int i2 = std::min(i+1, nSize-1);
  66             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                 mutated = true;
  69             }
  70             vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
  71                                        BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
  72         }
  73         j += nSize;
  74     }
  75     if (fMutated) {
  76         *fMutated = mutated;
  77     }
  78     return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
  79 }
  80
  81 std::vector<uint256> CBlock::GetMerkleBranch(int nIndex) const
  82 {
  83     if (vMerkleTree.empty())
  84         BuildMerkleTree();
  85     std::vector<uint256> vMerkleBranch;
  86     int j = 0;
  87     for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
  88     {
  89         int i = std::min(nIndex^1, nSize-1);
  90         vMerkleBranch.push_back(vMerkleTree[j+i]);
  91         nIndex >>= 1;
  92         j += nSize;
  93     }
  94     return vMerkleBranch;
  95 }
  96
  97 uint256 CBlock::CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex)
  98 {
  99     if (nIndex == -1)
 100         return uint256();
 101     for (std::vector<uint256>::const_iterator it(vMerkleBranch.begin()); it != vMerkleBranch.end(); ++it)
 102     {
 103         if (nIndex & 1)
 104             hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
 105         else
 106             hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
 107         nIndex >>= 1;
 108     }
 109     return hash;
 110 }
 111
 112 std::string CBlock::ToString() const
 113 {
 114     std::stringstream s;
 115     s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, hashReserved=%s, nTime=%u, nBits=%08x, nNonce=%s, vtx=%u)\n",
 116         GetHash().ToString(),
 117         nVersion,
 118         hashPrevBlock.ToString(),
 119         hashMerkleRoot.ToString(),
 120         hashReserved.ToString(),
 121         nTime, nBits, nNonce.ToString(),
 122         vtx.size());
 123     for (unsigned int i = 0; i < vtx.size(); i++)
 124     {
 125         s << "  " << vtx[i].ToString() << "\n";
 126     }
 127     s << "  vMerkleTree: ";
 128     for (unsigned int i = 0; i < vMerkleTree.size(); i++)
 129         s << " " << vMerkleTree[i].ToString();
 130     s << "\n";
 131     return s.str();
 132 }