Chapter 15: Many-time signatures

Lamport’s signature is 8,192 bytes because it treats each of 256 digest bits independently: one secret revealed per bit, one hash check per bit. The Winternitz one-time signature (WOTS+) compresses this by encoding the digest in base $w$ instead of base 2 (Hülsing, 2013). At $w = 16$, the 256-bit digest becomes 64 hexadecimal digits. Each digit selects one of the 16 positions along a hash chain, and the signature is one chain value per digit: 67 values instead of 256, totaling 2,144 bytes. The compression costs computation (up to 15 hash evaluations per chain instead of 1), but the size reduction is roughly 4x.

The catch is that WOTS+ is still one-time. The Merkle tree from Chapter 14 fixes this: place $2^h$ WOTS+ public keys as leaves of a tree of height $h$, publish only the root, and sign with one leaf per message. XMSS (RFC 8391) is this construction, with a public key that carries a public seed and a parameter identifier alongside the root (Hülsing et al., 2018). The signer maintains a counter that increments after each signature. The counter is the scheme’s central operational burden: reusing a leaf degrades WOTS+ security, and exhausting all leaves disables the key entirely. NIST approved the stateful schemes LMS/HSS and XMSS/XMSSMT in SP 800-208 (Cooper et al., 2020). NIST later standardized the stateless SLH-DSA scheme separately in FIPS 205 (National Institute of Standards and Technology, 2024), which eliminates the counter at the cost of larger signatures.

WOTS+ at small parameters

The WOTS+ walkthrough below is pedagogical and does not reproduce FIPS 205 byte-for-byte. It uses $w = 4$, $n = 4$-byte truncated SHA-256, and a flat pk_seed || addr || step || value domain separator so the arithmetic fits on the page. FIPS 205 (Chapter 17) sets $w = 16$, $n \in \{16, 24, 32\}$ bytes, and replaces the flat separator with the full 32-byte ADRS machinery (National Institute of Standards and Technology, 2024). The pedagogical structure below reproduces the security argument; the byte-level wire format differs from the standard.

A WOTS+ key at $w = 4$ and $n = 4$ bytes (truncated SHA-256) is small enough to walk by hand. WOTS+ uses two independent seeds: a secret seed that derives the chain start values via a PRF, and a public seed that domain-separates the chain function. RFC 8391 keeps these separate, and so must any implementation: the verifier needs the public seed, so anything derivable from it must not include a secret value (Hülsing et al., 2018). The chain function $F$ hashes the concatenation of the public seed, a chain address, a step index, and the current value:

$$F(x, \text{seed}, \text{addr}, \text{step}) = H(\text{seed} \| \text{addr} \| \text{step} \| x)$$

where $\text{seed}$ is the public seed and $H$ is SHA-256 truncated to $n$ bytes. Each chain has $w - 1 = 3$ steps, so the secret sits at the bottom (position 0), the public key sits at the top (position 3), and a signature for digit $d$ reveals the value at position $d$.

import hashlib

def chain_f(x, start, steps, pk_seed, addr, n=4):
    """Iterate the chain function F for *steps* from position *start*."""
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()[:n]
    return value

sk_seed = b"ch15-tiny-sk"   # secret: derives the chain start value
pk_seed = b"ch15-tiny-pk"   # public: domain-separates the chain
sk_0 = hashlib.sha256(sk_seed + b"sk" + (0).to_bytes(4, "big")).digest()[:4]
print(sk_0.hex())
# ==> 2c85517f

pk_0 = chain_f(sk_0, 0, 3, pk_seed, 0)
print(pk_0.hex())
# ==> 33b2bbda

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch15/, one file per block. Appendix C covers the clone and the environment they run on.

The secret 2c85517f hashes through three steps to the public-key endpoint 33b2bbda. The sk_seed-prefixed SHA-256 here is a toy stand-in for a keyed derivation. In FIPS 205 the secret seed SK.seed derives the private chain values through a specified PRF, while the public seed PK.seed feeds the tweakable hash functions (National Institute of Standards and Technology, 2024). A signature for digit $d = 1$ reveals the value at position 1:

import hashlib

def chain_f(x, start, steps, pk_seed, addr, n=4):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()[:n]
    return value

sk_seed = b"ch15-tiny-sk"
pk_seed = b"ch15-tiny-pk"
sk_0 = hashlib.sha256(sk_seed + b"sk" + (0).to_bytes(4, "big")).digest()[:4]

sig_0 = chain_f(sk_0, 0, 1, pk_seed, 0)
print(sig_0.hex())
# ==> 33fb9d07

# The verifier hashes forward w - 1 - d = 3 - 1 = 2 steps.
recomputed = chain_f(sig_0, 1, 2, pk_seed, 0)
pk_0 = chain_f(sk_0, 0, 3, pk_seed, 0)
print(recomputed == pk_0)
# ==> True

The verifier does not need the secret. It takes the signature value, hashes forward the remaining $w - 1 - d$ steps, and checks whether it reaches the public-key endpoint. If the chain function is preimage-resistant, no one can produce the value at position $d$ without knowing the secret or a value at position $\leq d$.

