ZKP MOOC Lecture 4: Interactive Proofs

TL;DR

The sum-check protocol is an interactive proof that allows the prover to offload the computation of evaluating a polynomial to the verifier.

Transcript

JUSTIN THALER: Hello. My name is Justin Thaler. And I will be presenting the fourth lecture of this MOOC on zero-knowledge proofs. This lecture describes SNARKs that are designed using so-called interactive proofs as the key building block. So let me begin by reminding you, going back to Dan's lecture, lecture 2, what is a SNARK. Of course, this no... Read More

Key Insights

• 📣 Interactive proofs and SNARKs:
• 🏛️ SNARK is an acronym for succinct non-interactive argument of knowledge, which is a short and fast-proof system that proves the truth of a statement.
• 📌 The trivial proof system for verifying a claim is to specify the message the prover knows, but this can be inefficient if the message is large.
• 🔑 SNARKs are non-interactive and publicly verifiable, meaning they don't require back-and-forth interaction and can be checked by anyone in the future.
• 💻 Interactive proofs are different from SNARKs as they are statistically sound and require interaction between the prover and verifier.
• 🔬 The difference between standard soundness and knowledge soundness is that the latter requires the prover to prove they actually know the witness, while the former only establishes the existence of such a witness.
• ⚖️ SNARKs are arguments, not proofs, meaning they have weaker soundness properties and are only sound against computationally bounded cheaters.
• 🛠️ Multivariate polynomials and their extensions, such as multilinear extension polynomials, are commonly used in interactive proofs because they allow for efficient verification and computation.
• 💡 The sum-check protocol is an interactive proof that reduces the computational burden on the verifier by delegating the work to the prover and requiring only a single evaluation of a polynomial.

Questions & Answers

Q: How does the sum-check protocol reduce the prover's workload in computing the sum of a polynomial's evaluations?

The sum-check protocol allows the prover to offload the computation of evaluating the polynomial to the verifier, reducing the prover's workload. Instead of computing all the evaluations and summing them, the prover simply sends a univariate polynomial to the verifier, who then checks if it is consistent with the true answer. This allows the prover to avoid making all the computations on their own and rely on the verifier to perform them efficiently.

Summary & Key Takeaways

• The sum-check protocol is designed to solve the problem of evaluating an l-variate polynomial using a more efficient approach.

• The protocol involves the prover sending a univariate polynomial to the verifier, who then checks if it is consistent with the true answer.

• The verifier also checks if the true answer is consistent with the polynomial sent by the prover.

• The protocol allows the prover to offload the computation of evaluating the polynomial to the verifier, reducing the prover's workload.