Listenly

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

— questions searchable right now

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.

Shafi Goldwasser on a16z crypto showAll answers from this podcast →
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

Zero-knowledge proofsMental poker problemInteractive proofsProbabilistically checkable proofs (PCP)SumCheck protocolSNARKsMerkle treesFiat-Shamir transformation

More answers from this episode

 ·  All answers from a16z crypto show →
—
—
0:00
0:00