The diagram below shows a single WOTS+ hash chain at $w = 16$. The secret key value sits at position 0 (bottom). Each arrow represents one application of the chain function $F$. The public key endpoint sits at position 15 (top). A signature for digit $d = 7$ reveals the chain value at position 7 (marked in teal). The verifier hashes forward 8 steps from position 7 to reach position 15 and compares against the public key.

Figure 15.1. A single WOTS+ hash chain at $w = 16$. The secret value sits at position 0. Each step applies the chain function $F$. A signature for digit $d = 7$ reveals the chain value at position 7 (teal). The verifier hashes forward 8 steps to recover the public-key endpoint at position 15.

The chain has $w = 16$ positions. A signature for digit $d$ reveals position $d$. The verifier hashes forward $w - 1 - d = 15 - d$ steps and compares. Lower digit values reveal positions closer to the secret; higher values reveal positions closer to the public key. The checksum ensures that no adversary can shift all digits toward the public-key end of their chains without simultaneously shifting a checksum digit toward the secret-key end.

Base-w encoding, checksums, and the chain function

Base-w encoding

A WOTS+ signature encodes a message digest as a sequence of base-$w$ digits. For a hash output of $n$ bytes, the number of message digits is:

$$\ell_1 = \left\lceil \frac{8n}{\log_2 w} \right\rceil$$

Each digit takes values in $\{0, 1, \ldots, w - 1\}$. For $w = 16$ and $n = 32$: $\ell_1 = \lceil 256 / 4 \rceil = 64$. Each byte of the digest yields two hexadecimal digits, extracted MSB-first.

import hashlib, math

def base_w(data, w, out_len):
    """Encode *data* as *out_len* base-*w* digits (MSB-first per byte)."""
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

digest = hashlib.sha256(b"XMSS test message").digest()
msg_digits = base_w(digest, 16, 64)
print(msg_digits[:8])
# ==> [12, 1, 11, 7, 15, 0, 13, 3]
print(len(msg_digits))
# ==> 64

The first byte of the digest is 0xC1 (binary 11000001), which in base 16 is [12, 1]. The encoding is deterministic and reversible.

The checksum

Without a checksum, an adversary who sees a signature can forge signatures on messages whose digits are component-wise larger. If the original digit at position $i$ is $d_i = 7$, the adversary holds the chain value at position 7. Hashing forward one step gives position 8, which is a valid signature for a message with digit 8 at that position. The adversary can only hash forward (increasing the digit), never backward (decreasing it).

The checksum closes this gap. Define:

$$C = \sum_{i=0}^{\ell_1 - 1} (w - 1 - d_i)$$

This sum is always non-negative. For $w = 16$ and $\ell_1 = 64$, the maximum is $64 \times 15 = 960$. Encode $C$ in base $w$ as $\ell_2$ additional digits, where:

$$\ell_2 = \left\lceil \frac{\lfloor \log_2(\ell_1 \cdot (w-1)) \rfloor + 1}{\log_2 w} \right\rceil$$

For $w = 16$, $\ell_1 = 64$: $\lfloor \log_2 960 \rfloor + 1 = 10$, so $\ell_2 = \lceil 10/4 \rceil = 3$. The total number of chains is $\ell = \ell_1 + \ell_2 = 67$.

The checksum prevents forgery by digit increase: if the adversary increases any message digit $d_i$ by $\delta$, the checksum $C$ decreases by $\delta$. To forge the checksum chains, the adversary would need to hash backward on at least one checksum chain (a smaller $C$ has at least one smaller base-$w$ digit), which requires inverting the hash function.

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

w = 16
ell_1 = 64
digest = hashlib.sha256(b"XMSS test message").digest()
msg_digits = base_w(digest, w, ell_1)

c = sum(w - 1 - d for d in msg_digits)
print(c)
# ==> 481

# Left-shift c so the ell_2 digits fill the MSB of the byte encoding,
# matching RFC 8391 Section 3.1.5, Algorithm 5.
ell_2 = 3
lg_w = 4
total_bits = ell_2 * lg_w  # 12 bits
num_bytes = 2              # ceil(12 / 8)
shift = 8 * num_bytes - total_bits  # 4
c_shifted = c << shift
c_bytes = c_shifted.to_bytes(num_bytes, "big")
csum_digits = base_w(c_bytes, w, ell_2)
print(csum_digits)
# ==> [1, 14, 1]

Without the left-shift, the low 4 bits of the 12-bit checksum would fall off the end of the 16-bit byte array. The base_w routine reads 3 base-16 digits from the most significant byte, so checksums need to occupy the high 12 bits, not the low 12. The shift places the significant digits at the most significant positions of the byte representation.

The full digit string has 67 entries: 64 message digits followed by 3 checksum digits. Each digit indexes a chain position in one of 67 hash chains.

The chain function

WOTS+ uses a randomized chain function rather than bare hash iteration (Hülsing, 2013). Each step incorporates a public seed (shared across the key, and safe to publish) and an address (unique per chain and step):

$$F(x) = H(\text{seed} \| \text{addr} \| \text{step} \| x)$$

The public seed provides key-level domain separation. The address and step index ensure that no two hash calls within a key share the same input domain.

