SPHINCS+

Introduction

Every other algorithm in this post-quantum series — Kyber, Dilithium, Falcon, NTRU, FrodoKEM, SABER — bets on a lattice problem being hard. SPHINCS+, NIST’s third and most conservative standardized signature scheme (FIPS 205), makes a much smaller bet: it needs nothing more than a secure cryptographic hash function — no algebraic structure, no lattice, no number theory at all. That minimalism comes from a decades-old idea (Merkle’s hash-based signatures, 1979) scaled up with modern refinements. The trade-off is size: SPHINCS+ signatures run tens of kilobytes, dramatically larger than Dilithium’s or Falcon’s — but its security proof is about as simple and well-trusted as post-quantum cryptography gets.

Table of Contents

• Why Hash-Based Signatures Need a Tree
• WOTS+: A One-Time Signature
• The Merkle Tree: Authenticating Many One-Time Keys
• The Hypertree: Stacking Trees for Statelessness
• A Worked Example
• FAQ
• References

Why Hash-Based Signatures Need a Tree

A hash chain gives you a one-time signature almost for free: reveal a value partway down a chain of repeated hashing, and anyone can verify it by hashing forward the remaining steps and checking they land on your published public value. The catch is right in the name — it’s safe to sign exactly once per key. Sign a second message with the same chain values and you leak enough information for a forger to sign arbitrary further messages. A full signature scheme needs many keys, all traceable back to one compact public key — which is exactly what a Merkle tree provides: hash all the one-time public keys together, pairwise, up to a single root. That root is the actual public key; each signature reveals which leaf was used and proves — via a chain of sibling hashes — that this leaf really is part of the tree under that root.

WOTS+: A One-Time Signature

SPHINCS+ uses WOTS+ (Winternitz One-Time Signature+) as its underlying one-time scheme:

1. Generate several random private values, one per “chain position.”
2. The public key is each private value hashed a fixed number of times (say, w−1 times, where w is the Winternitz parameter).
3. To sign, split the message digest into small digits (base w), and for each digit d, reveal the private value hashed just d times (partway down the chain, not all the way).
4. To verify, hash each revealed value the remaining number of steps and check it matches the corresponding public value.
5. Extra checksum digits (computed from the message digits) get signed the same way — this stops a forger from taking a valid signature and simply hashing revealed values forward to claim a different message digest that would otherwise look valid.

The Merkle Tree: Authenticating Many One-Time Keys

Generate many WOTS+ keypairs — say 4, 16, or (in real SPHINCS+) up to 2¹⁶ or more. Hash each public key down to a single “leaf” value, then build a Merkle tree: pair up leaves and hash them together, then pair up those hashes, repeating until a single root remains. That root is published as the actual signing public key. A signature reveals which leaf (i.e., which one-time key) was used, the WOTS+ signature itself, and an authentication path — the sibling hash at every level needed to recompute the root from that one leaf, proving the leaf genuinely belongs to this tree without revealing any other leaf.

The Hypertree: Stacking Trees for Statelessness

One Merkle tree only has as many one-time keys as it has leaves — far too few for a signature scheme meant to sign a practically unlimited number of messages over a key’s lifetime, and tracking “which leaves have I used already” (statefulness) is exactly the kind of implementation bug that has broken real deployed hash-based signature schemes in the past. SPHINCS+’s fix: stack multiple layers of Merkle trees into a hypertree. A bottom-layer tree’s leaf doesn’t sign the message directly forever — instead, each message essentially gets a pseudorandomly chosen path through the whole hypertree structure, so different messages statistically land on different leaves across the layers, without any need to remember which leaves were used before. The visualizer below implements exactly two layers: a bottom tree whose selected leaf signs the message, and a top tree whose selected leaf signs the bottom tree’s root — chaining trust upward to a single overall public key, exactly the mechanism real SPHINCS+ repeats across many more layers.

Interactive Visualizer

Real SPHINCS+ additionally uses FORS (Forest of Random Subsets), a specialized few-time signature scheme, to authenticate the message digest itself before it enters the hypertree — this lets one hypertree leaf safely authenticate many different possible messages rather than exactly one, dramatically increasing the total number of signatures a single key can produce. The visualizer omits FORS for toy scope (disclosed here rather than silently) and instead has the bottom-layer WOTS+ directly sign the message digest — which preserves the genuine one-time-signature-under-a-hypertree mechanism, just with real SPHINCS+’s extra few-time-signature layer left out. Tree height is 2 (4 leaves per layer) and the Winternitz parameter is 4, small enough to watch every hash chain and authentication path directly; real SPHINCS+ uses trees with 2¹⁶+ leaves per layer and multiple hypertree layers.

A Worked Example

Using the visualizer’s toy parameters:

1. Two 4-leaf Merkle trees are built (layer 0 and layer 1), each from 4 freshly generated WOTS+ keypairs. The layer-1 root is published as the public key.
2. To sign a message, its hash picks a layer-0 leaf; that leaf’s WOTS+ chains sign the message digest, and an authentication path proves the leaf belongs to the layer-0 tree.
3. The layer-0 root itself gets hashed to pick a layer-1 leaf; that leaf’s WOTS+ chains sign the layer-0 root, with its own authentication path up to the layer-1 root (the public key).
4. Verification recomputes both authentication paths from the two WOTS+ signatures and checks the final recovered value matches the published public key — succeeding for the signed message and (overwhelmingly) failing for any other.

FAQ

Why do SPHINCS+ signatures end up so large compared to Falcon or Dilithium?

Each signature has to include a full WOTS+ signature (dozens of hash values) per hypertree layer, plus an authentication path per layer, plus the FORS signature — real SPHINCS+ signatures run 8KB-50KB depending on parameter set, versus roughly 1-4KB for Dilithium and under 1KB for Falcon.

Why would anyone choose SPHINCS+ over a smaller lattice-based signature?

Conservatism: SPHINCS+’s security reduces essentially only to the collision- and preimage-resistance of its underlying hash function — properties hash functions have been studied for far longer, and with much simpler proofs, than lattice problems. NIST standardized it specifically as a structurally-independent backup in case an unexpected weakness were ever found in lattice cryptography generally.

What happens if a WOTS+ one-time key gets used twice?

Exactly the vulnerability the whole hypertree exists to prevent — reusing a WOTS+ key to sign two different messages leaks enough of the private hash-chain values that an attacker can often forge a signature for a third, chosen message. This is precisely why real SPHINCS+ (and the toy visualizer) always route each new signature to a pseudorandomly-selected leaf rather than reusing one.

Is SPHINCS+ “stateless” in the way the name of the family implies?

Yes — unlike classic Merkle signatures (and the earlier stateful hash-based scheme XMSS), SPHINCS+ never needs to remember which leaves it has already used; the leaf index is derived pseudorandomly from the message and a secret key each time, so signing never risks accidental key reuse from lost or duplicated state — a real operational hazard with stateful schemes.

References

1. Bernstein, D.J., Hülsing, A., Kölbl, S., et al. “SPHINCS+: Practical Stateless Hash-Based Signatures.” EUROCRYPT, 2015 (and subsequent NIST submission).

2. Merkle, R. “Secrecy, Authentication, and Public Key Systems.” Stanford PhD Thesis, 1979 (introduces hash-tree signatures).

3. NIST. “Stateless Hash-Based Digital Signature Standard.” FIPS 205, 2024.

4. SPHINCS+ Team. “SPHINCS+.” Available at: https://sphincs.org/