search

shuklaayush / noir-bigint

BigInt library for Aztec's noir language
MIT License
30 stars 11 forks source link

Implement faster non-native modular multiplication #6

Open shuklaayush opened 1 year ago

shuklaayush commented 1 year ago

PrimeField currently uses the montgomery method for doing modular multiplication https://github.com/shuklaayush/noir-bigint/blob/e3192a859420ed2aea3842eea1b288a0815a5954/src/prime_field.nr#L144-L149

This is a bottleneck right now. Explore if there are faster ways to do this

One idea is to use unconstrained functions/brillig to optimize - https://github.com/noir-lang/acvm-docs/blob/main/docs/brillig/00_intro.md

Links:

  1. https://eprint.iacr.org/2022/1470
  2. https://github.com/okuyiga/noir-mul-mod-non-determinstic/blob/master/circuits/src/main.nr
  3. https://hackmd.io/@arielg/B13JoihA8
  4. https://github.com/axiom-crypto/halo2-lib/blob/4060f2a703ca5ca3ed03fd869cfdf0c778aae240/halo2-ecc/src/bigint/carry_mod.rs