XMSSMT

XMSSMT (eXtended Merkle Signature Scheme Multi-Tree) is a hash-based digital signature scheme that extends the XMSS family by organizing the signing keys into a hypertree of multiple Merkle trees. It remains a stateful scheme and is designed to provide post-quantum security based on the hardness of cryptographic hash functions.

The construction uses a hierarchy of L XMSS trees with heights h1, h2, ..., hL, where the total height H = sum hi. The public key corresponds to the root of the topmost tree, while the private key contains seeds and one-time keys for each layer. Signing a message produces a signature that includes the necessary authentication data (Merkle proof components and one-time signatures) across the layers, effectively chaining the layers to reach the top-level root. The design accommodates higher signing throughput and can scale the total number of potential signatures through the choice of layer counts and per-layer heights.

Security properties rely on the designed hash functions and the security of the underlying Merkle and Winternitz-type signatures. Like XMSS, XMSSMT is stateful: each signature consumes part of the private state, and reusing state or leaves can compromise security. The maximum number of signatures is typically 2^H, so parameter choices must balance desired total signatures against signature size and signing speed.

Common parameterizations use a small number of layers (for example L = 2 to 4) with layer heights chosen to meet target signature sizes and performance. XMSSMT is utilized in environments requiring long-term post-quantum resilience, such as firmware signing and secure software update workflows, where deterministic, hash-based signatures are preferred and state management can be controlled.