In Jim Posen's note, the protocol ends with the verifier querying

$$v_{i,j}=M_i(j||r_0,\dots ,r_{\nu -k-1})$$
for all

$j\in B_k$.

Using these, the verifier computes the evaluations

$${\hat{v}}_i={\hat{M}}_i(r_Y,r_0,\dots ,r_{\nu -k-1})=\sum _{j\in D}{v}_{i,j}\cdot L_{j,D}(r_Y),$$
and is able to check that

$C({\hat{v}}_0,\dots ,{\hat{v}}_{n-1})$ equals the final Sumcheck sum.

If we assume that the values

$v_{i,j}$ are provided as-is, we can check that they are correct using a single query to

$M_i$. Moreover, this avoids an extra invocation of the Sumcheck protocol, though it comes at the expense of more verifier work.

The verifier sends a new random element

$r_e\in \mathbb{F}$ and evaluates the

$2^k$ Lagrange polynomials over

$B_k$ at

${\overrightarrow{r}}_e=(r_e,r_e^2,\dots ,r_e^{2^{k-1}})$. The evaluations

$L_{j,B_k}({\overrightarrow{r}}_e)$, for each

$j\in B_k$ can be computed using

$O(k{2}^k)$. This allows the verifier to compute an evaluation

$v_i$ of

$M_i$ at

$({\overrightarrow{r}}_e||r_0,\dots ,r_{\nu -k-1})$. The following shows how the same evaluation can be derived by the verifier:

$$\begin{array}{rl}{v}_i& =M_i({\overrightarrow{r}}_e||r_0,\dots ,r_{\nu -k-1})\\ & =\sum _{j\in B_k}{M}_i(j||r_0,\dots ,r_{\nu -k-1})\cdot L_{j,B_k}({\overrightarrow{r}}_e)\\ & =\sum _{j\in B_k}{v}_{i,j}\cdot L_{j,B_k}({\overrightarrow{r}}_e)\end{array}$$

Alternatively, we can minimize the amount of verifier work by invoking a slightly more optimized Sumcheck instance.

Reusing the same random value

$r_e$, we define the

$k$-variate polynomial

${\mathsf{pow}}_{r_e}(X_0,\dots ,X_{k-1})$ such that

${\mathsf{pow}}_{r_e}(j)=r_e^j$ for all

$j\in B_k$. The verifier computes

$${\sigma }_i=\sum _{j=0}^{2^k-1}{r}_e^j\cdot v_{i,j}$$

which is the claimed sum for the Sumcheck instance

$${\mathsf{pow}}_{r_e}(X_0,\dots ,X_{k-1})\mathsf{eq}(r_0,\dots ,r_{\nu -k-1};X_k,\dots ,X_{\nu -1})\cdot M_i(X_0,\dots ,X_{\nu -1})$$

The following shows that the sum is correct:

$$\begin{array}{rl}{\sigma }_i& =\sum _{j_1\in B_k}\sum _{j_2\in B_{\nu -k}}{\mathsf{pow}}_{r_e}(j_1)\mathsf{eq}(r_0,\dots ,r_{\nu -k-1};j_2)\cdot M_i(j_1||j_2)\\ & =\sum _{j_1\in B_k}{\mathsf{pow}}_{r_e}(j_1)\sum _{j_2\in B_{\nu -k}}\mathsf{eq}(r_0,\dots ,r_{\nu -k-1};j_2)\cdot M_i(j_1||j_2)\\ & =\sum _{j_1\in B_k}{\mathsf{pow}}_{r_e}(j_1)\cdot M_i(j_1||r_0,\dots ,r_{\nu -k-1})\\ & =\sum _{j_1\in B_k}{r}_e^{j_1}\cdot M_i(j_1||r_0,\dots ,r_{\nu -k-1})\\ & =\sum _{j_1\in B_k}{r}_e^{j_1}\cdot v_{i,j}\end{array}$$

While this introduces

$\nu$ additional rounds of interaction, the verifier only performs

$O(2^k+\nu )$ field operations.