Campanelli, M; Gailly, N; Gennaro, R; Jovanovic, P; Mihali, M; Thaler, J; (2023) Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. In: International Conference on Cryptology and Information Security in Latin America LATINCRYPT 2023: Progress in Cryptology – LATINCRYPT 2023. (pp. pp. 331-351). Springer: Cham, Switzerland.

Preview

Text testudo.pdf - Accepted Version Download (536kB) | Preview

Abstract

We present 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. Testudo is based on a variant of Spartan [28]–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 [25] and IPPs [9]. To achieve constant-size SNARK proofs in Testudo we then combine our PCS openings proofs recursively with a Groth16 SNARK. We also evaluate Testudo 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 [6], since opening computations are heavily parallelizable and operate on smaller polynomials. Furthermore, a Testudo proof for a witness of size requires a setup of size only tens of kilobytes). Finally, we show that a Testudo variant for proving data-parallel computations is almost 10x faster at verifying Poseidon-based Merkle tree opening proofs than the regular version.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as XMLJSONCSV

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item