# What is a Merkle tree?

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.

Also called hash tree.

## How it works

Every item is hashed, pairs of hashes are hashed together, and so on up to a single root. To prove that an item is included, you show the hashes along its path to the root.

## Where it is used

Bitcoin blocks commit to their transactions with a Merkle root. Shielded pools keep their note commitments in a Merkle tree, and a zero-knowledge proof shows that a note is in the tree without revealing where.

## In Redacted

Redacted’s note tree is append-only and 4.3 billion slots deep. Proving that a note is in it always takes thirty-two hashes, whether it is the fourth note or the four billionth.

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

## Related terms

- [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.
- [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.
- [Shielded pool](https://redacted.gg/glossary/shielded-pool.md): A shielded pool holds funds as private notes inside a smart contract. Deposits and withdrawals are public, but what happens inside is proved with zero-knowledge proofs and does not reveal who owns what.

Sources: [Merkle tree, Wikipedia](https://en.wikipedia.org/wiki/Merkle_tree), [Bitcoin whitepaper](https://bitcoin.org/bitcoin.pdf)
---

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