Post-Quantum Signatures, Part 2: From Trees to Forests

Introduction

In our first post of this series, we broke down the core building block of hash-based cryptography: One-Time Signature (OTS). We reviewed how schemes like W-OTS+ achieve post-quantum security by relying solely on the robustness of cryptographic hash functions.

But OTS has one major catch: you can only use it once. By definition, an OTS key pair $(sk_{OTS}, pk_{OTS})$ can securely sign only one message. If a system requires the capacity to sign $N$ messages (where $N$ might be $2^{20}$ or more, typical for blockchain validators), you’d basically have to create and share $N$ distinct public keys:

$PK = \{ pk_{OTS, 0}, pk_{OTS, 1}, \dots, pk_{OTS, N-1} \}$

This linear scaling is a logistical nightmare. For a verifier (e.g., a blockchain light client or a smart contract) to validate a signature, they would need access to this entire registry of keys. For hash-based signatures to actually compete with RSA or BLS in high-throughput systems, we need a way to squash all these temporary keys down into a single, constant-size master public key.

In this post, we’re diving into how cryptography solves this exact problem, originally proposed by Ralph Merkle and later refined into XMSS (eXtended Merkle Signature Scheme).

Merkle Commitment

Ralph Merkle’s breakthrough was simple yet powerful: instead of listing OTS keys linearly, we organize them as the leaves of a hash tree (Merkle tree). By recursively hashing pairs of nodes, the system can commit to an exponential number of OTS keys using a single hash value: the root of the tree.

$PK_{Master} = \text{Root}$

This structure fundamentally alters the verification process. Instead of checking a signature against a linear list of keys, the verifier checks a cryptographic proof, the authentication path, which links a specific, one-time used $pk_{OTS}$ to the trusted global $PK_{Master}$.

From MSS to XMSS

While the classical Merkle Signature Scheme (MSS) established the theoretical framework, it lacks the efficiency and tight security proofs required for modern deployment. XMSS is specified in RFC 8391, an IRTF Informational RFC that describes WOTS+, single-tree XMSS, and the multi-tree variant XMSS^MT. For U.S. federal guidance, NIST SP 800-208 later approved selected XMSS and LMS stateful hash-based signature parameter sets, with strict operational constraints around private-key state management.

Merkle Signature Scheme (MSS)

The Merkle Signature Scheme (MSS), proposed by Ralph Merkle, wraps thousands of independent OTS key pairs into a single robust structure. The central data structure enabling this transformation is the binary hash tree, commonly referred to as the Merkle Tree.

Tree Construction and Key Generation

Think of the tree height, $h$ as the capacity setting for MSS. It dictates exactly how many signatures ($N = 2^h$) we can squeeze out of a single master public key.

Key Generation

1. OTS Generation: The signer generates $N = 2^h$ independent OTS key pairs using a secure OTS scheme (such as W-OTS+). Let these pairs be denoted as: $(sk_{OTS, i}, pk_{OTS, i}) \quad \text{for } i \in \{0, 1, \dots, 2^h - 1\}$
2. Leaf Construction: The public keys of these OTS instances form the leaves of the tree. To ensure uniform format, each OTS public key is hashed to produce a fixed-length leaf value $L_i$: $L_i = H(pk_{OTS, i})$
3. Tree Hashing: The tree is built bottom-up. Internal nodes are computed by hashing the concatenation of their two child nodes. Let $Node_{j, k}$ denote the node at height $j$ (where leaves are at height 0) and index $k$. The relationship is defined as: $Node_{j, k} = H(Node_{j-1, 2k} \mathbin{\|} Node_{j-1, 2k+1})$
4. Root Computation: We repeat this process until we reach the very top - the single root node of the tree, $Node_{h, 0}$. This root serves as the MSS master public key ($pk_{MSS}$). The private key ($sk_{MSS}$) consists of the sequence of OTS secret keys and the index $s$ of the next available key.

Authentication Path

A critical innovation of MSS is the authentication path. Since the verifier only holds the root $pk_{MSS}$, they cannot directly verify an OTS signature corresponding to a leaf $L_i$. Instead of verifying the leaf directly, the signer has to prove that $L_i$ actually belongs to that specific tree.

For a given leaf index $i$, the authentication path $Auth_i$ consists of the set of sibling nodes required to recompute the root. Specifically, for every node on the direct path from leaf $i$ to the root, its sibling (the child of the same parent that is not on the direct path) is included in $Auth_i$.

The length of the authentication path is equal to the height of the tree, $h$. This logarithmic scaling ($O(\log N)$) is what makes MSS practical compared to the linear scaling of storing all public keys.

Signature Generation and Verification

Signature Generation

