Stateful Hash-Based Signatures: XMSS, LMS, and the Rule That Must Never Break

Abstract

The stateful hash-based signatures XMSS and LMS predate the stateless standard and remain specified for constrained, disciplined settings. This piece builds them from the same Merkle-tree-of-one-time-keys idea introduced earlier, but keeps the state that statelessness was invented to remove: a counter recording which one-time leaf to use next. It explains why that state is both the source of the schemes' efficiency — small, fast signatures — and their gravest hazard, since reusing a single one-time leaf can expose enough of a key to forge. It catalogs the concrete ways state gets corrupted in practice, from backups and virtual-machine clones to crashes and concurrent signers, and summarizes the strict state-management the standards mandate. It covers capacity limits and the multi-tree extension that raises them, then frames when a stateful scheme is appropriate versus the stateless alternative. The theme: identical hash-only security, but the operational burden of never reusing a leaf makes state a liability to be engineered around, not a convenience.

Before the stateless hash-based standard existed, the same Merkle-tree construction was standardized in a form that keeps its state — the schemes known as XMSS and LMS. They are attractive because keeping the state makes them far smaller and faster than the stateless design: no hypertree, no few-time trickery, just a tree of one-time keys and a counter of which leaf comes next. That counter is also their peril. A one-time key used twice can leak enough to forge, so the entire security of the scheme hangs on a single operational invariant — never sign twice from the same leaf — that ordinary computing practices like backups and cloning conspire to violate. This article develops the construction and the discipline it demands.

The construction: a tree of one-time keys plus an index

The structure is the Merkle tree from the previous article, used directly. Each leaf holds a one-time signature key — the Winternitz variant in XMSS, a closely related one-time scheme in LMS — and the hashes of all the leaves are combined up a binary tree to a single root that serves as the public key. A signature consists of three parts: the index of the leaf being used, the one-time signature produced under that leaf's key, and the authentication path of sibling hashes climbing from the leaf to the root.

Verification is a direct replay. The verifier checks the one-time signature against the leaf's one-time public key, then uses the index and the authentication path to recompute the root, hashing the leaf together with each sibling in turn, and accepts only if the recomputed root equals the published public key. Nothing here appeals to any assumption beyond the hash function: the one-time signature's security and the tree's collision resistance are both hash properties, exactly as in the stateless scheme. The security foundation is identical.

What differs is the absence of the hypertree and the few-time bottom keys. Because a plain tree with genuine one-time leaves is used, signatures are compact and signing is quick — there is no forest of trees to thread paths through. That efficiency is precisely what the state buys, and it is a real advantage for constrained environments. The catch is entirely in how the index is managed.

The index names a leaf; the one-time signature is checked, and the authentication path recomputes the root to match the public key.

\[\text{signature} = (\text{index } i,\ \text{one-time sig},\ \text{auth path}); \quad \text{tree height } h \Rightarrow 2^{h} \text{ leaves}\]

\[\text{verify: recompute root from leaf } i \text{ and path}, \ \text{check} = \text{public key}\]

The rule that must never break

The invariant is simple to state and unforgiving: each leaf's one-time key may be used for exactly one signature, ever. Operationally, this means the signer must, before releasing a signature, advance the stored index to the next unused leaf and persist that advance durably, so that the same leaf can never be selected again. The index is the state, and moving it forward permanently — before the signature leaves the machine — is the whole of the discipline.

The reason a violation is catastrophic lies in how one-time signatures work. Signing a message under a Winternitz leaf reveals certain intermediate points of the leaf's hash chains determined by the message digest. A single signature reveals a safe subset; but two signatures on different digests under the same leaf reveal two different subsets, and their combination can give an attacker enough chain points to compute a valid signature on a message of the attacker's choosing. One accidental reuse of one leaf can therefore hand over the ability to forge under that leaf — and depending on the scheme and messages, undermine confidence in the key entirely.

This is a qualitatively different failure mode from the lattice signature's. ML-DSA fails only if its internal randomness discipline is broken inside the algorithm; a stateful hash signature fails if the surrounding system loses track of a counter, which is a far more ordinary event. The security is not weaker in assumption — it is the same conservative hash-only assumption — but it is contingent on an external state invariant that the operating environment must guarantee.

Persisting the incremented index before signing keeps every leaf single-use; reusing a leaf on two messages can expose the one-time key.

How state gets corrupted in practice

The danger is that routine computing operations silently roll the state backward. Restoring from a backup or a filesystem snapshot resets the index to an earlier value, so the next signatures reuse leaves already spent. Cloning a virtual machine or a container image duplicates the key and its counter, and the two copies then hand out signatures from the same leaves independently. A crash in the window between producing a signature and durably persisting the incremented index can, on restart, reuse the leaf that was just used. Concurrency compounds all of this: two threads or two hosts sharing a key can grab the same index before either persists.

None of these is an exotic attack; they are the normal behaviors of resilient, distributed systems — backup, replication, failover, horizontal scaling — turned into cryptographic breaks by the reuse rule. That is why the standards for stateful schemes impose strict requirements on state management: the index must be advanced and persisted atomically before a signature is emitted, keys must never be copied across instances, and the schemes are recommended only where such guarantees can genuinely be met, typically inside dedicated hardware or tightly controlled signing services.

