librustzcash icon indicating copy to clipboard operation
librustzcash copied to clipboard

Improve asymptotic efficiency of nullifier checks in `scan_block`

Open daira opened this issue 2 years ago • 0 comments

This currently takes $O(m \cdot n)$ time where m is the number of notes in the wallet, and n is the number of nullifiers in blocks. It should take $O(q \cdot \log q)$ time where $q = \max(m, n)$, by sorting and scanning.

daira avatar Aug 16 '22 20:08 daira