Merkle tree

A Merkle tree, or hash tree, is a binary tree built over a sequence of data blocks: each leaf is the hash of one block, and each interior node is the hash of the concatenation of its children^[1]. The root hash is a short commitment to the entire sequence. Anyone who holds only the root can check that a block belongs to the sequence, at a given position, from the sibling hashes along the block's path to the root, which are logarithmic in number; and two parties holding large sequences can find where they differ by exchanging hashes top-down, descending only where they disagree. Ralph Merkle introduced the construction in 1979 to sign many messages with one public key^[2]^[3]. It is now used in version control, cryptocurrencies, certificate transparency logs, replicated storage and post-quantum signatures.

§ 01

Construction

Let $H$ be a collision-resistant hash function and $d_{0}, \dots, d_{n - 1}$ the data blocks. The Merkle tree hash of RFC 6962, used by Certificate Transparency, splits a sequence of $n \geq 2$ blocks at $k$ , the largest power of two less than $n$ , and hashes leaves and interior nodes with different one-byte prefixes^[4]:

MTH (d_{i}) MTH (d_{0.. n}) = H (0x00 ∥ d_{i}) = H (0x01 ∥ MTH (d_{0.. k}) ∥ MTH (d_{k .. n}))

The left subtree is always a perfect binary tree, and a tree with $n$ leaves has depth $⌈ lo g_{2} n ⌉$ . Building it takes $n$ leaf hashes and $n - 1$ interior hashes.

An RFC 6962 Merkle tree over an array of strings, with audit paths and their verification. Sha256.digest is a plain implementation of SHA-256.

(* A Merkle tree over a list of entries, as specified by RFC 6962.
   Leaves and interior nodes are hashed with different one-byte prefixes. *)
let h = Sha256.digest
let leaf_hash d = h ("\x00" ^ d)
let node_hash l r = h ("\x01" ^ l ^ r)
 
(* The largest power of two strictly less than n (n >= 2). *)
let split n = let k = ref 1 in while 2 * !k < n do k := 2 * !k done; !k
 
let sub a i n = Array.sub a i n
 
let rec root (d : string array) =
  match Array.length d with
  | 0 -> h ""
  | 1 -> leaf_hash d.(0)
  | n -> let k = split n in node_hash (root (sub d 0 k)) (root (sub d k (n - k)))
 
(* The audit path for entry m: the sibling hashes from the leaf up. *)
let rec path m (d : string array) =
  match Array.length d with
  | 1 -> []
  | n ->
    let k = split n in
    if m < k then path m (sub d 0 k) @ [root (sub d k (n - k))]
    else path (m - k) (sub d k (n - k)) @ [root (sub d 0 k)]
 
(* Recompute the root from one entry, its index, the tree size and the
   path. The verifier needs nothing else. *)
let root_from_path m n entry path =
  let rec go m n path =         (* path is in top-down order here *)
    if n = 1 then leaf_hash entry
    else
      let k = split n in
      match path with
      | sib :: rest -> if m < k then node_hash (go m k rest) sib
                       else node_hash sib (go (m - k) (n - k) rest)
      | [] -> failwith "path too short"
  in
  go m n (List.rev path)
 
let short s = String.sub (Sha256.hex s) 0 12

§ 02

Inclusion proofs

To show that $d_{m}$ is the $m$ -th block of a sequence whose root is $r$ , a prover sends the audit path: the hash of the sibling of every node on the path from $d_{m}$ 's leaf to the root. The verifier hashes $d_{m}$ , combines the result with each sibling in turn, on the left or the right according to the bits of the position, and accepts if it arrives at $r$ . The proof has $⌈ lo g_{2} n ⌉$ hashes; the verifier needs nothing else about the other blocks^[1]^[4].

The tree for seven entries. To prove entry 4, the prover sends the three shaded sibling hashes; the verifier recomputes the highlighted path and compares the result with the root.

Proving and verifying membership of one entry.

open Merkle
 
let entries = [| "alice pays bob 5"; "bob pays carol 2"; "carol pays dan 7";
                 "dan pays erin 1"; "erin pays frank 3"; "frank pays gina 4";
                 "gina pays alice 9" |]

Running it.

root of 7 entries: 8eda8ac2eef5
audit path for entry 4 (3 hashes):
  826cb8405bce
  5046acbe2ec2
  491857a27003
entry 4 as recorded:  true
entry 4 altered:      false
path length in a tree of 1000000 entries: 20

Changing any entry, or presenting the entry at a different position, produces a different root unless the verifier has found a collision in $H$ . The argument is an induction on the tree: if two different sequences had the same root, then at the first node where they differ, the hashed inputs differ and the outputs agree.

A log that only grows can also prove that its tree of $n$ entries extends an earlier tree of $n_{0} < n$ entries without rewriting it, again with $O (lo g n)$ hashes. Certificate Transparency logs publish such consistency proofs so that auditors can detect a log that shows different histories to different clients^[4]^[8]^[13].

§ 03

Domain separation and odd levels