Where this chain function departs from RFC 8391

RFC 8391 uses a 32-byte ADRS structure with fields for tree layer, tree index, OTS address, chain address, and hash address, and the chain function XORs the input with a pseudorandom bitmask before hashing (Hülsing et al., 2018). The implementation in this chapter simplifies both the address (two 4-byte integers instead of a 32-byte ADRS) and the chain construction (concatenation instead of XOR-bitmask). The essential property is preserved: distinct inputs to $H$ at every call. The formal security reduction in Hülsing (Hülsing, 2013) is stated for a keyed function family used with the paper’s own bitmask chaining, and its Theorem 1 asks that family for three properties: one-wayness, second-preimage resistance and undetectability. It does not rest on preimage resistance of the bare hash alone.

Parameter summary

• $w = 16$, $n = 32$ bytes (SHA-256)
• $\ell_1 = 64$ message chains
• $\ell_2 = 3$ checksum chains
• $\ell = 67$ total chains
• WOTS+ signature size: $67 \times 32 = 2{,}144$ bytes
• WOTS+ public key (raw): $67 \times 32 = 2{,}144$ bytes
• XMSS leaf after L-tree compression: 32 bytes
• XMSS public key core material (root + public seed): $2 \times 32 = 64$ bytes

Building WOTS+ and XMSS

WOTS+ keygen, sign, and verify at standard dimensions

Key generation derives $\ell = 67$ secret values from a secret seed via a PRF, then chains each one forward $w - 1 = 15$ steps to its public-key endpoint using the public seed. The dimensions ($w = 16$, $n = 32$, $\ell = 67$) match RFC 8391; the chain function is still the simplified flat-separator form from above, not the RFC 8391 ADRS-and-bitmask construction:

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

sk_seed = b"ch15-full-sk"   # secret: derives the WOTS+ secret values
pk_seed = b"ch15-full-pk"   # public: domain-separates the chain
w, n = 16, 32
lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(max_c)) + 1) / lg_w)
ell = ell_1 + ell_2

sk = [hashlib.sha256(sk_seed + b"sk" + i.to_bytes(4, "big")).digest() for i in range(ell)]
pk = [chain_f(sk[i], 0, w - 1, pk_seed, i) for i in range(ell)]
print(ell)
# ==> 67
print(sk[0].hex()[:16])
# ==> 52c38cfc379ebaaf
print(pk[0].hex()[:16])
# ==> c4608f81e170d3b7

Signing hashes the message, encodes the digest in base 16, computes the checksum, and chains each secret forward by the corresponding digit value:

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

sk_seed = b"ch15-full-sk"
pk_seed = b"ch15-full-pk"
w, n = 16, 32
lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(max_c)) + 1) / lg_w)
ell = ell_1 + ell_2

sk = [hashlib.sha256(sk_seed + b"sk" + i.to_bytes(4, "big")).digest() for i in range(ell)]
pk = [chain_f(sk[i], 0, w - 1, pk_seed, i) for i in range(ell)]

message = b"XMSS test message"
digest = hashlib.sha256(message).digest()
msg_digits = base_w(digest, w, ell_1)
c = sum(w - 1 - d for d in msg_digits)
c_shifted = c << (8 * 2 - ell_2 * lg_w)
c_bytes = c_shifted.to_bytes(2, "big")
csum_digits = base_w(c_bytes, w, ell_2)
all_digits = msg_digits + csum_digits

sig = [chain_f(sk[i], 0, all_digits[i], pk_seed, i) for i in range(ell)]
print(sig[0].hex()[:16])
# ==> fcf28dd604c58b8f

Verification recomputes the digits, chains each signature value forward the remaining steps, and compares against the public key:

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

sk_seed = b"ch15-full-sk"
pk_seed = b"ch15-full-pk"
w, n = 16, 32
lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(max_c)) + 1) / lg_w)
ell = ell_1 + ell_2

sk = [hashlib.sha256(sk_seed + b"sk" + i.to_bytes(4, "big")).digest() for i in range(ell)]
pk = [chain_f(sk[i], 0, w - 1, pk_seed, i) for i in range(ell)]

message = b"XMSS test message"
digest = hashlib.sha256(message).digest()
msg_digits = base_w(digest, w, ell_1)
c = sum(w - 1 - d for d in msg_digits)
c_shifted = c << (8 * 2 - ell_2 * lg_w)
c_bytes = c_shifted.to_bytes(2, "big")
csum_digits = base_w(c_bytes, w, ell_2)
all_digits = msg_digits + csum_digits

sig = [chain_f(sk[i], 0, all_digits[i], pk_seed, i) for i in range(ell)]

ok = all(
    chain_f(sig[i], all_digits[i], w - 1 - all_digits[i], pk_seed, i) == pk[i]
    for i in range(ell)
)
print(ok)
# ==> True

The signature is 67 chain values of 32 bytes each: 2,144 bytes total. Lamport at $n = 256$ produces 256 revealed secrets of 32 bytes: 8,192 bytes. The roughly 4x compression ($8{,}192 / 2{,}144 \approx 3.8$) comes from treating the digest in base 16 instead of base 2, with a minor overhead for the 3 checksum chains.

