Towards a more efficient version

We have considered two ways in which the validator $V$ can check whether zero-equality constraints are met: either evaluating the constraint for reach gate of the circuit (i.e. evaluating the polynomial $t(x)$ encoding the sum constraint on each index), or computing the polynomial multiplication between the quotient polynomial $Q(x)$ and the vanishing polynomial $Z(x)$ and check equality against the polynomial encoding the constraints (i.e. $t(x)=Q(x)\cdot Z(x)$). Among the reasons why the second alternative is advantageous is that we can perform the equality check very efficient with a probabilistic algorithm at the price of (very rarely) making some mistakes.

Consider the following algorithm:

• The validator has $t(x)$, $Q(x)$ and $Z(x)$ and wants to know whether $t(x)=Q(x)\cdot Z(x)$.
• They sample a random value $\gamma \in {\mathbb{F}}_p$.
• They check whether $t(\gamma )=Q(\gamma )\cdot Z(\gamma )$.

Why does this work? Certainly this check is a necessary condition, that is, if the polynomial equality holds, then it also holds when evaluated on a single point. But is it sufficient? In other words, can it be that $t(\gamma )=Q(\gamma )\cdot Z(\gamma )$ holds but $t(x)\ne Q(x)\cdot Z(x)$? It turns out that yes, that can unfortunately happen, but we can count on how many points this may at most happen, and therefore compute a probability for that event which allows us to reason on how "risky" our protocol is.

Schwartz-Zippel Lemma

Consider two polynomials $f(x),g(x)\in {\mathbb{F}}_p[x]$ of degree at most $d$, such that $f(x)\ne g(x)$. Consider the set of points $S\subseteq {\mathbb{F}}_p$ such that $\mathrm{\forall }s\in S:f(s)=g(s)$. This set of points $S$ is exactly the set of points for which $f(x)-g(x)=0$. By assumption $f(x)\ne g(x)$ so $h(x)=f(x)-g(x)\in {\mathbb{F}}_p[x]$ is a non trivial polynomial of degree at most $d$. This polynomial $h(x)$ has at most $d$ roots, so the size of $S$ is bounded $|S|\le d$. Given that we are sampling a value $\gamma$ uniformly at random from ${\mathbb{F}}_p$, the probability of selecting a point in $S$, in case $f(x)\ne g(x)$, is $\frac{|S|}{p}\le \frac{d}{p}$. This is known as the Schwartz-Zippel Lemma (which is more generally stated in a multi-variate polynomial setting).

In our circuit example, given that the polynomials involved are of degree 3, we get an extremely low probability of an incorrect equality check of at most $\frac{3}{p}\approx \frac{1}{2^{252}}$.

Exercise 5

Compute the equality checks for the gate and recursive constraints with the following random values: ${\gamma }_1=42$, ${\gamma }_2=74102$ and ${\gamma }_3=987654321987654321$. You should obtain:

$$\begin{array}{rl}t({\gamma }_1)& =Q({\gamma }_1)\cdot Z({\gamma }_1)=21888242871839275222246405745257275088548364400416034343698204183303103172977\\ f_1({\gamma }_2)& =Q_1({\gamma }_2)\cdot Z_1({\gamma }_2)=271248759392650\\ f_2({\gamma }_3)& =Q_2({\gamma }_3)\cdot Z_1({\gamma }_3)=21888242871839275222245442326925691337956137906799110242993653357780575606177\end{array}$$

γ1 = 42
γ2 = 74102
γ3 = 987654321987654321
#Solve here!