The prefixes matter. Without them, an interior node is the hash of 64 bytes, and those 64 bytes are also a valid leaf. A tree with the leaves $a, b, c, d$ then has the same root as the two-leaf tree whose leaves are $H (a) ∥ H (b)$ and $H (c) ∥ H (d)$ , which gives a second preimage of the root without breaking $H$ . How an odd number of nodes is paired matters too. Bitcoin's transaction tree pairs the last node of an odd level with itself^[5], so a block's transaction list and the same list with its last transaction repeated have the same root; an attacker could use this to make nodes reject a valid block, which was reported as CVE-2012-2459^[6].

A naive tree without prefixes that pairs an odd node with itself, against the RFC 6962 tree.

(* A naive tree: no prefixes, and an odd node is paired with itself,
   as in Bitcoin's transaction tree. *)
let h = Sha256.digest
let rec naive_level = function
  | [] -> []
  | [x] -> [h (x ^ x)]
  | x :: y :: rest -> h (x ^ y) :: naive_level rest
let rec naive_top = function [x] -> x | l -> naive_top (naive_level l)
let naive_root leaves = naive_top (List.map h leaves)

Running it.

naive [a;b;c]:       d31a37ef6ac1
naive [a;b;c;c]:     d31a37ef6ac1
naive [a;b;c;d]:     14ede5e8e97a
naive [x;y]:         14ede5e8e97a
RFC 6962 [a;b;c;d]:  33376a3bd63e
RFC 6962 [x;y]:      22c47d7198de
RFC 6962 [a;b;c]:    36642e73c254
RFC 6962 [a;b;c;c]:  e9636069c740

§ 04

Comparing replicas

Two replicas that each keep a Merkle tree over the same key ranges can find their differences by comparing roots, then the children of any node whose hashes differ, and so on down to the leaves. When $k$ entries differ in a tree of $n$ , this compares $O (k lo g n)$ hashes instead of $n$ entries. Amazon's Dynamo used such trees for anti-entropy between replicas^[7], and Cassandra and Riak adopted the scheme.

Finding the two changed entries among 65,536.

open Merkle
 
(* A tree kept in memory, so two replicas can compare it level by level. *)
type tree = Leaf of int * string | Node of string * tree * tree
let hash_of = function Leaf (_, x) -> x | Node (x, _, _) -> x
 
let rec build d lo n =
  if n = 1 then Leaf (lo, leaf_hash d.(lo))
  else
    let k = split n in
    let l = build d lo k and r = build d (lo + k) (n - k) in
    Node (node_hash (hash_of l) (hash_of r), l, r)
 
(* Find the entries that differ, descending only into subtrees whose
   hashes disagree. Counts the hashes that had to be compared. *)
let compared = ref 0
let rec diff a b =
  incr compared;
  if hash_of a = hash_of b then []
  else match a, b with
    | Leaf (i, _), Leaf _ -> [i]
    | Node (_, al, ar), Node (_, bl, br) -> diff al bl @ diff ar br
    | _ -> invalid_arg "trees of different shapes"

Running it.

entries: 65536, differing: [4242; 60000]
hashes compared: 63

§ 05

Applications

Content addressing

In Git, every file is stored under the hash of its contents, a directory is stored as a list of names and child hashes, and a commit records the hash of its root directory and of its parents^[10]. The result is a Merkle DAG rather than a balanced tree: a commit hash commits to the complete history and every file in it, and two trees can be compared by skipping subdirectories whose hashes agree. File systems such as ZFS store each block's checksum in its parent pointer for the same reason, and peer-to-peer systems such as IPFS and BitTorrent address content by Merkle roots.

Blockchains

A Bitcoin block header contains the Merkle root of the block's transactions. A lightweight client that stores only headers can check that a transaction was included in a block from its audit path, which Nakamoto called simplified payment verification^[5].

Transparency logs

Certificate Transparency requires certificate authorities to submit certificates to public append-only logs, which are Merkle trees; browsers can demand an inclusion proof, and monitors check consistency proofs between successive published roots^[4]^[13].

Hash-based signatures

Merkle's original purpose was signatures. A Lamport one-time signature key signs a single message^[11]. Generating $2^{h}$ one-time key pairs and publishing the root of a Merkle tree over their public keys gives a single public key for $2^{h}$ messages: a signature is a one-time signature, the one-time public key, and its audit path^[1]. The signer needs to produce authentication paths efficiently, which Szydlo showed can be done in $O (lo g n)$ time and space per signature^[9]. Because their security rests only on the hash function, these schemes are believed to resist quantum computers; SPHINCS+ was standardized by NIST as SLH-DSA in 2024^[12].

§ 06

History

Merkle described hash trees in his 1979 Stanford thesis^[2] and in a patent filed the same year and granted in 1982^[3], as a way to authenticate many Lamport one-time signature keys with a single value^[11]. The published paper, “A digital signature based on a conventional encryption function”, appeared at CRYPTO ’87^[1]. The structure spread well beyond signatures: Git (2005) and Bitcoin (2008) put Merkle DAGs and trees at the core of their data models^[5]^[10], Dynamo used them for replica repair^[7], and Crosby and Wallach's history trees for tamper-evident logs^[8] led to Certificate Transparency, standardized in RFC 6962 in 2013^[4].