🛡️

Testudo

A new proof system enabling larger circuit size, much faster proving time and with universal setup (i.e. new circuits don’t require trusted setup anymore).

Quick Links

🛡️Testudo - 📊 Motivation

🛡️Testudo - 🔥 Current Risks

🛡️Testudo - 🚀 Impact on Filecoin

🛡️Testudo - 📆 Current Expected Improvements

📊 Motivation

Current proofs in the Filecoin protocol use the Groth16 SNARK in the trusted setup. This requires writing the computation being proven as a circuit and then feed it into the SNARK process.

The main limiting factors in this approach are

the size of the structured common reference string CRS (which is linear in the size of the circuit). It forces us to use 10 proof to prove one sector.
Proving time (which is quasilinear in the size of the circuit) and thus requires high cost in hardware and code optimization on hardware

🚀 Impact on Filecoin

Why Testudo in Filecoin?

Unique features of Testudo vs competitors

‣

⭐️ Backward compatible SNARK for sectors data

‣

⭐️ Backward compatible benefits from existing speedups

‣

⭐️ Fast/Easy upgradability of the Filecoin protocol without new trusted setups

‣

⭐️ Verifiable Computing on Filecoin data due thanks to ability to support large circuits

Cost reduction

‣

Expected 4-20x cheaper proving costs for ProveCommit and WindowPoSt

‣

Cost-effective to SnapDeal versus ProveCommit, which unlocks 15EiB for FIL+

‣

eIn practice - SP need 4-20x less hardware (GPU) for same throughput

Filecoin improvements

‣

Time to generate ProveCommit and SnapDeal <1 min instead of 5min

‣

Unlocks new SP cost-saving & use cases protocol upgrades (🎇No Buffer PoRep , 🧩DailyPost )

Why better than Halo2 and similar or new proposals?

All the improvements of Testudo are backward compatible with existing Filecoin proofs
Re-uses all of the optimizations we made for Groth16
Faster than the state of art

📆 Current Expected Improvements

Benchmarks ran on an R1CS instance with $2^{26}$ constraints using the arkwork-rs framework.*

	Groth16 (bellperson)	Testudo81 (predicted - NO optimization, NO GPU)	Testudo77 (predicted - NO optimization, NO GPU)
With 2^26 circuit
Type of Setup	Circuit Specific	Universal	Universal
Setup Size Estimation	19.3 GB	49.1 MB	49.1 MB
Proving	est. 50s (batched)	<190s	<190s
Proof Size	192 bytes	8kB	288 bytes
Verifying	2ms	<10-15ms	TODO
With 1 sector
Proving	883s	TODO	TODO
Proof Size	2kB	8kB	288 bytes
Verifying	<10ms	<10-15ms	TODO
With 100 sectors	with Snarkpack
Proving	883*100 = 24h	TODO	TODO
Proof Size	<20kB	8kB	288 bytes
Verifying	<20ms	<10-15ms	TODO

🔥 Current Risks

‣

(Engineering: Medium) Testudo81 proof size may reduce overall cost savings.

‣

(Engineering: Low) Testudo81 with BLST + GPU optimizations may not be as fast as we thought

‣

✅ solved on 30/01/23 ~~(Reseach: Low) Testudo81/77 requires a new trusted setup protocol that we need to finalize~~

🎯 Workplan

⚠️

The following db is synced automatically with our current weekly SitRep

Open the arrows to discover more

✅ Done ⚪️ TBD 🔵 In Progress 🟡 Needs attention 🔴 Stopped

