SLH-DSA: Signing from Hashing Alone, and the Hypertree That Buys Statelessness

Abstract

SLH-DSA, standardized from SPHINCS+, is the conservative post-quantum signature whose security rests on nothing beyond the strength of a hash function. This piece constructs it from the ground up. It starts with one-time signatures built from hash chains, which are secure for a single use; assembles many of them into a Merkle tree whose single root becomes the public key, with an authentication path proving membership; and confronts the statefulness that a plain Merkle scheme imposes. It then explains the two ideas that buy statelessness: few-time signatures at the bottom that tolerate limited reuse, and a hypertree of trees in which each message pseudo-randomly selects a bottom key, so that accidental reuse is astronomically rare and no state need be tracked. It closes with the size-and-speed cost that conservatism imposes and where the scheme fits. The theme: with only hashing as an ingredient, careful combinatorics turns a single-use primitive into a stateless signature secure under the weakest assumption in the standards.

Every other signature in the standards rests on a structured mathematical assumption — lattice hardness, and before quantum computers, factoring or discrete logarithms. SLH-DSA rests on none of these. Its only cryptographic ingredient is a hash function, and its security reduces to standard properties of that hash: an attacker who could forge a signature could invert or find collisions in the hash. This is the most conservative foundation available, because hash functions are the best-studied and most trusted primitives in cryptography and are not threatened by quantum computers beyond a mild, well-understood speedup. The price of that conservatism is size, and this article builds the construction that pays it — from one-time keys up to the stateless hypertree.

One-time signatures from hash chains

The atom of the construction is a one-time signature, secure if the key is used exactly once. The standardized variant is a Winternitz-style scheme built from hash chains. A secret key is a set of random values; the public key is obtained by hashing each of them a fixed number of times, walking each value to the end of its chain. To sign, the signer interprets the message digest as a sequence of small numbers and, for each, reveals the corresponding secret value hashed that many times — an intermediate point along its chain rather than the endpoint.

Verification completes each revealed chain to its end by hashing the remaining number of times and checks that the results match the public key. Forgery is prevented because producing a valid signature for a different digest would require walking a chain backward — computing an earlier point from a later one — which is inverting the hash. The scheme is one-time because a single signature reveals intermediate chain points that, combined across two different messages, would let an attacker forge; two uses of the same key break it. This one-time restriction is the constraint the rest of the construction exists to manage.

The takeaway is that a one-time signature is cheap and rests only on the hash being hard to invert, but it is single-use. Turning many single-use keys into a reusable long-lived signature is the job of the tree structures that follow, and doing so without leaking which keys have been used is the central difficulty.

The public value is the secret hashed to the end of a chain; a signature reveals an intermediate point, and verification hashes the rest of the way.

\[\text{public} = H^{w}(\text{secret}); \quad \text{sign digit } b:\ \text{reveal } H^{b}(\text{secret})\]

\[\text{verify: } H^{\,w-b}(H^{b}(\text{secret})) \stackrel{?}{=} \text{public}; \quad \text{one-time only}\]

Merkle trees and the statefulness problem

To get more than one signature, take many one-time public keys and hash them together into a binary tree — a Merkle tree. Each leaf is the hash of a one-time public key; each internal node is the hash of its two children; the single value at the top, the root, becomes the scheme's long-lived public key. A signature now consists of a one-time signature under some leaf, that leaf's one-time public key, and an authentication path: the sequence of sibling hashes climbing from the leaf to the root, which lets the verifier recompute the root and confirm the leaf genuinely belongs to it.

This gives as many signatures as there are leaves, each backed by a fresh one-time key, all certified by one small public root. The security still reduces only to the hash function: forging requires either breaking a one-time key or finding a collision that lets a fake leaf recompute the real root. But a fatal operational problem appears — the scheme is stateful. Each leaf may be used only once, so the signer must remember which leaves it has already spent and never reuse one. Losing track of that state, for instance by restoring a backup or running two copies, reuses a one-time key and breaks the scheme.

Statefulness is a serious deployment hazard, taken up directly in the next article for the schemes that embrace it. SLH-DSA instead chooses to eliminate state entirely, accepting larger signatures in exchange. The two ideas that make a hash-based signature stateless are the subject of the next section.

\[\text{root} = \text{hash tree over } 2^{h} \text{ one-time public keys}; \quad \text{auth path} = h \text{ sibling hashes}\]

\[\text{stateful: each of the } 2^{h} \text{ leaves usable once} \Rightarrow \text{signer must track used leaves}\]

Buying statelessness: few-time keys and a hypertree

Statelessness comes from two moves. The first replaces the one-time bottom keys with few-time signatures, which tolerate a small number of uses before security degrades rather than breaking after one. The standardized few-time scheme signs a message by revealing a handful of secret values selected from a large set by the message digest; signing a few different messages under the same key is safe because forging still requires reproducing a specific pattern of revealed values, which stays hard until many reuses accumulate. Few-time tolerance is what makes accidental reuse survivable.

The second move is the hypertree: a tree of Merkle trees, stacked in layers. The top-layer tree's leaves certify the roots of middle-layer trees, whose leaves certify the roots of lower trees, and so on down to the bottom, where few-time keys sign the actual message. This layering makes the total number of virtual bottom keys astronomically large — far too many to enumerate — while keeping each individual tree small. To sign, the message digest pseudo-randomly selects one bottom key out of this enormous space, and the signature bundles the few-time signature plus the authentication paths threading up through every layer to the single top root.

