Stable wNAF API

[ebfull]

Currently you have to opt-in to it because it's a low level API. I want a simple API that you cannot misuse.

[daira]

Is this just a matter of being able to preprocess the exponent into wNAF form (so that it can be reused)? If so then perhaps the API does not need to specify that it is wNAF, so that other things like mbwNAF can be implemented later.

[daira]

Also, consider having separate APIs for constant-time and variable-time (or side-channel resistant and non-side-channel-resistant).

[ebfull]

There are many use cases for wNAF (MPC, solo paramgen, multiexp perhaps, verification) but various ways of interacting and sharing allocated space for window tables and wNAF-form scalars across threads, and it's a little bit tricky to balance all of these requirements for a nice clean API. In particular, I want it to be impossible to accidentally use the wrong window table sizes in these different contexts.

I know there's a nice API to do it, I just haven't come up with it yet. :)

[ebfull]

Alright, I have a mockup of something that may work. It's similar to what I originally wrote for bellman a while back.

There's a Wnaf<W, B, S> object that you can instantiate as Wnaf<(), Vec<G>, Vec<i64>> with new(). If you call .base(..) on this, it populates the window table and returns a Wnaf<usize, &'a [G], &'a mut Vec<i64>>, i.e., a distinctly typed Wnaf which immutably borrows the window table and mutably borrows the scalar representation vector space. Similarly, you can call .scalar(..) on it which returns Wnaf<usize, &'a mut Vec<G>, &'a [i64]> which immutably borrows the scalar representation space after conversion and mutably borrows the window table vector space.

Once you have one of these objects with a defined window size, you can call .scalar() or .base() on them as appropriate. (They're defined abstractly over whether the scalar space is mutable or the window table space is.) If you need to toss this around threads, you can also call .shared() which will replace the appropriate mutable representation with an owned vector and an immutable reference to the original Wnaf -- which is always Send and thus threadsafe.

All using the typesystem, no unsafe code:

• can reuse window tables and scalar representations for multiple exponentiations without unnecessary allocation
• can reuse window tables and scalar representations for multiple threads
• window size is defined for you
• the window size is fixed when you specify the base or the scalar, so you can never mix things up and use the wrong window size.
• cannot accidentally overwrite a window table before exponentiation