A Merkle tree is a data structure that allows efficient and secure verification of large data structures. The Merkle tree is named after its inventor Ralph C. Merkle, but is also called a binary hash tree because of its technical implementation. Binary on the one hand means that each node of the tree has two child nodes. Hash, on the other hand, points out that it does not store the data themselves but hash values, double SHA256 in the case of Bitcoin. As shown in the diagram below, the calculation of hash values is based on the data elements that should be part of the tree.

There is a hash value in the form of a sheet for each data element in the tree.

In order to ensure the binary properties of the tree, 2n objects are needed.

The Bitcoin implementation bypasses this problem by duplicating the last elements of an odd number, i.e. adding them once more to the tree. However, this approach creates a serious security problem, as duplicating elements from different input values could result in the same Merkle root.

This problem has been fixed in Bitcoin version 0.6.2 by checking for duplicates before creating the Merkle root. Now, when the hash values of the leaves have been calculated, the nodes of the next level are calculated by combining two leaves and calculating the hash value. As shown in the diagram above, h1 (the hash value of AAAA) and h2 (the hash value of BBBB) are used, linked together and the hash value is calculated again. The result is called h12 in this case. This procedure is repeated until the root node (also called Root Merkle) is calculated.

Bitcoin calculates a Merkle tree from all transactions that are grouped into a block and stores its root (the Merkle root) in the block header.

You can find the Merkle Root of a transaction on the blockchain.info site for example.

 

A Merkle Root looks like this: 29577fd708108261f9029d06fed593f655af2dd6ef2b9a2ce3bd7127df9dc854

 

As already mentioned, by using Merkle trees, it is possible to effectively check if a particular element is part of the tree.

The diagram above shows a 16 leaf tree that could represent transactions in a bitcoin block. In order to check whether a particular transaction – in this case, hK – is part of a block, not all transactions need to be loaded, but only the 4 blue nodes (hL, hIJ, hMNOP and hABCDEFGH).

By calculating 4 hashes (hKL, hIJKLL, hIJKLMNOP, hABCDEFGHIJKLMNOP) and comparing the resulting Merkle root, it can be proven at any time that hK is part of the tree.              

In a Merkle tree with N elements, checking the inclusion of a particular element is at most necessary

2*ln(N)

The calculations. A Bitcoin block generally contains several hundred transactions (in May 2018, a block contains on average 1500 transactions). For the block 520 000, it comprises 1829 transactions, therefore :

2 ∗ ln(1829) = 15.02304929678