Limber, Low Overhead SNARKs for Integers from Any PCS
Lucas Xia
Abstract:
In real-world applications of SNARKs, non-native arithmetic, the emulation of computation outside of the specified SNARK field, is a key bottleneck. It introduces large overheads, and proof system designers often resort to non-standard SNARK-friendly hash-functions or other means like elliptic curve cycles to mitigate its costs. Besides performance concerns, non-native circuit arithmetization is also a major cause of implementation errors. In a collection of 27 critical bugs in real world ZK systems (0xPARC/zkbugtracker), 9 were related to non-native arithmetization. We tackle these challenges by constructing a minimal overhead SNARK for integer computation that generically handles non-native arithmetic. We follow the recipe of Zaratan (PKC 26), which proves an integer relation such as a * b = c + u * m by fingerprinting - reducing it to the same relation but over a randomly sampled prime field. Realizing this recipe requires an integer mod-PCS that commits to integer polynomials and opens their evaluations modulo a random prime, which is crucially chosen after the underlying PCS's setup and commitment phases. Our central contribution is Limber, the first practical integer mod-PCS construction that asymptotically has o(1) multiplicative commitment overhead and can be instantiated with any standard field polynomial commitment scheme, including ones over small fields. Combining Limber with a PIOP for integer R1CS over the random prime yields our SNARK. We demonstrate its practicality by implementing our scheme and showing that we can prove RSA arithmetic more than 15x faster than prior circuit-based approaches. This is joint work with Jessica Chen, Wilson Nguyen, and Benedikt Bünz.
Bio:
Lucas Xia is a second-year PhD student at NYU advised by Benedikt Bünz. His research focuses on verifiable computation, particularly efficient proof system constructions and applications. He previously received an MS in Computer Science from Stanford University and a BS in Computer Science from UCLA.