ed25519: optimize reuse of instantiated BatchVerifier about curve25519-voi

[Yawning]

A quick improvement I believe would be to include a Reset() method that would re-slice the internal entries []entry of a BatchVerifier into a slice of length zero. An alternative would be to also change up the BatchVerifier API to accept slices and not allocate on its own so that allocations can be managed by the caller.

Any thoughts on this?

I would rather not break the API at this point. Exposing a Reset() call is certainly something I could do though. I'll think about if there are any other things I can do to make this use-case better behaved as well.

I also have a quick question: is there any reason entry.signature is a byte slice rather than a fixed 32 byte array?

Because the only time entry.signature gets set is when the caller specifies cofactor-less verification, which should be extremely uncommon since attempting to do that is basically a bug in the calling code. I debated between panic() and "forcing fallback to serial verification" when such a thing was requested and went with the latter.

[Yawning]

Something like in #69 should make this case better behaved. I debated adding BatchVerifier.SetCapacityHint, but opted for a ctor that does preallocation for the sake of simplicity.

As an aside, if your use case involves repeatedly verifying huge batches, where the set of public keys in each batch is dramatically different, then storing the public key in the entry in expanded (precomputed table) form will also cause significantly more allocation overhead than necessary.

I can't really think of any good ideas on how to improve this while keeping the code easy to maintain (since my use case favors what is being done now, and I would rather not do something like, expose multiple BatchVerifier types), but I am open to suggestions.

[lithdew]

PR #69 allowed me to pool BatchVerifiers; thanks!

In terms of areas where it might be worth looking into optimizing away allocations, it looks like the one last hotspot I've noticed from my benchmarks is around how public keys are expanded prior to signature batch verification. Unfortunately, it isn't trivial to optimize the allocations around it away.

If I get any ideas I'll open up a new issue. For the time being though, here's a pprof heap profile graph straight from my benchmarks:

[Yawning]

In terms of areas where it might be worth looking into optimizing away allocations, it looks like the one last hotspot I've noticed from my benchmarks is around how public keys are expanded prior to signature batch verification. Unfortunately, it isn't trivial to optimize the allocations around it away.

Yeah, the current behavior is an explicit design decision, around the assumption that the application code will repeatedly verify batches using the same (or similar) set of public keys, so the routine is written to make AddExpandedWithOptions fast/efficient.

For the batch sizes that you use, storing A as a curve.EdwardsPoint would make more sense (both from a performance and allocation efficiency standpoint), but it's tricky to have a single implementation that does the right thing for both of our use cases, unfortunately.

[Yawning]

I went ahead and opened a new issue for further improvements in this area, with a design sketch of how this could be improved. The associated PR is still very much a work in progress and is not nearly as tested as it should be, but it is much better behaved.