# Small field zerocheck

This describes how to efficiently perform more computations in the first round of zerocheck to take advantage of small field operations. As a jumping off point, we start with the idea from section 5 of [Gruen24].

Assume we are zerochecking a $\nu$-variate polynomial $F(X_0, ..., X_{\nu-1})$ defined as a composition over $n$ multilinears:

$$
F(X_0, ..., X_{\nu-1}) = C(M_0(X_0, ..., X_{\nu-1}), ..., M_{n-1}(X_0, ..., X_{\nu-1}))
$$

We have that $M_0, ..., M_{n-1}$ are all multilinear and $C$ has degree $d$. Thus $F$ has individual degree $\le d$ in all variables.

We begin by considering the multivariate zerocheck protocol over $F$ where the first round computes a partial sum over a $k$-variate multilinear, with $k \in \{1, ..., \nu\}$. That is, in the first round, the zerocheck prover sends a polynomial

$$
P_0(X_0, ..., X_{k-1}) = \sum_{i \in B_{\nu - k}} F(X_0, ..., X_{k-1} \parallel i) \; \widetilde{\text{eq}}(\alpha_k, ..., \alpha_{\nu-1} \parallel i)
$$

Gruen observes that the number of point evaluations required to specify $P_0$ is $(d + 1)^k - 2^k$ (since it is known that $P_0$ evaluates to $0$ over the $2^k$ hypercube points). This grows as $O((d+1)^k)$ with $d = 2$ and is already $81 - 16 = 65$ points in the relatively conservate setting of $d = 2$ and $k = 4$.

## Hybrid univariate-hypercube domain

Gruen suggests instead using a hybrid univariate-hypercube domain. That is, each "trace column" is interpolated over a domain $D \times B_{\nu - k}$, where $|D| = 2^k$. In this case, each column is $M_i(Y, X_0, ..., X_{\nu-k-1})$, with $\text{deg}_Y(M_i) \le 2^k - 1$. We define

$$
F(Y, X_0, ..., X_{\nu-k-1}) = C(M_0(Y, X_0, ..., X_{\nu-k-1}), ..., M_{n-1}(Y, X_0, ..., X_{\nu-k-1}))
$$

and the zerocheck claim is that $F$ is 0 over the domain $D \times B_{\nu - k}$. We see that $\text{deg}_Y(F) \le d(2^k - 1)$. This means that the number of point evaluations required to specify $P_0$ is now only $d(2^k - 1) + 1 - 2^k$, which is multiplicative in $d$ rather than exponential. With $d = 2$, this is only $2^k - 1$ points, which has a much slower rate of growth than $O((d+1)^k)$, like in the regular hypercube setting.

The annoying part of this is that it is rather unnatural to define the entire SNARK protocol over this domain.

## Univariatizing

Here's a solution zerocheck protocol that works for multilinear composites defined over the hypercube with $O(d 2^k)$ point evaluations instead of $O((d+1)^k)$.

Fix a domain $D \subset K$ with $|D| = 2^k$. Let $\{L_j(Y)\}_{j \in D}$ be the univariate Lagrange basis polynomials for $D$. For each multilinear $M_i(X_0, ..., X_{\nu-1})$, we define its partial univariate interpolation $\hat{M}_i$:

$$
\hat{M}_i(Y, X_0, ..., X_{\nu - k - 1}) = \sum_{j=0}^{2^k - 1} M_i(j \parallel X_0, ..., X_{\nu - k - 1}) L_j(Y)
$$

Somewhat abusing notation, we let $j$ index both into the hypecube $B_k$ and the domain $D$. We know that $\hat{M}_i(j, X_0, ..., X_{\nu - k - 1}) = M_i(j \parallel X_0, ..., X_{\nu - k - 1})$ for all $j$. Now we can run Gruen's section 5 zerocheck protocol on

$$
F(Y, X_0, ..., X_{\nu-k-1}) = C(\hat{M}_0(Y, X_0, ..., X_{\nu-k-1}), ..., \hat{M}_{n-1}(Y, X_0, ..., X_{\nu-k-1}))
$$

At the end of the zerocheck protocol, the verifier needs to check the evaluations of $\hat{M}_i(r_Y, r_0, ..., r_{\nu-k-1})$. The verifier queries the values of $M_i(j \parallel r_0, ..., r_{\nu-k-1})$ for $j \in B_k$ and then can compute

$$
\hat{M}_i(r_Y, r_0, ..., r_{\nu - k - 1}) = \sum_{j=0}^{2^k - 1} M_i(j \parallel r_0, ..., r_{\nu - k - 1}) L_j(r_Y)
$$

We could even use the multilinear sumcheck protocol, where the verifier computes the multilinear extension $\widetilde{L}_{r_Y}(X_0, ..., X_{k-1})$ where $\widetilde{L}_{r_Y}(j) = L_j(r_Y)$. The verifier is required to do $O(2^k)$ additional work.

[Gruen24]: https://eprint.iacr.org/2024/108