Statelessness now follows from a probability argument. Because each signature's bottom key is chosen pseudo-randomly from a space so vast, the chance that two signatures ever land on the same bottom key is negligible over any realistic number of signatures — and even if they did, the bottom key is few-time and tolerates it. The signer therefore needs to remember nothing between signatures: no counter, no used-leaf list, no state. The combinatorics replace state with overwhelming odds, which is exactly the trade the hypertree exists to make.

Upper-layer trees certify the roots of lower ones; a message pseudo-randomly selects a bottom few-time key that signs it, with paths threading up to one root.

\[d \text{ layers of trees} \Rightarrow 2^{h} \text{ virtual bottom keys, astronomically large}\]

\[\Pr[\text{two signatures share a bottom key}] \approx \text{negligible} \Rightarrow \text{no state needed}\]

The cost of conservatism

Nothing in the construction is free, and the bill arrives as size. A signature must carry a few-time signature at the bottom plus authentication paths through every layer of the hypertree, so SLH-DSA signatures run from several kilobytes to tens of kilobytes — an order of magnitude or more larger than ML-DSA's. Signing is also comparatively slow, since it involves computing many hash chains and tree paths. Verification is more reasonable but still heavier than a lattice signature. These costs are the direct consequence of building everything from hashing and refusing structured shortcuts.

In return, the assumption is as weak as cryptography offers. Security reduces to standard hash properties — chiefly resistance to finding preimages and second preimages — and the standardized parameter sets, offered over the SHA-2 and SHAKE families at the three security categories with small-signature and fast-signing variants, are proved in the quantum random oracle model. Quantum computers speed up hash attacks only by the mild square-root factor of generic search, which the parameters already absorb; there is no structured problem here for a quantum algorithm to exploit. This is why SLH-DSA is the natural fallback if confidence in lattice assumptions were ever shaken.

For autonomous AI systems the fit is specific rather than general. SLH-DSA is poorly suited to high-volume, latency-sensitive signing because of its size and speed, so it should not be the default for signing every agent message. It is well suited to a small number of extremely long-lived, high-assurance keys — a root that anchors a chain of trust, a key that signs released model artifacts meant to remain verifiable for decades — where assumption diversity and conservatism outweigh the size penalty. The design pattern is to sign rarely and durably with SLH-DSA while using ML-DSA for everyday volume, letting each scheme cover the other's weakness.

✅

The weakest assumption, on purpose. SLH-DSA's security reduces only to hash-function properties — no lattice or number-theoretic hardness. That conservatism, paid for in signature size, makes it the ideal anchor for a few very long-lived, high-assurance keys.

Key takeaways

SLH-DSA builds a signature from a hash function alone, so its security reduces to standard hash properties — the most conservative assumption in the standards and unthreatened by quantum computers beyond a mild speedup.
The atom is a one-time signature from Winternitz hash chains: the public key is the secret hashed to the end of a chain, a signature reveals intermediate points, and reuse breaks it.
A Merkle tree hashes many one-time public keys into a single root (the public key), with an authentication path proving a leaf's membership — but a plain Merkle scheme is stateful and must track used leaves.
Statelessness comes from few-time bottom keys that tolerate limited reuse, plus a hypertree whose enormous virtual key space makes each message's pseudo-randomly selected bottom key almost never collide.
The cost is size and speed: signatures range from several to tens of kilobytes and signing is slow, an order of magnitude heavier than ML-DSA.
The fit is a few very long-lived, high-assurance keys (trust anchors, durable artifact signing) rather than high-volume agent messaging, pairing SLH-DSA's conservatism with ML-DSA's efficiency for assumption diversity.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Deciding whether SLH-DSA fitschecklist

Judge whether the conservative hash-only signature is the right tool.

Is the key long-lived and high-assurance (a trust anchor or durable artifact key)?
Is the signing volume low enough to tolerate large, slow signatures?
Is assumption diversity from lattices a stated goal?
Can the transport and storage carry several to tens of kilobytes per signature?
Is the standardized SHA-2 or SHAKE parameter set matched to the target category?

🚀Deploy SLH-DSA as an anchorquickstart

Use the hash-only scheme where conservatism matters most.

Reserve SLH-DSA for a small set of durable, high-value keys.
Select a parameter set (small-signature vs fast-signing variant) for your budget.
Pair it with ML-DSA for high-volume everyday signing.
Verify the implementation is conformant and proved in the quantum random oracle model.

🔒Signature role-split policypolicy

A stub assigning schemes to roles by lifetime and volume.

signature_roles:
  high_volume_everyday: ML-DSA        # small, fast
  durable_high_assurance: SLH-DSA     # hash-only, conservative
slh_dsa:
  assumption: hash_properties_only
  proof_model: quantum_random_oracle
  signature_size: kilobytes_to_tens
  use_for: [trust_anchor, artifact_signing]
rationale:
  assumption_diversity: true

Illustrative documentation template, not a product config.

Glossary

One-time signature: A signature secure only if its key is used exactly once; the Winternitz variant reveals intermediate points of hash chains.
Hash chain: A value repeatedly hashed; the endpoint is public and revealing an intermediate point signs a digit, secure because the hash is hard to invert.
Merkle tree / authentication path: A binary hash tree whose root is the public key; the authentication path is the sibling hashes proving a leaf recomputes the root.
Few-time signature: A signature tolerating a small number of uses before security degrades, used at the bottom of the hypertree to survive accidental reuse.
Hypertree: A tree of Merkle trees in layers; upper trees certify the roots of lower ones, creating an astronomically large space of bottom keys.
Statelessness: The property of needing no signer-side memory between signatures, achieved because pseudo-random bottom-key selection almost never collides.