Paper 2023/961
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup
Abstract
We present $\mathsf{Testudo}$, a new FFT-less SNARK with a near linear-time prover, constant-time verifier, constant-size proofs and a square-root-size universal setup. $\mathsf{Testudo}$ is based on a variant of Spartan~\cite{C:Setty20}—and hence does not require FFTs—as well as a new, fast multivariate polynomial commitment scheme (PCS) with a square-root-sized trusted setup that is derived from PST (TCC 2013) and IPPs (Asiacrypt 2021). To achieve constant-size SNARK proofs in $\mathsf{Testudo}$ we then combine our PCS openings proofs recursively with a Groth16 SNARK. We also evaluate our construction and its building blocks: to compute a PCS opening proof for a polynomial of size $2^{25}$, our new scheme opening procedure achieves a 110x speed-up compared to PST and 3x compared to Gemini (Eurocrypt 2022), since opening computations are heavily parallelizable and operate on smaller polynomials. Furthermore, a $\mathsf{Testudo}$ proof for a witness of size $2^{30} (\approx 1\,GB)$ requires a setup of size only $2^{15}$ ($\approx$ tens of kilobytes). Finally, we show that a $\mathsf{Testudo}$ variant for proving data-parallel computations is almost 10x faster at verifying $2^{10}$ Poseidon-based Merkle tree opening proofs than the regular version.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- snarkspolynomial commitments
- Contact author(s)
-
matteo @ protocol ai
nikkolasg @ protocol ai
rosario gennaro @ protocol ai
mara @ aztecprotocol com
justin thaler @ georgetown edu - History
- 2023-06-20: approved
- 2023-06-19: received
- See all versions
- Short URL
- https://ia.cr/2023/961
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/961, author = {Matteo Campanelli and Nicolas Gailly and Rosario Gennaro and Philipp Jovanovic and Mara Mihali and Justin Thaler}, title = {Testudo: Linear Time Prover {SNARKs} with Constant Size Proofs and Square Root Size Universal Setup}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/961}, year = {2023}, url = {https://eprint.iacr.org/2023/961} }