Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup

Matteo Campanelli; Nicolas Gailly; Rosario Gennaro; Philipp Jovanovic; Mara Mihali; Justin Thaler

Paper 2023/961

Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup

Matteo Campanelli, Protocol Labs

Nicolas Gailly, Protocol Labs

Rosario Gennaro, CCNY, Protocol Labs

Philipp Jovanovic, UCL, p.jovanovic@ucl.ac.uk

Mara Mihali, Aztec Labs

Justin Thaler, Georgetown University, a16z crypto research

Abstract

We present , a new FFT-less SNARK with a near linear-time prover, constant-time verifier, constant-size proofs and a square-root-size universal setup. 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 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 , 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 proof for a witness of size requires a setup of size only ( tens of kilobytes). Finally, we show that a variant for proving data-parallel computations is almost 10x faster at verifying Poseidon-based Merkle tree opening proofs than the regular version.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: snarks polynomial 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}
}