Applied Crypto #2: Polynomial Commitments

Description

Yi Sun talks about polynomial commitments.

🔑 For polynomial $P$ and pair $(x, y)$, a polynomial commitment allows the prover to show that $P(x) = y$, such that the verifier can verify this evaluation without knowing what $P$ actually is.

A polynomial commitment scheme starts with a trusted setup to generate public parameters used throughout the protocol. Then, the prover commits to a polynomial $P$ and is verified to be a valid commitment to $P$. To create a polynomial opening, the prover shows that $P(x) = y$ such that this evaluation can be checked by the verifier. To construct a polynomial $P$ with a series of desired points, we use Lagrange interpolation — which basically means that you draw a line through all of the points you want in the polynomial.

There are different ways to implement polynomial commitment schemes. In this lecture, Yi discusses the Kate polynomial commitment scheme (which uses elliptic curve pairings) and the Fast Reed-Solomon IOP (FRI)-based commitment scheme (which uses merkle trees). While the Kate commitment schemes has a trusted setup (and FRI-based doesn’t), the proof size is smaller and independent of the size of the polynomial, thus making verification time more efficient.

Slides Link(s)

https://drive.google.com/file/d/1vd5sgMUgZh3t3nP28zjfEE2h0oWOeCmw/view

Additional resources

More on Polynomial commitment schemes.