Chapter 16: FORS and the stateless hypertree

XMSS signs up to $2^h$ messages (where $h$ is the tree height) before the signer runs out of leaves. The leaf counter is the scheme’s operational burden: back up an XMSS key, restore it after signing, and the restored copy reuses a WOTS+ leaf (Chapter 15). NIST’s conformance requirements in SP 800-208 §8.1 address this with nonexportable private keys and durable leaf-index advancement inside validated hardware modules, but the fundamental problem remains: a stateful signature scheme ties cryptographic security to operational discipline (Cooper et al., 2020).

Two ideas eliminate the counter. First, replace WOTS+ at the message level with FORS (Forest of Random Subsets), a few-time signature scheme that tolerates bounded reuse because signing reveals a random selection of leaves rather than a unique one-time key (Aumasson et al., 2020). Second, replace the flat Merkle tree with a hypertree, a tree of WOTS+ trees, so each signature lands at a pseudorandom position in an astronomically large leaf space instead of incrementing a counter (Bernstein et al., 2015). Together, FORS and the hypertree produce a stateless hash-based signature. The tradeoff is size: SLH-DSA signatures range from 7,856 to 49,856 bytes (National Institute of Standards and Technology, 2024), against 2,500 bytes for XMSS-SHA2_10_256, the 256-bit-output set at tree height $h = 10$ (Hülsing et al., 2018, sec. 5.3.1).

FORS at toy parameters

The FORS walkthrough below is pedagogical and does not reproduce FIPS 205 byte-for-byte. It uses $k = 3$ to $k = 6$, $t = 4$ to $t = 16$, and $n = 4$-byte truncated SHA-256 so a single signature fits in a diagram. FIPS 205 SLH-DSA-128s (Chapter 17) uses $k = 14$ and $a = 12$, so $t = 2^{12} = 4{,}096$, with $n = 16$-byte hash outputs (National Institute of Standards and Technology, 2024). In the SHA2-128 instantiation those $n$-byte outputs are SHA-256 truncated to $n$, and the message digest is MGF1-SHA-256 at $m = 30$ bytes. The “16 bytes” is the truncated parameter, not an untruncated SHA-256 digest (National Institute of Standards and Technology, 2024). The probability arithmetic in this chapter mirrors the parameter relationships behind the FIPS 205 construction at toy scale; Chapter 18 develops the formal target-count taxonomy at production parameters.

FORS stores $k$ independent Merkle trees, each built over $t$ secret values, with the hash of each value as its leaf. To sign a message, the signer hashes the message to extract $k$ indices (one per tree, each in $\{0, \ldots, t-1\}$), then reveals the selected secret value and its authentication path from each tree. The verifier hashes each revealed value into its leaf, reconstructs the $k$ tree roots from the leaves and auth paths, hashes the roots together, and compares the result to the public key.

At $k = 3$, $t = 4$, and $n = 4$ bytes (SHA-256 truncated to 4 bytes for readability), the entire structure fits on a page.

import hashlib

def sha_n(data, n=4):
    """SHA-256 truncated to n bytes."""
    return hashlib.sha256(data).digest()[:n]

seed = b"ch16-fors-toy"
k, t, n = 3, 4, 4

# Generate k lists of t secret values; each tree's leaves are their hashes.
all_leaves = []
all_trees = []
roots = b""
for j in range(k):
    leaves = []
    for i in range(t):
        leaf = sha_n(seed + b"fors" + j.to_bytes(4, "big") + i.to_bytes(4, "big"), n)
        leaves.append(leaf)
    all_leaves.append(leaves)

    # Merkle tree: 1-indexed flat array, same layout as Chapter 14.
    tree = [b""] * (2 * t)
    for i, lf in enumerate(leaves):
        tree[t + i] = sha_n(lf, n)  # the leaf is F(secret), never the secret
    for i in range(t - 1, 0, -1):
        tree[i] = sha_n(tree[2 * i] + tree[2 * i + 1], n)
    all_trees.append(tree)
    roots += tree[1]

pk = sha_n(roots, n)
print(f"Tree 0 root: {all_trees[0][1].hex()}")
# ==> Tree 0 root: 8a6b98ad
print(f"Tree 1 root: {all_trees[1][1].hex()}")
# ==> Tree 1 root: c9a89a2e
print(f"Tree 2 root: {all_trees[2][1].hex()}")
# ==> Tree 2 root: 69143929
print(f"pk = {pk.hex()}")
# ==> pk = 969f73b4

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch16/, one file per block. Appendix C covers the clone and the environment they run on.

