GKR based Zero-Knowledge Proofs
summary
Claims a practical blueprint that turns GKR-style low-degree extension encodings plus the sum-check protocol into doubly efficient interactive proofs where the prover runs in roughly poly(S) time, the verifier runs in time proportional to circuit depth (and polylog size per sum-check), and round complexity is about the circuit depth. Adds an interactive-PCP layer and compiles to succinct zero-knowledge arguments using polynomial commitments or Merkle-like shrinking commitments. Implementations exist (pairing-friendly, polynomial-commitment based) and work, but depth dependence remains unless the computation is squashed to configurations or moved to multi-prover models.
AI-written summary · about
chapters (6)
- 0:00Introduction to GKR
- 6:54The GKR protocol mechanics
- 14:40Handling gate types
- 19:22GKR for NP and PCP
- 25:13Constructing SNARKs
- 31:39Overcoming depth limitations
related talks
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
01h 03mProofs, Knowledge, and Computation
51mWhy you shouldn't trust me
59mCommit-and-Prove Zero-Knowledge Proof Systems and Extensions
44mStandardizing Zero Knowledge Proofs - Keynote
25mHigh-Speed zkSNARKs without Trusted Setup
54mVerification Dilemmas, Law, and the Promise of Zero-Knowledge Proofs
20mSNARKs from the sum-check protocol