Welcome to the resource topic for 2023/961
Title:
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup
Authors: Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler
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.
ePrint: https://eprint.iacr.org/2023/961
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 .