SNARKs from the sum-check protocol
summary
Explains how the sum-check protocol underpins a three-step snark design: produce a polynomial IOP + polynomial commitment, apply Fiat–Shamir, and get a succinct argument. Claims a verifier runs essentially linear time (just reads input and evaluates a few random points) while the prover runs near the cost of solving the problem; univariate proofs give O(√n)-length proofs or constant-size proofs when combined with KZG but require constant-size proofs with trusted setup. The multivariate sum-check yields proof length proportional to total degree (often much smaller) and logarithmic-size witnesses for circuit satisfiability; examples include applications to disjointness and triangle counting, and systems like Spartan follow this paradigm.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:22Key Paradigm for Backend Design
- 1:41Interactive Proofs (IPS)
- 2:20Doubly-Efficient Interactive Proof
- 3:02Checking if two polynomials are equal
- 4:02The Sum-Check Protocol, Simplified Say we want to design an IP computing some function
- 7:58Pros and cons
- 9:15Sum-Check Protocol (LFKN90)
- 11:50Arithmetic Circuit Satisfiability
- 12:37The Start of the Polynomial-IP
- 14:24The Polynomial IP for Circuit-SAT
related talks
26mzk-SHARKs: Combining Succinct Verification and Public Coin Setup
25mLegoSNARK: Modular Design and Composition of Succinct Zero Knowledge Proofs
41mGKR based Zero-Knowledge Proofs
51mWhy you shouldn't trust me
25mSonic: zkSNARKs from Linear Size Universal and Updatable SRS
17mSNARK Flipper. FLIP & Prove multiple instances efficiently
25mSuccinct Proofs in Ethereum
28mNotes from the SNARKonomicon: Techniques for Writing SNARK Programs