Univariate Skip

Here, we begin in earnest our treatment of vanishing claims. As we've mentioned elsewhere, the main complication at hand is that the polynomials we want to verify the vanishing of are defined over small fields. In this page we sketch Binius's zerocheck variant, which is designed to exploit precisely this small-field situation. The theoretical ideas of this page largely come from Gruen [Gru24].

Algorithms for sumcheck and zerocheck are extremely complicated in general (especially in the small-field setting), and we can only hope to give a very rough survey in this page. As usual, here, we adopt the verifier's point of view, and sketch the security story. Of course, using a univariate zerocheck—as opposed to a standard one—serves to lighten rather the prover's load, and not the verifier's; so our motivation cannot be purely verifier-centric. For the full details, we opt to defer to the Binius codebase.

As we've repeatedly mentioned, the multivariate composition polynomials we're interested in zerochecking are, in general, defined over small fields. This fact makes the 0^th round of the zerocheck special, in that much of the computation required by that round may be carried out over an appropriate small field. In the zerocheck's positive-indexed rounds, on the other hand, the polynomials at hand "saturate" to the maximal field size—and many of the small-field advantages disappear.

The univariate skip is designed to trade off 0^th-round computation for positive-round computation. That is, the univariate skip serves to move as much work as possible into the 0^th round; it vastly reduces, in the process, the amount of work which must be performed in the subsequent, positive-indexed rounds.

The Standard Zerocheck

As always, we are going to fix an $\ell$-variate composite polynomial $C(X_0, \ldots , X_{\ell - 1})$; our goal is to check that $C(v) = 0$ for each $v \in \mathcal{B}_\ell$. As usual, we will obtain $C$ itself from underlying $\ell$-variate multilinears $t_0, \ldots , t_{n - 1}$, by subjecting those multilinears to some $n$-variate composition polynomial $c(Z_0, \ldots , Z_{n - 1})$.

In the basic zerocheck, we wind up sumchecking the multivariate product $C(X_0, \ldots , X_{\ell - 1}) \cdot \widetilde{\texttt{eq}}(r_0, \ldots , r_{\ell - 1}, X_0, \ldots , X_{\ell - 1})$. The 0^th round is special: since the multilinears $t_i$ have small coefficients, their evaluations within the cube itself—as well as on nearby points of the form $(2, v_1, \ldots , v_{\ell - 1})$, say, where the trailing coordinates $(v_1, \ldots , v_{\ell - 1})$ are boolean—will themselves be small. By consequence, evaluating the composition $c(Z_0, \ldots , Z_{n - 1})$ on these points (the main "workhorse" task of the zerocheck) will be very efficient.

On the other hand, after a single folding round goes by, this advantage will disappear. Indeed, the partially specialized multilinears $t_i(r_0, X_1, \ldots , X_{\ell - 1})$ will no longer have small coefficients; neither, therefore, will their evaluations at points of the form $(r_0, x_1, v_2 \ldots , v_{\ell - 1})$, where $x_1$ is small and the trailing coordinates $(v_2, \ldots , v_{\ell - 1})$ are boolean. Thus, evaluating $c$ on tuples of these evaluations will stop being efficient. We thus see that we only get to reduce the problem size by 2 before the small-field efficiency advantage all-but disappears.

The Basic Idea

