Merkle Tree

The concept of a Merkle Tree as a binary authentication tree was introduced in [MER79].

We use JavaScript to display the mathematics on this page. Please enable JavaScript in your browser for it to work.

A Merkle Tree is a binary authentication tree built over a set of $n$ values, $Y_0 \ldots Y_{n-1}$.
These $Y$ may be chunks of data we need to authenticate (perhaps in a Bitcoin chain), or OTS private keys we may want to reveal as part of a larger scheme.
The parent of each leaf $Y_i$ is the hash of that value, $H(Y_i)$.
Each node in the binary tree is the hash of the values of both its children in order left-right.
- node = H(leftchild || rightchild)
The value of the root node is published as a public authentication value.

Merkle Tree with $n=8$

Merkle Tree

If we know all the values, $Y_0 \ldots Y_{n-1}$, we can reconstruct the tree and compare the resulting root value with the published value.
But this means an end user needs to store all the values, $Y_0 \ldots Y_{n-1}$
What if we just need to verify one value, say $Y_6$?
To do this we actually only need the values of the nodes at $E$, $5$ and $1$ (shown shaded in the diagram above).
Along with the value of $Y_6$ we can use these 3 values to compute the root value and compare to the published value.
We call this an authentication path.
The procedure to authenticate this example is as follows:
INPUT: Value $Y_6$ to be authenticated, published root value, and authentication path $(E,5,1)$.
PROCEDURE:
1. Node $D = H(Y_6)$
2. Node 6 = $H(D||E)$ // $E$ is given
3. Node 2 = $H(5||6)$ // $5$ is given
4. Node 0 = $H(1||2)$ // $1$ is given
5. if Node 0 = published root value then return OK
  else return Invalid.
Note we require the value of exactly one node at each level to do this.
That means if we have $n$ leaves, the authentication path will consist of $\log_2(n)$ values, e.g. $\log_2(8) = 3$

For a more detailed treatment of authenticating the tree see the next page Authentication Path for a Merkle Tree.

The issuer can publish a single root value as a "trusted" authentication value for the $n$ leaves.
The issuer can publish a single leaf value along with its authentication path.
A verifier can recompute and check that the authentication path results in the "trusted" root value.

See Bitcoin vulnerability (CVE-2012-2459) a vulnerability if the number of hashes in the list at a given level is odd.
Hint: Merkle trees work most efficiently (and safely) if they are perfect. In a perfect tree, all internal nodes have two children and all leaves are at the same level. A perfect Merkle tree of height $h$ has exactly $2^h$ leaf nodes. This avoids the Bitcoin vulnerability above.
- Pedantic note: Some authors use the word complete, but not all definitions of "complete" mean "perfect" as described above.
All the Merkle trees we will look at here will be perfect, so the Bitcoin vulnerability is not an issue.

We can use the Merkle tree construction to generate N one-time signatures. We call this an N-time OTS scheme.

For more details, see our page Basic Merkle Signature Scheme. We don't actually use that scheme in SLH-DSA, but include it here for completeness.

Zhanglu Wang has kindly translated this page to Chinese on the CSDN site Merkle 树. Thank you Wang.

Contents

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 30 August 2026.