A Merkle signature scheme compresses many one-time signatures into one hash-based public key. Each tree leaf contains a one-time-signature public key hash; the root hash becomes the public key. section 14.2.3
A signature follows this pattern:
- Choose a one-time signature that has not been used. section 14.2.3
- Sign the message with that one-time signature. section 14.2.3
- Attach a Merkle proof containing neighboring nodes, allowing verification that the one-time signature belongs to the tree. section 14.2.3
The construction is stateful: reusing a one-time signature is unsafe, so the signer must track the last used leaf. Larger trees support more signatures but increase regeneration work and proof overhead. section 14.2.3
XMSS
XMSS standardizes and optimizes the construction in RFC 8391. It regenerates one-time-signature keys from a seed and leaf position, storing a counter instead of every private key. 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.
Use the diagram to see how one-time-signature public keys become leaves, how the root compresses them into a public key, and how membership proofs accompany signatures. section 14.2.3
