Every deployed digital signature rests on an assumption. RSA relies on the hardness of factoring and ECDSA on discrete logarithms. Both fail against a sufficiently large quantum computer running Shor's algorithm. Lattice schemes like ML-DSA replace those assumptions with new ones about structured lattice problems. These problems have resisted cryptanalysis, but they have been studied for decades rather than centuries. The real question is how little you can assume and still sign.

Hash-based signatures come close to the theoretical minimum. Rompel showed in 1990 that one-way functions are sufficient for secure signatures. Practical hash-based schemes approach that bound: their security reduces to properties such as second-preimage resistance and the pseudorandomness of a hash function. Grover's algorithm gives only a quadratic speedup against these properties, and parameter choices absorb it directly. If SHA-2 or SHAKE breaks, we have larger problems than signatures.

The cost is size and, historically, state. SLH-DSA, which NIST standardised as FIPS 205 in 2024 from the SPHINCS+ submission, is the stateless answer. It has signatures of roughly 8 to 50 kilobytes, public keys of 32 to 64 bytes, and no counter to protect. To see why it looks the way it does, we start with Merkle's original construction. Then we follow the design decisions that turned a fragile, stateful primitive into something you can deploy without synchronisation.

The one-time signature is the basic building block. Lamport's 1979 scheme publishes hashes of two secret values per message bit, and signing reveals one preimage per bit. Winternitz generalises this by grouping bits into base-w digits and committing to the ends of hash chains of length w−1. Signing a digit d reveals the chain element at position d. WOTS+ is the variant used in modern schemes. It masks each chain step so that its security reduces to second-preimage resistance rather than collision resistance.

A naive Winternitz signature is malleable. Anyone can hash a revealed chain value forward and obtain a valid signature on a larger digit. The checksum closes this gap. It sums w−1−d_i across the message digits and signs that sum as additional digits. Increasing any message digit decreases the checksum, so a forger must invert the chain somewhere. With n = 16 bytes and w = 16, this gives 32 message chains plus 3 checksum chains, for 35 chains in total.

Merkle's insight was to commit to many one-time keys with a single value. The signer generates 2^h WOTS+ key pairs, hashes each public key into a leaf, and builds a binary hash tree whose root is the public key. A signature contains the leaf index, the one-time signature, and the authentication path: the h sibling nodes needed to recompute the root. The verifier recovers the one-time public key from the signature and then hashes up the tree to the root.

The security reduction is clean. A forger against the Merkle scheme must either forge one of the one-time instances or find a second preimage somewhere in the tree. A tight analysis needs care with multi-target attacks. With 2^h leaves and many internal nodes, the attacker gets many targets at once, and generic preimage search speeds up proportionally. XMSS counters this with per-node bitmasks and keyed hashing, so that each hash call behaves as an independent function.

Everything depends on one rule: never use a leaf twice. Two WOTS+ signatures under the same key reveal, for each chain, the lower of the two positions. An attacker can then forge any message whose digits, including the checksum, are all at or above those positions. The tree turns a one-time scheme into a 2^h-time scheme, but it does so by moving the burden into the signer's bookkeeping. SPHINCS+ was designed to eliminate that bookkeeping.

Takeaway

A Merkle tree does not strengthen a one-time signature; it multiplies it. The multiplication only holds if the signer tracks every use perfectly.

SPHINCS+ starts from Goldreich's observation: if the tree is large enough, the signer can pick a leaf at random instead of tracking which leaves have been used. A single tree of height 64 is infeasible to compute, so SPHINCS+ uses a hypertree. This is d layers of XMSS trees, each of height h' = h/d. A WOTS+ key in the layer above signs each tree's root, and only the top root is published. The signer regenerates trees on demand from a secret seed.

At the bottom sits FORS, a Forest Of Random Subsets. FORS is a few-time signature made of k independent trees of height a, each with 2^a secret leaves. The signer splits the message digest into k indices of a bits each and reveals one leaf per tree along with its authentication path. The bottom-layer WOTS+ key signs the FORS public key. Deriving the hypertree index from the message digest itself prevents an adversary from steering signatures toward a chosen FORS instance.

