ZKP Lecture 5: The Plonk SNARK (Part 1)

This lecture is part of a course on SNARKs and focuses on constructing a widely used SNARK called Plonk. The lecture begins with a review of how SNARKs are typically built, starting from a polynomial commitment scheme. It explains the KZG polynomial commitment scheme, detailing the setup procedure, the importance of deleting the random field element tau, and how to commit to a polynomial using global parameters. The lecture further explains how to perform an evaluation proof, including the computation of the quotient polynomial and the verifier's role. It also covers properties of the KZG scheme, such as its ability to handle k-variate polynomials, efficient batch proofs, and linear time commitments using Lagrange interpolation. The lecture concludes by discussing the limitations of KZG, including the trusted setup requirement and the size of global parameters, and briefly introduces the Dory commitment scheme as an alternative. It also touches on applications of polynomial commitment schemes beyond SNARKs, such as replacing Merkle trees with Verkle trees for vector commitments.