The public key is a single 4-byte hash of the three roots concatenated. Signing requires extracting $k = 3$ indices from the message hash. Each index needs $\log_2 t = 2$ bits, so the signer reads 6 bits from the first byte of SHA-256(message):

import hashlib

def sha_n(data, n=4):
    return hashlib.sha256(data).digest()[:n]

seed = b"ch16-fors-toy"
k, t, n = 3, 4, 4

# Regenerate the key material.
all_leaves = []
all_trees = []
roots = b""
for j in range(k):
    leaves = []
    for i in range(t):
        leaf = sha_n(seed + b"fors" + j.to_bytes(4, "big") + i.to_bytes(4, "big"), n)
        leaves.append(leaf)
    all_leaves.append(leaves)
    tree = [b""] * (2 * t)
    for i, lf in enumerate(leaves):
        tree[t + i] = sha_n(lf, n)
    for i in range(t - 1, 0, -1):
        tree[i] = sha_n(tree[2 * i] + tree[2 * i + 1], n)
    all_trees.append(tree)
    roots += tree[1]
pk = sha_n(roots, n)

# Extract k=3 indices from the message hash.
message = b"test FORS"
digest = hashlib.sha256(message).digest()
indices = []
for idx_i in range(k):
    shift = 6 - idx_i * 2
    val = (digest[0] >> shift) & 0x03
    indices.append(val)
print(f"Indices: {indices}")
# ==> Indices: [3, 0, 1]

# Sign: reveal the selected secret value and its auth path from each tree.
sig = []
for j in range(k):
    secret = all_leaves[j][indices[j]]
    node = t + indices[j]
    path = []
    for _ in range(2):  # depth = log2(t) = 2
        path.append(all_trees[j][node ^ 1])
        node //= 2
    sig.append((secret, path))
    print(f"Tree {j}: secret[{indices[j]}] = {secret.hex()}")
# ==> Tree 0: secret[3] = 176ff120
# ==> Tree 1: secret[0] = 9c88ece5
# ==> Tree 2: secret[1] = fe0e9264

# Verify: hash each revealed secret into its leaf, then climb the auth path.
recon_roots = b""
for j in range(k):
    current = sha_n(sig[j][0], n)
    idx = indices[j]
    for sib in sig[j][1]:
        if idx % 2 == 0:
            current = sha_n(current + sib, n)
        else:
            current = sha_n(sib + current, n)
        idx //= 2
    recon_roots += current

recon_pk = sha_n(recon_roots, n)
print(recon_pk == pk)
# ==> True

The verifier sees $k$ secret values, one per tree, and never a secret it did not ask for: the authentication path is made of leaf hashes and internal nodes, so the sibling of a revealed position stays hidden behind one hash. Had the secret itself been the Merkle leaf, the first path element would have been the neighbouring secret, and one signature would have covered $(2/t)^k$ of all targets instead of $(1/t)^k$. Each tree contributes one revealed secret value and a 2-node authentication path, for a total signature of $3 \times (4 + 2 \times 4) = 36$ bytes at these toy parameters.

The diagram below shows a FORS instance at $k = 3$ and $t = 4$. Each tree has 4 leaves, each the hash of a secret value, and a depth-2 Merkle structure. The signed indices (one per tree) are highlighted in teal. The authentication-path siblings are highlighted in amber. The three roots flow into a single hash to produce the public key.

Figure 16.1. FORS at $k = 3$, $t = 4$. The message hash extracts three indices, one per tree. Each signed leaf (teal) contributes its authentication path (amber). The three roots feed a single hash to produce the FORS public key, which the verifier reconstructs by hashing each revealed secret into its leaf and climbing the paths.

Few-time security and the birthday bound

FORS is not one-time. Signing with the same FORS key twice reveals a second set of $k$ leaf values, drawn from the same $k$ trees. If two messages select the same index in a given tree, the signer reveals the same leaf both times and no new information leaks. The reuse danger is narrower than a repeated message. The adversary can forge a target once each of its $k$ selected indices already lies in the revealed set of its tree, and those indices may come from several different earlier signatures rather than one matching message.

Two different quantities describe this, and they are easy to confuse. The first is the birthday count of repeated draws. After $q$ signatures on a FORS instance of $k$ trees with $t$ leaves each, the expected number of colliding index pairs in one tree is $\binom{q}{2}/t$ by linearity of expectation, so across $k$ trees:

$$E_q = \frac{k\binom{q}{2}}{t} = \frac{k\,q(q-1)}{2t} \approx \frac{k q^2}{2t}$$

