Constant-Round Arguments from One-Way Functions
summary
Assumes only one-way functions and constructs a constant-round doubly-efficient argument for any language with log-space-uniform, polynomial-size circuits of linear depth: verifier time and communication are n^{1+σ} for any small σ, honest prover runs in polynomial time, and rounds do not scale with circuit depth. Key tools are locally openable commitments built from universal one-way hash trees and a batching/translation step that turns committed layer roots into low-degree-encoding claims, replacing collision-resistant hashes used by Kilian.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:17Interactive Proof/Argument [GMR85,BCC88]
- 6:14Main Result: New Theorem ["flat GKR"]
- 8:21Comparison to prior work: DE arguments for poly-size depth-D
- 12:04GKR Overview
- 15:35Commit and parallelize?
- 26:22The Commitment Scheme
- 34:23Layer Subprotocol
- 40:22Summary and Open Questions
related talks
01h 01mLocal Proofs Approaching the Witness Length
01h 03mLinear-Time Zero-Knowledge Arguments with Logarithmic Proof-Size
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
23mSonic: Nearly Trustless SNARK Setups
01h 12mAn Introduction to Commitment-Based Succinct Arguments
01h 09mProofs - Practice 1
33mSecret Sharing, Slice Formulas, and Monotone Real Circuits
01h 00mError-Correcting Codes That Enable Efficient SNARKs