Random index selection means collisions are expected. With h = 63 and up to 2⁶⁴ signatures, some FORS instances will sign more than one message. FORS degrades gracefully: each reuse reveals more leaves, but a forger still needs all k indices to land on leaves that have already been revealed. The security bound is computed over the distribution of reuse counts, which ties k and a to h. The WOTS+ keys inside the hypertree never face this problem, because each one always signs the same deterministic root.

All of this runs on tweakable hash functions. Every call takes a public seed, an address structure that encodes its exact position, and the input. This domain separation gives tight multi-target security across an enormous number of hash calls. Message signing is randomised. The signer computes R = PRF_msg(SK.prf, opt_rand, M), and H_msg(R, PK.seed, PK.root, M) yields both the FORS digest and the hypertree index. Setting opt_rand to the public seed gives deterministic signing.

Parameter selection trades size against speed. SLH-DSA-SHA2-128s uses h = 63, d = 7, a = 12 and k = 14, giving a 7,856-byte signature but slow signing. SLH-DSA-SHA2-128f uses h = 66, d = 22, a = 6 and k = 33, giving 17,088 bytes with much faster signing. Fewer, taller trees shrink signatures because each signature includes fewer WOTS+ signatures and authentication paths. The cost is that each tree requires 2^h' leaf computations. All standard parameter sets fix w = 16.

Takeaway

SPHINCS+ is less a new primitive than an arrangement. It layers one-time, few-time, and many-time components so that each component's weakness is covered by the next.

XMSS and LMS are excellent signature schemes, but they share one operational requirement that is easy to underestimate: the private key is a mutable object. Each signature must advance a counter, and that counter must be durably stored before the signature leaves the device. NIST SP 800-208 restricts stateful hash-based signatures to hardware cryptographic modules and forbids exporting their private keys. That is how seriously the standard treats this requirement.

The failures are mundane. A virtual machine snapshot is restored, rolling back the counter. A key is replicated across a cluster for availability. A process crashes after emitting a signature but before saving its state to disk. A backup is restored after a hardware failure. Each of these is routine practice in systems engineering. Each one silently turns a stateful signing key into a reused one-time key.

The consequence is not a gradual loss of security margin. Two WOTS+ signatures from the same leaf can give an adversary enough chain values to forge signatures on related messages with non-negligible probability. Attackers can often influence which messages get signed, which makes this worse. Unlike nonce reuse in ECDSA, which leaks the key outright, the damage here is confined to one leaf. Even so, a forgery that verifies under the long-term public key is a complete break of the scheme's guarantee.

SPHINCS+ pays to make the problem disappear. Because leaf selection is pseudorandom over a space of 2⁶³ or more, the private key is a constant: two seeds and a PRF key. It can be cloned, backed up, and loaded into many signers at once without coordination. The worst case of reuse is already priced into the FORS security bound. The cost is signatures several times larger than XMSS at comparable security, along with substantially slower signing for the small parameter sets.

This is why the field has not abandoned stateful schemes. CNSA 2.0 endorses LMS and XMSS for firmware signing, where signing volume is low and a single hardened signer is realistic. Meanwhile, research continues to narrow the gap from the stateless side. SPHINCS+C uses counter-based grinding to remove the checksum chains and the last FORS tree. Proposed parameter sets capped well below 2⁶⁴ signatures could shrink signatures substantially for applications that will never approach that limit.

Takeaway

Stateless signatures trade bytes for the elimination of an entire class of operational failure. The exchange looks expensive only until you count what a rolled-back counter costs.

Hash-based signatures show that post-quantum security does not require new hardness assumptions. A one-time signature, a Merkle tree, and careful accounting of reuse are enough to build a scheme whose security tracks the hash function underneath it.

SPHINCS+ shows what that minimalism costs and where the cost can be placed. The hypertree, FORS, and tweakable hashing move the burden of correctness from runtime state to static parameters. Those parameters can be analysed once instead of being enforced on every signature.

The broader design principle is that a security proof holds only under the assumptions the deployment actually satisfies. A scheme that requires perfect state is secure in a model that real infrastructure rarely provides. When choosing between schemes, ask which assumption you can genuinely guarantee: the hardness of a lattice problem, the discipline of a counter, or only the integrity of a hash.