2
$\begingroup$

The reference uses treeHash algorithm everytime a signature is generated, thus generating authentication path AND the root, which is not necessary, as the root has only to be generated once. Generating root with every new signature is not efficient, but are there more efficient ways to generate the authentication path without recomputing the xmss root?

My first approach is to save all the xmss leaves during root computation, then create authentication path out of them if needed, but this requires a lot of memory for bigger tree heights.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

are there more efficient ways to generate the authentication path without recomputing the xmss root?

Yes (and without using large amounts of memory to store the entire tree).

These are Merkle tree walking algorithms; these are algorithms which output the 'next' authentication path for a Merkle tree - they store some number of internal nodes, and recompute some small number of leaf nodes while generating an authentication path.

The best known (and best described, if not the simplest) would be the BDS algorithm, which generates the next authentication path in $O(h)$ time and storing $O(h)$ intermediate nodes (where $h$ is the height of the tree).

Another (simpler approach) would be the Fractal algorithm (which isn't well described in the paper); this uses more internal storage, but it requires fewer numbers of computations per authentication path generated (and hence may be a better trade-off, depending on which you are trying to minimize)

These are not the only two; google can point you to others...

Improve this answer
$\endgroup$
2
  • $\begingroup$ do you have some code examples for BDS algorithm used in XMSS? $\endgroup$
    – denis98
    Commented Feb 18, 2021 at 21:16
  • $\begingroup$ @denis98: actually, the pseudocode in the BDS paper is pretty good - if you'll looking for some actual code, well, the reference XMSS implementation github.com/joostrijneveld/xmss-reference uses BDS... $\endgroup$
    – poncho
    Commented Feb 19, 2021 at 15:10

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.