Blockchain security firm CertiK continues its exploration of post-quantum cryptography as the digital transformation of key industry segments continues in 2026. Following an update mostly covering one-time signatures (OTS) like W-OTS+, this update from CertiK now carefully examines how to overcome their core limitation—single-use keys—through efficient tree-based structures that enable multiple signatures from a compact master public key.
The challenge with basic OTS is clear. Blockchain focused CertiK pointed out that effectively supporting thousands or millions of signatures requires managing an impractical number of separate public keys. Verifiers, such as blockchain nodes or smart contracts, would struggle with storage and retrieval.
Hash-based solutions address this by leveraging Merkle trees, originally proposed by Ralph Merkle, to commit to exponentially many OTS keys using just one root hash as the master public key.
In the classic Merkle Signature Scheme (MSS), signers generate 2^h independent OTS key pairs, where h is the tree height determining total signature capacity (e.g., h=20 for over a million signatures). Each OTS public key is hashed into a leaf node.
The tree builds upward by repeatedly hashing pairs of child nodes, culminating in a single root.
To sign a message, the signer produces an OTS signature along with an authentication path—a logarithmic set of sibling nodes proving the leaf belongs to the tree.
Verification first checks the OTS signature, reconstructs the leaf, and recomputes the root using the path. If it matches the master public key, the signature is valid.
This approach scales logarithmically rather than linearly, making it far more practical.
XMSS (eXtended Merkle Signature Scheme), standardized in RFC 8391 and recommended in NIST SP 800-208, refines MSS for real-world use.
It introduces randomized hashing via an XOR-tree construction: each node computation XORs children with unique bitmasks derived from a public seed and node-specific address before hashing.
This strengthens security against multi-target attacks and enables tighter proofs.
XMSS also employs L-trees to compress lengthy W-OTS+ public key vectors into single leaf values for the main tree.
Key generation uses pseudorandom functions for deterministic derivation, while signatures include a randomized message digest for added protection.
The scheme remains stateful—the signer must track and increment a leaf index after each use to prevent key reuse, which would compromise security.
For greater scalability, XMSS^MT (multi-tree or hyper-tree) stacks multiple smaller XMSS trees. Lower layers sign messages, while upper layers sign roots of the layer below.
According to the insights from CertiK, this cuts key generation time for very large capacities (e.g., 2^60 signatures) at the cost of modestly larger signatures containing authentication paths from each layer.
State management remains a critical consideration. XMSS suits controlled environments like blockchain validators where monotonic index tracking can be reliably enforced.
However, it poses risks for typical wallets due to potential state resets during backups, which could enable key reuse attacks.
CertiK pointed out that XMSS bridges theoretical OTS to practical post-quantum signing with compact verification and strong security rooted in hash functions.
While not fully stateless, it offers a seemingly viable option for high-assurance systems. Blockchain security company CertiK‘s updates also focus on fully stateless alternatives like SPHINCS+ (SLH-DSA), which build on these foundations using randomization for broader usability.