Multiscalar multiplication with precomputation

[hdevalence]

The current multiscalar API looks like:

pub fn multiscalar_mul<I, J>(scalars: I, points: J) -> RistrettoPoint
where
    I: IntoIterator,
    I::Item: Borrow<Scalar>,
    J: IntoIterator,
    J::Item: Borrow<RistrettoPoint>, 

This takes an iterator of scalars and an iterator of points, and computes Q = c_1 P_1 + \cdots + c_n P_n. This is super-flexible and very useful (it makes it easy to combine statements), but it doesn't allow precomputation.

To do that, we could create a struct (not sure about naming, let's say MultiscalarPrecomputation for now) that looks like:

struct MultiscalarPrecomputation {
    /// Takes points B_1, ..., B_m
    pub fn new<I>(points: I) -> Self
    where
        I: IntoIterator,
        I::Item: Borrow<Scalar>,
    { ... }

    /// Computes (a_1*A_1 + ... + a_n *A_n) + (b_1*B_1 + ... + b_m * B_n)
    pub fn multiscalar_mul<I,J,K>(
        dynamic_scalars: I, 
        dynamic_points: J,
        static_scalars: K,
    ) -> RistrettoPoint
    where
        I: IntoIterator,
        I::Item: Borrow<Scalar>,
        J: IntoIterator,
        J::Item: Borrow<RistrettoPoint>,
        K: IntoIterator,
        K::Item: Borrow<Scalar>,
    { ... }
}

This API would let us cover every combination of static/dynamic points, and because the precomputation is opaque, it means that we can pick what kind of static data we want to use depending on the backend implementation. This would supersede #79.

[hdevalence]

I think that a basic version of this would be easy to implement using the existing scalar mul code, but I'm not sure if it's worth doing before 1.0.

[hdevalence]

Some work-in-progress on this is in the https://github.com/dalek-cryptography/curve25519-dalek/tree/feature/multiscalar-traits branch.

This has an additional upshot: by eliminating the bare functions and the vartime modules, we would have the option (if we wanted) to expose a flat API namespace.

[hdevalence]

Work-in-progress traits for constant-time and variable-time multiscalar multiplication here: 8f659c3

@isislovecruft does this look generally okay? One thing I'm wondering about is how we would like to expose this API.

For the multiscalar multiplication without precomputation (also WIP in that branch), the trait is implemented externally on EdwardsPoint / RistrettoPoint and also internally in various backend code for each algorithm's implementation. This means that we have the flexibility to select an algorithm or a backend transparently.

For multiscalar multiplication with precomputation, should we take the same strategy, exposing structs like VartimeRistrettoPrecomputation that implement the precomputation traits, and keep the flexibility to select the algorithm?

[hdevalence]

Since this is a new API, not a change to an existing one, we can add it after 1.0.

[hdevalence]

One reason to do this before 1.0 would be that we could get rid of the vartime_double_scalar_mul_basepoint and replace it with an instance of this API, whereas if we waited we would be stuck with it.

[hdevalence]

scratch work now located here: https://github.com/hdevalence/curve25519-dalek/tree/lost-precomputaton-branch-rebased

[hdevalence]

Closed by #230 and released in 1.1.0.