Merkle Trees

What are Merkle trees?

A Merkle tree, also referred to as a hash tree, is a hash-based cryptographic data structure that allows efficient database verifications in order to provide data integrity. The core concept was patented by Ralph Merkle in 1979 and plays an important role in blockchain-based systems.

Merkle trees rely entirely on hash functions. The leaves of the tree are computed as hashes of the data blocks, and the nodes are then subsequently computed by concatenating and hashing their respective children. This procedure is repeated until a single hash reference remains, which is also called the root of the Merkle tree.

The figure below shows a binary Merkle tree of depth two, where four data blocks are linked together with hash references in a tree-like fashion. As we can see, the leaves $n_{00}$ and $n_{01}$ are computed by hashing the data blocks $d_{00}$ and $d_{01}$, respectively. The resulting hashes $n_{00}$ and $n_{01}$ are then concatenated and hashed again to the node $n_{0}=H\left(n_{00} \| n_{01}\right)$, which is then hashed together with $n_{1}$ to the Merkle root $r$.

Figure 1