22

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?

24

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
5

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

0

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 agree to our terms of service, privacy policy and cookie policy

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