[Resource Topic] 2023/1240: Improved SNARK Frontend for Highly Repetitive Computations

Welcome to the resource topic for 2023/1240

Improved SNARK Frontend for Highly Repetitive Computations

Authors: Sriram Sridhar, Yinuo Zhang


Modern SNARK designs typically feature a frontend-backend paradigm: The frontend compiles a user’s program into some equivalent circuit representation, while the backend calls for a SNARK specifically made for proving satisfiability of the circuit. While the circuit may be defined over small fields, the backend prover often needs to lift the computation to much larger fields for achieving soundness. This gap results in concrete overheads, for example, when representing a SHA-256 program as a circuit with pairing-based backend SNARKs.

For a class of computations that are \textit{highly repetitive}, we propose an improved frontend that partially bridges this gap. Compared with existing works, our frontend yields circuit representations defined over larger fields but of smaller size. Our implementation shows that for SIMD computation with \approx 180 SHA-256 instances, our improved frontend improves prover runtime by over 2.6 \times and reduces memory usage by over 1.3 \times.

Central to our result and of independent interest, is an efficient technique for proving non-native modulo arithmetic.

ePrint: https://eprint.iacr.org/2023/1240

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .