In this blog post, we present Testudo a new near linear-time$^*$ prover SNARK with the following advantages:
Small & Universal Setup: It uses a trusted setup of square-root size — i.e., for an R1CS of size $N$, the trusted setup is of size $O(\sqrt{N})$. For large circuits, this brings the trusted setup material to MBs rather than GBs.
Very fast prover: Estimated to run more than ~5x faster than fastest Groth16 implementation (i.e., Bellperson) for data-parallel computations.
Small Proofs & Fast Verifier: Constant size proofs and verification time.
Uses R1CS, the most widely used approach to writing circuits in deployed libraries. This gives us the following advantages:
(*) Our prover runs $\sqrt{N}$ multi-exps of size $\sqrt{N}$, which is roughly $O(N * \lambda/\log(N))$ group operations with $\lambda >> \log(N)$ for security.
Internals: At its core, our SNARK relies on three carefully combined building blocks:
Testudo has an ongoing implementation using arkworks with a blst integration with GPU support:
Call for participation: We welcome anyone interested to contribute to the Testudo implementation. The project tackles many challenging points and is at the state of the art when it comes to proving R1CS circuits. See the last section for more information!
Why the name Testudo? Testudo was a type of battle formation that ancient Rome adopted, where its soldiers operated “under the hood” of their shields. Testudo, the proof scheme, is similar: a Spartan prover woking under the hood of Groth16.
Our initial motivation for developing Testudo was to improve the SNARKs used in Filecoin. Filecoin requires storage providers to prove to the whole network that they are holding the storage they had initially committed to. The circuit involved has $\approx 2^{30}$ constraints (one of the largest circuits used in practice today) and is verified by Groth16.
The computation is large enough to push current hardware to its limits: the big circuit is actually “broken down” into 10 subcircuits each of size $\approx 2^{27}$, due to limitations on the maximum size of the trusted setup. Also, one issue with Groth16 is the function-specific trusted setup which complicates deployment of new versions of the Filecoin protocol (e.g., a new proof-of-space) since this would require a new circuit. While Filecoin is an interesting specific study-case, issues of this kind may also apply more generally to other deployed systems with similar requirements.
Therefore, our goals were as follows: