[Guest: Barry Whitehat] PLONK & the Future of ZK

Description

In this session, Barry Whitehat discusses the next generation of ZKPs including Plookup and recursive ZKPs, and what is possible with next generation of zktooling.

🔑 A commitment scheme allows you to publicly publish a value (called a commitment) that binds you to some message without revealing the message itself. A polynomial commitment allows you to commit to a polynomial such that someone else can verify the claimed evaluations of the committed polynomial. A polynomial commitment can be thought of as committing to a list of numbers (i.e. a polynomial’s coefficients).

The construction of ZK proof systems rely on some form of generated randomness (i.e. public parameters), but it is crucial that this randomness remains secret and cannot be re-created — otherwise, the security of the system would be compromised. In practice, trusted setup is a way for many parties to contribute to such secret randomness and thus the security of a cryptographic protocol. Each party contributes their own secret value to the trusted setup process and doesn’t tell anyone else what their contribution was.

A polynomial opening is created using public parameters from the trusted setup + polynomial commitments + elliptic curve pairings. This opening can be used to build constraints and check public inputs. For example, to build the constraint $a * b = c$ (where $a(x)$, $b(x)$, and $c(x)$ are polynomials created by the prover), the prover first commits to $a$, $b$, and $c$ using polynomial commitments. Then, the verifier sends a random value $r$ and asks the prover for polynomial openings of $a$, $b$, and $c$ at $r$. The verifier verifies that $a * b = c$ by checking $a(r) * b(r) - c(r) = 0$. This is possible due to the Schwartz Zippel lemma, which essentially says that checking one point of the polynomial is equivalent to checking all points on the polynomial with high probability.

Why is all of this important? In ZK protocols, the information you want to prove is encoded into a polynomial. The goal of the prover is to show that it knows some secret polynomial that evaluates to 0 for specific values chosen by the verifier (which are encoded as another polynomial). In other words, the prover needs to show that this secret polynomial has certain roots. The prover does this by showing it knows a quotient polynomial $Q(x)$ such that if the secret polynomial $P(x)$ is divided by $Q(x)$, the result is the polynomial provided by the verifier. The ZK part comes from the fact that we are using some pretty magical math tools like pairings and the power of collective security from the trusted setup!

In recent years, ZK proof systems have been modified for different use cases. Plonk is a highly efficient and general-purpose zk-SNARK proof system that uses Plookup — which translates polynomials into pre-computed lookup tables for fast computation. Other extensions include ultra plonk, mobile proofs, and recursive proofs.

Slides Link(s)

https://docs.google.com/presentation/d/1YwT_x2LI7X3izMiueHhnCsfNvnCHGcHAirQwsqNfzf8/edit?usp=sharing

Additional resources

For more explanation on PLONK, check out Vitalik's blog post.

Check-in Questions

(1) Forging Polynomials: Let's suppose the prover didn't commit to a polynomial before the verifier sends evaluation points. What is problematic about this construction?

(2) Role of random value $r$: Why does the verifier send a random value $r$ to the prover to check that the $a * b = c$ constraint is satisfied? Why is it important that $r$ is random?

Sample Answers

(1) Forging Polynomials: The prover needs to show that they know some polynomial that satisfies some constraints without revealing the polynomial itself. To show proof that the polynomial satisfies these constraints, the prover must provide polynomial openings which require evaluations at points the verifier sends. Without committing to the polynomial beforehand, the prover could simply construct a polynomial that satisfies the constraints at the given evaluation points — and thus forge a proof that the verifier accepts.

(2) Role of random value $r$: The verifier generates a random value $r$ to check that the evaluations of the $a$, $b$, and $c$ polynomials at $r$ are equivalent to $a(r) * b(r) - c(r) = 0$. The reason the verifier need to send a random value is so the prover doesn’t know $r$ ahead of time — otherwise, the prover could falsify the proof by choosing polynomials (different than the ones they committed to) that also satisfy $a(r) * b(r) - c(r) = 0$.

Learning Group 1 lecture video and slides for reference.