05 — The Hypertree

The Stateful Problem

Earlier hash-based signatures (XMSS, LMS) use a single Merkle tree:

Public key: The tree root (32 bytes)
Private key: All leaf keys + index counter
Maximum signatures: $2^h$ (tree height)
Critical requirement: You MUST remember which keys you've used

If you lose the state (e.g., crash, restore from backup, multiple servers): You might reuse a key. With WOTS+, reuse = forgery = catastrophic.

SLH-DSA's Solution: The Hypertree

SLH-DSA uses a hypertree — a tree of trees — to achieve statelessness. You don't need to track which keys are used.

Structure

Level d-1:  Root (long-term public key)
               |
    +----------+----------+----------+
    |          |          |          |
Level d-2:  WOTS+       WOTS+       WOTS+ ... (2^h trees)
               |          |          |
    +----------+          |          |
    |                     |          |
Level 1:    FORS        FORS       FORS ... (many trees)
               |                     |
               +---- Message 1      +---- Message 2
               +---- Message 3      +---- Message 4

How It Works

Level d-1 (top): A single WOTS+ key signs the root of the next level.
Level d-2: $2^h$ WOTS+ keys, each signing a subtree root.
... continuing down ...
Level 1 (bottom): FORS trees that actually sign messages.

Stateless Selection

Instead of tracking "which key is next," the signer:

Hashes the message to get a pseudorandom path through the tree.
Uses that path to select which FORS tree and which WOTS+ keys to use.
No state needed — the message itself determines the path.

Message + public key seed
         |
         v
    Pseudorandom generator
         |
         v
    Path: (idx_d-2, idx_d-3, ..., idx_1)
         |
         v
    Select specific WOTS+ and FORS keys

Key insight: Different messages produce different paths (with overwhelming probability). The same message always produces the same path, so re-signing the same message uses the same key — but that's OK because it's the same signature.

Hypertree Parameters

Parameter	Symbol	Typical	Meaning
Total layers	d	7 or 9	Number of levels in the tree
Tree height	h	3 or 4	Height of each Merkle tree
WOTS+ Winternitz	w	16	Hash iterations per chain
FORS trees	k	33	Subsets in FORS
FORS height	a	14	Height of each FORS tree

Signature Size Breakdown

A SLH-DSA signature contains:

Component	Size	What it is
FORS signature	k × (n + a × n)	Selected leaves + Merkle paths
WOTS+ signatures	(d-1) × len × n	One per tree level
Merkle paths	(d-1) × h × n	Paths up the hypertree
Randomness	n	Message hash salt

Total for SHA2-128s (d=7, h=3, k=33, a=14):

$\displaystyle \approx 33 \times (32 + 14 \times 32) + 6 \times 67 \times 32 + 6 \times 3 \times 32 + 32 \approx 7,856 \text{ bytes}$

Stateless vs. Stateful Comparison

Property	XMSS (Stateful)	SLH-DSA (Stateless)
State management	Must track index	No state needed
Signing speed	Fast (~µs)	Slow (~ms)
Signature size	Small (~2–3 KB)	Large (~8–30 KB)
Scalability	Limited by tree size	Virtually unlimited
Backup safety	Dangerous (state loss)	Safe
Multi-device	Complex (sync state)	Trivial

Why It Works: Random Oracle Model

The security proof assumes the hash function acts like a random oracle:

Message → path mapping is unpredictable
Collisions (two messages mapping to the same path) are exponentially unlikely
An adversary can't control which keys they force the signer to reveal

The hypertree structure ensures that even with billions of signatures, the probability of path collision remains negligible.

Resources

Bernstein et al., "The SPHINCS+ signature framework" (2019), ACM CCS
Hülsing et al., "SLH-DSA specification" (2022), NIST submission
NIST FIPS 205, Section 7: Hypertree Algorithm