keep-starknet-strange / garaga

State-of-the-art Elliptic Curve operations and SNARKS verification for Cairo & Starknet 🐺.
https://felt.gitbook.io/garaga
MIT License
181 stars 39 forks source link

Emulated Field arithmetic research, audit, and update #71

Closed feltroidprime closed 1 year ago

feltroidprime commented 1 year ago

This fixes security issues in fq.add, and fq.mul. Initially, approximately 0.6% of all the possible values that the prover could fill were passing although wrong. Now only the true and expected value is passing.

Research lib is available in EmulatedBigInt.pyx Test in emulated_bigint.py (do make cython before running)

Benchmarks are also updated, resulting in ~+20% cost.

This sets up the base for building emulated arithmetic builtins and when completed, should give a more than 70% reduction of pairing costs.