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

CC BY-SA 3.0
2011-09-17T01:44:47.073Z
2011-09-17T01:44:47.073Z
theymos
<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>

CC BY-SA 4.0
2018-09-27T16:23:07.543Z
2018-09-27T16:23:07.543Z
MCCCS
<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>

CC BY-SA 3.0
2011-09-17T11:11:06.820Z
2011-09-17T11:11:06.820Z
Pieter Wuille
<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>

<development><protocol><hash>
How do I implement a Merkle Tree?
ThePiachu
# How do I implement a Merkle Tree?

(Asked by: username_0 on 2011-09-16)

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?

**Tags:** development, protocol, hash


---

## 3 answers

### Answer by username_3 on 2011-09-17. Score: 25 | Accepted answer

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


---

### Answer by username_1 on 2011-09-17. Score: 5

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


---

### Answer by username_2 on 2018-09-27. Score: 1

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


---

