Paper 2023/1240
Improved SNARK Frontend for Highly Repetitive Computations
Abstract
Modern SNARK designs usually 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 circuit satisfiability. 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 proving SHA2 programs with pairing-based SNARKs. For a class of computations that are \emph{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 $\approx 100$ iterations of SHA2-256 instances, our improved frontend boosts prover runtime by over $3.8 \times$. Central to our result and of independent interest, is an efficient technique for proving non-native ring arithmetic.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- zero knowledge proofs
- Contact author(s)
-
srirams @ berkeley edu
yinuo yz @ gmail com - History
- 2023-10-19: revised
- 2023-08-16: received
- See all versions
- Short URL
- https://ia.cr/2023/1240
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1240,
author = {Sriram Sridhar and Yinuo Zhang},
title = {Improved SNARK Frontend for Highly Repetitive Computations},
howpublished = {Cryptology ePrint Archive, Paper 2023/1240},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1240}},
url = {https://eprint.iacr.org/2023/1240}
}
