Description:
Bernstein mentions in the ed25519 paper that batch verification can be done using a multi-scalar exponentiation algorithm such as pippengers or bos-corter. Bos-Corter is used in his benchmarks, since its easier to implement and uses less memory (he was primarily concerned with fitting things inside the L1 processor cache in that paper). Using bos-corter, he found that the time per signature halved when batch verifying 64 signatures under 64 different pubkeys. This only improves as the number of signatures being batch verified increases. Also note that this requires one random number to be chosen per signature. I suggest implementing this via bos-corter for now, and benchmark pippengers at a later date.

Further optimizations

• Using the same public key multiples times in a batch verification. For every signature here, the group operations are one 253 bit scalar mul, and one 128 bit scalar mul. If we re-use the same public key multiple times in a batch verification, we can just add the 253 bit scalars for those public keys together, so the second signature in effect only contributes one 128 bit scalar mul. (There are still more group operations and randomness needed for that signature, just no scalar mul)
• crypto/ed25519: Caching public key decompression #1784 - will reduce time taken here by > 20%, since decompression isn't getting sped up, plus the window is going to be recomputed for each pubkey.
• Unroll FeZero, FeOne ed25519#9 - implementation detail which may carry over speedups here

Things needed:

• We need a fast heap implementation.
• Actually implementing this
• Optimizing said implementation
• Figuring out the API, in a way that we can quickly detect the same pubkey was reused. Sorting would be too slow I think. This may be something that should be handled on the tendermint side for fast syncing, as opposed to being done in crypto/ed25519.
• Getting the implementation reviewed, since this affects signature verification