solana-perf-libs icon indicating copy to clipboard operation
solana-perf-libs copied to clipboard

Faster algorithm for ed25519 batch signature verification

Open aweinstock314 opened this issue 1 year ago • 0 comments

ed25519_verify_many in both the CUDA and OpenCL backends appears to verify the individual signatures in parallel.

The subsection "Fast batch verification" from Section 5 of DJB's paper "High-speed high-security signatures" (https://eprint.iacr.org/2011/368.pdf) gives an expression of Ed25519 batch signature verification in terms of multi-scalar multiplication (a problem that has been independently optimized since this paper was published), which is likely applicable.

aweinstock314 avatar Jan 12 '24 20:01 aweinstock314