Zerocheck

Code: crates/hypercube/src/verifier/shard.rs::verify_zerocheck

The goal of the zerocheck protocol is two-fold:

• verify the evaluations at the GKR point $\vec{r}$ chosen above.
• verify that the constraints (specified via AIRs) hold on all rows (except for the padded rows).

Actually the zerocheck does not fully verify these claims but rather it reduces them to a claim about the multilinear extension of the sparse representation - this will be fed into the subsequent jagged step.

The zerocheck protocol proceeds as follows. First, the challenger samples three random extension field elements

• $\alpha$, for a RLC over the constraints.
• $\beta$, for batching the claimed evaluations from GKR.
• $\lambda$ for an RLC over the chips in zerocheck.

We now discuss the zerocheck per chip - combining will be done using $\lambda$ as an RLC.

The usual manner in which zerocheck is used is to reduce the claim that

$$C(p_1(x), p_2(x), \cdots, p_n(x)) = 0$$

for all $x \in \{0, 1\}^H$ to claims about the individual underlying multilinears $p_1,\dots,p_n$. This is done by first choosing a random $z$ and checking that

$$\sum_{x} \text{eq}(x, z) \cdot C(p_1(x), \cdots, p_n(x)) = 0$$

via the sumcheck protocol, where this will reduce to an evaluation claim of $p_1, \cdots, p_n$ on another random point. However, since we pad with zeroes, and $C$ may not evaluate to zero on an all-zero row, the claim actually is that

$$\text{constraint}(x) = C(p_1(x), \cdots, p_n(x)) - C(0, \cdots, 0) \cdot \text{geq}(x, \text{real height}) = 0$$

for all $x \in \{0,1\}^H$, where $geq : \mathbb{F}^m \to \mathbb{F}^m$ is a multilinear polynomial that given $a,b$ checks that $b \geq a$.

At the same time, we also want to verify that GKR evaluation claims at $r$ are correct. Thus, we check that

$$\sum_x \text{eq}(x, r) \cdot \text{batch open}(x) = \text{batch open}(r)$$ $$\text{batch open}(x) = \text{RLC}(\beta, (p_1(x), \cdots, p_n(x))) = \beta p_1(x) + \beta^2 p_2(x) + \cdots + \beta^{n} p_n(x)$$

Since $r$ is already random, we can use this as our random $z$ for the zerocheck. This means that we're just checking

$$\sum_{x} \text{eq}(x, r) \cdot (\text{constraint}(x) + \text{batch open}(x)) = \text{batch open}(r)$$

where the latter sum can be computed from the GKR evaluation claims.

We run the sumcheck here, and we would require

$$\text{eq}(z, r) \cdot (\text{constraint}(z) + \text{batch open}(z))$$

which can be derived from all the column evaluations at $z$. We hash in the claimed openings $p_1(z), \cdots, p_n(z)$ at the end of the zerocheck function.