Markov’s inequality bounds the probability of at least one repeated draw anywhere in the instance by the same quantity, $\Pr[\text{any repeat}] \leq E_q$. Under the $q^2$ approximation this reaches $1/2$ at $q = \sqrt{t/k}$ ($\approx 1.63$ at $k = 6$, $t = 16$). A repeated draw is not a forgery: it re-reveals a leaf the signer already exposed.

In a simplified random-target model the quantity that governs forgery is the number of distinct leaves revealed per tree. Let $U_j$ be the count of distinct indices revealed in tree $j$ after $q$ signatures. A given leaf is missed by all $q$ signatures with probability $(1 - 1/t)^q$, so:

$$\mathbb{E}[U_j] = t\left(1 - \left(1 - \tfrac{1}{t}\right)^{q}\right)$$

A random target digest is forgeable from already-revealed material exactly when its selected index falls in the revealed set of every tree. Conditioned on the $U_j$, that probability is $\prod_{j} U_j / t$. In expectation this becomes:

$$P_{\text{forgery}} \approx \left(1 - \left(1 - \tfrac{1}{t}\right)^{q}\right)^{k} \approx \left(1 - e^{-q/t}\right)^{k}$$

For $q \ll t$ this reduces to $(q/t)^k$, the simple bound the cryptanalysis literature usually quotes, valid only while $q$ stays small relative to $t$. At the teaching parameters $k = 6$ and $t = 16$ the two forms separate quickly:

$q$	Occupancy $(1 - (1 - 1/t)^{q})^{k}$	Small-$q$ $(q/t)^{k}$
3	$2.97 \times 10^{-5}$	$4.35 \times 10^{-5}$
10	$0.012$	$0.060$
16	$0.071$	$1.000$
20	$0.145$	$3.815$

At $q = t = 16$ the occupancy form gives about one in fourteen, not certainty, and the small-$q$ form has arrived at exactly 1. By $q = 20$ it has passed 1 and stopped meaning anything, while the next subsection’s demo measures the deterministic coverage at $0.1246$, about one in eight.

SLH-DSA production parameters keep $q$ far below $t$: SLH-DSA-128s has $k = 14$, $a = 12$, $t = 4{,}096$, so $(1 - e^{-q/t})^{14}$ is negligible for any realistic per-instance $q$ (National Institute of Standards and Technology, 2024). The full SLH-DSA EUF-CMA argument also covers adaptive message choice, total target counts, and the properties of $H_{\text{msg}}$. FIPS 205 §11 states the security target and the $2^{64}$-message bound, and refers the argument itself out to the research literature (National Institute of Standards and Technology, 2024). Chapter 18 develops that formal model from those sources.

Hypertree layer addressing

A hypertree of total height $h$ with $d$ layers has subtree height $h' = h / d$. Each subtree is a standard Merkle tree of $2^{h'}$ WOTS+ leaves (Hülsing, 2013; Merkle, 1989).