The basic idea is to "reshape" our fundamental domain $\mathcal{B}_\ell$ into another domain, which has just as many points (that is, $2^\ell$ of them) but which is much "longer" in its 0^th dimension. The goal will be to get more work out of the way in the 0^th round (which we've already seen is special). That is, instead of reducing by just half our problem size during the course of the 0^th round, we will rather want to reduce it by $2^k$-fold, for some parameter $k$ generally bigger than 1.

Thus we fix a skipping parameter $k \geq 1$ (in practice, $k$ will be around 7). We are going to pick a univariate domain $D \subset \mathcal{T}_\tau$ in our huge field of size $|D| = 2^k$. (In practice, we will moreover want $D$ to be an $\mathbb{F}_2$-subspace of $\mathcal{T}_\tau$.) Our fundamental domain will be $D \times \mathcal{B}_{\ell - k}$, now viewed as a subset of $\mathcal{T}_\tau^{\ell - k + 1}$. Note that this thing's size is exactly $2^\ell$.

We—that is, both the prover and the verifier—are now going to simply "pretend" that the initial multilinears $t_0, \ldots , t_{n - 1}$, and so also the composite $C(X_0, \ldots , X_{\ell - 1})$, were defined to begin with on $D \times \mathcal{B}_{\ell - k}$, instead of on $\mathcal{B}_\ell$. This isn't a problem, conceptually: since our initial multilinears essentially amount to lists of $2^\ell$ elements, we can always decide to identify these lists with $D \times \mathcal{B}_{\ell - k}$ instead of with $\mathcal{B}_\ell$. Thus, instead of multilinears $t_i(X_0, \ldots , X_{\ell - 1})$, we now have polynomials $\widehat{t}_i(Y, X_0, \ldots , X_{\ell - k - 1})$ of degree less than $2^k$ in $Y$ and linear their subsequent variables. The defining property of these rectangularizations $\hat{t}_i$ is that for each $u \in \mathcal{B}_k$,

as $\ell - k$-variate multilinears. Here, we write $\{ \cdot \} : \mathcal{B}_k \to D$ for a the natural injection which sends $(u_0, \ldots , u_{k - 1}) \mapsto \sum_{i = 0}^{k - 1} u_i \cdot \beta_i$ (here, $\beta_0, \ldots , \beta_{k - 1}$ is an $\mathbb{F}_2$-basis of $D$).

Just as $\ell$-variate multilinears are exactly captured by their values on $\mathcal{B}_\ell$, so too are polynomials of this degree profile exactly captured by their values on $D \times \mathcal{B}_{\ell - k}$. By applying the usual composition polynomial $c(Z_0, \ldots , Z_{n - 1})$ to the rectangularized underlying polynomials $\widehat{t}_i(Y, X_0, \ldots , X_{\ell - k - 1})$, we get a rectangularized composition polynomial $\widehat{C}(Y, X_0, \ldots , X_{\ell - k - 1})$. Since $\widehat{C}$ takes the same values on $D \times \mathcal{B}_{\ell - k}$ that $C$ does on $\mathcal{B}_\ell$, it's enough to check that $\widehat{C}$ vanishes identically on $D \times \mathcal{B}_{\ell - k}$.

What is the point of moving the goalposts like this? It turns out that the standard zerocheck and sumcheck protocols have variants for rectangular domains, which are moreover more efficient than the standard procedures are in the small-field setting.

The Rectangular Zerocheck

We've already seen that a multivariate polynomial vanishes identically on the cube if and only if its multilinear extension vanishes everywhere. Here, we are going to use an analogous idea, adapted to the rectangular setting. We write $\delta_D(X, Y)$ for the bivariate equality indicator polynomial on the domain $D$. That is, $\delta_D(X, Y)$ is the unique polynomial whose restriction to $D \times D$ is the equality indicator function, and which moreover is of individual degree less than $2^k$ in both $X$ and $Y$.

We want to check whether the rectangularized composite polynomial $\widehat{C}(Y, X_0, \ldots , X_{\ell - k - 1})$ vanishes identically on $D \times \mathcal{B}_{\ell - k}$. To do this, we can rather consider its low-degree extension $\widetilde{C}(Y, X_0, \ldots , X_{\ell - k - 1})$: that is, the unique polynomial which agrees with $\widehat{C}$ identically on $D \times \mathcal{B}_{\ell - k}$, but which is moreover of degree less than $2^k$ in $Y$ and multilinear in its other variables. Exactly as in the classical zerocheck, we note that $\widehat{C}$ vanishes identically on $D \times \mathcal{B}_{\ell - k}$ if and only if $\widetilde{C}$ vanishes everywhere on $\mathcal{T}_\tau^{\ell - k + 1}$. Thus, it's complete and sound for the verifier to sample a random point $(s, r_0, \ldots , r_{\ell - k - 1}) \gets \mathcal{T}_\tau^{\ell - k + 1}$, and check whether $\widetilde{C}(s, r_0, \ldots , r_{\ell - k - 1}) \stackrel{?}= 0$.

We get an expression for $\widetilde{C}$ in the following way:

Specializing this thing to $(s, r_0, \ldots , r_{\ell - k - 1})$, we see that it's enough to run a rectangular sumcheck on the product polynomial

That is, it's enough for the verifier to check whether the sum of this thing over the domain $D \times \mathcal{B}_{\ell - k}$ equals 0 or not.

The protocol for this exactly follows the script of the normal sumcheck. In particular, the prover will start by sending the 0^th univariate round polynomial

The verifier will first check that $\sum_{u \in D} g(u) \stackrel{?}= 0$ holds. Then, the verifier will sample $s' \gets \mathcal{T}_\tau$, and update its running sum claim to $g(s')$, and send $s'$ to the prover. Finally, the prover will locally specialize the indeterminate $Y$ of its underlying polynomials $\widehat{t}_i$ to $s'$, and fold everything. From that point onwards, things will look essentially like a normal zerocheck.

Efficiency Gains

The prover's round polynomial $g(Y)$ is univariate of degree at most $(2^k - 1) \cdot (d + 1)$, where $d$ is the total degree of the composition polynomial $c(Z_0, \ldots , Z_{n - 1})$. The prover can send it to the verifier by specifying its evaluations on more than $(2^k - 1) \cdot (d + 1)$ points.

In fact, $g(Y)$ will in fact vanish identically on $D \subset \mathcal{T}_\tau$, since $\widehat{C}$ vanishes on $D \times \mathcal{B}_{\ell - k}$. The prover can thus just refrain from sending $g$'s evaluations on $D$ at all. Similarly, the verifier can implicitly "backfill" $g$ to be 0 on $D$, and skip its check $\sum_{u \in D} g(u) \stackrel{?}= 0$.

As the prover computes $g(y)$ for various points $y$, the prover will need to repeatedly evaluate the composition $c(Z_0, \ldots , Z_{n - 1})$ on evaluations of the form $\widehat{t}_i(y, v_0, \ldots , v_{\ell - k - 1})$. (Here, the suffix $(v_0, \ldots , v_{\ell - k - 1})$ is boolean, while $y \in \mathcal{T}_\tau$ is a relatively small element—it lives in some extension of the domain $D$, roughly $d$-fold the size of $D$.) And here, we get to the key efficiency point: if the $t_i$s' coefficients are small, then so too will be the $\widehat{t}_i$s' evaluations at points of the form $(y, v_0, \ldots , v_{\ell - k - 1})$. Thus the bulk of our work—namely, repeatedly evaluating $c$—will take place over a small field. Moreover, we get to knock out $k$ "rounds' worth" of work in this way, instead of just one. By the time the univariate skip ends, the polynomials we're left with will be just $\frac{1}{2^k}$th the size they were when we started, a huge efficiency gain.