# What is a Merkle proof?

A Merkle proof shows that an item belongs to a Merkle tree. It is the item together with a short list of sibling hashes, which lets anyone recompute the tree's root and compare it with the root they already trust.

Also called Merkle path, Merkle branch, authentication path or inclusion proof.

## How a Merkle tree is built

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.

## How the proof works

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.

## Why it matters for privacy

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.

## In Redacted

In Redacted, each note is a SHA-256 commitment in a Merkle tree, and spending requires a zero-knowledge proof that you own an unspent note in that tree, without revealing which one. The tree has 67 million slots, and appending a note costs twenty-six hashes whichever note it is.

More: [Architecture](https://redacted.gg/docs/protocol/architecture.md)

## Related terms

- [Merkle tree](https://redacted.gg/glossary/merkle-tree.md): A Merkle tree fingerprints a long list with one short value, the root, so that anyone can prove an item is in the list with a handful of hashes instead of the whole list.
- [Commitment](https://redacted.gg/glossary/commitment.md): A commitment locks in a piece of data without revealing it. Later it can be opened and anyone can check that it matches, but until then it gives nothing away and cannot be changed.
- [Hash function](https://redacted.gg/glossary/hash-function.md): A hash function turns any input into a short fingerprint of fixed size. The same input always gives the same fingerprint, and nobody can work back from it or find two inputs that share one.
- [Note](https://redacted.gg/glossary/note.md): A note is a sealed entry on-chain that records coins in Redacted’s Reserve and that only your keys can open. From the outside all notes look alike, whoever owns them and whatever they hold.
- [Zero-knowledge proof](https://redacted.gg/glossary/zero-knowledge-proof.md): A zero-knowledge proof lets someone prove that a statement is true without revealing anything else, for example that they own funds and may spend them, without showing which funds or who they are.
- [FRI](https://redacted.gg/glossary/fri.md): FRI is the low-degree test used in STARKs. It checks that committed values come from a polynomial of low degree by halving the problem round after round and testing a few random points, and it rests only on hash functions.

Sources: [Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto](https://bitcoin.org/bitcoin.pdf), [Merkle tree, Bitcoin Wiki](https://en.bitcoin.it/wiki/Merkle_tree), [Fast Reed-Solomon Interactive Oracle Proofs of Proximity, ECCC 2017](https://eccc.weizmann.ac.il/report/2017/134/)
---

Page: https://redacted.gg/glossary/merkle-proof/