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?
1 Answer
$\begingroup$
$\endgroup$
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.