Layer $d - 1$ (the top) has one subtree. Its root is the hypertree public key. Layer $d - 2$ has $2^{h'}$ subtrees. Each lower-layer root is signed by a WOTS+ key in the layer above. The corresponding upper-layer Merkle leaf is the compressed WOTS+ public key for that signing key, not the lower root itself. In general, layer $j$ has $2^{(d - 1 - j) \cdot h'}$ subtrees. The total number of leaf positions is $2^h = 2^{d \cdot h'}$.

At $d = 2$ and $h' = 4$: total height is 8, with $2^8 = 256$ leaf positions. The bottom layer has $2^4 = 16$ subtrees of 16 WOTS+ leaves each. The top layer has 1 subtree of 16 WOTS+ leaves. Total WOTS+ keypairs: $16 \times 16 + 16 = 272$.

SLH-DSA combines hypertree position randomization with FORS to remove the per-signer counter that XMSS and LMS require. The message-hash function takes the message and a per-signature randomizer to produce the hypertree leaf position, and therefore the FORS instance at that position. A signer does not maintain or synchronize a leaf counter, even when signatures are produced by independent replicas of the same private key (National Institute of Standards and Technology, 2024). Blockchain signers can therefore run independent seeds without any coordination layer. Part VII develops the L1 signature migration where SLH-DSA-128s is one of the conservative-assumption candidates.

Building FORS and hypertrees

FORS at teaching parameters

Scaling to $k = 6$, $t = 16$, and $n = 32$ (full SHA-256 output), the FORS structure becomes large enough to illustrate real tradeoffs.

Index extraction at these parameters: each index needs $\log_2 16 = 4$ bits, and $k = 6$ indices need $6 \times 4 = 24$ bits, which is 3 bytes from the SHA-256 digest. The extraction reads bits MSB-first:

import hashlib

def message_indices(message, k, t):
    """Extract k indices from SHA-256(message), each in {0, ..., t-1}."""
    lg_t = t.bit_length() - 1            # t is a power of two; no float log
    digest = hashlib.sha256(message).digest()
    indices = []
    bit_offset = 0
    for _ in range(k):
        value = 0
        for b in range(lg_t):
            cur = bit_offset + b
            by = cur // 8
            bi = 7 - (cur % 8)
            value = (value << 1) | ((digest[by] >> bi) & 1)
        indices.append(value)
        bit_offset += lg_t
    return indices

indices = message_indices(b"FORS example", 6, 16)
print(indices)
# ==> [10, 9, 6, 9, 13, 4]
print(f"Bits used: {6 * 4} of 256")
# ==> Bits used: 24 of 256

FORS keygen generates $k \times t = 96$ secret values, hashes each into a Merkle leaf, builds $k = 6$ Merkle trees, and hashes their roots together into a single 32-byte public key:

import hashlib

def sha(data):
    return hashlib.sha256(data).digest()

seed = b"ch16-fors-teach"
k, t, n = 6, 16, 32

roots_concat = b""
for j in range(k):
    leaves = []
    for i in range(t):
        leaf = sha(seed + b"fors" + j.to_bytes(4, "big") + i.to_bytes(4, "big"))[:n]
        leaves.append(leaf)
    tree = [b""] * (2 * t)
    for i, lf in enumerate(leaves):
        tree[t + i] = sha(lf)[:n]  # leaf = F(secret)
    for i in range(t - 1, 0, -1):
        tree[i] = sha(tree[2 * i] + tree[2 * i + 1])
    roots_concat += tree[1]

pk = sha(roots_concat)[:n]
print(f"pk: {pk.hex()[:16]}...")
# ==> pk: 5618a209f1b98db8...
print(f"Secret key: {k * t * n} bytes")
# ==> Secret key: 3072 bytes
print(f"Signature: {k * (n + 4 * n)} bytes")
# ==> Signature: 960 bytes
print(f"Public key: {n} bytes")
# ==> Public key: 32 bytes

The signature is $k \times (n + \log_2 t \times n) = 6 \times (32 + 4 \times 32) = 960$ bytes: six revealed secret values plus six authentication paths of depth $\log_2 t = 4$.

Where this FORS departs from FIPS 205

The leaf hash above is a bare sha_n of the secret. SLH-DSA derives the secret with a PRF and hashes it with the tweakable function $F$ under a position address, so a leaf at one position is not a target for the same guess at another (National Institute of Standards and Technology, 2024). FIPS 205 also compresses the $k$ roots into the FORS public key with one tweakable-hash call $T_k$ under a dedicated FORS-roots address, which is neither the plain concatenate-and-hash used here nor a further Merkle tree over the roots (National Institute of Standards and Technology, 2024). Chapter 17 adds both.

The few-time collision demo

Signing multiple messages with the same FORS key reveals more indices. The raw saturation count grows, but the quantity that matters for a forgery is the number of distinct leaves exposed per tree:

import hashlib

def message_indices(message, k, t):
    lg_t = t.bit_length() - 1            # t is a power of two; no float log
    digest = hashlib.sha256(message).digest()
    indices = []
    bit_offset = 0
    for _ in range(k):
        value = 0
        for b in range(lg_t):
            cur = bit_offset + b
            by = cur // 8
            bi = 7 - (cur % 8)
            value = (value << 1) | ((digest[by] >> bi) & 1)
        indices.append(value)
        bit_offset += lg_t
    return indices

k, t = 6, 16
for q_max in [5, 10, 15, 20]:
    used = [set() for _ in range(k)]
    redundant = 0
    for q in range(1, q_max + 1):
        idxs = message_indices(f"msg-{q}".encode(), k, t)
        for j in range(k):
            if idxs[j] in used[j]:
                redundant += 1
            used[j].add(idxs[j])
    print(f"q={q_max:2d}: {redundant} redundant leaf exposures")
# ==> q= 5: 3 redundant leaf exposures
# ==> q=10: 18 redundant leaf exposures
# ==> q=15: 32 redundant leaf exposures
# ==> q=20: 52 redundant leaf exposures

# Distinct leaves per tree is what a reuse forgery needs, not the raw count.
k, t, q = 6, 16, 20
used = [set() for _ in range(k)]
for s in range(1, q + 1):
    for j, ix in enumerate(message_indices(f"msg-{s}".encode(), k, t)):
        used[j].add(ix)
distinct = [len(u) for u in used]
print(f"distinct leaves/tree at q={q}: {distinct}")
# ==> distinct leaves/tree at q=20: [12, 11, 10, 12, 12, 11]
coverage = 1.0
for u in distinct:
    coverage *= u / t
print(f"random-target coverage = {coverage:.4f}")
# ==> random-target coverage = 0.1246
occ = (1 - (1 - 1 / t) ** q) ** k
print(f"occupancy estimate = {occ:.4f}")
# ==> occupancy estimate = 0.1451
print(f"small-q (q/t)^k = {(q / t) ** k:.4f}")
# ==> small-q (q/t)^k = 3.8147

The loop counts redundant leaf exposures: each time a signature draws an index already revealed in that tree. This is the saturation count, not the birthday pair count $E_q$ and not a forgery probability. A redundant draw re-reveals a leaf the signer already exposed. At $q = 20$ the six trees have only $[12, 11, 10, 12, 12, 11]$ distinct revealed leaves, not all 16. The random-target coverage $\prod_j U_j/t \approx 0.1246$ matches the occupancy estimate $(1 - (1 - 1/t)^{q})^{k} \approx 0.1451$, while the small-$q$ form $(20/16)^6 \approx 3.81$ has left its range of validity and is meaningless here. Forgery is not certain at $q = t$: the occupancy estimate at $q = 16$ is $\approx 0.071$ (about one in fourteen), well under the $q = 20$ coverage above ($\approx 0.1246$, about one in eight). SLH-DSA’s $t = 4{,}096$ keeps the real per-instance probability negligible at realistic reuse levels.

Hypertree construction

A hypertree replaces XMSS’s single Merkle tree with a stack of $d$ layers of smaller Merkle subtrees. Each subtree has height $h' = h/d$, and its $2^{h'}$ leaves hold L-tree-compressed WOTS+ public keys exactly as in Chapter 15. The bottom layer holds many such subtrees. Each subtree’s root is signed by a WOTS+ key one layer up. The top layer has a single subtree, and its root is the hypertree’s public key.

