Winternitz chains and Merkle trees

From pairs to chains

Lamport signatures spend one 32-byte secret per message bit, so a signature is 8 KB. Ralph Merkle's 1979 work credits Robert Winternitz with a better idea: sign several bits at once by walking along a hash chain.

Pick a Winternitz parameter w, such as 16. Split the message digest into base-w digits. With w = 16 that's 4 bits per digit, so a 256-bit digest has 64 digits. For each digit, keep one chain:

x_0 = random secret
x_1 = H(x_0), x_2 = H(x_1), …, x_(w−1) = H^(w−1)(x_0)    # public end

• Public key: the chain ends Hw−1(x0) for every chain (usually hashed together into one value).
• Sign digit d: reveal Hd(x0), the value d steps along.
• Verify: hash the revealed value w − 1 − d more times and check that you land on the public end.

One chain now does the work of four Lamport pairs. The cost is computation: key generation hashes every chain all the way, and signing plus verifying together walk each chain once.

The checksum

There's a flaw. Anyone holding Hd(x0) can compute Hd+1(x0), Hd+2(x0) and so on. An attacker can therefore raise any digit of your signature for free. To block this, Winternitz schemes also sign a checksum:

C = Σ (w − 1 − d_i)    over all message digits

C is written in base w and signed with a few extra chains. Raising any message digit lowers C, and lowering a checksum digit means walking a chain backwards, which requires a hash preimage. Raise one, and you must lower the other: stalemate.

Click the attacker's "hash one chain forward" button with the checksum on: the forgery is blocked, because a checksum chain would have to move backwards. Untick the box and the same trick verifies. Then flip between w = 2 and w = 256 and watch the trade-off.

The trade-off in numbers

For SHA-256 (32-byte chain values), the number of chains is len1 = ⌈256 / log2w⌉ message chains plus len2 checksum chains:

Those chain counts match the LM-OTS parameter sets in RFC 8554 exactly: p = 265, 133, 67 and 34 for LMOTS_SHA256_N32_W1, W2, W4 and W8. Watch the naming: RFC 8554's "W4" means 4 bits per digit, which is base 16. XMSS (RFC 8391) writes the same thing as w = 16, with 67 chains. RFC 8554's full signature sizes (8,516 / 4,292 / 2,180 / 1,124 bytes) add a type field, a randomizer and the chain values.

Real schemes also refuse to use a bare H. LM-OTS computes each chain step as H(I ‖ q ‖ i ‖ j ‖ tmp): key identifier, leaf number, chain number and step number. WOTS+ in XMSS XORs in per-step bitmasks. Either way, every hash call in the system is unique, which defeats attacks that try to invert one of millions of hashes at once.

Merkle trees: many one-time keys, one public key

A Winternitz key still signs only once. Ralph Merkle's 1979 tree answers the obvious next question: how do you publish one short public key that covers thousands of one-time keys?

1. Generate 2^h one-time key pairs. Hash each one-time public key into a leaf.
2. Hash pairs of nodes together, parent = H(left ‖ right), level by level, up to a single root.
3. The root, 32 bytes, is the long-term public key.

To sign message number i, use one-time key i, and send the leaf index, the one-time signature and the authentication path: the h sibling hashes along the way from leaf i to the root. The verifier recomputes the one-time public key from the signature, hashes up the path, and compares with the root. For h = 10, that's 1,024 signatures from one key, with a path of 10 × 32 = 320 bytes.

Click different leaves: the orange siblings are what a signature carries. Tick "tamper" and a single flipped bit anywhere on the path produces the wrong root. Then use the counter controls: sign twice, take a backup, sign twice more, restore, and sign again. The tree is still mathematically perfect. You've just reused a one-time key.

LMS and XMSS

These two standards are Merkle trees of Winternitz keys, plus careful domain separation. LMS uses distinct prefixes such as D_LEAF and D_INTR for leaf and interior hashes. Both are specified in RFCs and approved by NIST SP 800-208:

• LMS (RFC 8554): tree heights 5, 10, 15, 20 or 25, so up to 2²⁵ signatures per tree. HSS stacks LMS trees into a multi-level hierarchy.
• XMSS (RFC 8391): heights 10, 16 and 20 in the main parameter sets, with w = 16. XMSS^MT is the multi-tree variant.

Multi-level trees matter in practice. Generating a single 2²⁵-leaf tree means computing every leaf up front. A top-level tree that signs the roots of lower trees lets you generate capacity as you need it.

State: the part that bites

A Merkle signer has one piece of mutable state: the index of the next unused leaf. NIST SP 800-208 is blunt about it. If an attacker gets two signatures from the same one-time key, forgery becomes "computationally feasible." Its requirements:

• Key generation and signing happen in hardware cryptographic modules validated to FIPS 140-2 or 140-3 Level 3 or higher, which must not export private keying material, "even in encrypted form."
• On every signing request, the module must increment the leaf index and store it in nonvolatile storage before releasing the signature.
• For capacity or redundancy across several modules, don't copy keys. Use separate keys, or a two-level HSS/XMSS^MT tree whose lower trees live on different modules.

The standard also lists the traps: an OS that caches a file write, so a crash loses the counter update; a signature released before the write reaches disk. Add the operational ones every engineer has met: VM snapshots, backup restores, cloned HSM partitions and active-active clusters that each think they own the counter. SP 800-208 notes that hardware monotonic counters "may be very helpful."

Stateless: SLH-DSA

SLH-DSA (FIPS 205, derived from SPHINCS+) removes the counter. It builds a hypertree: layers of XMSS-style trees with WOTS+ signatures, each layer signing the roots below it. At the bottom sits FORS (Forest of Random Subsets), a few-time signature scheme. The leaf used for each message is chosen pseudorandomly from the message itself. The tree is so large that accidental reuse is vanishingly unlikely, and FORS tolerates occasional reuse anyway.

No state means no counter to corrupt, at the cost of size and speed. SLH-DSA-SHA2-128s has a 32-byte public key and a 7,856-byte signature. The faster 128f variant has 17,088-byte signatures. For where each scheme fits in a real migration, see migrating certificates, code signing and firmware.

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

• RFC 8554: Leighton-Micali Hash-Based Signatures
• RFC 8391: XMSS: eXtended Merkle Signature Scheme
• NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes
• NIST FIPS 205: Stateless Hash-Based Digital Signature Standard
• Merkle, A Certified Digital Signature (1979 manuscript)

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet16 of 18

PartIII · Engineer

Rev.18 Oct 2026

Sources5 cited

Found an error?Send a correction