Build a Merkle Tree

hash tree with inclusion proofs

Challenge 8 of Indexes & StructuresAdvanced~55 min

Prove a piece of data belongs to a huge dataset by checking a handful of hashes. Hash the leaves, fold them pairwise into a single root, generate an inclusion proof for any leaf, and verify it, the tamper-evident structure behind Git, Bitcoin, and database anti-entropy.

4 steps

1. 1Hashing Leaves and Pairs
2. 2Building the Root
3. 3Inclusion Proofs
4. 4Verifying a Proof