In hash-based signature schemes that use Merkle trees (e.g. XMSS), what is exactly the purpose of the multi-tree variant? Seems like the same number of keys can be represented by a single larger tree? Am I missing something?


What exactly is the purpose of the multi-tree variant in hash-based signature schemes?

The biggest reason for using a multitree variant is to keep the public key generation time reasonable, even if the upper limit on the number of signatures is huge.

With a single Merkle tree, the value of the root is a function of all the Winternitz public keys. That is, if we wanted to create single Merkle tree that could sign (say) a trillion (circa $2^{40}$) messages, we would need to compute all $2^{40}$ WOTS public keys. And, if a single WOTS public key requires a thousand hash computations (say, with LMS and W=16; XMSS would take about three times as many hash computations), we're looking at $2^{50}$ hash computations - that takes too long for most purposes.

In contrast, if we have multiple levels of trees, we only need to compute the top level Merkle tree; if that's a $h=20$ tree, then the same public key computation would take $2^{30}$ hash computations - still quite a lot, but far more feasible.

Of course, as we sign all trillion messages, we'll need to generate all trillion WOTS public keys as a part of that process. However, the vast part of that computation can be done as a part of the trillion signature operations we'll (adding a small fixed cost to each one), and hence is never a large burden to an one operation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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