A stateful signature scheme must preserve signing state, usually a counter, so it never reuses one-time signing material. XMSS and XMSSMT depend on this discipline: reusing an OTS can enable signature forgery. section 14.2.3
Statefulness shapes both the construction and its operational risks:
- XMSS uses a Merkle tree of one-time-signature keys; larger trees support more signatures, while signing advances through distinct leaves. section 14.2.3
- XMSSMT arranges multiple Merkle trees as a hypertree, regenerating only trees on the path to the selected one-time key. section 14.2.3
- Rollback to an earlier filesystem state or sharing one signing key across servers can repeat a path and reuse signing material. section 14.2.3
- SPHINCS+ removes this state-management requirement by deriving signing paths deterministically and presenting a stateless interface. section 14.2.3 section 14.5
A dangerous rollback
A signer produces signatures, then its filesystem rolls back to an earlier snapshot. The restored counter can select the same one-time key again, creating a path to forgery. section 14.2.3
Figure 14.5 The Merkle signature scheme is a stateful hash-based algorithm that makes use of a Merkle tree to compress many OTS public keys into a smaller public key (the root hash). The larger the tree, the more signatures it can produce. Note that signatures now have the overhead of a membership proof, which is a number of neighbor nodes that allow one to verify that a signature’s associated OTS is part of the tree.
Visualizes how a Merkle tree compresses many one-time public keys into one root hash while retaining stateful signature capacity. section 14.2.3
