Linearization in Plonk and Kimchi. Why?

This is a short note on the linearization step in Plonk (the zero-knowledge proof system), which is in my opinion the hardest step to understand.

Essentially, the linearization in Plonk exists due to two reasons:

The polynomials we’re dealing with are too big for the SRS (in the case of a polynomial commitment scheme, or PCS, like KZG) or URS (in the case of a PCS like bulletproof).
During a proof verification, the verifier reconstructs the commitment to the polynomial that is aggregating all the constraints. To construct that commitment, the verifier adds commitments together, but must avoid multiplications as the commitment scheme used is only additively homomorphic.

Let’s look at each of these in order.

The Reference String has a maximum size limit

The polynomials we’re dealing with are too big for the SRS (in the case of a polynomial commitment scheme, or PCS, like KZG) or URS (in the case of a PCS like bulletproof).

Imagine that you have a polynomial with 4 coefficients:

f = f_{0} + f_{1} x + f_{2} x^{2} + f_{3} x^{3}

Now imagine that your reference string is of size 2. This means that you can commit polynomials that have 2 coefficients max. The only way to commit to $f$ is to commit to the two polynomials with 2 or less coefficients separately:

$c o m_{1} = f_{0} + f_{1} x$
$c o m_{2} = f_{2} + f_{3} x$

Then, as part of the protocol, the prover evaluates this polynomial at some challenge point $ζ$ and produces an evaluation proof for that. The verifier will have to first reconstruct the commitment to that polynomial, which can be constructed as:

c o m = c o m_{1} + ζ^{2} c o m_{2}

Take a few minutes to understand why this works if needed.

Commitments are not homomorphic for the multiplication

During a proof verification, the verifier reconstructs the commitment to the polynomial that is aggregating all the constraints. To construct that commitment, the verifier adds commitments together, but must avoid multiplications as the commitment scheme used is only additively homomorphic.

Both the KZG and bulletproof PCS’s use the Pedersen commitment, which is an homomorphic commitment scheme for the addition, but not for the multiplication. In other words, this means we can add commitments together (or add a commitment to itself many times), but not multiply commitments together.

So if $c o m_{1}$ is the commitment of the polynomial $g_{1}$ and $c o m_{2}$ is the commitment of the polynomial $g_{2}$ . Then the following is fine:

c o m_{1} + c o m_{2} = c o m (g_{1} + g_{2})

While the following is not possible:

c o m_{1} \cdot c o m_{2}

In this last case, the solution is to simply have the prover evaluate one of the commitments. For example, if we want to evaluate the polynomial (behind this commitment) to a challenge point $ζ$ , the prover could provide $g_{1} (ζ)$ and the verfier would then compute the commitment of $g_{1} \cdot g_{2}$ as

g_{1} (ζ) \cdot c o m_{2}

This works, as long as the protocol uses this commitment to later verify an evaluation proof of $g_{1} (ζ) \cdot g_{2} (ζ)$ .

Note that if $g_{1}$ is a polynomial that needs to remain private (part of the witness), then it should be blinded if you care about zero-knowledge.

As such, the linearization step of Plonk is a way to have the verifier construct a commitment as a linear combination of commitments. These commitments are generally preprocessed commitments contained in the verifier index (also called verifier key) or commitments that the verifier can generate themselves (the commitment to the public input polynomial for example).