To sign a message $M$ using the $s$-th OTS key pair:

1. The signer computes the OTS signature $\sigma_{OTS}$ of $M$ using $sk_{OTS, s}$.
2. The signer computes (or retrieves) the authentication path $Auth_s$ for the leaf index $s$.
3. The final MSS signature is the tuple: $\sigma = (s, \sigma_{OTS}, pk_{OTS, s}, Auth_s)$
4. Crucially, the signer updates the state $s \leftarrow s + 1$ to prevent key reuse.

Signature Verification

Given a message $M$, signature $\sigma$, and public key $pk_{MSS}$:

1. OTS Verification: The verifier first checks the validity of $\sigma_{OTS}$ against $pk_{OTS, s}$ using the underlying OTS verification algorithm. If this fails, the signature is invalid.
2. Leaf Reconstruction: The verifier computes the leaf candidate $L'_s = H(pk_{OTS, s})$.
3. Root Reconstruction: Using the index $s$, the candidate leaf $L'_s$, and the authentication path $Auth_s$, the verifier iteratively computes the path up to the root. At each height $j$, the index $s$ determines whether the current computed node is a left or right child.
4. Final Check: The signature is valid if and only if the computed root matches the trusted public key $pk_{MSS}$.

XMSS: eXtended Merkle Signature Scheme

While MSS gave us a great blueprint, it isn't quite fast or provably secure enough for high-stakes, real-world use. XMSS (eXtended Merkle Signature Scheme), specified in RFC 8391, upgrades the design with optimized primitives. It keeps the tree structure but rebuilds the engine.

Randomized Hashing and the XOR Tree

In a standard Merkle tree, a node is computed as $P = H(L \mathbin{\|} R)$. This deterministic structure makes formal security proofs difficult against multi-target attacks (where an attacker tries to find any preimage in the tree).

XMSS fixes this with randomized tree hashing. The main idea? Every single hash operation in the tree gets its own unique "key" or "mask", making sure that hashing at one spot looks completely different (e.g., layer 1, node 5) from hashing anywhere else.

This is implemented via the XOR tree construction. Before hashing, we XOR each child node with a unique bitmask. For a cryptographic hash function $H$, a key $K$, and bitmasks $M_L, M_R$, the node computation is defined as:

$Parent = H(K, (Left \oplus M_L) \mathbin{\|} (Right \oplus M_R))$

Here, $\oplus$ denotes the bitwise XOR operation. The Key ($K$) and Bitmasks ($M_L, M_R$) are derived from a public seed ($P_{seed}$) and the unique address of the node being computed.

Hierarchical Construction: L-Trees and Main Tree

The full XMSS structure is built in distinct stages, applying the XOR Tree logic at every step to handle the W-OTS+ keys.

Leaf Compression: L-Tree

In the basic MSS, leaves are simple hashes. However, in XMSS, the underlying one-time signature is W-OTS+ (as described in the first post). A W-OTS+ public key is not a single value but a long vector of hash values (e.g., 67 values). Plugging this huge vector directly into the main tree is inefficient.

To solve this, XMSS uses a special structure called the L-tree:

1. Input: The W-OTS+ public key vector $pk_{WOTS} = (x_0, x_1, \dots, x_{len-1})$.
2. Process: These values are treated as the leaves of a miniature binary tree. The XOR Tree hashing logic is applied recursively: adjacent nodes are paired, XORed with specific L-Tree masks($B_L$ and $B_R$), and hashed.
3. Output: The single root of this L-Tree. This compressed value becomes the actual Leaf $L_i$ of the main XMSS tree.

Main XMSS Tree

Once the leaves $L_0, \dots, L_{2^h-1}$ are generated via L-trees, the main binary tree is constructed on top of them.

• For every node computation, RFC 8391 derives a fresh key and bitmasks from P_seed and ADRS, where ADRS identifies the specific hash call. The diagram suppresses the full address structure for readability.
• For intuition, a parent node can be viewed as $Parent = H(K, (Left \oplus BM_0) \parallel (Right \oplus BM_1))$, where $K$, $BM_0$, and $BM_1$ are derived from $P_{seed}$ and $ADRS$, not only from the tree height. $ADRS$ encodes the context of the hash call, including the tree type, height, and node position.
• This process culminates in the single XMSS root.

This is a simplified view of RFC 8391's address-based hashing. The full RFC construction uses $ADRS$ to separate different hash calls across WOTS+, L-trees, and the main XMSS tree.

XMSS Protocol Description

With the structural components defined, we can formalize the operation of XMSS. A critical engineering optimization in XMSS is the use of a Pseudorandom Function (PRF) to derive deterministic secret keys.

Key Generation

