I`m slowly implementing some Bitcoin protocols, and I'm not sure how to properly understand the Merkle Tree from the Bitcoin wiki: https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees I have strings a, b, c, I double-hash them and I get the three leaf nodes. But I'm not sure what to do with the higher nodes. Do I double hash the sum of the resulting bytes (treating them like big numbers), or do I concatenate (treating them like strings), or perhaps do I should something else?

up vote 23 down vote accepted

In each iteration, you concatenate two subsequent hashes of the previous level, and double-sha256 them. If there is an odd number of hashes, concatenate the last element with itself. This gives you a new list of hashes. Repeat, and stop when one hash remains. This is the merkle root.

Assume you have tx hashes Ha1,Ha2,Ha3,Ha4,Ha5,Ha6,Ha7

  • First iteration: Hb1=Hash(Ha1|Ha2), Hb2=Hash(Ha3|Ha4), Hb3=Hash(Ha5|Ha6), Hb4=Hash(Ha7|Ha7)
  • Second iteration: Hc1=Hash(Hb1|Hb2), Hc2=Hash(Hb3|Hb4)
  • Third iteration: Hd1=Hash(Hc1|Hc2) => Merkle root

You hash the hashes. See the bottom of https://en.bitcoin.it/wiki/Dump_format#CBlock for an image.

Bitcoin Core's merkle root calculation function can be found here. Here's the simplified version:

// Input: individual transaction hashes (a.k.a. leafs)
uint256 ComputeMerkleRoot(std::vector<uint256> hashes) {
    while (hashes.size() > 1) {
        // If there's an odd number of hashes
        if (hashes.size() & 1) {
            // Copy it to the end of the hashes array
            hashes.push_back(hashes.back());
        }
        // Compute double SHA256s of (hashes.size() / 2) blocks
        // Save the output to hashes
        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
        // Save the output to hashes
        hashes.resize(hashes.size() / 2);
    }
    // If there were no original hashes, return 0
    if (hashes.size() == 0) return uint256();
    return hashes[0];
}

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.