The encyclopedia · Software & IT · Technical decision · 1979
Merkle's hash tree proves one record is in a giant file with a handful of hashes
Ralph Merkle's 1979 hash tree commits to a whole dataset in one root so any single record is verified with only ~log n hashes, not the file.
Stanford University
the move
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.
why it works
- 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.
what transfers
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.
what came after
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.
references
spotted an error? The archive wants to know.