The checksum-bypass forgery

Without the checksum, an adversary who sees a valid signature can forge signatures on messages with larger digit values at any position. The attack works because hashing forward along a chain is easy, but hashing backward requires inverting $H$.

Suppose the original message has digit $d_0 = 7$ at position 0. The adversary holds the chain value at position 7. Hashing forward one step produces the value at position 8:

import hashlib, math

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

sk_seed = b"ch15-forgery-sk"
pk_seed = b"ch15-forgery-pk"
w = 16
sk_0 = hashlib.sha256(sk_seed + b"sk" + (0).to_bytes(4, "big")).digest()

# Legitimate signature value at position d=7.
sig_at_7 = chain_f(sk_0, 0, 7, pk_seed, 0)

# Adversary hashes forward one step to get position 8.
forged_at_8 = chain_f(sig_at_7, 7, 1, pk_seed, 0)

# This matches what signing with digit 8 would produce.
expected_at_8 = chain_f(sk_0, 0, 8, pk_seed, 0)
print(forged_at_8 == expected_at_8)
# ==> True

The forged value verifies correctly at position 8 because the chain is deterministic. Without a checksum, the adversary can increase any digit at any position by hashing forward.

With the checksum, this attack fails. Increasing a message digit by 1 decreases the checksum by 1. To forge the checksum chains, the adversary would need to hash backward by 1 step, which requires computing $F^{-1}$:

import hashlib

w = 16
msg_digits = [7, 3, 15, 0, 10, 5, 12, 8]
c_original = sum(w - 1 - d for d in msg_digits)
print(c_original)
# ==> 60

# Increase digit 0 from 7 to 8.
modified = list(msg_digits)
modified[0] = 8
c_modified = sum(w - 1 - d for d in modified)
print(c_modified)
# ==> 59

print(c_original - c_modified)
# ==> 1

The checksum dropped from 60 to 59. The checksum digit encoding changed, and at least one checksum chain position decreased. The adversary holds a chain value at the original checksum position and needs the value at a lower position, which is a preimage of the value it holds. The checksum transforms a “hash forward” attack (easy) into a “hash backward” attack (hard).

L-tree compression

A WOTS+ public key has $\ell = 67$ chain endpoints, each 32 bytes: 2,144 bytes total. XMSS does not hash these by simple concatenation. Instead, it uses an L-tree: a binary hash tree over the $\ell$ endpoints that compresses them into a single 32-byte leaf (Hülsing et al., 2018).

The L-tree handles non-power-of-2 counts by promoting the last node at each level when the count is odd. For $\ell = 67$:

Level	Nodes in	Pairs hashed	Promoted	Nodes out
0	67	33	1	34
1	34	17	0	17
2	17	8	1	9
3	9	4	1	5
4	5	2	1	3
5	3	1	1	2
6	2	1	0	1

The pairs column sums to 66, so compressing one WOTS+ public key at $\ell = 67$ costs 66 hash evaluations.

import hashlib

def ltree(pk_values, seed):
    """Compress a list of values into a single hash via an L-tree."""
    nodes = list(pk_values)
    level = 0
    while len(nodes) > 1:
        next_level = []
        i = 0
        pair_index = 0
        while i + 1 < len(nodes):
            combined = hashlib.sha256(
                seed
                + level.to_bytes(4, "big")
                + pair_index.to_bytes(4, "big")
                + nodes[i]
                + nodes[i + 1]
            ).digest()
            next_level.append(combined)
            i += 2
            pair_index += 1
        if i < len(nodes):
            next_level.append(nodes[i])
        nodes = next_level
        level += 1
    return nodes[0]

seed = b"ch15-ltree"
values = [hashlib.sha256(f"pk-{i}".encode()).digest() for i in range(67)]
root = ltree(values, seed)
print(root.hex()[:16])
# ==> 6df796321be29a7e

The L-tree compresses 2,144 bytes of WOTS+ public key into a single 32-byte hash. This compressed hash becomes the leaf of the XMSS Merkle tree. SLH-DSA (Chapter 17) does not reuse this L-tree. FIPS 205 compresses the WOTS+ chain endpoints with a single tweakable-hash call and builds every tree over a power-of-two number of leaves, so odd-node promotion is specific to RFC 8391 XMSS (National Institute of Standards and Technology, 2024).

XMSS: WOTS+ in a Merkle tree

XMSS places $2^h$ WOTS+ public keys as leaves of a Merkle tree of height $h$ and publishes the root and the public seed, together with the parameter identifier: RFC 8391 §4.1.7 gives the public key as OID || root || SEED (Hülsing et al., 2018). RFC 8391 uses $h$ for the height of a single XMSS tree. FIPS 205 instead uses $h$ for the total SLH-DSA hypertree height, the sum of its per-layer XMSS subtree heights. This chapter keeps the RFC 8391 convention because it builds a single XMSS tree. The construction is the same as the Merkle signature scheme from Chapter 14, with two changes: WOTS+ replaces Lamport as the leaf OTS, and L-tree compression replaces direct public-key hashing.

