user323: 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?

user38618: 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];
}


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

user208: 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


323: <p>I`m slowly implementing some Bitcoin protocols, and I'm not sure how to properly understand the Merkle Tree from the Bitcoin wiki:
<a href="https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees" rel="noreferrer">https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees</a>
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?</p>
 38618: <p>Bitcoin Core's merkle root calculation function can be found <a href="https://github.com/bitcoin/bitcoin/blob/master/src/consensus/merkle.cpp#L46" rel="nofollow noreferrer">here</a>. Here's the simplified version:</p>

<pre><code>// Input: individual transaction hashes (a.k.a. leafs)
uint256 ComputeMerkleRoot(std::vector&lt;uint256&gt; hashes) {
    while (hashes.size() &gt; 1) {
        // If there's an odd number of hashes
        if (hashes.size() &amp; 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];
}
</code></pre>
 403: <p>You hash the hashes. See the bottom of <a href="https://en.bitcoin.it/wiki/Dump_format#CBlock" rel="noreferrer">https://en.bitcoin.it/wiki/Dump_format#CBlock</a> for an image.</p>
 208: <p>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.</p>

<p>Assume you have tx hashes Ha1,Ha2,Ha3,Ha4,Ha5,Ha6,Ha7</p>

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