wire / wire-format / merkle-tree
A Merkle tree is a binary tree where each leaf is a hash of a data block, and each internal node is a hash of its children. The root hash (Merkle root) summarizes all data. Used for data integrity verification, blockchain (Bitcoin, Ethereum), Git (commit graph), and distributed systems (Cassandra, IPFS).
aka: Merkle tree (hash tree)
spec: Merkle tree (Ralph Merkle, 1979)
A Merkle tree is a binary tree where each leaf is a hash of a data block, and each internal node is a hash of its children. The root hash (Merkle root) summarizes all data. Used for data integrity verification, blockchain (Bitcoin, Ethereum), Git (commit graph), and distributed systems (Cassandra, IPFS).
| field | size | meaning |
|---|---|---|
| Leaf node | hash size | Hash of a data block (e.g., SHA-256 of a 4KB block). |
| Internal node | hash size | Hash of (left child hash || right child hash). For odd number of leaves, duplicate the last leaf. |
| Root (Merkle root) | hash size | Top of the tree. Summarizes all data blocks. |
| Proof of inclusion | log2(n) hashes | To prove a leaf is in the tree, provide the leaf and the sibling hashes along the path to the root (Merkle proof). |
| Verification | O(log n) | Recompute the path from the leaf to the root using the provided siblings. Compare with the expected root. |
example:
00 00 00 00
Merkle tree (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/merkle-tree
or /wire-format/merkle-tree.json