Merkle tree

To prove that a piece of data belongs to the set, an inclusion proof (Merkle proof) suffices: the minimal set of sibling hashes along the path from the leaf to the root. The verifier recomputes the hashes up to the root and compares, with logarithmic cost, on the order of log n hashes for n elements, without needing the full set. The concept comes from Ralph Merkle, who patented it in his 1979 digital-signatures application, and is built entirely on cryptographic hash functions.

It is a foundational blockchain structure: it lets integrity and inclusion of large volumes be verified with minimal data. It enables light clients (SPV), which verify a transaction against the block root without downloading the entire block, a key feature for modest devices to trust the network.

In Bitcoin, each block header stores the Merkle root of its transactions, and SPV nodes use Merkle proofs. Ethereum uses a variant, the Merkle-Patricia Trie, for state, transactions and receipts. Many airdrops, such as Uniswap (UNI) or Optimism (OP), commit the eligibility list as a Merkle root and each user claims with their inclusion proof. It is also the internal commitment structure of zk-STARKs and a common support for membership proofs in zk-SNARKs.