Bitcoin Merkle Tree - merklehub/wiki GitHub Wiki

1. What's Merkle Tree in Bitcoin

Calculating the nodes in a merkle tree" shows the Merkle Root (HABCD) of a list of four transactions: Tx A, Tx B, Tx C, and Tx D:

To verify that a transaction—for example, that with hash HK—is a valid transaction (i.e., part of a list of, in this example, 16 transactions with hashes HA, HB, … HP), one need only perform at most 2*log2(N) < N hashes, shown in the Merkle path here:

If HK leads to the correct Merkle root, then TK was in the transaction list. And the Merkle path, needed to verify Hk corresponds with the Merkle root, only contains 4 hashes in the above example. The Merkle path takes up much less space than storing all the transactions in a block. (In the example above: 4 hashes takes much less space than 16.) This is why SPV is lighter-weight. In this case N = 16, and 2*log2(16) = 5.55… is indeed less than 16.

2. Source code:

uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
    bool mutation = false;
    while (hashes.size() > 1) {
        if (mutated) {
            for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
                if (hashes[pos] == hashes[pos + 1]) mutation = true;
            }
        }
        if (hashes.size() & 1) {
            hashes.push_back(hashes.back());
        }
        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
        hashes.resize(hashes.size() / 2);
    }
    if (mutated) *mutated = mutation;
    if (hashes.size() == 0) return uint256();
    return hashes[0];
}


uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
{
    std::vector<uint256> leaves;
    leaves.resize(block.vtx.size());
    for (size_t s = 0; s < block.vtx.size(); s++) {
        leaves[s] = block.vtx[s]->GetHash();
    }
    return ComputeMerkleRoot(std::move(leaves), mutated);
}

Code Warning:

If you're reading this because you're learning about crypto and/or designing a new system that will use merkle trees, keep in mind that the following merkle tree algorithm has a serious flaw related to duplicate txids, resulting in a vulnerability (CVE-2012-2459).

The reason is that if the number of hashes in the list at a given time is odd, the last one is duplicated before computing the next level (which is unusual in Merkle trees). This results in certain sequences of transactions leading to the same merkle root. For example, these two trees:

        A               A
      /  \            /   \
    B     C         B       C
   / \    |        / \     / \
  D   E   F       D   E   F   F
 / \ / \ / \     / \ / \ / \ / \
 1 2 3 4 5 6     1 2 3 4 5 6 5 6

for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and 6 are repeated) result in the same root hash A (because the hash of both of (F) and (F,F) is C).

The vulnerability results from being able to send a block with such a transaction list, with the same merkle root, and the same block hash as the original without duplication, resulting in failed validation. If the receiving node proceeds to mark that block as permanently invalid however, it will fail to accept further unmodified (and thus potentially valid) versions of the same block. We defend against this by detecting the case where we would hash two identical hashes at the end of the list together, and treating that identically to the block having an invalid merkle root. Assuming no double-SHA256 collisions, this will detect all known ways of changing the transactions without affecting the merkle root.

⚠️ **GitHub.com Fallback** ⚠️