The diagram below shows an XMSS tree at $h = 3$ (8 leaves). Each leaf is the L-tree compression of a WOTS+ public key. Leaf $L_2$ (the most recently consumed leaf) is expanded to show the L-tree and the WOTS+ chain endpoints feeding into it. The state counter currently points to leaf 3 (the next leaf to be used).

Figure 15.2. XMSS tree at height 3, leaf L2 expanded. Each leaf is the L-tree root of 67 WOTS+ chain endpoints. State counter next = 3; leaves L0, L1, and L2 are consumed (L2 is the most recently used leaf, shown expanded in teal); L3 is next.

Each leaf in the XMSS tree is the L-tree root of 67 WOTS+ public-key chain endpoints. The state counter (next = 3) indicates that leaves 0, 1, and 2 have been consumed. The next signature will use leaf 3. After leaf 7 is consumed, the key is exhausted.

An XMSS signature at leaf index $j$ consists of four components (Hülsing et al., 2018):

• The leaf index $j$ (4 bytes)
• A randomness value $r$ ($n$ bytes) used for randomized message hashing, which defends against multi-target attacks
• The WOTS+ signature (67 chain values, 2,144 bytes)
• The Merkle authentication path ($h$ sibling hashes, $32h$ bytes)

The WOTS+ public key is not part of the signature. The verifier recomputes it: for each digit $d_i$, the verifier chains the signature value forward $w - 1 - d_i$ steps to recover the public-key endpoint. It then L-tree-compresses the recovered endpoints to get the leaf hash and verifies the authentication path from the leaf to the published root.

The pedagogical code below passes the public key directly for clarity. In a production XMSS implementation, the verifier reconstructs the WOTS+ public key from the signature, the message digest, the leaf index, and the public seed, L-tree-compresses it, and checks the authentication path against the published XMSS root.

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

def ltree(pk_values, pk_seed):
    nodes = list(pk_values)
    level = 0
    while len(nodes) > 1:
        next_level = []
        i = 0
        pair_index = 0
        while i + 1 < len(nodes):
            combined = hashlib.sha256(
                pk_seed + level.to_bytes(4, "big") + pair_index.to_bytes(4, "big")
                + nodes[i] + nodes[i + 1]
            ).digest()
            next_level.append(combined)
            i += 2
            pair_index += 1
        if i < len(nodes):
            next_level.append(nodes[i])
        nodes = next_level
        level += 1
    return nodes[0]

sk_seed = b"ch15-xmss-sk"
pk_seed = b"ch15-xmss-pk"
w, n, h = 16, 32, 3
lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(max_c)) + 1) / lg_w)
ell = ell_1 + ell_2
num_leaves = 1 << h

# Generate all WOTS+ keypairs and build the Merkle tree.
all_sk, all_pk, leaves = [], [], []
for li in range(num_leaves):
    sk_leaf = sk_seed + b"leaf" + li.to_bytes(4, "big")
    pk_leaf = pk_seed + b"leaf" + li.to_bytes(4, "big")
    sk_i = [hashlib.sha256(sk_leaf + b"sk" + j.to_bytes(4, "big")).digest() for j in range(ell)]
    pk_i = [chain_f(sk_i[j], 0, w - 1, pk_leaf, j) for j in range(ell)]
    all_sk.append(sk_i)
    all_pk.append(pk_i)
    leaves.append(ltree(pk_i, pk_leaf))

tree = [b""] * (2 * num_leaves)
for i in range(num_leaves):
    tree[num_leaves + i] = leaves[i]
for i in range(num_leaves - 1, 0, -1):
    tree[i] = hashlib.sha256(tree[2 * i] + tree[2 * i + 1]).digest()

root = tree[1]
print(root.hex()[:16])
# ==> 95751d240dbaaed6

Signing consumes leaf 0. The state counter advances to 1:

import hashlib, math

def base_w(data, w, out_len):
    lg_w = int(math.log2(w))
    digits = []
    for byte in data:
        for shift in range(8 - lg_w, -1, -lg_w):
            digits.append((byte >> shift) & (w - 1))
            if len(digits) == out_len:
                return digits
    return digits[:out_len]

def chain_f(x, start, steps, pk_seed, addr):
    value = x
    for i in range(start, start + steps):
        value = hashlib.sha256(
            pk_seed + addr.to_bytes(4, "big") + i.to_bytes(4, "big") + value
        ).digest()
    return value

def ltree(pk_values, pk_seed):
    nodes = list(pk_values)
    level = 0
    while len(nodes) > 1:
        next_level = []
        i = 0
        pair_index = 0
        while i + 1 < len(nodes):
            combined = hashlib.sha256(
                pk_seed + level.to_bytes(4, "big") + pair_index.to_bytes(4, "big")
                + nodes[i] + nodes[i + 1]
            ).digest()
            next_level.append(combined)
            i += 2
            pair_index += 1
        if i < len(nodes):
            next_level.append(nodes[i])
        nodes = next_level
        level += 1
    return nodes[0]

