Partial evaluations and linearization posted Yesterday

I already wrote about the linearization technique of plonk here and here. But there's a more generalized and high-level view to understand it, as it's being used in many protocols (e.g. Shplonk) as well.

Imagine you have the following check that you want to do:

$$f(x) \cdot g(x) \cdot h(x) + 3 \cdot m(x) + 7 = 0$$

but some of these polynomials contain secret data, what you do is that you use commitments instead:

$$[f(x)] \cdot [g(x)] \cdot [h(x)] + 3 \cdot [m(x)] + 7 \cdot [1] = [0]$$

now it looks like we could do the check within the commitments and it could work.

The problem is that we can't multiply commitments, we can only do linear operations with commitments! That is, operations that preserves scaling and addition.

So we give up trying to do the check within the commitments, and we instead perform the check in the clear! That is, we try to perform the following check at a random point $z$ (this is secure thanks to Schwartz-Zippel):

$$f(z) \cdot g(z) \cdot h(z) + 3 \cdot m(z) + 7 = 0$$

To do that, we can simply ask a prover to produce evaluations at $z$ (accompanied with evaluation proofs) for each of the commitments.

Note that this leaks some information about each committed polynomials, so usually to preserve zero-knowledge you'd have to blind these polynomials

But Plonk optimizes this by saying: we don't need to evaluate everything, we can just evaluate some of the commitments to obtain a partial evaluation. For example, we can just evaluate $f$ and $g$ to obtain the following linear combination of commitments:

$$ f(z) \cdot g(z) \cdot [h] + 3 \cdot [m] + 7 \cdot [1] $$

This semantically represents a commitment to the partial evaluation of a polynomial at a point $z$. And at this point we can just produce an evaluation proof that this committed polynomial evaluates to 0 at the point $\textbf{z}$.

Since we are already verifying evaluation proofs (here of $f$ and $g$ at $z$), we can simply add another evaluation proof to check to that list (and benefit from some batching technique that makes it look like a single check).

That's it, when you're stuck trying to verify things using commitments, just evaluate things!