Proofs of proofs: incremental verifiability from recursion and accumulation
summary
Builds incremental verifiability for t‑step computations by three concrete paradigms: starting from SNARKs with subliminal verification (needs a strong extractor/knowledge assumption so the recursive verifier fits inside the proved circuit), moving to atomic accumulation where an accumulator stays constant size and a cheap per‑step verifier plus one expensive decider yields O(t) cheap checks and one final heavy check, and finally split accumulation that accepts large non‑succinct proofs by reading only small instance parts; preserves zero‑knowledge and post‑quantum security under the stated assumptions and has prototype implementations (ArcWorks) using curve cycles.
AI-written summary · about
chapters (8)
- 0:00Start
- 3:11Incrementally Verifiable Computation
- 11:10Instantiate the Weaker Building Blocks from Simpler Tools
- 13:08Ivc Prover
- 14:52Atomic Accumulation
- 19:07Split Accumulation
- 21:13Cycles of Elliptic Curves
- 21:36Recursion Threshold
related talks
01h 25mIntroduction to Verifiable Computing
33mA Wishlist for Verifiable Computation: An Applied CS Perspective
31mSequential Composition of Rational Proofs
41mGKR based Zero-Knowledge Proofs
25mLegoSNARK: Modular Design and Composition of Succinct Zero Knowledge Proofs
50mTrust but Verify: Scaling Deductive Verification with Abstract Interpretation
51mWhy you shouldn't trust me
01h 03mProofs, Knowledge, and Computation