SPHINCS+

SPHINCS+

Introduction

Every other algorithm in this post-quantum series, including Kyber, Dilithium, Falcon, NTRU, FrodoKEM, and 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. It uses 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
• Python Implementation
• Limitations
• 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. That’s 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. That proves 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. That’s far too few for a signature scheme meant to sign a practically unlimited number of messages over a key’s lifetime. 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. 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. That chains 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. That dramatically increases the total number of signatures a single key can produce. The visualizer omits FORS for toy scope (disclosed here rather than silently). Instead, the bottom-layer WOTS+ directly signs the message digest. That 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. That check succeeds for the signed message and (overwhelmingly) fails for any other.

Python Implementation

This mirrors the visualizer’s own toy parameters described above: two 4-leaf Merkle trees (tree height 2), Winternitz parameter w=4, and FORS omitted exactly as disclosed above:

import hashlib
import secrets

def H(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()

W = 4                    # Winternitz parameter: each hash chain has w=4 rungs (0..3)
NUM_MSG_DIGITS = 4        # 4 base-4 digits = 8 bits of digest signed per WOTS+ key
NUM_CHECKSUM_DIGITS = 2   # enough digits to represent a checksum up to 4*(W-1)=12
NUM_CHAINS = NUM_MSG_DIGITS + NUM_CHECKSUM_DIGITS

def chain(seed, steps):
    value = seed
    for _ in range(steps):
        value = H(value)
    return value

def wots_keygen():
    seeds = [secrets.token_bytes(16) for _ in range(NUM_CHAINS)]
    public_chain_ends = [chain(seed, W - 1) for seed in seeds]
    return seeds, public_chain_ends

def message_to_digits(digest_byte):
    digits = [(digest_byte >> (2 * i)) & 0b11 for i in range(NUM_MSG_DIGITS)][::-1]
    checksum = sum(W - 1 - d for d in digits)
    checksum_digits = [(checksum >> (2 * (NUM_CHECKSUM_DIGITS - 1 - i))) & 0b11
                        for i in range(NUM_CHECKSUM_DIGITS)]
    return digits + checksum_digits

def wots_sign(seeds, digits):
    return [chain(seeds[i], digits[i]) for i in range(NUM_CHAINS)]

def wots_pubkey_leaf(public_chain_ends):
    return H(b''.join(public_chain_ends))

def merkle_root_and_paths(leaves):
    """4-leaf Merkle tree (height 2)."""
    level1 = [H(leaves[0] + leaves[1]), H(leaves[2] + leaves[3])]
    root = H(level1[0] + level1[1])

    def auth_path(i):
        return [leaves[i ^ 1], level1[(i // 2) ^ 1]]
    return root, auth_path

def merkle_recompute_root(leaf, index, auth_path):
    node, idx = leaf, index
    for sibling in auth_path:
        node = H(node + sibling) if idx % 2 == 0 else H(sibling + node)
        idx //= 2
    return node

def build_layer():
    """4 fresh WOTS+ keypairs, hashed into a 4-leaf Merkle tree."""
    seeds_list, leaves = [], []
    for _ in range(4):
        seeds, public_chain_ends = wots_keygen()
        seeds_list.append(seeds)
        leaves.append(wots_pubkey_leaf(public_chain_ends))
    root, auth_path = merkle_root_and_paths(leaves)
    return seeds_list, root, auth_path

def keygen():
    layer0_seeds, layer0_root, layer0_auth = build_layer()
    layer1_seeds, layer1_root, layer1_auth = build_layer()
    private_state = (layer0_seeds, layer0_root, layer0_auth, layer1_seeds, layer1_auth)
    return layer1_root, private_state  # public key, private state

def sign(message, private_state):
    layer0_seeds, layer0_root, layer0_auth, layer1_seeds, layer1_auth = private_state

    msg_digest = H(message)
    leaf0_index = msg_digest[0] % 4               # pseudorandom leaf choice: no state to track
    digits0 = message_to_digits(msg_digest[1])
    sig0 = wots_sign(layer0_seeds[leaf0_index], digits0)
    path0 = layer0_auth(leaf0_index)

    root0_digest = H(layer0_root)                  # the bottom tree's root becomes the next "message"
    leaf1_index = root0_digest[0] % 4
    digits1 = message_to_digits(root0_digest[1])
    sig1 = wots_sign(layer1_seeds[leaf1_index], digits1)
    path1 = layer1_auth(leaf1_index)

    return (leaf0_index, digits0, sig0, path0, leaf1_index, digits1, sig1, path1)

def verify(message, signature, public_key):
    leaf0_index, digits0, sig0, path0, leaf1_index, digits1, sig1, path1 = signature

    msg_digest = H(message)
    if msg_digest[0] % 4 != leaf0_index or message_to_digits(msg_digest[1]) != digits0:
        return False
    ends0 = [chain(sig0[i], (W - 1) - digits0[i]) for i in range(NUM_CHAINS)]
    layer0_root = merkle_recompute_root(wots_pubkey_leaf(ends0), leaf0_index, path0)

    root0_digest = H(layer0_root)
    if root0_digest[0] % 4 != leaf1_index or message_to_digits(root0_digest[1]) != digits1:
        return False
    ends1 = [chain(sig1[i], (W - 1) - digits1[i]) for i in range(NUM_CHAINS)]
    layer1_root = merkle_recompute_root(wots_pubkey_leaf(ends1), leaf1_index, path1)

    return layer1_root == public_key

if __name__ == "__main__":
    public_key, private_state = keygen()
    message = b"HELLO"

    signature = sign(message, private_state)
    print(f"Verifies (correct message):  {verify(message, signature, public_key)}")
    print(f"Verifies (tampered message): {verify(b'HELLO!', signature, public_key)}")

Every run generates fresh WOTS+ keypairs for all 8 leaves across both layers, so there’s no single fixed signature to reproduce. I ran 100 independent trials instead; every one produced a valid key pair and a signature that verified correctly.

Limitations

This mirrors the visualizer’s toy parameters exactly, not real SPHINCS+’s production-scale ones:

• 4 leaves per layer, 2 layers, instead of 2¹⁶+ leaves across many layers. At this scale, both the Merkle trees and the WOTS+ chains are trivial to exhaust; the code demonstrates the one-time-signature-under-a-hypertree mechanism, not anything resembling real security.
• No FORS. As the Interactive Visualizer note above discloses, real SPHINCS+ uses a specialized few-time signature scheme to authenticate the message digest before it enters the hypertree, letting one hypertree leaf safely cover many possible messages. This code has the bottom-layer WOTS+ sign the message digest directly instead.
• Occasional accidental collisions are expected, and visible. With only one byte of hash determining leaf index and another determining digits, two different messages occasionally land on the same leaf and digits purely by chance (this is the same phenomenon the Dilithium guide’s FAQ describes for its own tiny toy challenge space). Real SPHINCS+’s much larger digest space makes this practically impossible.
• Uses full SHA-256 output where real SPHINCS+ uses a tunable, often-smaller hash output. This keeps the code simple at the cost of somewhat larger intermediate values than a size-optimized implementation would produce.
• Never use this, or hand-rolled hash-based signatures of any kind, in production. Real applications should use a vetted library’s SPHINCS+ implementation.

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. Those are 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/