zkcrypto / group

Elliptic curve group traits and utilities.
Other
91 stars 32 forks source link

Const generic equivalent of `Curve::batch_normalize` #50

Open tarcieri opened 1 year ago

tarcieri commented 1 year ago

batch_normalize currently documents this caveat:

This function will panic if p.len() != q.len().

However, with const generics you can construct an output array that matches the input size with compile-time assurances:

fn batch_normalize_array<const N: usize>(points: &[Self, N]) -> [Self::AffineRepr; N] { ... }

This issue is to suggest an addition, rather than a replacement, specifically for use cases where the number of points is fixed at compile-time.

Note that this approach is also useful for stack allocating all intermediate values (since you can size the arrays by N), allowing for efficient implementations on heapless targets.

tarcieri commented 12 months ago

We ended up solving this with a BatchNormalize trait which is generic around its input type and therefore supports overlapping impls.

This allows the trait to be impl'd for [ProjectivePoint] and [ProjectivePoint; N] as inputs, where the former is gated on the alloc feature, and the latter supporting heapless usage, with the const generics completely disentangled from the trait definition: https://docs.rs/primeorder/0.13.6/primeorder/struct.ProjectivePoint.html#impl-BatchNormalize%3C%5BProjectivePoint%3CC%3E%5D%3E-for-ProjectivePoint%3CC%3E