Merkle Trees

Cryptography · Axiom Academy

Hash Trees for Efficient Data Verification Leaves contain hashes of data blocks Internal nodes contain hashes of their children concatenated together Root is a single hash that commits to all data in the tree 2 Building a Merkle Tree Step-by-Step Hash each data block to create the leaf nodes Pair adjacent leaves and hash their concatenation Continue pairing and hashing until only one hash remains (the root) 3 Handling Odd Numbers of Leaves Duplicate the last node - most common in Bitcoin Promote the odd node - skip a level Pad with a null hash - use a predetermined value 4 Merkle Proofs: Efficient Verification The data block you want to verify The Merkle root (trusted value) The sibling hashes along the path from leaf to root Bitcoin & Blockchain: Each block contains a Merkle tree of all transactions. Light clients can verify transactions without downloading the entire blockchain. Git Version Control: Git uses a Merkle tree structure to efficiently track file changes and verify repository integrity. Certificate Transparency: Public logs of SSL certificates use Merkle trees to provide cryptographic proofs of log consistency and inclusion. IPFS & Distributed Storage: Content-addressed storage systems use Merkle DAGs (Directed Acyclic Graphs) to verify data integrity. Apache Cassandra: Uses Merkle trees for anti-entropy repair and detecting inconsistencies between replicas. ZK-SNARKs: Merkle trees provide efficient membership proofs in zero-knowledge proof systems.

This is the written version of the interactive lesson above. See the full Cryptography course.