Chapter 20Merkle Trees and Stateless Signatures

20.1Why this chapter matters#

The previous chapter left us with a problem: every key we built – Lamport, WOTS⁺, even FORS – is usable only once or a few times. A real signer must produce many signatures under one public key. This chapter supplies the two ideas that make that possible. A Merkle tree binds a large batch of one-time keys under a single public root, and a hypertree addressed by hashing the message turns the whole construction stateless, so the signer need not remember which keys it has already used. These are the last pieces before the FIPS 205 standard of Chapter 21.

20.2Learning goals#

After reading this chapter, you should be able to:

build a Merkle tree over many one-time public keys and verify an authentication path;
explain what makes a many-time hash-based scheme (XMSS) stateful and why that is dangerous;
describe the hypertree and how it enlarges the number of usable keys;
explain how hashing the message to select a leaf removes the state entirely.

20.3The Merkle tree#

A single one-time key is nearly useless on its own. The Merkle tree [1] fixes this: generate many one-time (WOTS⁺) key pairs, hash each public key into a leaf, and build a binary tree in which every internal node is the hash of its two children. The single value at the top – the root – is the public key for all the leaves at once.

To use leaf \(i\), the signer publishes the leaf’s one-time signature plus the authentication path: the sibling hash at each level from the leaf up to the root. The verifier recomputes the leaf, folds it up the path, and accepts only if the final value equals the known root.

**Figure 20.1.** A Merkle tree of height \(3\). Each leaf is the hash of one WOTS⁺ public key; internal nodes hash their two children; the single root is the public key. To authenticate the marked leaf, the signature carries the three orange sibling nodes (the authentication path). The verifier recomputes the leaf and hashes up the path, accepting only if it lands on the known root.

Input: Leaf value \(\ell\), leaf index \(i\), authentication path \((a_0,\dots,a_{h-1})\), root \(r\)

Output: accept or reject

1:\(node \gets \ell\)

2:for \(j = 0,\dots,h-1\) do

3:if bit \(j\) of \(i\) is \(0\) then

4:\(node \gets H(node \,\|\, a_j)\)▷ current node is the left child

5:else

6:\(node \gets H(a_j \,\|\, node)\)▷ current node is the right child

7:end if

8:end for

9:return accept if \(node = r\), else reject

Algorithm 26. Verify a Merkle authentication path

A tree of height \(h\) turns \(2^h\) one-time keys into a single public key of one hash value, at the cost of an \(h\)-node authentication path in every signature.

20.4XMSS and the burden of state#

A Merkle tree of WOTS⁺ keys is essentially the scheme XMSS. It signs \(2^h\) messages under one root – but only if each leaf is used at most once. That is a stateful requirement: the signer must remember which leaves are spent and never repeat one.

Remark 1.1 (Why state is dangerous). State makes a many-time hash signature fragile in practice. If a key is backed up and restored, or run on two machines, or a virtual machine is rolled back, the same leaf index can be used twice – and reusing a one-time key breaks it completely. Stateful hash-based schemes (XMSS, LMS) are standardized and useful, but their safety depends on flawless state management, which is exactly what fails in real deployments.

20.5The hypertree#

Two problems remain: a single tree tall enough to never repeat a leaf would be astronomically expensive to build, and we still want to remove the state. The hypertree addresses the first. It stacks \(d\) layers of Merkle trees so that each tree’s root is signed by a one-time key in the tree one layer up; only the very top root is published.

**Figure 20.2.** A hypertree with \(d=3\) layers. FORS signs the message digest; the bottom Merkle tree signs the FORS public key; each higher layer signs the root of the tree below it; only the top root is the public key. A single “signature” is this whole chain of one-time signatures and authentication paths from the message up to the published root. Chaining \(d\) trees of height \(h\) yields \(2^{dh}\) effective leaves while only ever building trees of height \(h\).

Chaining \(d\) trees of height \(h\) multiplies the exponents: the hypertree behaves like one tree of height \(dh\), giving \(2^{dh}\) usable bottom-layer keys, while never building a tree taller than \(h\). With \(dh\) around sixty, the number of keys is so vast that collisions become negligible – which is what finally lets us drop the state.

20.6From stateful to stateless#

The last idea is how the leaf is chosen. Instead of a counter that must be remembered, the signer hashes the message (together with a fresh random value \(R\)) to pseudorandomly select which bottom-layer tree and leaf to use, and which FORS leaves to reveal: \[(R,\ \text{tree index},\ \text{leaf index},\ \text{FORS indices}) \;\longleftarrow\; H(R \,\|\, PK \,\|\, M).\] Two different messages almost never land on the same addresses because the hypertree is enormous and the message randomizer is included in the selection hash. This is a probability statement, not permission to reuse keys: implementations must never deliberately reuse a WOTS or FORS address. FORS security degrades with the number of signatures and any accidental collisions, while WOTS leaf reuse remains serious. No index is ever recorded, so there is no state to corrupt.

Remark 1.2 (The role of the public seed). One subtlety carries over to the standard. Every hash in the tree is tweaked by a public seed and by an address identifying the node’s position, so that structurally identical nodes in different trees hash differently. Without this, an attacker could attack many positions at once (a multi-target attack). The seed is public but essential, and we return to it in the next chapter.

20.7Summary#

This chapter completed the ladder from one-time keys to a practical many-time signature:

a Merkle tree binds \(2^h\) one-time keys under a single root, authenticated by an \(h\)-node path;
using each leaf once gives a stateful scheme (XMSS), whose safety is fragile in deployment;
a hypertree of \(d\) layers multiplies the key supply to \(2^{dh}\) without building tall trees;
hashing the message and message randomization select the path without signer state, while the enormous address space makes accidental collisions negligible; intentional address reuse is forbidden.

Everything is now in place. The next chapter assembles these pieces exactly as the FIPS 205 standard specifies them, deriving all secrets deterministically from a handful of seeds and addresses.

References

[1]

R. C. Merkle. A digital signature based on a conventional encryption function. In Advances in Cryptology – CRYPTO 1987, pages 369–378, 1987.