Error-Correcting Codes That Enable Efficient SNARKs

on YouTube ↗01h 00m

" summary

Claim: building SNARKs from linear error-correcting codes yields very fast provers (operations limited to field add/mul and hashes) and plausible post‑quantum security, but proof size hinges on code distance and Merkle paths. Tools used: IOPPs/IOPs of proximity, Fiat–Shamir, Merkle trees, polynomial commitments, and code switching (e.g., Blaze) between RAA and Reed–Solomon. Concrete findings: prover cost ≈ encoding time, Reed–Solomon gives best proximity gaps, and RAA needs rows ≥ 2^20 to reach distance ≈0.19.

AI-written summary · about

" chapters (14)

1. 0:00Welcome
2. 0:43SNARKs from error-correcting codes
3. 2:12Error-correcting codes
4. 5:27Talk outline
5. 7:36Interactive proofs and PCPs
6. 9:08Interactive oracle proofs
7. 11:42Interactive oracle proofs of proximity
8. 16:16Non-interactive IOPPs
9. 20:33SNARK costs
10. 24:05SNARK-friendly code classes
11. 36:38SNARK-friendly codes
12. 46:31Code switchable codes
13. 53:34Prover vs verifier trade-offs
14. 57:24Open questions

" related talks

• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 39mPrivacy and Evolution of SNARKsAriel G. Gabizon, Lucas Nuzzi, Eugene Leventhal, Aleksandr Vlasov · Smart Contract Summit #1 2021
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 23mSonic: Nearly Trustless SNARK SetupsSean Bowe · Zcon1: Zero to Privacy Hero 2019
• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 52mFaster, Smaller, Weaker, DarkerBenedikt Bunz · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 18mA Selection of Pairing Based zk-SNARKsMary Maller · Zcon1: Zero to Privacy Hero 2019
• 01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other TopicsAllison Bishop · The Mathematics of Modern Cryptography