Where the teaching hypertree departs from FIPS 205

The hypertree built here keeps Chapter 15’s L-tree for continuity. FIPS 205 SLH-DSA does not use the RFC 8391 L-tree. It compresses the $\text{len}$ WOTS+ public chain values directly with one addressed tweakable-hash call $T_{\text{len}}(\text{PK.seed}, \text{ADRS}, \cdot)$, and Chapter 17 adopts that form (National Institute of Standards and Technology, 2024).

At $d = 2$ layers and $h' = 4$:

• The bottom layer (layer 0) has $2^4 = 16$ subtrees, each containing $2^4 = 16$ WOTS+ leaves.
• The top layer (layer 1) has 1 subtree of 16 WOTS+ leaves. The WOTS+ key at position $j$ of the top subtree signs the root of bottom subtree $j$.
• The top-layer root is the hypertree public key.
• Total WOTS+ keypairs: $16 \times 16 + 16 = 272$.

To sign a message at leaf index $\ell$ in the hypertree:

• Decompose $\ell$ into two $h'$-bit parts. The bottom $h' = 4$ bits select the leaf within a bottom subtree. The next $h'$ bits select which bottom subtree (equivalently, which leaf in the top subtree).
• At the bottom layer: sign the message with the selected WOTS+ key, produce the authentication path within the bottom subtree.
• At the top layer: the “message” is the bottom subtree’s root. Sign it with the corresponding WOTS+ key, produce the authentication path within the top subtree.

The diagram below shows a hypertree at $d = 2$ and $h' = 4$. The top layer has one subtree of 16 WOTS+ leaves. Each top-layer leaf is the compressed public key of a WOTS+ key that signs the root of one bottom-layer subtree (also 16 WOTS+ leaves). The signing path through both layers is highlighted: the bottom layer signs the message, the top layer signs the bottom subtree root.

Figure 16.2. Two-layer hypertree at $d = 2$, $h' = 4$. WOTS+ key $j$ in the top subtree signs the root of bottom subtree $j$; WOTS+ key $i$ in the bottom subtree signs the message. Verification walks both layers upward to the public key.

