src/consensus/merkle.cpp

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