Baby CQ Lookups

Baby CQ Lookups

A simple Python implementation of [Cached Quotient Lookups](https://eprint.iacr.org/2022/1763.pdf)

The problem Baby CQ Lookups solves

Cached Quotient Lookups improve prover's performance in field operations from O(n log^2 n) to
O(n log n). Currently there is only rust implementation for it, this work implement it with python programming language

Challenges I ran into

  1. Trusted setup: normal trusted setup will not setup powers of tau for G2 and commit with it, I added it and verify it works
  2. Pairing: pairing params in py_ecc and paper is different, spent sometime to figure it out
  3. A lots of variables interaction between prover and verifier, need to carefully handle them

Discussion