sk_seed = b"ch15-xmss-sk"
pk_seed = b"ch15-xmss-pk"
w, n, h = 16, 32, 3
lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n / lg_w)
max_c = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(max_c)) + 1) / lg_w)
ell = ell_1 + ell_2
num_leaves = 1 << h

all_sk, all_pk, leaves = [], [], []
for li in range(num_leaves):
    sk_leaf = sk_seed + b"leaf" + li.to_bytes(4, "big")
    pk_leaf = pk_seed + b"leaf" + li.to_bytes(4, "big")
    sk_i = [hashlib.sha256(sk_leaf + b"sk" + j.to_bytes(4, "big")).digest() for j in range(ell)]
    pk_i = [chain_f(sk_i[j], 0, w - 1, pk_leaf, j) for j in range(ell)]
    all_sk.append(sk_i)
    all_pk.append(pk_i)
    leaves.append(ltree(pk_i, pk_leaf))

tree = [b""] * (2 * num_leaves)
for i in range(num_leaves):
    tree[num_leaves + i] = leaves[i]
for i in range(num_leaves - 1, 0, -1):
    tree[i] = hashlib.sha256(tree[2 * i] + tree[2 * i + 1]).digest()

root = tree[1]

# Sign with leaf 0. Signing needs only the public seed for the chain;
# the secret values are already in all_sk.
state = {"next_leaf": 0}
leaf_idx = state["next_leaf"]
pk_leaf = pk_seed + b"leaf" + leaf_idx.to_bytes(4, "big")

message = b"first XMSS message"
digest = hashlib.sha256(message).digest()
msg_digits = base_w(digest, w, ell_1)
c = sum(w - 1 - di for di in msg_digits)
c_shifted = c << (8 * 2 - ell_2 * lg_w)
csum_digits = base_w(c_shifted.to_bytes(2, "big"), w, ell_2)
all_digits = msg_digits + csum_digits

wots_sig = [chain_f(all_sk[leaf_idx][j], 0, all_digits[j], pk_leaf, j) for j in range(ell)]

# Authentication path for leaf 0.
node = num_leaves + leaf_idx
path = []
for _ in range(h):
    path.append(tree[node ^ 1])
    node //= 2

state["next_leaf"] = leaf_idx + 1
print(state["next_leaf"])
# ==> 1

# Verify: WOTS+ check, then Merkle path check.
ok_wots = all(
    chain_f(wots_sig[j], all_digits[j], w - 1 - all_digits[j], pk_leaf, j)
    == all_pk[leaf_idx][j]
    for j in range(ell)
)
leaf_hash = ltree(all_pk[leaf_idx], pk_leaf)
current = leaf_hash
idx = leaf_idx
for sibling in path:
    if idx % 2 == 0:
        current = hashlib.sha256(current + sibling).digest()
    else:
        current = hashlib.sha256(sibling + current).digest()
    idx //= 2

print(ok_wots and current == root)
# ==> True

State management and leaf exhaustion

A height-$h$ XMSS tree supports exactly $2^h$ signatures. After the last leaf is consumed, the key is exhausted. At $h = 10$, the limit is 1,024 signatures. At $h = 20$, the limit is 1,048,576.

The signer must never reuse a leaf index. NIST SP 800-208 requires implementations to maintain the state counter in non-volatile storage and update it before releasing the signature, not after (Cooper et al., 2020). SP 800-208 also requires key generation and signing to run inside a hardware module that does not export private keying material, which blocks the clone-and-replay path entirely (Cooper et al., 2020). If the signer crashes between signing and updating the counter, the safe behavior is to skip that leaf (waste one slot) rather than risk reuse.

The state counter creates a backup hazard. Exercise 4 in Chapter 6 asked why a stateful signature scheme cannot be safely backed up across two machines. The answer: a backup freezes the counter. If the original signs message $A$ using leaf 4 (advancing the counter to 5) and the backup, restored from an earlier snapshot, signs message $B$ using leaf 4 again, both signatures are valid individually. But the WOTS+ key at leaf 4 has now been used twice, and an adversary who sees both signatures gains partial knowledge of the secret chains. The adversary can hash forward from the lower of the two revealed positions at each chain, reconstructing chain values that were never intended to be public.

XMSS signature sizes at $w = 16$, $n = 32$ (leaf index + randomness $r$ + WOTS+ signature + authentication path):

• $h = 10$ (1,024 signatures): $4 + 32 + 2{,}144 + 320 = 2{,}500$ bytes
• $h = 20$ (1,048,576 signatures): $4 + 32 + 2{,}144 + 640 = 2{,}820$ bytes

The WOTS+ signature dominates. The authentication path adds only $32h$ bytes. The Merkle root is 32 bytes for $n = 32$ regardless of $h$. The RFC 8391 XMSS public key carries both the root and the public seed, so its core material is 64 bytes before any algorithm identifier or container encoding (Hülsing et al., 2018). Both totals come from RFC 8391 Section 4.1.8, which gives an XMSS signature as $4 + n + (\ell + h)n$ bytes, evaluated at the Table 2 parameters for XMSS-SHA2_10_256 and XMSS-SHA2_20_256 (Hülsing et al., 2018, sec. 5.3). Those parameter sets fix $n = 32$, $w = 16$ and $\ell = 67$. Table 2 carries the parameters; the sizes are tabulated separately, in Table 3 of the parameter guide, which gives the same $2{,}500$ and $2{,}820$ bytes (Hülsing et al., 2018, sec. 5.3.1).

