A Merkle Tree OTS scheme such as XMSS pregenerates 2^h keys that are tied to 1 public key

When the 2^h keys run out, does all the 2^h keys get removed/deleted and the device pregenerates another new 2^h keys and the corresponding public key?

  • $\begingroup$ Well, regenerate and publish! $\endgroup$
    – kelalaka
    Commented Oct 4, 2023 at 6:44

1 Answer 1


What happens when a Merkle Tree OTS scheme runs out of keys?

Well, obviously you cannot generate any more signatures for that public key.

How that is handled is beyond the scope of the signature system, and would need to be handled by whatever is using the signature scheme. You mentioned 'regenerate a fresh public key, and publish that' - this can work in some cases, but other cases (where you cannot update the public key that someone else has) it doesn't work. Another possibility is that, before you run out, use the current public key to sign the next one, and when you need to start signing with the new public key, include the attestation of that public key with the original one - the downside of that is that signatures become variable length.

The most generic answer is 'just select $h$ large enough that you never run out'. And, if you cannot generate a Merkle tree that large, consider a multilevel Merkle scheme, such as $XMSS^{MT}$ (which supports $h$ up to 60) or $HSS$ (which allows even larger values of $h$). You will never need to generate $2^{60}$ signatures, and so selecting an $h$ large enough is practical.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.