The GKR Protocol
65610.csail.mit.edu · 2,642 words · saved by 1 readers
N/A
The GKR Protocol Notes by Yael Kalai MIT - 6.5610 Lecture 12 (March 13, 2024) Warning: This document is a rough draft, so it may contain bugs. Please feel free to email me with corrections. Outline • Warmup for the GKR protocol • Low-degree Extension • The GKR protocol Intuition for the GKR protocol Given a circuit C of depth D and size S, an input x ∈ {0, 1}n and an output y, the prover needs to convince the verifier that C ( x ) = y. In other words, the verifier wants to catch the prover if y is incorrect. Here is a simple idea: The verifier will ask the…
related reading
- Zero Knowledge Proofs: An illustrated primer – A Few Thoughts on Cryptographic Engineeringblog.cryptographyengineering.com
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- 1482.pdfeprint.iacr.org
- Zero-knowledge proof - Wikipediaen.wikipedia.org
- Lecture 14: Zero knowledge proofsboazbarak.org
- small-sumcheck.pdfpeople.cs.georgetown.edu
- A Zero Knowledge Sumcheck and its Applicationsarxiv.org
- 118.pdfeprint.iacr.org
- STARKs, Part II: Thank Goodness It's FRI-dayvitalik.eth.limo
- Math & Engineeringxn--2-umb.com
- 17 misconceptions about SNARKs - a16z cryptoa16zcrypto.com
- Computer Scientists Figure Out How To Prove Lies | Quanta Magazinequantamagazine.org