FIPS 205 standardizes a stateless hash-based alternative, SLH-DSA, which removes the mutable counter and the whole operational burden that comes with it (National Institute of Standards and Technology, 2024). SLH-DSA replaces the flat Merkle tree with a hypertree of WOTS+ trees and uses FORS (a few-time signature scheme) at the leaves, eliminating the counter entirely. Chapter 16 builds FORS and the hypertree. Chapter 17 assembles them into SLH-DSA.

A blockchain seed may live on multiple devices, and a chain hosts many independent signers who never coordinate counters. SP 800-208 treats state management as part of the security boundary: an approved module must prevent OTS-key reuse, store the incremented leaf index in non-volatile storage before releasing a signature, and never export private keying material (Cooper et al., 2020). SP 800-208 Section 7 gives two ways to spread signing across modules, and handing pre-generated one-time keys to each module is not one of them: the export prohibition rules it out. One option is a separate independent key per module, with verifiers accepting a signature under any of them. The other splits a single two-level HSS or XMSSMT key, so the top tree signs the roots of bottom trees held on separate modules (Cooper et al., 2020). Neither is a shared counter. Against a stateful scheme, the stateless SLH-DSA construction is the more natural target for blockchain transaction signing. Chapter 38 walks the wallet-rotation cadence and rates the primitives against custody shapes.

Cryptanalysis and known attacks

Checksum-bypass forgery

The checksum is the only defense against forgery by digit increase. Without it, a revealed WOTS+ signature value can always be shifted forward along its chain. A complete message forgery then succeeds for any target digest whose base-$w$ digits are component-wise $\geq$ the signed digest’s digits. The probability that a random target satisfies this across all $\ell_1 = 64$ positions is negligible, but a chosen-message adversary can search for such targets. The checksum removes this monotone forgery class by forcing at least one checksum digit to move backward, which requires inverting the chain function.

With the checksum, the adversary has two ways to forge. One is inverting the chain function: producing a chain value at a lower position from a value at a higher position, which informally requires computing $F^{-1}$ and reduces to preimage search on the hash function. The other is a second preimage: a forged value at the lower position whose chain merges into the legitimate chain at some later step, so that verification reaches the public key without the forger ever inverting anything. The formal security reduction in Hülsing (Hülsing, 2013) covers both. Its Theorem 1 bounds the forgery probability by separate one-wayness, second-preimage-resistance and undetectability terms for the keyed function family used with its bitmask chaining, so the proof rests on more than preimage resistance of the bare hash. For SHA-256, the classical preimage cost is $O(2^{256})$ and the quantum cost under Grover search is $O(2^{128})$ ideal serial hash queries (Grover, 1996).

Leaf reuse

Two WOTS+ signatures on different messages under the same key leak intermediate chain values. If message $A$ has digit 7 at position $i$ and message $B$ has digit 11 at position $i$, the adversary holds the chain value at position 7 (from signature $A$) and can hash forward to positions 8 through 15. From signature $B$, the adversary holds position 11 and can reach positions 12 through 15. Combined, the adversary knows chain values at every position from 7 to 15 and can forge any message whose digit at position $i$ is $\geq 7$.

The checksum still applies: forging a complete signature requires matching both message and checksum digits, and increasing any message digit forces a checksum digit to decrease. But the leakage narrows the remaining secret at each chain. After $k$ signatures on distinct messages, the adversary learns the minimum digit ever signed at each position, and the set of forgeable messages grows. This is analogous to the Lamport two-signature forgery in Chapter 14, where each additional signature exposes more secret halves.

NIST SP 800-208 §8.1 prohibits leaf reuse outright: a conforming cryptographic module shall not use a one-time key more than once, and it shall store the incremented leaf index in nonvolatile storage before the signature leaves the module (Cooper et al., 2020).

Multi-target preimage

A standalone WOTS+ public key exposes $\ell = 67$ chain endpoints. In XMSS the WOTS+ public key is not a standing long-term key. The verifier reconstructs it from a signature, so the endpoints for a leaf become visible only once that leaf is used. If those endpoints were outputs of one untweaked hash function, a multi-target preimage attack, which seeks a preimage of any one of them, would gain $\log_2 67 \approx 6$ bits classically, taking single-target preimage security from $2^{256}$ to about $2^{250}$, and about half that in the exponent under Grover ($2^{128}$ to about $2^{125}$), because the Grover speedup is square-root. The chain function above binds every call to a chain address and a step, so the toy does not pay this. It is the hypothetical Chapters 16 and 18 price to show what the binding is worth.

SLH-DSA’s multi-target analysis is more subtle than standalone WOTS+ because randomized message hashing, FORS, the hypertree, and the parameter choices all interact. This chapter only gives the WOTS+/XMSS intuition; Chapter 18 treats the full target-counting model.

Tradeoffs inside Part III

