KZG - Is Zero Quotient Okay?

Overview

This is a note to show that the witness being zero is sound and is valid for some polynomials.

This skims through the original KZG protocol as a refresher and then shows why the zero quotient/proof/witness is okay.

Trusted setup

In KZG, we commit to polynomials using a trusted setup of the form:

$T = ({[s^{0}]_{1}, [s^{1}]_{1}, . . ., [s^{n - 1}]_{1}}, {[s^{0}]_{2}, [s^{1}]_{2}})$

ie the trusted setup is two lists of group elements, one list has group elements in G1 denoted $[x]_{1}$ , notice the subscript. The other list has elements in G2 denoted $[x]_{2}$ .

Committing

Given a polynomial $f (x)$ in monomial form, we commit to it by doing an MSM with the elements in G1 and the coefficients of the polynomial. You can think of this as an inner product between the G1 elements and the coefficients.

One can check that the commitment to $f (x)$ is equivalent to $[f (s)]_{1}$ , ie its the same as evaluating $f (x)$ with the scalar $s$ and doing a scalar multiplication with the generator of the G1 group.

Lets denote $[f (s)]_{1}$ as $C_{f}$ .

Witness

We ultimately want to make a proof that attests to the statement that "some polynomial $f (x)$ when evaluated at some point $z$ returns the value $y$ "

The TLDR is that our witness is the existence of the following polynomial : $Q (x) = \frac{f (x) - f (z)}{x - z}$

The prover commits to such a polynomial and this commitment is routinely referred to as the KZGProof in the consensus-specs in the deneb folder.

We will refer to the commitment to Q(x) as $π$ .

Verification

In order to know if setting Q(x) = 0 is sound, we need to check what the verifier is doing.

In order to check that $f (z) = y$ the verifier checks the following relation:

$Q (x) * (x - z) ? = f (x) - f (z)$

They ultimately want to check this with the commitments of $f (x)$ and $Q (x)$ because:

Those can be very large polynomials
The verifier's runtime, ideally should be constant.

We can use pairings for this. The verifier instead checks:

$e ([Q (s)]_{1}, [s - z]_{2}) ? = e ([f (s)]_{1} - [f (z)]_{1}, [1]_{2})$

Using the notation from earlier, this is:

$e (π, [s - z]_{2}) ? = e (C_{f} - [f (z)]_{1}, [1]_{2})$

Soundness

If $π$ == 0:

Without loss of generality, if any of the elements inside of the pairings functions are zero, then we say the output of the pairing function is 1.

Since $π == 0$ , then we have on the LHS $e ([0]_{1}, [s - z]_{2})$ which means the LHS is equal to 1.

The only way for one of the components in the pairing on the RHS to be equal to 0 is if $C_{f} - [f (z)]_{1} = [0]_{1}$ which implies that $C_{f} = [f (z)]_{1}$

This is only possible if $f (x)$ was the constant polynomial.

Completeness

As noted in the last sentence, when the polynomial we are committing to is the constant polynomial, $π$ is 0. One example, to see this is to look at the polynomial $f (x) = 0$