WOTS+ and XMSS: The Hash-Based Schemes Bitcoin Proposals Lean On

Picture a signature scheme so paranoid about quantum computers that it makes you destroy each key right after you sign with it. One signature per key, ever. You sign with it once, then burn it. Sounds inconvenient because it absolutely is, and it’s also exactly the kind of architecture that comes out of cryptographers thinking really hard about what a hash function can do for them when they refuse to assume anything else.

Welcome to burn-after-signing.

Burn-after-signing is the operating model of WOTS+ (Winternitz One-Time Signature Plus), a hash-based signature scheme that’s been around since the early 2010s. WOTS+ does one thing well. It produces a signature that’s unforgeable as long as the underlying hash function (typically SHA-256 or SHAKE-256) remains secure. The cost is that each WOTS+ key can sign exactly one message. Use it twice and you’ve leaked enough of the private key for an attacker to forge new signatures, even without a quantum computer.

That’s the architectural quirk that pulls hash-based signatures into Bitcoin’s post-quantum conversation. The math is the most conservative thing in cryptography. The packaging, especially around statefulness and key management, is where the engineering gets interesting.

Burn-after-signing (WOTS+, 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.

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.

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.

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.

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.

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.