Dr. Sarah ChenWhat Is XMSS?
XMSS (eXtended Merkle Signature Scheme) is a hash-based digital signature scheme standardized by NIST in Special Publication 800-208 (2020) and by the IETF in RFC 8391 (2018). Like SPHINCS+, its security depends only on the collision resistance and preimage resistance of the underlying hash function, not on algebraic hardness assumptions. Unlike SPHINCS+, XMSS is stateful: the signer must track which one-time keys have been used and must never reuse a key index.
XMSS was developed by Buchmann, Dahmen, and Huelsing starting around 2011, building on earlier work by Merkle (1989) and Lamport (1979). It is one of the oldest post-quantum signature constructions, with a security proof that predates the NIST post-quantum standardization process by over a decade.
How XMSS Constructs Signatures From One-Time Keys
XMSS builds signatures in three layers. Understanding each layer is necessary to understand both the security guarantees and the state management requirement.
The base layer is WOTS+ (Winternitz One-Time Signature Plus). WOTS+ signs a single message by encoding the message as a series of integers, then applying a hash chain to secret key material a corresponding number of times. The public key is the result of applying the maximum number of hash chain steps to the secret key material. Signing reveals partial hash chains. Verification computes the remaining hash chain steps and checks against the public key. This is one-time because revealing any partial chain constrains future signatures: signing two different messages with the same WOTS+ key leaks enough information to forge signatures.
The middle layer is an L-tree, which compresses a WOTS+ public key (which consists of multiple hash values) into a single hash value. This compression is needed to insert WOTS+ public keys as leaves in the Merkle tree.
The top layer is a Merkle tree. The root of the Merkle tree is the XMSS public key. Each leaf is a compressed WOTS+ public key. To sign a message, the signer picks the next unused leaf index, generates a WOTS+ signature for that leaf, and appends the authentication path (sibling nodes up the Merkle tree) needed to verify that leaf against the root. The state that must be maintained is the current leaf index. Every time a signature is generated, the index increments. When all 2^h leaves are exhausted (where h is the tree height), no more signatures can be generated with that key.
XMSS Key and Signature Sizes
NIST SP 800-208 defines parameter sets for XMSS at SHA2 and SHAKE variants, with tree heights of 10, 16, and 20. The key sizes are small because the public key is just a Merkle tree root plus some domain parameters.
- XMSS-SHA2_10_256: 2^10 = 1,024 signatures per key. Public key: 64 bytes. Signature: 2,500 bytes. Tree height: 10.
- XMSS-SHA2_16_256: 2^16 = 65,536 signatures per key. Public key: 64 bytes. Signature: 2,692 bytes. Tree height: 16.
- XMSS-SHA2_20_256: 2^20 = 1,048,576 signatures per key. Public key: 64 bytes. Signature: 2,820 bytes. Tree height: 20.
Signature sizes are smaller than SPHINCS+ (7,856 bytes for the smallest parameter set) but larger than ML-DSA-44 (2,420 bytes). The maximum signature count of 2^20 sounds large, but consider a validator signing attestations at one per second: a 2^20 key exhausts in roughly 12 days.
XMSS^MT (Multi-Tree XMSS) addresses this by layering multiple XMSS trees, with the top-level tree signing the roots of lower-level trees. XMSS^MT with d=2 layers and total height H=40 supports 2^40 signatures, roughly 34,000 years of signing at one signature per second. The trade-off is larger signature sizes (roughly 4,963 bytes for the d=2, h=20 variant).
The State Management Problem
The statefulness of XMSS is not a minor implementation detail. It is a fundamental security requirement. If any leaf index is used to sign two different messages, the security proof breaks: an attacker can combine the two WOTS+ signatures to forge additional signatures. This is not a theoretical concern. It is a practical attack that requires only the two signatures themselves.
State management failures happen in several realistic scenarios. First, hardware failure after signing but before the state counter persists to durable storage: the signer restarts, reads the pre-signing state, and reuses the same index. Second, VM snapshots: a cloud instance is snapshot before signing and restored to the pre-signing state. Third, parallel signing: two processes both read state k, both increment to k+1, and both use index k for different messages.
These failure modes make XMSS unsuitable for any system where multiple processes might sign concurrently, where state persistence cannot be guaranteed to be atomic with signature generation, or where disaster recovery might involve restoring from backup (which restores old state).
SPHINCS+ solves the statefulness problem by deriving the leaf index deterministically from the message and the secret key. Reusing the same key with the same message produces the same index, which is safe. Using the same key with different messages produces different indices with overwhelming probability. No external state counter is needed. For systems that cannot guarantee atomic state persistence, SPHINCS+ is the correct choice.
Where XMSS Is Appropriate
XMSS is the right choice for applications where state can be reliably managed and the total signature count is known in advance:
Root CA certificates. A root CA might sign 100 to 1,000 intermediate certificates over its lifetime. XMSS-SHA2_10_256 with 1,024 signature capacity is sufficient, and the signing infrastructure can be designed as a single, audited HSM with atomic state updates.
Firmware signing. Embedded devices that boot from signed firmware images perform a small, predictable number of verification operations. The manufacturer's signing key needs to sign perhaps a few hundred firmware releases over a product lifecycle. XMSS-SHA2_10_256 handles this easily, and the signing system can be air-gapped with explicit state tracking.
HSMs with internal state management. A hardware security module can manage the XMSS state counter in tamper-resistant hardware, making state reuse physically impossible as long as the HSM is not cloned. This is the environment XMSS was designed for.
The common thread is that all of these are single-signer, low-frequency, high-security environments where the operational requirements of state management are tractable. The NIST PQC standards overview explains why NIST SP 800-208 was a separate publication from the FIPS standards and what that means for deployment guidance.
Why XMSS Does Not Fit Blockchain Applications
Blockchain signing has exactly the properties that make XMSS difficult to use safely. Transactions are signed by wallets that might run on multiple devices. Validator nodes may run in clustered configurations for high availability. Block proposers sign attestations at rates of one per slot (12 seconds in Ethereum-based systems, potentially faster). Recovery from crashes must be possible without reverting to a pre-crash state that might reuse indices.
ML-DSA-65 produces 3,309-byte signatures, slightly larger than XMSS-SHA2_16_256's 2,692 bytes, but without any state management requirement. A wallet can sign on any device with the same private key, in parallel, without any coordination. This is the correct operational model for a blockchain.
For the specific throughput impact of signature sizes on blockchain transaction capacity, the analysis of Dilithium signature size and blockchain throughput provides concrete numbers. The short version: XMSS's modest size advantage over ML-DSA does not compensate for its operational constraints in a blockchain context.
XMSS vs. SPHINCS+: Which Hash-Based Scheme to Use
Both XMSS and SPHINCS+ derive security from hash function hardness alone. The choice between them reduces to one question: can the deployment reliably maintain signing state?
If yes, and if signing frequency is low (fewer than 2^20 signatures per key) and the system is a single-signer HSM or air-gapped CA: XMSS. Smaller signatures, better-understood security proof, IETF RFC standardization useful for existing PKI integration.
If no, or if signing happens in distributed systems, cloud environments, or anything with parallel processes: SPHINCS+ (SLH-DSA, FIPS 205). Larger signatures, but stateless operation, FIPS standardization, and no risk of catastrophic state reuse.
For high-throughput applications, both hash-based schemes lose to ML-DSA on signature size and signing speed. Hash-based schemes are appropriate when the security independence from algebraic hardness assumptions matters more than performance.
Summary
XMSS is a stateful hash-based signature scheme standardized in NIST SP 800-208 and RFC 8391. It produces 2,500 to 2,820-byte signatures with security that reduces to hash function hardness alone. Its fundamental limitation is statefulness: the signer must never reuse a leaf index or security breaks catastrophically. This makes it suitable for single-signer HSMs, root CAs, and firmware signing systems, but unsuitable for distributed blockchain signing. SPHINCS+ (SLH-DSA) solves the statefulness problem at the cost of larger signatures (7,856 bytes minimum), and ML-DSA provides better performance at the cost of relying on Module-LWE hardness.
