Merkle's hash tree proves one record is in a giant file with a handful of hashes

Proving that a record is part of a large dataset usually meant sending the dataset. That is impractical for a backup, a file of transactions, or a web cache.

Merkle's 1979 dissertation and 1989 paper describe a tree in which every block is hashed and hashes are paired until one root remains. Verifying a member requires the log-n hashes on the path, not the file.

The tree turns a membership test into an equality test on the root, and a change anywhere shows up as a changed path. It is how a whole data structure can be vouched for without every byte being seen.

Commit to leaves by hashing pairwise up to one root

Proof size is logarithmic, so verification stays cheap on the biggest datasets.

The root commits to the entire dataset, so any tampering is detected.

A verifier needs only the root and a short path, not a trust in the server.

It is a chain of one-way hashes, so no information about the data is disclosed.

To prove a fact about a huge whole, do not send the whole. Collapse it to one digest, then give only the short path that connects the one claim to that digest.

Merkle trees are foundational in Git, cryptocurrency blockchains, certificate transparency, and distributed storage. They let a client verify a small piece of a large, unauthenticated store by trusting only one short root.