The signature contains $d = 2$ layers, each consisting of a WOTS+ signature and a Merkle authentication path. The verifier recovers each WOTS+ public key from the signature by completing each chain to its endpoint (as in Chapter 15’s WOTS+ verification), then L-tree-compresses the recovered public key to obtain the leaf hash.

import hashlib

# Hypertree size computation at d=2, h'=4, w=16, n=32.
# FIPS 205 forbids floating point in parameter derivations, so ell is
# computed with integer arithmetic only.
d, h_prime, w, n = 2, 4, 16, 32

lg_w = w.bit_length() - 1               # w is a power of two
ell_1 = (8 * n + lg_w - 1) // lg_w      # ceil(8n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = 1
capacity = w
while capacity <= max_c:
    ell_2 += 1
    capacity *= w
ell = ell_1 + ell_2

total_leaves = 1 << (d * h_prime)
print(f"Total leaf positions: {total_leaves}")
# ==> Total leaf positions: 256

wots_sig_bytes = ell * n
auth_path_bytes = h_prime * n
layer_sig = wots_sig_bytes + auth_path_bytes
print(f"WOTS+ signature: {ell} chains * {n} B = {wots_sig_bytes} B")
# ==> WOTS+ signature: 67 chains * 32 B = 2144 B
print(f"Auth path: {h_prime} nodes * {n} B = {auth_path_bytes} B")
# ==> Auth path: 4 nodes * 32 B = 128 B

total_sig = d * layer_sig
print(f"Hypertree signature: {d} layers * {layer_sig} B = {total_sig} B")
# ==> Hypertree signature: 2 layers * 2272 B = 4544 B

Each layer contributes 2,272 bytes: a 2,144-byte WOTS+ signature plus a 128-byte authentication path. The total hypertree signature at these teaching parameters is $2 \times 2{,}272 = 4{,}544$ bytes. The WOTS+ public keys are not transmitted. The verifier derives them by completing each chain from the signature values, then L-tree-compresses the result to obtain the Merkle leaf hash.

Verification walks from the bottom layer upward. At each layer, the verifier:

• Completes each WOTS+ chain from the signature value to the endpoint, recovering the WOTS+ public key.
• L-tree-compresses the recovered public key into a single leaf hash.
• Verifies the Merkle authentication path from the leaf hash to the subtree root.
• Uses the subtree root as the “message” for the next layer.

The final subtree root must match the published hypertree public key. If it does, the signature is valid.

How FORS and hypertrees combine

SLH-DSA (FIPS 205) derives a FORS keypair at each leaf position of a hypertree (National Institute of Standards and Technology, 2024). The hypertree position is not chosen and stored. Both signer and verifier compute $\text{digest} = H_{\text{msg}}(R, \text{PK.seed}, \text{PK.root}, M)$ and split it into the FORS message digest, the hypertree tree index, and the leaf index. The signer derives the FORS and WOTS+ secret values at that position from SK.seed, signs the message with FORS, and authenticates the FORS public key upward through the hypertree with WOTS+ at each layer.

The signature contains three fields:

• The message randomizer $R$ ($n$ bytes)
• The FORS signature ($k$ revealed secret values and auth paths)
• The hypertree signature ($d$ layers of WOTS+ signatures and Merkle auth paths)

No counter. No state. The position is a function of $R$ and the message. The verifier recomputes it and nothing about it is transmitted. Two signatures collide on the same position with probability about $q(q-1)/(2 \cdot 2^h)$, small at ordinary signing volumes. SLH-DSA does not assume it away: FIPS 205 designs its standard parameter sets to stay EUF-CMA secure for up to $2^{64}$ signatures per key. Repeated FORS positions are therefore absorbed by the FORS few-time bound, not treated as impossible (National Institute of Standards and Technology, 2024). A collision reuses the same FORS keypair (deterministic derivation), so the few-time bound applies rather than a one-time break.

The original SPHINCS construction (Bernstein et al., 2015) used HORST (HORS with trees) instead of FORS. HORST builds a binary hash tree over the leaf values of a HORS key, which shrinks the public key from $t$ hash values to one at the cost of an authentication path per revealed leaf (Bernstein et al., 2015).

SPHINCS+ replaced HORST with FORS because HORS and HORST admit weak messages. Their $k$ indices all select from one set of secret values, so a message whose indices repeat reveals fewer secrets, and in the extreme a whole signature needs only one. FORS gives each index its own secret set, so $k$ repeated indices still cost $k$ distinct secret values. That strengthened security is what let $k$ and $t$ be rechosen, and the rechosen parameters give signatures smaller than HORST’s despite FORS building $k$ trees instead of one (Aumasson et al., 2020).