The Winternitz parameter $w$ controls a tradeoff between signature size and computation cost. Larger $w$ means fewer chains (shorter signatures) but longer chains (more hashing per sign and verify):

$w$	$\ell_1$	$\ell_2$	$\ell$	Signature	Chain ops
4	128	5	133	4,256 bytes	199
16	64	3	67	2,144 bytes	499
256	32	2	34	1,088 bytes	4,223

Signature size is $\ell \times 32$ bytes at $n = 32$. The chain-operation column is the expected number of chain steps a signature costs over uniformly random digests. The $\ell_1$ message digits are uniform, and a uniform digit sits halfway along its chain, so they contribute $\ell_1 (w - 1)/2$: $192$, $480$, and $4{,}080$. The $\ell_2$ checksum digits are not uniform. They are the base-$w$ digits of the checksum $C = \ell_1 (w - 1) - S$, where $S$ is the sum of the message digits. Algorithm 5 of RFC 8391 defines that encoding for $w = 4$ and $w = 16$, the two values the RFC allows, and the $w = 256$ row encodes $C$ the same way. Their expected digit sum, taken exactly over the distribution of $S$, is $6.98$, $19.08$, and $142.94$. The shortcut that treats every digit as uniform, $\ell (w - 1)/2$, gives $200$, $503$, and $4{,}335$ instead, at most 3 percent high. Each halving of the signature costs more than the last. Moving from $w = 4$ to $w = 16$ roughly halves the signature for 2.5 times the hashing; $w = 16$ to $w = 256$ halves it again for 8.5 times.

RFC 8391 specifies parameter sets only for $w = 16$, and Table 9 of NIST SP 800-208 fixes $w = 16$ in every approved WOTS+ parameter set (Cooper et al., 2020; Hülsing et al., 2018). RFC 8391 §6 does permit $w = 4$ generically, so the constraint is the specified and approved sets rather than conformance in the abstract. The tradeoff above is a design intuition, not a selectable parameter within those sets.

Across the Part III progression:

• Lamport + Merkle (Chapter 14): 8,192-byte Lamport one-time signature (256 revealed values). The complete Merkle signature Chapter 14 verifies also carries the 16,384-byte Lamport public key and the authentication path, 25,216 bytes at $d = 20$. Stateful. Simplest construction, largest signatures.
• WOTS+ + XMSS (this chapter): WOTS+ signature is 2,144 bytes (67 chain values); full XMSS signature is 2,500 bytes at $h = 10$ (including leaf index, randomness $r$, and authentication path). Still stateful. Roughly 4x compression over Lamport at the cost of chain computation.
• SLH-DSA (Chapters 16 and 17): stateless. Replaces the flat Merkle tree with a hypertree and FORS. Signatures range from 7,856 bytes (SLH-DSA-128s) to 49,856 bytes (SLH-DSA-256f) depending on the parameter set (National Institute of Standards and Technology, 2024). The security argument reduces entirely to hash function properties.

Exercises

1. WOTS+ parameters at $n = 24$. Compute $\ell_1$, $\ell_2$, and $\ell$ for $w = 16$ and $n = 24$ bytes (the SLH-DSA Category 3 hash size). State the signature size in bytes. Compare with the $w = 16$, $n = 32$ set used in this chapter, and explain what drives the size difference.

2. Checksum forgery attempt. A WOTS+ signature at $w = 16$ has digit value 9 at position 3. The adversary wants to forge a signature where position 3 has digit value 11. Explain the two steps the adversary can perform on the message chain at position 3. Then explain what happens to the checksum and why the adversary cannot complete the forgery.

3. L-tree for 5 values. Draw the L-tree level progression for 5 input values. At each level, mark which nodes are paired and which node (if any) is promoted. Count the total number of hash evaluations.

4. XMSS leaf budget. An XMSS key at $h = 20$ supports $2^{20}$ signatures. If the signer averages 100 signatures per day, how many days until the key is exhausted? Suppose the signer’s HSM is backed up weekly and a backup is restored after a crash. Explain what can go wrong and how SP 800-208 mitigates it.

5. Signature size comparison. Compute the full XMSS signature size (leaf index + randomness $r$ + WOTS+ signature + authentication path) at $w = 16$, $n = 32$, and $h = 20$. Compare with a Lamport + Merkle signature at the same depth (Chapter 14’s $d = 20$).

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 15. A separate track, for rebuilding rather than reading. The package exercises/ch15-xmss arrives with most of what the chapter prints already implemented, and stubs five functions for you to write, the checksum among them, because its reference version generalises what the page hardcodes. Run PQC_IMPL=exercises pytest tests/ch15 to grade your version against the suite that proves the reference one.

References

Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., & Miller, C. (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208. https://doi.org/10.6028/nist.sp.800-208

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. https://doi.org/10.1145/237814.237866

Hülsing, A. (2013). W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes. Progress in Cryptology – AFRICACRYPT 2013, 7918, 173–188. https://doi.org/10.1007/978-3-642-38553-7_10

Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., & Mohaisen, A. (2018). XMSS: eXtended Merkle Signature Scheme. IETF RFC 8391. https://doi.org/10.17487/rfc8391

National Institute of Standards and Technology. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205