XMSS (eXtended Merkle Signature Scheme)

XMSS (eXtended Merkle Signature Scheme) is a stateful hash-based signature scheme standardized in RFC 8391. It arranges many WOTS+ one-time key pairs as the leaves of a Merkle tree; the tree root is the long-lived public key, and each signature reveals one WOTS+ signature plus the authentication path linking its leaf to the root. Because every one-time key must be used exactly once, the signer keeps state: an index recording which leaves are already spent.

#State and standardization

The stateful requirement is the main operational hazard. If one index signs two different messages, for example after a virtual-machine rollback or a restored backup, security can collapse. For this reason NIST SP 800-208 approves XMSS and its multi-tree variant XMSS-MT only for constrained uses such as firmware signing, where a device signs in a controlled sequence. XMSS security reduces to standard hash function properties, so it is considered post-quantum secure. It is closely related to LMS, the other stateful scheme approved in the same document; stateless SLH-DSA avoids state at the cost of larger signatures.