Merkle proof

A Merkle tree is a binary tree of hashes: the leaves are hashes of the data and each internal node is the hash of the concatenation of its two children, up to the root. To prove a leaf belongs to the tree, the prover supplies the sibling hashes along the path to the root, about log₂(N) hashes for N leaves. The verifier recombines upward and checks that the result equals the known root. For a million leaves only some 20 hashes are needed, versus processing the entire set.

It verifies membership succinctly without downloading complete datasets. Its typical uses are airdrops, where the eligibility list is committed in a root and each user presents their proof to claim; exchange proof of reserves; and light clients (SPV in Bitcoin), which verify a transaction is in a block without downloading it. As good practice, a solid implementation separates the domain of leaves and internal nodes to prevent second-preimage attacks.