1. Secret Setup: The signer samples a secret WOTS+ derivation seed $S_{seed}$, a separate secret $SK_{PRF}$, and a public seed $P_{seed}$. $S_{seed}$ is used to derive WOTS+ private-key material, $SK_{PRF}$ is used to derive the per-signature randomizer, and $P_{seed}$ is used together with address information to derive the keys and bitmasks for randomized tree hashing.
2. OTS Generation: For every leaf index $i \in \{0, \dots, 2^h - 1\}$, the WOTS+ secret material can be derived pseudorandomly from $S_{seed}$, for example as $seed_i = PRF(S_{seed}, i)$. The corresponding W-OTS+ public key $pk_{OTS, i}$ is generated.
3. Tree Construction: Each $pk_{OTS, i}$ is compressed into a leaf $L_i$ using an L-Tree. The main Merkle tree is then built on top of these leaves using address-based randomized tree hashing parameterized by $P_{seed}$.
4. Output: The XMSS public key is $pk_{XMSS} = (\text{Root}, P_{seed})$. The secret key is $sk_{XMSS} = (idx, S_{seed}, SK_{PRF}, P_{seed}, \text{Root})$, where $idx$ is the next unused leaf index, $S_{seed}$ derives the WOTS+ private keys, and $SK_{PRF}$ derives the per-signature randomizer.

Signature Generation

To sign a message $M$ using the current state $idx$:

1. State Check: Snapshot the current signing index as $idx_{sig} \leftarrow idx$. Ensure $idx_{sig} < 2^h$, then immediately persist the updated state: $idx \leftarrow idx_{sig} + 1$.
2. Context Randomization: Derive the deterministic per-signature randomizer $r = PRF(SK_{PRF}, idx_{sig})$.
3. W-OTS+ Signing: Compute the randomized message digest $M' = H_{msg}(r \parallel \text{Root} \parallel idx_{sig}, M)$. Sign $M'$ using the $idx_{sig}$-th W-OTS+ key derived from $S_{seed}$ to obtain $\sigma_{OTS}$.
4. Auth Path: Compute the authentication path $Auth_{idx_{sig}}$ for the leaf at index $idx_{sig}$.
5. Output: The signature is $\sigma = (idx_{sig}, r, \sigma_{OTS}, Auth_{idx_{sig}})$.

Verification

Given $M$, $\sigma = (idx_{sig}, r, \sigma_{OTS}, Auth_{idx_{sig}})$, and $pk_{XMSS}$:

