Post-Quantum Cryptography and Encryption Field Guide
WOTS+ and XMSS: The Hash-Based Schemes Bitcoin Proposals Lean On
- WOTS+
- One signature per key
- sign twice and it’s forgeable
- XMSS
- Merkle tree of keys
- 1,024 to 65,536 signs per key
- THE CATCH
- Statefulness
- you must track which leaf you used
- SIZE EDGE
- XMSS 2–4 KB
- vs SLH-DSA’s 8–49 KB
WOTS+ and XMSS are hash-based signature schemes, the most conservative corner of post-quantum cryptography, and Bitcoin’s quantum proposals keep circling them. WOTS+ is a one-time signature: each key can sign exactly once, because signing twice leaks enough of the private key to forge, no quantum computer required. XMSS bundles many WOTS+ keys into a Merkle tree so one public key can sign thousands of times, with signatures of 2–4 KB, smaller than SLH-DSA’s 8–49 KB. The snag is statefulness: XMSS makes you track which key you have used, which is messy for wallets and backups, so Bitcoin discussion currently leans toward the stateless SLH-DSA.
Part of the Post-Quantum Cryptography and Encryption guide seriesBurn-after-signing (WOTS+, explained)
WOTS+ is a one-time signature: sign once, then the key is retired forever. XMSS bundles many of them so one key can sign thousands of times. For where these fit among the standards, see NIST’s PQC Standards Explained.
A Winternitz one-time signature is a clever piece of cryptographic engineering. You start with a private key that’s a bunch of random hash chains. Each chain is a sequence of repeated hash function applications, say SHA-256 of SHA-256 of SHA-256 of and so on. Your public key is the top of each chain (the most-hashed end). Your private key is the bottom (the least-hashed end).
To sign a message, you reveal a partial hash of each chain based on the message’s hash value. The verifier finishes hashing those partial reveals up to the chain top and checks the result against the public key. If they do, the signature is valid. If they don’t, the signature is forged.
It sounds clean enough. The architecture has one catch. Each partial reveal is a piece of your private key. If you sign two different messages with the same WOTS+ key, an attacker who sees both signatures can combine the revealed pieces and forge a signature on any third message. The whole design depends on never signing twice with the same key.
That’s burn-after-signing. One sign, then the key is permanently retired. If you sign twice, you’ve handed the attacker your wallet.
The Winternitz parameter (w) determines the size and speed trade-off. Standard choices range from w=4 for faster signing to w=16 for more compact signatures, with the exact value tuned to the application.
How a WOTS+ signature works
Build the chains
A private key is a set of random hash chains. The public key is the top (most-hashed) end; the private key is the bottom.
Sign
Reveal a partial hash of each chain, based on the message’s hash value.
Verify
The verifier finishes hashing the reveals up to the top and checks the result against the public key.
Burn
Each reveal is a piece of the private key, so the key signs once and is retired. A second signature lets an attacker forge.
Each partial reveal is a piece of your private key. Sign two different messages with the same WOTS+ key and an attacker who sees both can forge a signature on any third message, no quantum computer required. The whole design depends on never signing twice.
- Winternitz parameter (w)
- tunes size vs speed; w=4 is faster, w=16 is more compact
XMSS is a merkle tree of one-time keys
A WOTS+ key signs once. That’s not useful for a Bitcoin wallet that wants to sign more than one transaction. The fix is to generate many WOTS+ keys and arrange them so they share a single public identity. That’s what XMSS does.
XMSS (eXtended Merkle Signature Scheme, RFC 8391) builds a Merkle tree out of WOTS+ public keys. The tree’s leaves are individual WOTS+ public keys. Walk up the tree by hashing children together until you reach the root, which is the single 32-byte XMSS public key everyone refers to as your verification key.
To sign with XMSS, you pick an unused leaf and sign the message with the WOTS+ key at that leaf. The signature includes both the WOTS+ signature itself and an authentication path that proves the leaf is part of the tree.
A standard XMSS tree has 2^10 (1024) or 2^16 (65,536) leaves, meaning you can sign 1024 or 65,536 messages from one key before exhausting it. XMSS-MT (Multi-Tree) variants go higher, up to 2^60 or more, by stacking trees of trees.
The size argument is what makes XMSS interesting for Bitcoin. An XMSS signature is around 2-4 KB at standard parameters, compared to 8-49 KB for SLH-DSA (the stateless cousin in this family). Smaller signatures mean cheaper on-chain transactions and smaller block sizes, which is the kind of thing Bitcoin developers care about a lot.
To sign, you pick an unused leaf, sign with its WOTS+ key, and include an authentication path proving the leaf is part of the tree. Signatures are around 2–4 KB, which is what makes XMSS interesting for Bitcoin.
- Leaves
- individual WOTS+ public keys
- Root
- the single 32-byte XMSS public key
- Capacity
- 2^10 (1,024) or 2^16 (65,536) signs; XMSS-MT up to 2^60+
Why Bitcoin devs keep pointing at these
The cryptographic case for hash-based signatures is strong. Hash functions have been beaten on by cryptographers since the 1990s without any structural attacks emerging. SHA-256 specifically has been the target of sustained attack since 2001 and remains unbroken.
Why?
Because hash functions get attacked harder and longer than any other cryptographic primitive. SHA-256 has been attacked for 25 years without a practical break. That’s an unusual track record in cryptography.
That gives hash-based signatures a security argument that scales over long time horizons. A signature scheme provably reduced to SHA-256 will remain secure as long as SHA-256 does. The reduction is clean. An attack on the signature scheme would imply an attack on SHA-256 itself.
The size argument is also relevant. The Bitcoin block size limit makes signature size a hard constraint, and PQC schemes with multi-KB signatures have to fit somewhere. XMSS at 2-4 KB is a tighter fit than SLH-DSA at 8-49 KB.
BIP-360’s draft (P2MR for short, since “Pay-to-Merkle-Root” is the kind of name that requires an acronym to survive in conversation) is one of the Bitcoin proposals working through how to integrate a quantum-resistant signature scheme. The specific cryptographic primitives are still under discussion, and hash-based options like XMSS and SLH-DSA are part of the conversation alongside lattice-based alternatives.
Hash functions get attacked harder and longer than any other primitive, which gives hash-based signatures a security argument that scales over long time horizons. BIP-360 (P2MR) is weighing hash-based options like XMSS and SLH-DSA alongside lattice alternatives.
- Security
- provably reduces to SHA-256; break the scheme and you’ve broken SHA-256
- Track record
- SHA-256 attacked since 2001, still unbroken
- Size
- XMSS 2–4 KB beats SLH-DSA 8–49 KB for block space
The statefulness catch
Hash-based signatures with statefulness are clean in cryptography but messy in practice. XMSS requires you to remember which leaf you’ve used. If you sign with leaf #142 and then sign with leaf #142 again, you’ve broken the security of leaf #142’s WOTS+ key. An attacker can forge from there.
“You forgot which leaf you used” sounds like a problem you’d solve by writing it down (just keep a counter, what could go wrong). The reality is harder.
Consider what XMSS state management requires in a real wallet. Every signature operation has to atomically update the state. If the wallet crashes between signing and writing the new state, you’ve potentially signed twice with the same leaf without realizing it. Backups create the same risk. Restore from a backup taken before some signatures, and you’ve reset your state to a point where those leaves haven’t been used yet, even though the chain already has signatures from them.
Single-user wallets with careful state management can handle this. Multisig setups and hardware-wallet workflows that move keys between devices add operational complexity that hash-based schemes weren’t designed for.
This is why SLH-DSA exists. SLH-DSA is the stateless variant in the same family, built so you don’t have to track which leaf you used. The price of statelessness is signature size, which is 4-12x larger than XMSS at comparable security levels.
So Bitcoin proposals end up in a trade-off space. XMSS is smaller but stateful. SLH-DSA is bigger but stateless. Current Bitcoin discussion often favors SLH-DSA because it avoids state management. The final choice is still open.
Single-user wallets with careful state management can handle this. Multisig and hardware-wallet workflows that move keys between devices add operational complexity that hash-based schemes were not designed for. This is why SLH-DSA exists: the stateless variant, at the cost of 4–12x larger signatures.
- The rule
- never reuse a leaf; reuse #142 and its WOTS+ key is broken
- Crash risk
- a crash between signing and saving state can double-sign
- Backup risk
- restoring an old backup resets state to already-used leaves
| Scheme | State | Signature size | Trade-off |
|---|---|---|---|
| XMSS | stateful (track the leaf) | ~2-4 KB | smaller, but risky to manage |
| SLH-DSA | stateless | ~8-49 KB | bigger, but safe to integrate |
What wallets will probably do
If Bitcoin adopts a standardized hash-based signature scheme, current discussions point toward SLH-DSA at the protocol level (stateless, simpler to integrate). The state-tracking burden is large enough that mainstream wallet software is unlikely to default to a stateful scheme.
For users, you’re not going to interact with hash-based Bitcoin signatures this year. The protocol-level conversation is years away from a deployed change. The thing worth knowing is which family is winning the argument inside the developer community, because that determines what your wallet will look like in 2030 or 2035 when the migration actually happens.
The signal worth watching is which BIPs end up shipping with what underlying scheme. If BIP-360 or a similar proposal advances with SLH-DSA underneath, that’s the path. A stateful scheme making it in for niche use cases is a different path.
If Bitcoin adopts a hash-based scheme, current discussion points to SLH-DSA at the protocol level, because the state-tracking burden is too large for mainstream wallets to default to a stateful scheme. You won’t touch hash-based Bitcoin signatures this year; the change is years out. The signal to watch is which BIPs ship with which scheme underneath.
Yes, there’s a trade-off
Hash-based signatures fit some use cases well. XMSS-style stateful schemes have been deployed in production across certificate authorities, code-signing systems, IoT firmware updates, and various critical-infrastructure contexts where the state-management problem has been solved by careful engineering. The fit is harder for Bitcoin at the protocol level, mostly because of how statefulness interacts with consensus changes and wallet recovery.
The argument worth following is whether the size benefit of XMSS-style stateful schemes outweighs the operational pain. So far the discussion has favored stateless approaches, and SLH-DSA is the candidate moving forward. That can change. Statefulness is solvable in narrow contexts. But the boundary moves slowly, the way all standards arguments do.
XMSS is smaller but stateful. SLH-DSA is bigger but stateless. So far the discussion favors stateless, and SLH-DSA is the candidate moving forward.
This article is educational and does not constitute security or investment advice.
// FAQ
What does "one-time signature" mean?
A WOTS+ key can sign exactly one message. Signing a second message with it reveals enough of the private key for anyone to forge further signatures, even without a quantum computer, so each key is used once and retired.
How does XMSS let you sign more than once?
It bundles many WOTS+ one-time keys into a Merkle tree. The tree root is your single public key, and each signature uses a fresh leaf, so one XMSS key can sign 1,024 or 65,536 times, more with multi-tree variants.
Why does statefulness matter?
XMSS requires remembering which leaf you have used. A crash or an old backup can make you reuse a leaf, which breaks that key’s security. That operational risk is why Bitcoin discussion leans toward the stateless SLH-DSA.
Are hash-based signatures actually secure?
Yes. Their security reduces to the underlying hash function, and SHA-256 has been attacked since 2001 without a practical break. An attack on the signature would imply an attack on SHA-256 itself.
Which will Bitcoin use, XMSS or SLH-DSA?
Undecided, but current discussion favors SLH-DSA because it is stateless and simpler to integrate, despite larger signatures. XMSS’s smaller size keeps it in the conversation for niche uses.
// Sources
- XMSS, RFC 8391 https://datatracker.ietf.org/doc/html/rfc8391
- NIST, FIPS 205 (SLH-DSA) https://csrc.nist.gov/pubs/fips/205/final
- BIP-360 (draft), Pay-to-Merkle-Root https://github.com/bitcoin/bips/blob/master/bip-0360.mediawiki
- QNews, NIST's PQC Standards Explained https://qnews.io/guides/post-quantum-cryptography/nists-pqc-standards-ml-kem-ml-dsa-slh-dsa-falcon-hqc-explained/
- QNews, Post-Quantum Cryptography: The Quantum Computing Threat, in Plain English https://qnews.io/guides/post-quantum-cryptography/post-quantum-cryptography-a-plain-english-guide-for-crypto-holders/