Common use of Complete WOTS+ Chains Clause in Contracts

Complete WOTS+ Chains. Rather than providing a narrow API that allows a developer to efficiently make use of the underlying hash function primitive, the parallelism can be made trans- parent to the implementer through a more abstract API: computing WOTS+ chains and authentication paths. In the WOTS+ chains, there is a lot of opportunity for shared execution. Besides the natural ‘horizontal’ parallelism across many chains (which would be the primary candidate for optimizations discussed in the previous Subsect. 5.1), there is potential gain in coupling the ‘vertical’ computations that take place during WOTS+ public key and signature generation. On top of the benefits achieved from only passing through the Java stack once, rather than repeatedly for every application of the chaining function, the input to many of the under- lying SHA-256 compression function calls overlaps significantly. In particular, for a single WOTS+ key pair, the input to the first compression call is com- pletely identical across all 16 67 = 1072 calls of the chaining function. Note that this is a consequence of the specific instantiation of the compression function in XMSSMT as defined in [10], however, and does not immediately carry over to other function designs (in particular, the SPHINCS+ proposal [1] to the NIST standardization project [17] does not benefit from this). Such an API goes beyond a straight-forward parameter for the hash function specifying the number of iterations, as the iterated function is not simply SHA- 256, but rather the address- and key-aware chaining function. Furthermore, to make it effective for WOTS+ signature generation, it would require specifying the length of each individual chain, as well as a variable number of chains (as an entire WOTS+ signature will likely not fit in RAM on most Java Cards). This middle ground between abstracting away the parallelism of the hash functions but still requiring (or, indeed, allowing) the developer to puzzle together the pieces has its upsides, but is clearly not without added complexities. We stress that the API of such a hybrid solution needs to be carefully thought through to be sufficiently fine-grained to provide a benefit over an all-in-one API (as described later, in Sect. 5.4), yet convenient to use so that it actually reduces boilerplate code and development overhead when compared to a more straight-forward parallel hashing API.