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

📊 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?

User Experience

‣

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

This decreases the time to onboard new deals in CC sector to be <1 min (currently 5min)

Time and Cost reduction

‣

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

SNARK ProveCommit cost: 10-30% the cost of adding a new sector on-chain

‣

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

SNARK SnapDeal cost: same as ProveCommit - expensive for most miners
Having lower cost SnapDeal enables the CC-sector → SnapDeal pipeline for efficient mining as a service

‣

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

Filecoin improvements

‣

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

Stepping stone for more upgrades later on with a much lower cost
Enables fast proving of new poreps which can be harder to prove (NI porep) which is at the heart of Filecoin

‣

Backward compatible SNARK for existing sectors

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

‣

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

Testudo would enable NI-PoRep which is currently the best No Buffer PoRep solution

‣

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

Testudo can support large circuits which means we can do higher amount computation at a cheaper cost

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.

Changing Testudo to be backward compatible (Testudo81) may end up leading to worse conditions than original testudo (Testudo77 using new curve)
Medium because prover time is likely to still be good, but proof size will increase. Different solutions are being tracked.

‣

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

Once using optimizations + GPU code, may not be faster than our super optimized Filecoin proof stack
Low because other companies (e.g. Espresso Systems) are moving to similar proof system, lot of optimizations w/ GPU landed recently (zkPrize competitions). It is believed by the community to give the fastest prover ever.

‣

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

~~Low~~ ~~because it is very similar to Groth16 (current Filecoin trusted setup) and our researchers feel 90% confident to find a solution~~
The protocol has been written and we show it is totally doable and simple (similar to trusted setup from Ethereum KZG ceremony)

🎯 Workplan

‣

✅ 2022Q4: Testudo77 v0.1: Initial performance prediction

Establish if the protocol can be used to replace current FIL proofs
Compare protocol to other SNARKS with universal trusted setup

‣

✅ 2022Q4: Testudo77 v0.2: Basic research done

‣

✅ 2023-02: Small universal trusted setup

~~Implement the MIPP proving and verification (50%)~~

🟡 2023Q1: Testudo81 v0.3: De-risking Filecoin deployment

‣

✅ 2023-02: Remove Trusted Setup risk

‣

✅ 2023-02: Backward compatible solution BLS12-381 designed

Main solutions explored and chosen solution https://www.notion.so/pl-strflt/Options-for-Testudo-on-BLS12-381-310b0a529f5542a1b0a1bdf214f55e2c

‣

🟡 2023-02: Bellperson speed ups are ported to Testudo

~~Exploratory doc on the topic completed~~

Implementation of wrapper testudo ↔ blst completed (50%)

‣

🟡 2023-02: Optimization using GPU

VMX working on GPU porting

‣

⚪️ 2023-03: Benchmark implementation of Testudo81 (potentially optional)

❓ Decision whether the final proof size / verifier time of chosen Testudo81 solution is viable

Step 1: Estimate it ✅

Step 2: Implement it

Implement circuit building features in Testudo (need 2nd engineer OR longer VMX time)

Implement Testudo81 verifier in proof (need Mara)

⚪️ 2023Q2: Testudo81 v1: Ready for writing proofs

‣

⚪️ 2023-03: Add Ability to support circuits

‣

⚪️ 2023-03: Verification circuit for Testudo

‣

⚪️ 2023-04: More optimizations if needed

‣

⚪️ 2023-06: Aggregation feature implemented

‣

⚪️ 2023-05: Trusted setup is finalized

Write trusted setup protocol on paper

Implementation

Running it

⚪️ 2023Q2: Testudo81 Filecoin Proofs live on testnet

⚪️ 2023-05: Filecoin Proofs are written for Testudo
⚪️ 2023-05: FIP for adding support to Testudo Proofs

‣

⚪️ 2023-05: Paper is public

Paper will be submitted at CRYPTO2024

⚪️ 2023-06: New proofs are live in Filecoin Testnet

⚪️ 2023Q3: Testudo81 Filecoin Proofs live on mainnet

⚪️ 2023-08: Testudo is audited
⚪️ 2023-09: Testudo is launched into Filecoin

📈 Progress so far

Repo: ‣

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