The practical consequence is that a stateful hash-based signature is safe only in an environment engineered to make reuse impossible, not merely unlikely. A hardware security module that owns the key and enforces monotonic counter advancement is the archetypal safe home; a general-purpose server that might be snapshotted, load-balanced, or restored from backup is precisely where these schemes must not be deployed casually.

Ordinary resilience mechanisms — backups, cloning, crashes, concurrency — each roll the index back and cause a fatal leaf reuse.

Capacity, multi-trees, and when to use them

A tree of height h provides exactly two-to-the-h signatures, after which the key is exhausted and must be retired — a real planning constraint, since a taller tree costs more to generate and manage. To raise capacity without an impractically tall single tree, the standards define multi-tree variants: a top tree whose leaves sign the roots of subordinate trees, so the total capacity is the product of the layers' capacities. This is the same layering idea as the stateless hypertree, but here the trees are traversed in order and the state tracks position across all layers, keeping signatures small at the cost of continued state discipline.

Choosing between stateful and stateless hash-based signatures is therefore a choice about the operating environment, not about the mathematics, since both share the identical hash-only assumption. Where a disciplined, single-owner signing context can guarantee monotonic state — a hardware module signing firmware or issuing certificates in a controlled pipeline — the stateful schemes offer meaningfully smaller and faster signatures. Where state cannot be guaranteed, the stateless scheme's larger signatures are the price of removing the reuse hazard entirely, and it is the safer default.

For autonomous AI systems the guidance is pointed. A fleet of agents that scales horizontally, clones instances, and recovers from snapshots is the worst possible host for a stateful signing key, because every one of its resilience features is a reuse trigger. Stateful hash-based signatures belong, if anywhere in such an architecture, inside a dedicated hardware-backed signing service that no agent can clone or roll back — and for durable, high-assurance keys that must live outside such a service, the stateless SLH-DSA of the previous article is the appropriate hash-only choice. The reuse rule is not a caution to remember but a constraint to design the system around.

⚠️

One reuse can be terminal. A single repeated leaf — from a restored backup, a cloned VM, or a crash before the index is persisted — can expose a one-time key and enable forgery. Deploy stateful schemes only where monotonic state is hardware-guaranteed.

Key takeaways

XMSS and LMS use a Merkle tree of genuine one-time keys plus a leaf index; a signature is the index, the one-time signature, and the authentication path, verified by recomputing the root — a hash-only assumption identical to SLH-DSA's.
Keeping the state makes them small and fast (no hypertree), which is their advantage over the stateless scheme.
The invariant is absolute: each leaf is used once, and the incremented index must be persisted before a signature is released; reusing a leaf on two messages can expose the one-time key and enable forgery.
Ordinary resilience operations break the invariant: backup restore, VM or image cloning, crashes before persistence, and concurrent signers all roll the index back or duplicate the key.
A tree of height h allows two-to-the-h signatures; multi-tree variants raise capacity by layering, at the cost of continued state discipline.
The choice is environmental, not mathematical: use stateful schemes only where hardware guarantees monotonic state (e.g., an HSM signing firmware); otherwise prefer stateless SLH-DSA — and never host stateful keys in a horizontally scaled, cloneable agent fleet.

Practitioner Toolkit

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

✅Is your environment safe for stateful signing?checklist

Verify the reuse invariant can actually be guaranteed.

Is the index advanced and persisted atomically before any signature is released?
Is the key prevented from being copied across instances, images, or clones?
Are backups and snapshots unable to roll the state backward?
Is concurrent access to the key serialized or hardware-serialized?
Is the signing key owned by a dedicated hardware module or controlled service?

🚀Choose stateful or statelessquickstart

Pick the right hash-based scheme for the context.

If a hardware module guarantees monotonic state, consider XMSS/LMS for smaller signatures.
If state cannot be guaranteed, use stateless SLH-DSA.
Size the tree height (and multi-tree layers) to the expected signature count.
Never place a stateful key in a horizontally scaled or cloneable service.

🔒Stateful-key containment policypolicy

A stub restricting where stateful keys may live.

stateful_hash_signing:
  allowed_host: hardware_module_or_controlled_service
  index_advance: atomic_persist_before_emit
  key_cloning: forbidden
  backup_rollback: must_be_impossible
  concurrency: serialized
fallback_when_unmet:
  use: SLH-DSA_stateless
agent_fleets:
  host_stateful_keys: never_directly

Illustrative documentation template, not a product config.

Glossary

Stateful hash-based signature: A hash-only scheme (XMSS, LMS) that keeps a counter of which one-time leaf to use next; security depends on never reusing a leaf.
Leaf index (state): The persisted counter naming the next unused one-time key; it must be advanced and saved durably before each signature is emitted.
One-time-key reuse: Signing two messages under the same leaf, which reveals combinable chain points and can expose the key to forgery.
Multi-tree (HSS): A layered variant where a top tree signs subordinate tree roots, multiplying capacity while keeping signatures small and state ordered.
Key exhaustion: Running out of leaves in a height-h tree after two-to-the-h signatures, requiring the key to be retired.
Monotonic state guarantee: An environment property (typically hardware-enforced) ensuring the index only ever advances, never rolls back or forks.