Merkle Trees

Learn about Markle trees, which are briefly described in this lesson.

We'll cover the following

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 n00n_{00} and n01n_{01} are computed by hashing the data blocks d00d_{00} and d01d_{01}, respectively. The resulting hashes n00n_{00} and n01n_{01} are then concatenated and hashed again to the node n0=H(n00n01)n_{0}=H\left(n_{00} \| n_{01}\right), which is then hashed together with n1n_{1} to the Merkle root rr.

Figure 1

Get hands-on with 1200+ tech skills courses.