Some Notes on Polynomial Commitment in Zero Knowledge Proofs

Encode Club zkEVM Bootcamp (presented by ZKsync) wrapped up about a week ago. Although I’ve had lots of exposure to polynomials, discrete elliptic curves, and finite fields, it took me longer to wrap my head around the central feature of Zero Knowledge Proofs (ZKPs)—how did they prove the correctness of a computation without the Verifier having to retrace all the computational steps, really?? Here, I explain the final pieces that explained it for me.

Zero Knowledge Proofs (ZKPs) are exciting for their applications to privacy. As with other types of cryptographic protocols, they can allow parties who do not trust one another to work together; they’re being increasingly used to enable scalability and privacy on blockchains. Technical introduction from Vitalik’s blog (archived).

The Polynomial Commitment Scheme (PCS) is the key component of the proving system that allows the Verifier to be confident that a statement by the Prover is true, without the Verifier needing to re-derive the statement, step by step. The proof can also depend on information which is known only by the Prover, called the witness.

Polynomials are used by many error-detecting and correcting codes such as CRC and Reed-Solomon because they can be used to make errors more obvious to the receiver/decoder. This property of polynomials is known as “error amplification”. More formally, if we have two distinct (non-equal) polynomials of degree at most d, they can intersect at no more than d points. In essence, while it would be possible to create a convoluted, malicious, high-degree polynomial M(x) to coincide with most of the same points as our honest polynomial P(x), M(x) would have to be of much higher degree than P(x); such a malicious polynomial would be detected in the low-degree testing step, causing the proof to be rejected by the Verifier. However, while the degree of polynomials in an error-detecting/correcting scheme is settled ahead of time, in Zero Knowledge proof systems low-degree testing requires additional, complicated steps, for example FRI, Kate, or bulletproofs. Fiat-Shamir, which is the standard way of making proofs non-interactive, involves committing to a Merkle root r, then using that r as the entropy to choose which Merkle branches will be provided in the proof. Zero Knowledge Proofs, like most other types of cryptographic systems, rely on probabilistic proofs up to a specified security level (for example, 128 bits), and are performed on finite fields.

So in a nutshell, a proof must have:

1. Proof that the Prover knows a polynomial. This includes a Merkle root, and several Merkle branches (perhaps 16 or so; see Schwartz–Zippel lemma) as chosen by Fiat-Shamir. Each Merkle branch contains an evaluation of the polynomial at a randomly-chosen point.
2. Constraints. These are the essence of the statement which is being proven; they must be checked/enforced by the Verifier.
3. Proof that the polynomial is of low degree, usually taken to be < 10^8. Applications that need more than this, such as zkVMs, normally use proof aggregation to make the individual proofs smaller.

The explanation that most helped me was this discussion of Polynomial Commitment at Vitalik’s blog (archived).