Add multiscalar multiplication helper

[str4d]

We currently have a group::Wnaf helper that enables downstream groups to perform optimised scalar multiplications. We should similarly have a helper that enables downstream groups to perform multiscalar multiplication (aka multiexponentiation or sum-of-products).

Code examples we could use as a basis for figuring out a generic, usable, and performant design:

• halo2::arithmetic::best_multiexp
• Add sum-of-products for G1Projective and G2Projective bls12_381#70 (from the bls12_381_plus fork of bls12_381).
• bellperson::groth16::multiscalar

[tarcieri]

Sum-of-products would be helpful for ECDSA implementations.

The k256 crate presently uses k256::lincomb for this, but it'd be nice to have something generic across curves and would be one more step closer to having a fully generic ECDSA implementation which is reusable and performant.

[tarcieri]

I ended up adding a simple LinearCombination trait to the elliptic-curve crate:

https://docs.rs/elliptic-curve/latest/elliptic_curve/ops/trait.LinearCombination.html

It'd be nice to have something upstream in group for this though (and perhaps more general, with the ability to compute the sum of an arbitrary number of products)

[kayabaNerve]

Oh. I just came here to ask for a trait of PrimeGroupBits for PrimeFieldBits + PrimeGroup. It comes up often when you write code requiring PrimeFieldBits for the given group, because you have a multiexp lib based on it :p

I published my work a few weeks ago, surprised there wasn't one already. It's a basic Straus + Pippenger implementation, automatically deciding which based on some numbers I got from benchmarking efficiency against k256 and dalek.

https://crates.io/crates/multiexp
https://github.com/serai-dex/serai/tree/develop/crypto/multiexp

There's also a Batch Verifier API which automatically weights queued statements, enabling secure signature validation without manually doing so, and discovering blame using a binary search.

Depending on WnafGroup adoption, with my primary interest being in k256, I'd be happy to move over to it. Notably, my library doesn't currently allow caching tables between multiexps, so I've been considering ways to handle that. Moving to WnafGroup isn't something I'd object to, especially since my current window numbers are based on a crude amalgamation of k256 and dalek.

EDIT: k256 does not implement WnafGroup, so I will be unable to move over at this time. I have submitted an issue to elliptic-curves accordingly though. I do still plan to further review WnafGroup in general, and will note my library is naive, not working without std and not using any threading. While there's still work to be done, I wanted to note it as an option. I am also not against submitting it as a PR to here, if optimal,

[tarcieri]

I'd like to nominate this issue as something which would be nice to get addressed in group v0.14.

We have some requests for it which our current LinearCombination trait is not satisfying: RustCrypto/elliptic-curves#921

[ycscaly]

That would be very helpful for my use case