Chaining Trees Clause Samples

Chaining Trees. In order to be able to perform many signatures using the same public key, one could instantiate XMSS with a large tree. This comes at a considerable cost, as the signer needs to compute all leaf nodes when generating a signature. Spe- cialized tree traversal algorithms [5] move a large part of this cost to the key generation, but it remains a limiting factor. This is mitigated in XMSSMT , the multi-tree variant of XMSS. As the name suggests, this scheme makes use of a structure of trees. On the bottom layer, a WOTS+ key pair is used to sign the message. Along with the WOTS+ signature, the signer supplies an authentication path to the root of that subtree. Rather than interpreting this root as the public key, it is signed using a WOTS+ leaf of a new tree, one layer ‘above’ the current layer. This signature is authenticated by a path leading to the next root node, et cetera. Considering d layers of trees of height h/d, this allows for 2h signatures while only requiring h/d leafs on each layer to be computed to construct the authentication path (as well as opening up a whole new range of time-memory trade-offs with tree traversal [5]). Note that this trade-off leads to increased signature sizes. While an XMSS signature consists roughly of a WOTS+ signature (i.e. 67 32 bytes) and a number of intermediate nodes (say, 20 32 bytes), an XMSSMT signature consists of mul- tiple WOTS+ signatures. For the sake of simplicity, we now consider XMSSMT to be a direct generalization of XMSS, i.e. XMSS is the specific class of instances where d = 1.