Polymorphic MSM interface

[burdges]

I'd suggest MSM code become polymorphic over the curve, by replacing the interface under ark_ec::msm with trait methods on AffineCurve and ProjectiveCurve. There are small per-curve optimization choices one could make inside MSMs, but the primary usage would be acceleration via GPUs, WASM host calls, etc.

I believe the variable base interface should look like

pub trait AffineCurve: ... {
    ...
    pub fn variable_base_msm(
        bases: &[Self],
        scalars: &[<Self::ScalarField as PrimeField>::BigInt],
    ) -> Self::Projective
    where Self: Sized;
}

I think msm_checked_len and msm_chunks should become free functions, but maybe the chunk size should be controlled by the curve too, likely by making msm_chunks a trait method..

I'm unsure about the current form of the fixed base MSM, but assuming it's ideal then the fixed base interface could look like:

pub trait ProjectiveCurve : ... {
    ...

    type WindowTable = Vec<Vec<Self::Affine>>;

    fn get_window_table(
        scalar_size: usize,
        window: usize,
        g: Self,
    ) -> Self::WindowTable
    where Self: Sized;

    fn windowed_mul<T: ProjectiveCurve>(
        outerc: usize,
        window: usize,
        multiples_of_g: &Self::WindowTable,
        scalar: &Self::ScalarField,
    ) -> Self
    where Self: Sized;

    fn fixed_base_msm<T: ProjectiveCurve>(
        scalar_size: usize,
        window: usize,
        table: &Self::WindowTable,
        v: &[Self::ScalarField],
    ) -> Vec<Self>
    where Self: Sized
    {
        let outerc = (scalar_size + window - 1) / window;
        assert!(outerc <= table.len());

        cfg_iter!(v)
            .map(|e| Self::windowed_mul::<T>(outerc, window, table, e))
            .collect::<Vec<_>>()
    }
}

Afaik, there is no reason to preserve the ZSTs VariableBase and FixedBase, but their current methods could become free functions the default implementation of the trait method calls, which maybe simplifies implementing them elsewhere, not sure.

I've no idea about streaming MSMs or when they come in handy.

Thoughts?

[burdges]

There is also the WnafGroup stuff from zCash in https://github.com/zkcrypto/group/blob/main/src/wnaf.rs so maybe no reason to rush on the fixed based part.

[Pratyush]

I think this is a good proposal!