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
- This decreases the time to onboard new deals in CC sector to be <1 min (currently 5min)
Time and Cost reduction
- SNARK ProveCommit cost: 10-30% the cost of adding a new sector on-chain
- 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
Filecoin improvements
- 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
- All the improvements of Testudo are backward compatible with existing Filecoin proofs
- Re-uses all of the optimizations we made for Groth16
- Testudo would enable NI-PoRep which is currently the best No Buffer PoRep solution
- 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 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
- 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.
- 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.
Lowbecause 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
- Establish if the protocol can be used to replace current FIL proofs
- Compare protocol to other SNARKS with universal trusted setup
- 🟡 2023Q1: Testudo81 v0.3: De-risking Filecoin deployment
- ⚪️ 2023Q2: Testudo81 v1: Ready for writing proofs
- ⚪️ 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-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
Main solutions explored and chosen solution https://www.notion.so/pl-strflt/Options-for-Testudo-on-BLS12-381-310b0a529f5542a1b0a1bdf214f55e2c
VMX working on GPU porting
❓ Decision whether the final proof size / verifier time of chosen Testudo81 solution is viable
Step 1: Estimate it ✅
Step 2: Implement it
Paper will be submitted at CRYPTO2024
📈 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 | ||
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