The Univariate Skip

We now describe our univariate skip variant. We focus here on the overall protocol steps, and on the verifier's perspective. We defer the details of the prover's implementation to the page after this one.

By the definition of AND constraint satisfaction, the prover's AND constraints hold if and only if

holds for each $x \in \{0, \ldots , n_\text{and} - 1\}$. Here, $a$, $b$ and $c$ are the constraint arrays associated with the prover's AND constraints.

Whatever these arrays are, we can oblong-multilinearize them. In this way, we get oblong-multilinears $\widehat{a}(\widehat{I}, X)$, $\widehat{b}(\widehat{I}, X)$ and $\widehat{c}(\widehat{I}, X)$ whose respective tables of values on $D \times \mathcal{B}_{\ell_\text{and}}$ are the constraint arrays $a$, $b$ and $c$.

Having done this, we can say that prover's AND constraints hold if and only if

holds for each $\widehat{i} \in D$ and each $x \in \mathcal{B}_{\ell_\text{and}}$. Our goal here will be to reduce the satisfaction of this condition to a further one, involving evaluation claims on the oblong-multilinearizations $\widehat{a}(\widehat{I}, X)$, $\widehat{b}(\widehat{I}, X)$ and $\widehat{c}(\widehat{I}, X)$. It will be the job of the shift reduction to assess those latter claims (and in particular, to connect them to the witness).

Protocol Description

For notation's sake, we write

Our goal is now to show that $f(\widehat{I}, X)$ vanishes identically on $D \times \mathcal{B}_{\ell_\text{and}}$; more precisely, our goal is to reduce the question of this vanishing to evaluation claims on $\widehat{a}(\widehat{I}, X)$, $\widehat{b}(\widehat{I}, X)$ and $\widehat{c}(\widehat{I}, X)$. Note that $f(\widehat{I}, X)$ is multivariate in $1 + \ell_\text{and}$ variables; it is not oblong-multilinear.

We now describe the protocol explicitly. Later, we explain soundness and implementation considerations.

• the verifier samples a partial challenge $\overline{r_x} \gets \mathbb{F}_{2^{128}}^{\ell_\text{and} - 3}$, as usual in the deterministic zerocheck variant. the verifier sends $\overline{r_x}$ to the prover.
• the parties both define $$\begin{equation*} r_x \coloneqq (\sigma_0, \sigma_1, \sigma_2, \overline{r_{x, 0}}, \ldots , \overline{r_{x, \ell - 4}}),\end{equation*}$$ where the elements $\sigma_0$, $\sigma_1$, and $\sigma_2$ of $\mathbb{F}_{2^{128}}$ are the fixed deterministic challenges we've already explained.
• the univariate polynomial $$\begin{equation*}g(\widehat{I}) \coloneqq \sum_{x \in \mathcal{B}_{\ell_\text{and}}} f(\widehat{I}, x) \cdot \widetilde{\texttt{eq}}(r_x, x)\end{equation*}$$ is univariate, of degree at most $2 \cdot (2^k - 1)$, and vanishes on $D$ if the prover is honest. The prover sends this polynomial, by sending its values on at least $2^k - 1$ points outside of $D$ (we will be more precise about this later).
• the verifier checks that $g(\widehat{I})$ vanishes identically on $D$.
• the verifier samples a single challenge $r_{\widehat{i}} \gets \mathbb{F}_{2^{128}}$ and sends it to the prover.
• both parties write $s_0 \coloneqq g(r_{\widehat{i}})$, and run an $\ell_\text{and}$-round sumcheck on the claim $$\begin{equation*}s_0 \stackrel{?}= \sum_{x \in \mathcal{B}_{\ell_\text{and}}} f(r_{\widehat{i}}, x) \cdot \widetilde{\texttt{eq}}(r_x, x).\end{equation*}$$
• at the end, the verifier needs to evaluate $$\begin{equation*}s_{\ell_\text{and}} \stackrel{?}= f(r_{\widehat{i}}, r'_x) \cdot \widetilde{\texttt{eq}}(r_x, r'_x),\end{equation*}$$ where $s_{\ell_\text{and}}$ and $r'_x$ are values that arise during the sumcheck. The verifier can evaluate $\widetilde{\texttt{eq}}(r_x, r'_x)$ himself; he outputs the final evaluation claim on $f(r_{\widehat{i}}, r'_x)$.

Completeness and Soundness

If the prover is honest—i.e., if $f(\widehat{i}, x) = 0$ for each $\widehat{i} \in D$ and each $x \in \mathcal{B}_{\ell_\text{and}}$, and if the prover carries out the above protocol as prescribed—then he will pass. First off, $f(\widehat{I}, X)$'s vanishing on $D \times \mathcal{B}_\ell$ implies $g(\widehat{I})$'s vanishing on $D$. Moreover, if the prover computes $g(\widehat{I})$ as prescribed, then

will hold, by definition of $g(\widehat{I})$; this is exactly the claim that the parties will sumcheck.

If the prover is dishonest, then there exists an $\widehat{i}^* \in D$ for which the set $\left( f(\widehat{i}^*, x) \right)_{x \in \mathcal{B}_{\ell_\text{and}}}$ of bits is not identically zero.

By the soundness analysis of the partially-deterministic zerocheck, the chance, over the verifier's choice of $\overline{r_x} \gets \mathbb{F}_{2^{128}}^{\ell_\text{and} - 3}$, that

holds is at most $\frac{\ell - 3}{2^{128}}$. Assuming that this doesn't happen, we conclude that

here, we write

for the univariate polynomial that the prover should send in the first round.

In light of the verifier's check that $\left. g \right|_D$ is identically zero, the inequality $\overline{g}(\widehat{i}^*) \neq 0$ above implies that the prover can pass that check only by sending a round polynomial $g(\widehat{I})$ unequal to $\overline{g}(\widehat{I})$ (as polynomials).

By standard univariate Schwartz–Zippel, the probability, over the verifier's $r_{\widehat{i}} \gets \mathbb{F}_{2^{128}}$, that $g(r_{\widehat{i}}) = \overline{g}(r_{\widehat{i}})$ is thus at most $\frac{2 \cdot (2^k - 1)}{2^{128}}$. If that equality doesn't happen, then the parties' sumcheck claim

will be false, which proves soundness.

The End

At the very end of the $\ell_\text{and}$-round sumcheck, the verifier will need to evaluate

here, $s_{\ell_\text{and}}$ and $r'_x$ are further quantities that will arise during the sumcheck. In the second equality, we unroll the definition of $f(r_{\widehat{i}}, r'_x)$, using our definition of $f(\widehat{I}, X)$ above.

The verifier can locally evaluate $\widetilde{\texttt{eq}}(r_x, r'_x)$. At this point, the prover can nondeterministically send the verifier scalars $\alpha_a$, $\alpha_b$ and $\alpha_c$ which it claims satisfy:

Then the verifier can explicitly check whether

If this equality passes, then the verifier will have closed out the univariate skip, pending the correctness of the prover's three evaluation claims. These are exactly the kind of claims that the shift reduction is designed to evaluate.