Computational cryptography › Hashes and symmetric ciphers
COMMITMENTPrimitive

Merkle trees, hash commitments

In plain words

Fingerprint a huge pile of data into one short value, then prove any piece belongs with a short chain of fingerprints.

The idea: Hash every piece of data, then hash the hashes in pairs, and keep going up until one hash is left: the root. Anyone holding the root can be convinced that a piece belongs by being shown just the sibling hashes along its path to the top: about 20 hashes for a million items. Changing any piece would change the root, unless you could find a hash collision.

Why it matters: Used by git, certificate logs, blockchains and file systems.

A tree of fingerprints
12345678######rootdata itemspublished
Every box is the hash of the two boxes below it. To prove that item 3 is in the tree, hand over just the three orange hashes. The verifier hashes item 3 with them, climbing the blue path, and checks that the result equals the published root. Changing any item would change the root, unless someone could find a hash collision.

The details

On the map: certificate transparency, git, file integrity

Hash data in a tree so that one root hash commits to everything[1], and a short path of hashes proves any item is included.

Where you meet it: certificate transparency logs[2], git, blockchains, IPFS, file-system integrity (ZFS, dm-verity), and inside STARKs and hash-based signatures. It needs collision resistance.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. Ralph C. Merkle. A Digital Signature Based on a Conventional Encryption Function. Advances in Cryptology — CRYPTO ’87, 1987. doi:10.1007/3-540-48184-2_32
  2. B. Laurie, A. Langley and E. Kasper. Certificate Transparency. RFC 6962, 2013. rfc-editor.org/rfc/rfc6962