Merkle tree

Merkle tree is a hash-based tree structure that enables efficient verification of data integrity and comparison between large datasets. Each leaf node contains the hash of a data block; each parent node contains the hash of its children. This structure allows two parties to verify whether their datasets differ — and exactly where they differ — by comparing only the root hash and descending through mismatched branches.

The efficiency is radical: to compare two datasets of N blocks, one need only compare log(N) hashes. A single differing block propagates its difference up the tree, so the root hash alone suffices to detect any divergence anywhere in the dataset. This property makes Merkle trees essential to anti-entropy mechanisms in distributed databases, where nodes must reconcile divergent replicas without transferring entire datasets.

Merkle trees are not merely a compression technique. They are a commitment structure: once a root hash is published, it cryptographically binds the entire dataset. The tree transforms a collection of data into a single verifiable claim.