wire / wire-format / merkle-tree

Merkle tree (hash 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).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Merkle tree (hash tree)

wire format

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).

fieldsizemeaning
Leaf nodehash sizeHash of a data block (e.g., SHA-256 of a 4KB block).
Internal nodehash sizeHash of (left child hash || right child hash). For odd number of leaves, duplicate the last leaf.
Root (Merkle root)hash sizeTop of the tree. Summarizes all data blocks.
Proof of inclusionlog2(n) hashesTo prove a leaf is in the tree, provide the leaf and the sibling hashes along the path to the root (Merkle proof).
VerificationO(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)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/merkle-tree or /wire-format/merkle-tree.json