1. OTS Verification: Reconstruct the W-OTS+ public key $pk'_{OTS}$ from $\sigma_{OTS}$ and the message digest $M' = H_{msg}(r \parallel Root \parallel idx_{sig}, M)$.
2. Leaf Reconstruction: Compress $pk'_{OTS}$ into a leaf candidate: $L'_{idx_{sig}} = \text{LTree}(pk'_{OTS})$.
3. Root Reconstruction: Use $Auth_{idx_{sig}}$ and the tree index $idx_{sig}$ to recompute the path up to the root candidate $\text{Root}'$, applying the address-derived key and XOR masks at each level.
4. Final Check: The signature is valid if and only if $\text{Root}' = \text{Root}$ (from $pk_{XMSS}$).

Scaling Up: XMSS^MT Hyper-tree

Standard XMSS hits a wall when it comes to scaling. Because key generation time grows linearly with the number of signatures ($N=2^h$). For a tree with height $h=20$ (1 million signatures), generating the key pair might take minutes. For $h=60$ (virtually unlimited signatures), you'll quickly run into a massive latency bottleneck.

To get around this, RFC 8391 introduces the XMSS^MT (Multi-Tree) Hyper-tree. Instead of trying to build one insanely huge tree, we simply stack smaller trees on top of one another.

Tree-of-Trees Architecture

Imagine a structure with multiple layers.

• Top Layer: A single XMSS tree. Its root is the master public key.
• Middle Layers: The leaves of the top tree do not sign messages directly. Instead, they sign the roots of trees in the layer below them.
• Bottom Layer: Only the trees at the very bottom layer are used to sign actual messages.

For example, to achieve a total height of $h=60$, instead of building one massive tree, we can stack 3 layers of trees, each with height $20$.

Trade-offs: Latency vs. Size

So, what's the trade-off? We basically swap slow key generation for slightly larger signatures. You only need to generate the top-layer tree to get started, but in return, your final signature becomes a chain of smaller signatures.

For blockchain consensus, this can be an attractive trade-off: XMSS^MT reduces key-generation time and signing cost by splitting a large tree into smaller XMSS layers. While it easily supports virtually unbounded capacity (like $2^{60}$ signatures), the trade-off is larger signatures: an XMSS^MT signature contains one reduced XMSS signature per layer, and each reduced signature includes a WOTS+ signature plus that layer's authentication path. Signature size therefore grows roughly linearly with the number of layers, making it viable when kilobyte-range signatures are acceptable, rather than a drop-in replacement for compact BLS or ECDSA.

State Liability

Throughout this article, we've flagged that MSS and XMSS are stateful. The signer must persist the leaf index and never reset it.

For a regular crypto wallet, this is a ticking time bomb. If you restore from a backup and accidentally reset your index, you might reuse a one-time key. As we know, that completely breaks the security. This fragility makes XMSS poorly suited to ordinary wallet backup/restore workflows unless the signing system can guarantee monotonic state.

Conclusion

In this post, we have bridged the gap between theoretical One-Time Signatures and practical application. By organizing OTS keys into Merkle trees (MSS) and optimizing them with L-trees and hyper-trees (XMSS^MT), we achieve a signature scheme that offers compact proofs and rapid verification.

XMSS represents a major leap for stateful post-quantum signatures: it offers fast verification and manageable signature sizes compared to other stateful schemes, but it demands strict memory. It may be a candidate for tightly controlled consensus-signing systems, but only if the implementation guarantees crash-safe, monotonic XMSS index management. What about the rest of the world? What if we want a signature that is as "memoryless" and user-friendly as standard ECDSA?

In the next part of this series, we will explore SPHINCS+ and its standardized descendant, SLH-DSA (specified in NIST FIPS 205). We will discover how this stateless hash-based signature algorithm cleverly repurposes the very structures we analyzed, W-OTS+, XMSS and hyper-trees, but replaces the rigid state index with randomization to achieve the holy grail of statelessness.

FAQs

What is the Merkle Signature Scheme (MSS) and why does it matter?

MSS solves the core limitation of one-time signatures by organizing thousands of OTS key pairs as leaves of a binary hash tree, reducing an unwieldy list of public keys down to a single master public key (the tree root). This means a verifier only needs one constant-size value to authenticate any signature, with verification complexity scaling logarithmically rather than linearly.

How does XMSS improve on basic MSS?

XMSS introduces randomized tree hashing through an XOR-based construction, where every hash operation uses unique keys and bitmasks derived from a public seed and node address. This makes formal security proofs tighter against multi-target attacks, and the addition of L-trees efficiently compresses the lengthy W-OTS+ public key vectors into single leaf values.

What is XMSS^MT and when should it be used?

XMSS^MT is a multi-tree "hyper-tree" variant that stacks multiple smaller XMSS trees in layers rather than building one enormous tree, dramatically reducing key generation time. The trade-off is larger signatures, since each signature must include a chain of per-layer authentication paths, making it best suited to environments where kilobyte-range signatures are acceptable.

Why is XMSS described as "stateful" and why does that matter?

XMSS requires the signer to maintain and persist a leaf index that increments with every signature, because each underlying OTS key pair must never be reused. If this state is reset — for example, by restoring from a backup — an attacker who observes two signatures under the same key can break the scheme entirely.

Is XMSS a good fit for blockchain applications?

XMSS is a strong candidate for tightly controlled consensus-signing systems where state management can be guaranteed to be monotonic and crash-safe. However, its stateful nature makes it poorly suited to ordinary wallet workflows, and its larger signature sizes mean it is not a straightforward replacement for compact schemes like BLS or ECDSA.

References

1. Merkle, R.C. 1989: A certified digital signature.
2. Srivastava, Vikas, Anubhab Baksi and Sumit Kumar Debnath, 2023: An Overview of Hash Based Signatures.
3. Andreas Huelsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld, Aziz Mohaisen, 2018: RFC 8391, XMSS: eXtended Merkle Signature Scheme.
4. Andreas Hülsing, Lea Rausch, Johannes Buchmann, 2017: Optimal Parameters for XMSS^MT.
5. Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn, 2015: SPHINCS: Practical Stateless Hash-Based Signatures.
6. Aumasson JP, Bernstein DJ, Beullens W, Dobraunig C, Eichlseder M, Fluhrer S, Gazdag SL, Hülsing A, Kampanakis P, Kölbl S, Lange T, Lauridsen MM, Mendel F, Niederhagen R, Rechberger C, Rijneveld J, Schwabe P, Westerbaan B (2024) SPHINCS+: https://sphincs.org/
7. NIST SP 800-208, 2020: https://www.nist.gov/news-events/news/2020/10/recommendation-stateful-hash-based-signature-schemes-nist-sp-800-208
8. National Institute of Standards and Technology (NIST), 2024: https://csrc.nist.gov/pubs/fips/205/final