What is a Merkle proof?

A Merkle tree hashes each item, hashes pairs of those hashes together, and repeats until one hash remains, the root. Each level holds about half as many hashes as the level below it.

The root stands for the whole list, so one short value can commit to a list of any length.

To prove that an item is in the tree, the prover sends the item and the hash of each sibling along the path from the item up to the root. The verifier hashes its way up the path and compares the result with the root.

The path has one hash per level, so its length grows with the logarithm of the number of items. A list of a million items needs a path of about twenty hashes.

A plain Merkle proof reveals the item it proves. A private system can instead prove membership inside a zero-knowledge proof, so the verifier learns that some item in the tree is included without learning which one.