Skip to content

Zerocheck Review

A summary of the classical multilinear vanishing argument

We use this space to review the basic zerocheck, just so that we can refer to it later. Here, we generally want to fix a column height parameter ℓ≥0\ell \geq 0, and an ℓ\ell-variate polynomial C(X0,…,Xℓ−1)C(X_0, \ldots , X_{\ell - 1}) (not necessarily multilinear!).

The Mathematical Premise

The thing the verifier wants to ensure is that, for each cube point v∈Bℓv \in \mathcal{B}_\ell, C(v)=0C(v) = 0. In other words, the restriction of C(X0,…,Xℓ−1)C(X_0, \ldots , X_{\ell - 1}) to the cube is identically zero (hence the name zerocheck).

The funamental mathematical idea of the zerocheck is that CC vanishes on the cube if and only if its multilinear extension C~(X0,…,Xℓ−1)\widetilde{C}(X_0, \ldots , X_{\ell - 1}) also does. In fact, more is true:

  • Completeness. If CC vanishes identically on the cube, then C~\widetilde{C} vanishes everywhere on Tτℓ\mathcal{T}_\tau^\ell.
  • Soundness. If CC doesn't vanish identically on the cube, then C~\widetilde{C} vanishes almost nowhere; i.e., it vanishes on a proportion consisting of at most 1∣Tτ∣\frac{1}{|\mathcal{T}_\tau}| among Tτℓ\mathcal{T}_\tau^\ell's points.

Thus it's complete and sound for the verifier to sample a random r←Tτℓr \gets \mathcal{T}_\tau^\ell, and check whether C~(r)=?0\widetilde{C}(r) \stackrel{?}= 0.

The Sumcheck

How can the verifier do this efficiently? The trick is to write down a polynomial expression for C~(X0,…,Xℓ−1)\widetilde{C}(X_0, \ldots , X_{\ell - 1}). We've already seen how to construct multilinear extensions:

C~(X0,…,Xℓ−1)=∑v∈BℓC(v)⋅eq~(X0,…,Xℓ−1,v0,…,vℓ−1).\begin{equation*}\widetilde{C}(X_0, \ldots , X_{\ell - 1}) = \sum_{v \in \mathcal{B}_\ell} C(v) \cdot \widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, v_0, \ldots , v_{\ell - 1}).\end{equation*}

We now see that the verifier's main question C~(r)=?0\widetilde{C}(r) \stackrel{?}= 0 in turn amounts to the sum claim

0=?∑v∈BℓC(v)⋅eq~(r0,…,rℓ−1,v0,…,vℓ−1).\begin{equation*}0 \stackrel{?}= \sum_{v \in \mathcal{B}_\ell} C(v) \cdot \widetilde{\texttt{eq}}(r_0, \ldots , r_{\ell - 1}, v_0, \ldots , v_{\ell - 1}).\end{equation*}

This is exactly the kind of thing we can sumcheck; indeed, by sumchecking the multivariate product

X0,…,Xℓ−1)↦C(X0,…,Xℓ−1)⋅eq~(r0,…,rℓ−1,X0,…,Xℓ−1),\begin{equation*}X_0, \ldots , X_{\ell - 1}) \mapsto C(X_0, \ldots , X_{\ell - 1}) \cdot \widetilde{\texttt{eq}}(r_0, \ldots , r_{\ell - 1}, X_0, \ldots , X_{\ell - 1}),\end{equation*}

the verifier may reduce the above sum claim to two evaluation claims at some random point r′∈Tτℓr' \in \mathcal{T}_\tau^\ell—namely, to claims about the evaluations t(r′)t(r') and eq~(r,r′)\widetilde{\texttt{eq}}(r, r'). To resolve the first of these, the verifier may simply query tt directly. To resolve the second, the verifier may compute eq~(r,r′)\widetilde{\texttt{eq}}(r, r') locally (since the equality indicator polynomial is transparent!).