What is the relationship between probabilistically checkable proofs and SNARKs in modern cryptography?
Answered at 14:00 in How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser) · a16z crypto show
What is the relationship between probabilistically checkable proofs and SNARKs in modern cryptography?
Probabilistically checkable proofs use error-correcting codes to rewrite standard proofs so that if there was an error in the original classical proof, there would be many errors in the new one. This allows checking a proof by probing just a random location to detect errors. SNARKs compress these long proofs using Merkle trees and hash functions so they can be sent and verified while still allowing the verifier to poke at them and discover errors with high probability.
Full answer and detailsRead the whole answer, key facts and every other question from this episode
In short
Probabilistically checkable proofs use error-correcting codes to rewrite standard proofs so that if there was an error in the original classical proof, there would be many errors in the new one.
Shafi Goldwasser, Turing Award-winning cryptographer · How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser) · a16z crypto show · answer at 14:00
Key takeaways
- Probabilistically checkable proofs use error-correcting codes to rewrite standard proofs so that if there was an error in the original classical proof, there would be many errors in the new one.
Quote to remember
“The definition of zero knowledge is in some sense that at the end you will believe what I claim, but you will discover nothing else.”
— Shafi Goldwasser
The full answer · about 2 min
Probabilistically checkable proofs use error-correcting codes to rewrite standard proofs so that if there was an error in the original classical proof, there would be many errors in the new one. This allows checking a proof by probing just a random location to detect errors. SNARKs compress these long proofs using Merkle trees and hash functions so they can be sent and verified while still allowing the verifier to poke at them and discover errors with high probability.
Key facts
- Six submissions and rejections before publication of the GMR zero-knowledge interactive proofs paper
- Two provers used in multi-prover interactive proof systems before reduction to single-prover protocols
- IP equals PSPACE complexity class result derived from interactive proof techniques
People, companies and topics mentioned
More answers from this episode
- 4:03What was the mental poker problem that inspired the invention of zero-knowledge proofs?
- 5:00Why did interaction and randomness become essential to zero-knowledge proof design?
- 6:40What is the simulation paradigm in zero-knowledge proof verification?
- 9:00How did the GMR paper on zero-knowledge interactive proofs face rejection before publication?
- 21:00Why is the SumCheck protocol particularly efficient for building modern SNARKs?