The monomial-basis or projective sumcheck protocol is a variant of the sumcheck protocol where 1) the prover needs a few less arithmetic operations and 2) integration with other schemes that internally work with an monomial-base representation becomes conceptually simpler. In the paper, it is described by changing the interpolation set from $\{0,1\}^m$ to $\{0,\infty\}^m$. Evaluating a univariate at $\infty$ is defined as taking the top monomial-basis coefficient. For multilinears, the values on $\{0,\infty\}^m$ then are all the monomial-basis coefficients. Though I think everything can be notated just as well with coefficient vectors.

This post describes

  1. the monomial sumcheck protocol,
  2. why, as written, it only works for homogenous composition functions,
  3. how Protostar’s technique can make it work for arbitrary compositions.

Notation: monomial-basis coefficients of multilinear polynomials are indexed by bit strings: $f(x_1, \dots, x_m) = \sum_{i \in \{0,1\}^m} f[i] x_1^{i_1} \cdots x_1^{i_m}.$ Coefficients of univariate polynomials are indexed by integers: $p(x) = \sum_{i \in [0,\mathrm{deg}(p)]} p[i] x^i$.

Monomial-basis sumcheck

Here is a description of the protocol (eprint page 9) when used for compositions of $k$ multilinear polynomials $f_1, \dots, f_k$.

Monomial sumcheck for general $g$ (attempt):

Claim: $\sum_{i\in\{0,1\}^m} g(f_1[i], \dots, f_k[i]) = c.$

  1. Prover sends

    \[p(y) = \sum_{i \in \{0,1\}^{m-1}} g(f_1[0,i]+yf_1[1,i], \dots, f_k[0,i]+yf_k[1,i]).\]
  2. Verifier enforces $p[0]+p[\mathrm{deg}(g)]=c.$
  3. Verifier sends random $r.$
  4. Define $f’_j(x_2,\dots,x_m)=f_j(r,x_2,\dots,x_m)$ and $c’=p(r).$

New claim: $\sum_{i\in\{0,1\}^{m-1}} g(f’_1[i], \dots, f’_k[i]) = c’.$

This fails for inhomogenous $g$

The above protocol works fine when, for example, $g(f_1[i], f_2[i]) = f_1[i] f_2[i]$. But consider something like $g(f_1[i], f_2[i]) = f_1[i]^2 (f_2[i] + 1)$. We get

\[\begin{align*} p(y) &= \sum_{i \in \{0,1\}^{m-1}} (f_1[0,i]+yf_1[1,i])^2 (f_2[0,i]+yf_2[1,i]+1) \\ p[0] &= \sum_{i \in \{0,1\}^{m-1}} f_1[0,i]^2 (f_2[0,i]+1) \\ p[3] &= \sum_{i \in \{0,1\}^{m-1}} f_1[1,i]^2 f_2[1,i]. \end{align*}\]

The top coefficient is not the sum over $g(f_1[1,i],f_2[1,i])$, so the verifier’s check in step 2 would fail.

Protostar method

Here is one way out, inspired by Protostar folding. The idea would be to define the round polynomial differently, namely by adding shifted copies of each homogenous component of $g$:

\[p(y) = \sum_{j \in [0,\mathrm{deg}(g)]} {\color{green}(y+1)^{\mathrm{deg}(g)-j}} \sum_{i \in \{0,1\}^{m-1}} g_j(f_1[0,i]+yf_1[1,i], \dots)\]

where the homogenous components are uniquely defined such that each $g_j$ is homogenous of degree $j$ (all its monomials have degree exactly $j$) and $\sum_{j \in [0,\mathrm{deg}(g)]} g_j = g.$ That is, the only change is the ${\color{green}(y+1)^{\mathrm{deg}(g)-j}}$ in the sum. Since this expands to $1 + \cdots + y^{\mathrm{deg}(g)-j}$, it has the effect of adding shifted copies of each $g_j$. Consequently, the $y=0$ term of $p$ is still guaranteed to be $\sum_i g(f_1[0,i], \dots)$ and the top coefficient is forced to be $\sum_i g(f_1[1,i], \dots).$ This guarantees that the verifier’s check in step 2 will work.

It remains, however, to adjust $g$ at the end of the iteration, giving the full protocol below.

Monomial sumcheck for general $g$ (Protostar patch):

Claim: $\sum_{i\in\{0,1\}^m} g(f_1[i], \dots, f_k[i]) = c.$

  1. Prover sends

    \[p(y) = \sum_{j\in[0,\mathrm{deg}(g)]} {\color{green}(y+1)^{\mathrm{deg}(g)-j}} \sum_{i \in \{0,1\}^{m-1}} g_j(f_1[0,i]+yf_1[1,i], \dots, f_k[0,i]+yf_k[1,i]).\]
  2. Verifier enforces $p[0]+p[\mathrm{deg}(g)]=c.$
  3. Verifier sends random $r.$

  4. Define

    \[\begin{align*} f'_j(x_2,\dots,x_m) &= f_j(r,x_2,\dots,x_m), \\ c' &= p(r), \\ g' &= \sum_{j \in [0,\mathrm{deg}(g)]} {\color{green}(r+1)^{\mathrm{deg}(g)-j}} g_j. \end{align*}\]

New claim: $\sum_{i\in\{0,1\}^{m-1}} g’(f’_1[i], \dots, f’_k[i]) = c’.$