search

jimouris / draft-mouris-cfrg-mastic

Specification of the Mastic Verifiable Distributed Aggregation Function (VDAF)
https://datatracker.ietf.org/doc/draft-mouris-cfrg-mastic/
Other
1 stars 1 forks source link

Swap loop order in computation of path proof #49

Closed divergentdave closed 1 day ago

divergentdave commented 9 months ago

Currently, path proof computation iterates over prefixes in the outer loop, and levels in the inner loop. Switching this would improve the data locality of implementations, while still committing to all the same data. In particular, the first few iterations of an outer level loop would often hash the same field vector in consecutive iterations of the inner loop. (because, for example, at level 0, it would process node 0 several times, and then process node 1 several times) The field vector arithmetic could even be conditionally reused across inner loop iterations for a further speedup.

cjpatton commented 9 months ago

Thanks for the implementation feedback, @divergentdave! I'll make this change and request your review when the PR is ready. It may not happen before the new year.

cjpatton commented 8 months ago

@armfazh is going to do the implementation of VIDPF in libprio (https://github.com/divviup/libprio-rs). Armando, we will want to resolve this issue as part of this, as this issue aligns the VIDPF spec with the current IDPF implementation.