Stateful vs Stateless Hash-Based Signatures
The two branches of hash-based cryptography differ on one operational question: whether the signer has to remember which one-time keys it has already spent. LMS and XMSS do, which keeps their signatures compact and makes key reuse catastrophic. SLH-DSA designs the requirement away, which removes the hazard and makes its signatures large.
Both are current NIST standards aimed at different jobs rather than old-and-new versions of the same thing, and both rest on the same conservative assumption that a hash function stays collision- and preimage-resistant.
The short version:
- The difference is bookkeeping, and its consequence is severe. Signing two different messages with the same one-time key in a stateful scheme lets an attacker forge signatures at will.
- Stateful schemes have finite, pre-chosen capacity. An LMS key signs between 2^5 and 2^25 times depending on tree height, and the multi-tree forms reach 2^60. The number is fixed when the key is generated.
- SLH-DSA has no capacity limit and no state, because it randomizes which one-time keys get used, so there is no counter to maintain and no reuse footgun.
- The size gap is the whole price. SLH-DSA signatures run from 7,856 to 49,856 bytes against compact stateful signatures, while its public keys stay tiny at 32 to 64 bytes.
- SP 800-208 requires stateful signing to happen in hardware, and CNSA 2.0 approves LMS and XMSS specifically for software and firmware signing rather than for general-purpose use.
Picture a numbered pad of one-time wax seals with a logbook clipped to it. Each seal presses exactly one document and then gets crossed off, because pressing the same seal on two letters leaks enough of its shape for a forger to carve a copy. As long as the log is perfect the system is unbreakable, and the danger lives entirely in the bookkeeping: restore an old copy of the pad from a drawer, or hand a duplicate to a second office, and two people can press seal 41 on two different letters. The stateless design replaces the logbook by making the pad enormous and picking seals at random, so a collision is vanishingly unlikely without anyone tracking anything. The pad is much bulkier to carry.
What is the difference between stateful and stateless hash-based signatures?
The difference is whether the private key carries changing internal state that records which one-time keys have been consumed. Stateful schemes walk through the leaves of a Merkle tree in order and must never revisit one, so the signer maintains a counter that has to survive backups, restores, replication and failover without ever moving backward. Stateless SLH-DSA selects one-time keys pseudorandomly from a much larger structure, so no counter exists and no restore can duplicate one.
Everything else follows from that choice. Tracking state buys compact signatures and a fixed signing capacity. Removing state costs signature size and buys freedom from the single most dangerous operational failure in the family.
What are stateful hash-based signatures?
LMS and XMSS are the two NIST-approved stateful schemes, standardized in SP 800-208 in October 2020, roughly 4 years before the lattice signatures were finalized, which makes them the earliest standardized post-quantum signatures. LMS is the Leighton-Micali Signature, with a multi-tree form called HSS. XMSS is the eXtended Merkle Signature Scheme, with a multi-tree form called XMSS^MT.
Their capacity is finite and chosen at key generation:
| Scheme | Approved capacity per key | Determined by |
|---|---|---|
| LMS, single tree | 2^5 to 2^25 signatures, meaning 32 up to about 33.5 million | Tree height H of 5, 10, 15, 20 or 25 |
| XMSS, single tree | 2^10, 2^16 or 2^20 signatures | Tree heights of 10, 16 or 20 |
| HSS and XMSS^MT, multi-tree | Up to 2^60 signatures | Total multi-tree height up to 60 |
Source: NIST, “Recommendation for Stateful Hash-Based Signature Schemes,” SP 800-208, Tables 2, 10 and 11, October 2020, csrc.nist.gov.
What is stateless SLH-DSA?
SLH-DSA is the Stateless Hash-Based Digital Signature Standard, the standardized form of SPHINCS+, finalized by NIST in August 2024. It removes the state requirement entirely by randomizing which one-time keys are used, so there is no counter to maintain, no reuse hazard, and no capacity ceiling to plan around. That makes it safe to deploy in ordinary software with no special hardware.
The cost is signature size. SLH-DSA signatures run from 7,856 bytes for the smallest parameter set up to 49,856 bytes for the largest, while its public keys stay small at 32 to 64 bytes.
Source: NIST, “Stateless Hash-Based Digital Signature Standard,” FIPS 205, Table 2, August 2024, csrc.nist.gov.
Stateful vs stateless at a glance
| Dimension | Stateful (LMS, XMSS) | Stateless (SLH-DSA) |
|---|---|---|
| Members | LMS with HSS, XMSS with XMSS^MT | SLH-DSA, the standardized form of SPHINCS+ |
| Standard | SP 800-208, October 2020; RFC 8554 (LMS), RFC 8391 (XMSS) | FIPS 205, August 2024 |
| State required | Yes. The signer must track every one-time key consumed | None |
| Signatures per key | Finite and fixed at key generation: 2^5 to 2^25 single-tree, up to 2^60 multi-tree | Unbounded in practice |
| Signature size | Compact | 7,856 to 49,856 bytes by parameter set |
| Public key size | Small | 32 to 64 bytes |
| Consequence of key reuse | Catastrophic. Signing 2 messages with one one-time key permits arbitrary forgery | None. There is no key to reuse |
| How reuse actually happens | A restored backup, a cloned virtual machine, a replication or failover slip | Does not apply |
| Hardware signing | Required by SP 800-208 | Not required |
| Capacity planning | Required before key generation, since the ceiling is permanent | Not required |
| CNSA 2.0 position | Approved specifically for software and firmware signing in national security systems, and only when all of SP 800-208 is met | Available as the general-purpose conservative hash-based option |
| Security assumption | Collision- and preimage-resistance of the underlying hash function | The same |
| Quantum resistance | Shor’s does not apply; Grover’s absorbed through hash output sizing | The same |
| Does key establishment | No. ML-KEM handles that | No |
| Best fit | Low-volume, long-lived, hardware-controlled signing | Broad deployment where large signatures are acceptable |
How do they actually differ?
-
The failure mode is operational rather than cryptographic. Nothing about the mathematics of LMS or XMSS is weaker than SLH-DSA. The hazard is entirely in whether an operational environment can guarantee that a private key’s counter never moves backward, and ordinary infrastructure practices actively work against that guarantee. Snapshots, backups, virtual-machine cloning and high-availability replication all exist to duplicate state, which is exactly what must never happen here.
-
Capacity is a design-time decision in one branch and a non-question in the other. A stateful key has to be sized before it exists, which means forecasting how many signatures it will ever produce across its whole service life. For firmware signing, where a device might take a handful of updates a year across a decade, even a modest tree has enormous headroom. For anything with unpredictable volume, that forecast is a liability.
-
The size difference lands on different parts of a system. Compact stateful signatures suit constrained devices verifying a firmware image with limited storage and bandwidth. SLH-DSA signatures at up to 49,856 bytes are unremarkable next to a firmware image itself and are significant in a protocol handshake or a certificate chain.
-
Hardware is mandatory on one side. SP 800-208 requires stateful signing to occur in hardware, which makes an HSM or equivalent secure module part of the deployment cost rather than an optional hardening step. SLH-DSA carries no such requirement and runs safely in ordinary software.
-
The taller the tree, the higher the cost. A taller stateful tree signs more times, costs more to generate and produces a slightly larger signature, so the tree is sized to the job. That tuning axis has no equivalent in the stateless scheme.
Where do they agree?
-
On the security assumption, which is that the underlying hash function stays collision- and preimage-resistant. This is the most conservative bet available in cryptography and the reason the whole family exists.
-
On quantum resistance and how it is achieved. Shor’s algorithm needs algebraic structure that hash functions lack, so it does not apply. Grover’s algorithm halves the effective margin through a quadratic search speedup, and both branches absorb it by choosing hash output sizes accordingly.
-
On job scope. Both sign and neither performs key establishment, so ML-KEM handles confidentiality regardless of which is chosen.
-
On being current standards. Neither supersedes the other. SP 800-208 and FIPS 205 are both live NIST standards aimed at different operational contexts.
-
On the underlying construction. Both build a long-term public key by hashing many one-time public keys together into a Merkle-tree root, and both produce a signature carrying a one-time signature plus the authentication path needed to recompute that root.
When is each the right answer?
Stateful LMS or XMSS fits when three conditions hold together. The signing volume is low and predictable enough to size a tree confidently, the environment can guarantee the state is never duplicated (which in practice means signing inside a hardware module), and the compact signature is worth the operational burden. Firmware signing, software release signing and long-lived roots of trust are the canonical cases, and they are exactly what CNSA 2.0 names.
Stateless SLH-DSA fits everywhere else in the hash-based branch. It provides the same conservative assumption without a reuse footgun, runs in ordinary software, needs no capacity forecast, and asks only that the deployment absorb a signature measured in tens of kilobytes.
Neither is the general-purpose signature default. For high-volume, size-sensitive signing, ML-DSA is smaller and faster, and the hash-based branch earns its place at the durable, low-frequency, maximum-confidence end instead.
Why do people confuse them?
Because “stateless” reads as a newer and therefore better version of “stateful,” which maps onto how software terminology usually works. In cryptographic standards it means something narrower: a design decision about whether the scheme carries a counter, made differently for different deployment contexts.
The second confusion is treating the state requirement as an implementation detail that careful engineering can handle. It is a hard security boundary rather than a quality bar, which is why SP 800-208 mandates hardware signing rather than recommending careful practice. Any process that can restore, clone or replicate a signing key can reintroduce the hazard regardless of how carefully the signing code was written.
Common misconceptions
-
“Stateless SLH-DSA replaced stateful XMSS and LMS.” Both are current NIST-backed standards for different jobs. The stateful schemes remain far more compact, which is what firmware signing wants when state can be managed safely.
-
“Statefulness is just an implementation inconvenience.” Reusing a single one-time key permits arbitrary forgery, which is a total break rather than a degradation, and SP 800-208 requires hardware signing precisely because ordinary infrastructure duplicates state routinely.
-
“A stateful key can sign forever.” Capacity is finite and fixed at generation, between 2^5 and 2^25 signatures for a single-tree LMS key and up to 2^60 for the multi-tree forms. Exhausting it requires generating and distributing a new key.
-
“Hash-based signatures can also do key exchange.” Neither branch performs key establishment. Hash functions do not support key encapsulation, so ML-KEM handles confidentiality in either case.
-
“SLH-DSA’s large signatures make it impractical.” The size is the price of removing the sharpest operational hazard in the family, and for trust roots and firmware, where a signature is written once and trusted for years, it is usually worth paying. Size only becomes limiting in high-volume, bandwidth-sensitive contexts, which ML-DSA serves better anyway.
-
“Grover’s algorithm breaks hash-based signatures.” Grover delivers a quadratic speedup on preimage search, halving the effective margin, and both branches are designed to absorb that through hash output sizing.
Questions people ask
Which hash-based signature should I use? SLH-DSA unless you have a specific reason not to, because it carries no reuse hazard and needs no hardware. Choose LMS or XMSS when signing volume is low and predictable, an HSM can guarantee state integrity, and the compact signature genuinely matters.
What actually happens if a stateful key signs twice with the same one-time key? An attacker who sees both signatures gains enough information to forge arbitrary signatures under that key. It is a complete break of the key rather than a partial weakening.
How would that even happen in practice? Through ordinary operations that duplicate state: restoring a signing service from a backup, cloning a virtual machine, or a replication or failover event that reverts the counter. None of them requires a mistake in the cryptographic code.
How many signatures does a stateful key get? Between 2^5 and 2^25 for a single-tree LMS key, depending on tree height, and 2^10, 2^16 or 2^20 for single-tree XMSS. The multi-tree forms HSS and XMSS^MT reach up to 2^60.
How large is an SLH-DSA signature? Between 7,856 and 49,856 bytes depending on the parameter set, with public keys of 32 to 64 bytes. That size is the direct cost of removing the state requirement.
Do I need an HSM? For LMS and XMSS, yes. SP 800-208 requires the signing operation to happen in hardware. SLH-DSA carries no such requirement.
Are these approved for government use? Both are NIST standards. CNSA 2.0 names LMS and XMSS specifically for signing software and firmware in national security systems, and reminds implementers that they stay secure only when all of SP 800-208 is met, including state management and hardware signing.
Why did NIST standardize the stateful ones first? SP 800-208 landed in October 2020, roughly 4 years before the lattice signatures were finalized, because hash-based constructions rest on the best-understood assumption in cryptography and needed less new cryptanalysis to reach confidence.
Should either be my general-purpose signature? Neither. ML-DSA is the smaller, faster general-purpose post-quantum signature, and the hash-based branch is the conservative reserve for long-lived, high-assurance, low-frequency signing.
The map is free and I keep it that way. When the question becomes which of these belongs on which signing surface across a real estate, and whether the state guarantee actually holds there, that’s the work I do at LaMarr Labs.
Go deeper
- Stateful Hash-Based Signatures (XMSS - LMS) and FIPS 205 (SLH-DSA) for each branch in full
- Hash-Based Cryptography for the family both belong to
- Lattice vs Code-Based vs Hash-Based for how this family compares to the others
- ML-DSA vs SLH-DSA vs FN-DSA for the three signature standards compared
- NIST SP 800-208 for the stateful standard
- PQC in Firmware and Code Signing for the deployment context these were built for
- NSA CNSA 2.0 for the national-security-systems position
Last verified 2026-08-10 · Maintained by Addie LaMarr, LaMarr Labs.