Feature gate constant time impls about algebra HOT 1 OPEN

How should constant-time be handled in arkworks?

We could provide constant time methods within the regular traits, or use a feature gate, but could we really implement constant-time operations uniformly for all curves of a given type? Is constant-time a guarantee that requires testing? If we used a feature gate, then what performance cost?

We could provide some new ConstantTimeGroup trait with constant-time operations, but now code cannot be polymorphic over constant-time and non-constant-time operations. An issue with constant time methods too.

I'd tentatively suggest we have separate constant-time curves models implemented on a pub struct ConstantTime<C>(pub C); wrapper over the original non-constant-time representation, but which implement the non-constant-time operations. If you need constant-time then you need where A: AffineRepr, ConstantTime<A>: AffineRepr or where G: CurveGroup, ConstantTime<G>: CurveGroup. Yet, you could pass ConstantTime<A> into polymorphic code to get constant-time code, well hopefully.

We've two initial questions: Does mul_bigint make doing this tricky? We've few constant-time uses for pairings, but IBE makes sense, so could a wrapper like this play nicely with pairings? If no and yes, we'd provide constant-time BLS12 pairings but not MNT or BN or CP or BW, but constant-time SW code might still works outside BLS12, or maybe we only provide constant-time TE curves.

As an aside, miracl/amcl claimed constant-time, but this claim disappeared when deprecated for miracl/core.

from algebra.