Awesome
noir_bigcurve
noir_bigcurve is a @noir-lang library that evaluates operations over elliptic curves instantiated with an arbitrary prime field.
noir_bigcurve uses the noir-bignum library to evalaute arbitrary prime field arithmetic.
This library is a work in progress and likely full of bugs!
Overview
noir_bigcurve
make use of noir-bignum
to optimally evaluate group operations using a minimal number of modular reductions. Runtime lookup tables are also used to reduce the number of group operations required when evaluating scalar multiplications
Usage
See bigcurve_test.nr
for some ways in which the library can be used.
Complete elliptic curve operations can be evalauted using BigCurve::add
, BigCurve::sub
BigCurve::mul
and BigCurve::msm_with_hint
.
msm_with_hint
requires the generation of an AffineTranscript
object in an unconstrained function. See bigcurve_test.nr
for how this is done.
The most efficient method to evaluate curve operations is BigCurve::evaluate_linear_expression
(TODO: Brillig bug means this method does not currently work!)
Future work
- When performing MSMs, utilize the Montgomery Ladder to minimize the number of field operations (see
batch_mul
inbarretenberg/src/stdlib/biggroup
for example implementation) ScalarField
is not properly constrained when constructed from aBigNum
object- Add tests for curves that have a nonzero
a
parameter - Add hash to curve method
- Add method to check point is in prime-order subgroup for curves with a cofactor
- Parametrise and test with a degree-2 extension field instead of
BigNum
- Add curve parameters for commonly used curves (BN254, BLS12-381, MNT4, MNT6, Pasta, Vella, Secp256K1, Secp256R1)
- Create benchmarks
- Add support for curve endomorphisms where applicable (if base field and scalar field both contain cube roots of unity, we can reduce the number of point doublings required for an MSM in half)
FAQ
Q: What's up with the Jacobian points and the transcript objects? A: To minimize witness generation time (currently the bottleneck due to Brillig VM) we evaluate ECC operations over Jacobian coordinates in an unconstrained function, in order to efficiently batch-compute the modular inverses required to constrain ECC operations over Affine coordinates (which is more constraint-efficient)