Logo

    CryptoNet is a Protocol Labs initiative.

    🛡️

    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
    • All the improvements of Testudo are backward compatible with existing Filecoin proofs
    • Re-uses all of the optimizations we made for Groth16
    ‣
    ⭐️ Backward compatible benefits from existing speedups
    ‣
    ⭐️ 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
    Security mitigation
    Model how much not having this is costing
    ‣
    ⭐️ 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

    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
    ‣
    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
    • This decreases the time to onboard new deals in CC sector to be <1 min (currently 5min)
    ‣
    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

    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 2262^{26}226 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

    ⚠️
    The following db is synced automatically with our current weekly SitRep

    Open the arrows to discover more

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

    🚩
    Milestones

    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
    U
    Undefined
    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
    U
    Undefined
    February 27, 2023 → March 27, 2023
    Testudo81 v0.3: De-risking Filecoin deployment
    Testudo
    📖 Research Enablers
    Theory: Aggregation protocol
    ✅
    2023Q2
    U
    Undefined
    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: SpartanSpartan

    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

    No access