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,
Mara Mihali, Aztec Labs
Justin Thaler, Georgetown University, a16z crypto research

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.

Available format(s)
Public-key cryptography
Publication info
snarkspolynomial commitments
Contact author(s)
matteo @ protocol ai
nikkolasg @ protocol ai
rosario gennaro @ protocol ai
mara @ aztecprotocol com
justin thaler @ georgetown edu
2023-06-20: approved
2023-06-19: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.