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

Tracks Applied (1)

Chewing Glass

CQ lookups can be used by SNARKs which use KZG commitment scheme, which is a fundamental component

Discussion