Optimize batching MSM in Shplemini verifier

[codygunton]

If we use the function bn254_endo_batch_mul_with_generator (which needs to be generalized) we can see very significant savings in the Shplemini recursive verifier cost, particular in the base rollup VMs where there are about 100 (ECCVM) and 180 (Translator) commitments to batch. This is a 'short scalars optimization'.

[maramihali]

Edited as we will possibly do this for Shplemini not ZM

[codygunton]

@iakovenkos would you say this is handled in an indirect way by some of the work you've done? if so will you tag and close as appropriate?

[ledwards2225]

@iakovenkos pinging you again on this - what's your assessment of whether there's something more to be done?

[iakovenkos]

TLDR: let's close it

1. Currently, we are performing a single batch_mul() in BN254-based Recursive Verifiers, done in https://github.com/AztecProtocol/aztec-packages/pull/9329 and https://github.com/AztecProtocol/aztec-packages/pull/8351
2. The number of scalar muls is optimal in Translator (handled in https://github.com/AztecProtocol/aztec-packages/pull/9392)
3. batch_mul with short scalars is insecure (repeated commitments aren't handled properly), and its benefits are questionable. It requires more hashing, structural changes to proofs, and would require separate batch_mul calls for shifts and interleaved commitments. + The proof size remains the same

I'd say multi-shplemini is the way to go if we really want to optimize the rec verifiers gate counts and proof sizes at the same time.