Skip to content
ecdsa.com

Merkle tree

A binary hash tree in which each internal node hashes its two children, so one root hash commits to all leaves and membership or append-only growth can be proven with logarithmic-size proofs.
Also written ashash treeMerkle rootinclusion proofconsistency proof

Certificate Transparency (RFC 6962 §2.1, RFC 9162 §2.1) defines the hashing used by most transparency logs: leaves are SHA-256(0x00 ‖ data) and nodes SHA-256(0x01 ‖ left ‖ right), the prefixes preventing a leaf from being passed off as an internal node. An inclusion proof for one entry among a million needs about 20 hashes; a consistency proof shows that a newer tree extends an older one without rewriting history.

The structure underlies CT logs, Sigstore's Rekor, Go's checksum database (sum.golang.org), Bitcoin's transaction root (with a different, double-SHA-256 construction and a known duplicate-leaf quirk), Git and most content-addressed storage, and the hash-based signatures XMSS, LMS and SLH-DSA.

Transparency logs publish signed tree heads (checkpoints) that witnesses cosign, so a log that shows different histories to different clients can be caught.

Standards and references

All terms