reduce evaluations of 2^k MLPs that open at points (possibly distinct) to evaluations on one single point

[kunxian-xia]

Let's say we want to open $2^k$ multilinear polynomials (MLPs) that have same number of variable at points $\{ z_i: K^n \}$, i.e.

$f_i(z_i) = y_i$ where each point $z_i$'s length is $n$.

Then according to the construction in sec 3.8 of the HyperPlonk paper, this can be checked via a ZeroCheck ( $0 = \sum_i \textrm{eq}(\vec{t}, i) * (f_i(z_i) - y_i)$ ) where $\vec{t} \leftarrow K^k$ sampled uniformly by the verifier.

The above sumcheck can be rephrased as this

$s = \sum_i eq(t, i)*y_i = \sum_{i, b} eq(t, i) * f_i(b) * eq(z_i, b)$

1. Given function $g(i, b) = eq(t, i)*f_i(b)$ defined on the boolean hypercube $B_{k+n}$, apply multilinear extension (MLE) on it, we get a MLP $\tilde{g}(x, y)$.

2. Given function $h(i,b) = eq(z_i, b)$, apply MLE on it, we get a MLP $\tilde{h}(x, y)$

Then the above sumcheck can then rephrased again like this

$s = \sum_{i, b} \tilde{g}(i,b) * \tilde{h}(i,b)$

After doing the above sumcheck, we successfully reduce the validity of $f_i(z_i) = y_i$ to evaluation of $\tilde{g}(\alpha_1, \alpha_2)$ and $\tilde{h}(\alpha_1, \alpha_2)$ as shown in the algorithm 4 of the HyperPlonk paper.

Note that $\tilde{h}(\alpha_1, \alpha_2)$ can be computed by the verifier itself as $\tilde{h}(\alpha_1, \alpha_2) = \sum_i eq(\alpha_1, i) * \sum_b eq(\alpha_2, b) * eq(z_i, b) = \sum_i eq(\alpha_1, i) * eq(\alpha_2, z_i)$.

algorithm 4

1.1 How to compute $\tilde{g}(\alpha_1, \alpha_2)$?

1. $\tilde{g}(\alpha_1, \alpha_2) = \sum_i eq(\alpha_1, i) * eq(t, i) * \sum_b eq(\alpha_2, b) * f_i(b)$;
2. since $f_i(X)$ is a multilinear polynomial, we have $\sum_b eq(\alpha_2, b) * f_i(b) = f_i(\alpha_2)$;
3. Therefore, $\tilde{g}(\alpha_1, \alpha_2) = \sum_i eq(\alpha_1, i)* eq(t, i) * f_i(\alpha_2)$.

The above equation implies that we only need to

open MLPs $\{ f_i(X) \}$ at one single point $\alpha_2$.

1.2. Summary

Applying a sumcheck $s = \sum \tilde{g}(i, b) * \tilde{h}(i, b)$ (running in $k+n$ rounds) can reduce the original problem to the evaluations of $\tilde{g}(r_1, r_2) = \sum_i eq(r_1, i) * eq(t, i) * f_i(r_2)$.

Cost:

1. one sumcheck proof with $k+n$ rounds.
2. running batch open of $f_i(X)$ at single point $r_2$.

2. How to handle non-power-of-2 MLPs?