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

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

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.