# Flexible precomputation for verification checks

## Multiscalar multiplications versus multiple scalar multiplications

Many elliptic curve protocols spend most of their time performing scalar multiplication operations: computing `a*A` for a curve point `A` and a scalar (integer modulo the curve order) `a`. In this post I’ll use capital letters `A,B,P,Q,...` for curve points and lower-case letters `a,b,x,y,...` for scalars, so it’s always possible to distinguish the type from the variable name.

`a_1*A_1 + ... + a_n*A_n`

## Saving time with precomputation

Unfortunately, what these traits don’t allow is taking any advantage of precomputation. If the points are known up-front, it’s possible to trade memory for time by performing some precomputation on the points, then using it for each multiscalar multiplication.

## Specifying the problem at a high level

As noted above, one of the core reasons that multiscalar multiplication can be faster than multiple scalar multiplications is that the entire problem is specified at once, and an implementation can share work between all the parts. We can write the general problem of multiscalar multiplication with precomputation in the form

`a_1*A_1 + ... + a_n*A_n + b_1*B_1 + ... + b_m*B_m,`

## The VartimePrecomputedMultiscalarMul trait

This functionality is now provided in curve25519-dalek by the `VartimePrecomputedMultiscalarMul` trait, which takes the fixed points `B_1,...,B_m` in a constructor and returns a precomputation struct with three slightly different variants of the problem:

• `vartime_multiscalar_mul`, which handles the special case where `n=0` and there are no dynamic points;
• `vartime_mixed_multiscalar_mul`, which takes the dynamic points as already-validated `Point`s and is infallible;
• `optional_mixed_multiscalar_mul`, which takes the dynamic points as `Option<Point>`s and returns an `Option<Point>`, so that a verification check on compressed point data can compose point decompression/validation into the input iterators.

--

--