I was wondering if it would be quicker to instead multiply the public keys by r rather than the messages.
My thoughts were that since e(P, r*M) = e(r*P, M).
and public keys are on G1 then it would be quicker to do the elliptic curve multiplications by r on G1 rather than G2.
The downside I see to this would be that we would need to maintain a copy of the original public key so it would need to be copied before multiplication.
As an FYI I’ve implemented this and run some benchmarks
Verification of a Single Signature -> 8.3ms
Fast Verifcation: n = 10, m = 3 (Note mi = 3 for all i)
r * M -> 6.06ms per signature
r * P -> 5.86ms per signature
Fast Verification: n = 50, m = 6 (Note mi = 3 for all i)
r * M -> 5.14ms per signature
r * P -> 5.06ms per signature
Also r was chosen between 1..2^{63}