Name	Status	Quarter	DRI	Date	Goal	Area	Team
Testudo77 v0.1: Initial performance prediction	✅	2022Q4	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo77 v0.2: Basic research done	✅	2022Q4	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo81 v0.3: De-risking Filecoin deployment	✅	2023Q1	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo81 v1: Ready for writing proofs	🔴	2023Q2	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo81 Filecoin Proofs live on testnet	🔴	2023Q2	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo81 Filecoin Proofs live on mainnet	🔴	2023Q3	D Deleted User		🛡️Testudo	Testudo	📖 Research Enablers
Testudo is audited	🔴	2023Q4		August 31, 2023	Testudo81 Filecoin Proofs live on mainnet	Testudo	📖 Research Enablers
Testudo is launched into Filecoin	🔴	2023Q4		September 30, 2023	Testudo81 Filecoin Proofs live on mainnet	Testudo	📖 Research Enablers
Filecoin Proofs are written for Testudo	🔴			May 31, 2023	Testudo81 Filecoin Proofs live on testnet	Testudo	📖 Research Enablers
FIP for adding support to Testudo Proofs	🔴			May 31, 2023	Testudo81 Filecoin Proofs live on testnet	Testudo	📖 Research Enablers
Paper is public	✅	2023Q2		March 1, 2023 → June 19, 2023	🛡️Testudo	Testudo	📖 Research Enablers
New proofs are live in Filecoin Testnet	🔴			June 30, 2023	Testudo81 Filecoin Proofs live on testnet	Testudo	📖 Research Enablers
Add Ability to support circuits	🔴	2023Q1		March 31, 2023	Testudo81 v1: Ready for writing proofs	Testudo	📖 Research Enablers
Verification circuit for Testudo	🔴	2023Q1		March 31, 2023	Testudo81 v1: Ready for writing proofs	Testudo	📖 Research Enablers
More optimizations if needed	🔴	2023Q2		April 30, 2023	Testudo81 v1: Ready for writing proofs	Testudo	📖 Research Enablers
Aggregation feature implemented	🔴	2023Q2		June 30, 2023	Testudo81 v1: Ready for writing proofs	Testudo	📖 Research Enablers
Trusted setup is finalized	🔴	2023Q2		May 31, 2023	Testudo81 v1: Ready for writing proofs	Testudo	📖 Research Enablers
Can we design a Trusted Setup for Testudo?	✅	2023Q1		February 28, 2023	Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Backward compatible solution BLS12-381 designed	✅	2023Q1		February 28, 2023	Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Can Bellperson speed ups make Testudo 4x faster than Groth16? (blst+GPU) (low risk)	✅	2023Q2	D Deleted User	February 28, 2023	Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Will the final proof size and verification time be acceptable for Filecoin?	🔴	2023Q2	D Deleted User	March 31, 2023	Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Small universal trusted setup	🔴	2023Q1		January 31, 2023	Testudo77 v0.2: Basic research done	Testudo	📖 Research Enablers
Establish if the protocol can be used to replace current FIL proofs	✅	2022Q4			Testudo77 v0.1: Initial performance prediction	Testudo	📖 Research Enablers
Compare protocol to other SNARKS with universal trusted setup	✅	2022Q4			Testudo77 v0.1: Initial performance prediction	Testudo	📖 Research Enablers
🛡️Testudo	✅	2023Q2	D Deleted User			Testudo	📖 Research Enablers
Blog post on Testudo	✅	2023Q1		February 27, 2023 → March 27, 2023	Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Theory: Aggregation protocol	✅	2023Q2			Testudo81 v0.3: De-risking Filecoin deployment	Testudo	📖 Research Enablers
Code documentation	🔴	2023Q1	Mara Mihali	February 17, 2023	Testudo77 v0.2: Basic research done	Testudo	📖 Research Enablers

📈 Progress so far

Repo: Spartan

This table compares Testudo81 with Groth17 using arkworks.

	Groth16 on bls12-377 with Arkworks	Testudo77 v0.1 (2022-12 demo)	Testudo77 v0.2 (2023-01 demo)	Testud81 v0.3 (compatible with bls12-381)
Type of Setup	Circuit-Specific	Universal	Universal	Universal
Setup Size Estimation	19,3 GB	48 MB (Groth16) + 9.6 GB (PST) = 9.648 GB	48 MB (Groth16) + 1.1 MB (PST)= 49.1 MB
Proving	463s 100% multithreaded	400s 50% multithread	~~230s~~ 163s 50% multithread
Proof Size	192 bytes	3.6 KB	18.1 KB
Verifying	8ms multithreaded	27s 50% multithread	18ms 50% multithread

👥 People

Research:

Rosario Gennaro (50%)
Matteo Campanelli (20%)
Justin Thaler (Advisor, 5%)

Engineering:

Nicolas Gailly (50%)
TBD

Testudo Design Doc