FIPS 205 standardized SPHINCS+ as SLH-DSA. It defines FORS and the hypertree only as internal components. Neither is an approved standalone signature scheme, and the standalone FORS and hypertree in this chapter are pedagogical (National Institute of Standards and Technology, 2024). Chapter 17 implements the full SLH-DSA construction from FIPS 205.

Cryptanalysis and known attacks

FORS forgery via index collision

The adversary’s goal is a message $m^*$ the signer has not signed whose $k$ FORS indices each fall in the set of leaves already revealed for the corresponding tree, possibly from several different earlier signatures. With those leaves and their authentication paths in hand, the adversary assembles a valid signature for $m^*$.

At the teaching parameters ($k = 6$, $t = 16$), the per-instance forgery probability is the occupancy form $(1 - (1 - 1/t)^{q})^{6}$, with $(q/16)^6$ as its small-$q$ approximation. After $q = 10$ signatures the occupancy value is $\approx 0.012$; the small-$q$ form overshoots at $\approx 0.060$. A single-tree match is not enough; every one of the $k$ trees must already expose the target’s index.

SLH-DSA-128s uses $k = 14$, $a = 12$, $t = 4{,}096$. Each hypertree position derives its own FORS keypair. SLH-DSA-128s has $h = 63$, so at the full $2^{64}$-signature design limit the average occupancy is about two signatures per hypertree position. Position reuse is real, not assumed away. The few-time analysis absorbs it: even at $q = 16$ on one instance, the small-$q$ bound $(16/4096)^{14} = (2^{-8})^{14} = 2^{-112}$, and the occupancy form is smaller still. SLH-DSA-256s uses $k = 22$ and $t = 16{,}384$ ($a = 14$) (National Institute of Standards and Technology, 2024). FORS forgery is computationally infeasible at these parameters.

Multi-target preimage on FORS trees

Each FORS signature exposes $k$ secret values, their $k$ leaf hashes, and $k \times \log_2 t$ authentication-path nodes. A FORS instance has $k \cdot t$ leaf values in total, each a hash output. Inverting one of them recovers one missing secret for one tree. That is intuition for the target count, not a complete forgery. A forgery still needs a usable selected value and a matching authentication path in every one of the $k$ trees, plus an intact hypertree chain above the FORS public key.

The multi-target surface is also wider than one instance. Every FORS leaf, FORS interior node, WOTS+ chain step, and tree node is a separate domain-separated (ADRS-tagged) hash call across the full $2^{h}$-position structure. Domain separation prevents one successful preimage or collision from being reused across roles or positions, which removes the target-count amplification rather than bounding it. The SPHINCS+ generic bounds for distinct-function multi-target second-preimage resistance are independent of the number of targets (Aumasson et al., 2020). FIPS 205 gives ADRS that job, using a different address for each call to $F$, $H$, and $T_\ell$ (National Institute of Standards and Technology, 2024). What the parameter search still has to absorb is the signing-query and construction loss, not the number of hash targets in the tree.

What domain separation is worth can be sized by asking what a construction without it would pay. If every one of those values were reachable through one untweaked hash function, the first-order estimate of the loss would be $\log_2(k \cdot t)$ bits. At $k = 6$, $t = 16$ that is $\log_2(96) \approx 6.6$ bits, taking classical preimage security from $2^{256}$ to about $2^{249}$ at the teaching $n = 32$. At the SLH-DSA-128s shape ($k = 14$, $t = 4{,}096$) it is $\log_2(57{,}344) \approx 15.8$ bits, which against a 128-bit hash output would take the preimage-query count below the 128-bit figure its category is named for. ADRS is why SLH-DSA does not pay it (National Institute of Standards and Technology, 2024). Chapter 18 works this counterfactual through the six FIPS 205 SHA-2 parameter sets.

Hypertree WOTS+ key reuse

In SLH-DSA, two messages can map to the same hypertree position. The FORS keypair and the hypertree structure at a position are fixed by SK.seed and PK.seed, so on a repeated position the hypertree WOTS+ keys authenticate the same FORS public key and the same lower-layer roots both times. They sign the same inputs, so no new WOTS+ chain values are exposed. This is safe: WOTS+ one-time security requires that a key sign one value, and here it signs the same value twice.

Only the FORS instance at that position signs two different messages, and FORS tolerates bounded reuse by design. The few-time bound from the occupancy analysis above applies, with the message-dependent reuse burden pushed entirely into FORS.

