0
$\begingroup$

From what I understand, to reduce the time taken for public key generation, you can use nested trees in XMSS to form Multi-tree XMSS.

For an instantion of 2 layers, it seems that the leaf of each L tree (one of these nested trees) is an OTS public key. This means that the leaves of the top level tree sign the OTS keys in the L tree below it.

I read that this allows you to only compute the top main tree and only the first tree in each layer, which naturally saves a lot of storage and computation time.

However, I do not understand how this is possible because to compute the top layer tree, you need to know the root of each L tree, which involves computing the whole L tree below each leaf.

What am I missing here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

to compute the top layer tree, you need to know the root of each L tree, which involves computing the whole L tree below each leaf.

You need to compute the entire top level tree, which involves generating the WOTS+ public key for each of the leafs of that tree. However, you don't need to propagate below that; when it comes time to sign with a next-level tree, then at that time, you need to know that next-level tree root (so that you can generate a WOTS+ signature for it); you don't need to do that earlier (you can, if it is convenient).

So, to generate the initial signature, you need to generate the full XMSS tree for every tree that's on the left side of the hypertree; you don't have an immediate need to generate anything else.

In practice, we (or at least, I) find it convenient to incrementally generate the next XMSS tree at each level while we're using the leafs of the current XMSS tree; that just happens to work out well, but it's not mandatory.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think that makes sense (still processing), thank you! Just to confirm my intuition, we then use the leaves of the XMSS top tree to sign the roots of the L-trees. However, to verify this signature, since the leaves of the top tree are one time signatures, shouldn't you discard this one time public key at the root of the L tree? How would this work as each leaf of the L tree is also a OTS? With this logic, you would only be able to use one of the OTS pub keys in each L tree, no? $\endgroup$
    – João Diogo Duarte
    Commented Jun 10, 2022 at 10:25
  • $\begingroup$ @JoãoDuarte: The limit on one-time-signature is that are can't sign two different messages. well, the value that each leaf of the top level tree signs is the root for the next level tree. That root of the next level tree is always the same, and so we can sign it repeatedly, no problem (or just sign it once and stash that WOTS signature someplace - I've seen both) $\endgroup$
    – poncho
    Commented Jun 10, 2022 at 12:48

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.