search

AztecProtocol / aztec-2.0

C++ elliptic curve library
134 stars 37 forks source link

Cleanup/generic curves #15

Closed zac-williamson closed 4 years ago

zac-williamson commented 4 years ago

Fully implemented the grumpkin elliptic curve. This curve is described via the formula: 

y^2 = x^3 - 17 mod p

where p is the order of the BN254 curve. The order of grumpkin is equal to the prime field that the BN254 curve is defined over, which is extremely useful for implementing recursive proving systems using a half-pairing-friendly cycle of elliptic curves.

The pippenger algorithm has also been significantly refactored. The algorithm is now internally multithreaded. Previously, multithread support was implemented via splitting a multiple scalar multiplication by splitting it into t smaller multiple scalar multiplications, where t is the number of threads.

Internally threading pippenger allows us to leverage the O(n / logn) efficiency of the algorithm.

Combined with other small improvements (pre-allocating memory to avoid page faults and removing superfluous field multiplications in our coset ffts), overall prover efficiency has improved by 15-20%

charlielye commented 4 years ago

Merging as part of https://github.com/AztecProtocol/barretenberg/pull/16