Tradeoffs inside Part III

• Lamport + Merkle (Chapter 14): 8,192-byte Lamport one-time signature (256 revealed values). The complete Merkle signature Chapter 14 verifies also carries the 16,384-byte Lamport public key and the authentication path, 25,216 bytes at $d = 20$. Stateful. Simplest construction, largest signatures.
• WOTS+ + XMSS (Chapter 15): 2,500-byte signature at tree height $h = 10$. Stateful. Roughly 4x compression over Lamport via hash chains.
• FORS standalone (Chapter 16, $k = 6$, $t = 16$): 960-byte signature. Few-time. No state, but limited to a bounded number of signatures per key.
• Hypertree (Chapter 16, $d = 2$, $h' = 4$): 4,544-byte signature. Needs no counter of its own, but only because SLH-DSA hands it a position: $H_{\text{msg}}$ over $2^h \geq 2^{63}$ positions, with FORS absorbing the repeats. At 256 positions a random choice repeats after about 19 signatures, and a repeat makes a bottom WOTS+ key sign two messages. Larger than XMSS because each of $d$ layers contributes a full WOTS+ signature and authentication path.
• SLH-DSA (Chapter 17): 7,856 to 49,856 bytes depending on parameter set (National Institute of Standards and Technology, 2024). Stateless. The security argument reduces entirely to hash function properties, with no lattice or number-theoretic assumptions.

Eliminating the leaf counter costs signature size. Chapter 17 walks the size-versus-statelessness tradeoff against the canonical SLH-DSA-128s and SLH-DSA-128f parameter sets, and names the operator settings (TLS servers, cloud HSMs, firmware signers) where each choice fits.

Exercises

1. FORS index extraction. Compute SHA-256 of the string "exercise" and extract 6 indices at $t = 16$ (4 bits per index). Show the first 3 bytes of the digest in binary and identify the six 4-bit groups.

2. FORS collision threshold. For SLH-DSA-128s parameters $k = 14$, $t = 4{,}096$, compute the number of signatures $q$ at which the Markov bound on the any-tree collision probability exceeds 0.5. Use the formula $P \leq q^2 k / (2t)$. Give the continuous threshold and the first integer $q$ above it.

3. Hypertree signature size. Compute the full hypertree signature size (WOTS+ signatures + authentication paths) for $d = 3$, $h' = 5$, $w = 16$, $n = 32$. Break the calculation into per-layer components.

4. Why FORS at the bottom? SLH-DSA uses FORS, not WOTS+, at the message level. Suppose the bottom layer used WOTS+ instead, and two messages happened to map to the same random leaf index $r$. Explain what the adversary learns and why this is worse than the FORS case.

5. Verification direction. SLH-DSA verifies the hypertree from the bottom layer upward. Could the verifier start from the top layer and work downward instead? Explain what information the verifier has at each step and whether top-down verification is possible.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 16. A separate track, for rebuilding rather than reading. The package exercises/ch16-fors arrives with FORS already implemented, because the chapter prints it, and stubs the three hypertree routines, which the chapter walks in prose but never builds. Run PQC_IMPL=exercises pytest tests/ch16 to grade your version against the suite that proves the reference one.

References

Aumasson, J.-P., Bernstein, D. J., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.-L., Hülsing, A., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M. M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., & Westerbaan, B. (2020). SPHINCS+: Submission to the NIST Post-Quantum Cryptography Standardization Process. NIST PQC Round 3 submission; SPHINCS+ specification v3, 1 October 2020. https://sphincs.org/data/sphincs+-round3-specification.pdf

Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., & Wilcox-O’Hearn, Z. (2015). SPHINCS: Practical Stateless Hash-Based Signatures. Advances in Cryptology – EUROCRYPT 2015, 9056, 368–397. https://doi.org/10.1007/978-3-662-46800-5_15

Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., & Miller, C. (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208. https://doi.org/10.6028/nist.sp.800-208

Hülsing, A. (2013). W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes. Progress in Cryptology – AFRICACRYPT 2013, 7918, 173–188. https://doi.org/10.1007/978-3-642-38553-7_10

Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., & Mohaisen, A. (2018). XMSS: eXtended Merkle Signature Scheme. IETF RFC 8391. https://doi.org/10.17487/rfc8391

Merkle, R. C. (1989). A Certified Digital Signature. Advances in Cryptology – CRYPTO ’89, 435, 218–238. https://doi.org/10.1007/0-387-34805-0_21

National Institute of Standards and Technology. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205