Merkle Tree

A Merkle tree is a structure that allows for efficient and secure verification of content in a large body of data. This structure helps verify the consistency and content of the data.

How does it work ?

A Merkle tree summarizes all the transactions in a block by producing a digital fingerprint of the entire set of transactions enabling a user to verify whether or not a transaction is included in a block.

Let's take an example :

Consider four transactions in a block : A, B, C  and D. Each of these is hashed and stored in each leaf node, resulting in hash A, B, C and D. Consecutive pair of leaf nodes are then summarized in a parent node by hashing Hash A and Hash B, resulting in Hash AB and separately hashing Hash C and D resulting in Hash CD. The two hashes (Hash AB and Hash CD) are then hashed again to produce the Root Hash (the Merkle Root).

By the way, the Merkle Root is here going to summarize all of the data in the related transactions, and be stored in the block header in order to maintain the integrity of the data. Indeed, if a single detail in any of the transactions or the order of the transactions was to change, the merkle root will change signaling as such a modification of the initial tree. So, as you can see,  using Merkle tree is a convenient way for a quick and simple way of testing if a specific transaction is included in a set or not.

Merkel Tree use cases

Using a Merkel Tree significantly reduces the amount of data that a trusted authority has to maintain for verification purposes by separating the validation of the data from the data itself. As such, a Merkel tree can reside locally, or on a distributed system and allows several benefits among which :

• a mean to provide the integrity and validity of data

• little memory or disk space requirement as the proofs are computionally easy and fast

• easy proof and management thanks to the tiny amounts of information required to be transmitted across networks

Merkle trees are aspecially used in Simplified Payment verification (SPV) process and as such are an indispensable tools for miners and users on the blockchain. However, they're not only used among the crypto space and are also at the heart of several peer-to-peer networks such as BitTorrent, Git, Bitcoin and Ethereum.