Front-Loaded Sumcheck

Here, as preparation for our evaluation scheme, we explain how we batch sumchecks on differently-sized polynomials. The setup is that we have a list of sum claims

where each $C_j(X_0, \ldots , X_{\ell_j - 1})$ is an $\ell_j$-variate composition polynomial. As the claim index $j \in \{0, \ldots , n - 1\}$ varies, we allow $\ell_j$ to vary too! (They don't have to be the same across all polynomials.)

Standard Batched Sumcheck

When the sizes $\ell_0 = \cdots = \ell_{n - 1} = \ell$ are all the same, batching sumchecks is not conceptually hard. Indeed, it's enough for the verifier to generate a random combination scalar $\alpha \gets \mathcal{T}_\tau$, and to compute the combined sum claim:

The parties can then run an $\ell$-round sumcheck on the batched polynomial

At the very end, the verifier needs to learn $\sum_{j = 0}^{n - 1} \alpha^j \cdot C_j(r_0, \ldots , r_{\ell - 1})$, for some point $(r_0, \ldots , r_{\ell - 1}) \in \mathcal{T}_\tau^\ell$ that the verifier will sample throughout the course of the sumcheck. To do this, it can just ask the prover nondeterministically for the individual values $C_j(r_0, \ldots , r_{\ell - 1})$, and output these as reduced evaluation claims.

The Procedure

When the sizes $\ell_0, \ldots , \ell_{n - 1}$ are unequal, many aspects of the above recipe stop making sense. We can still define the polynomial $C^*(X_0, \ldots , X_{\ell - 1})$ above, provided we write $\ell \coloneqq \max_{j = 0}^{n - 1} \ell_j$, say. But this polynomial's sum over $\mathcal{B}_\ell$ is not what we're interested in. (It would "double up" the sums of the smaller polynomials, causing them to become annihilated.) So we can't run a simple sumcheck on it.

Roughly, our approach is to "kick off" all sumchecks at the same time. On the other hand, since the polynomials are of different sizes, some will end earlier than others. We thus need to "prune" the finished sumchecks away from the protocol on the fly, as we run it. More precisely, each time a polynomial "finishes", that its sumcheck has been fully evaluated, we need to "knock out" that polynomial's contribution from the running sum claim.

Without further ado, we now present our procedure. For notational convenience, we assume that the polynomials are sorted in descending order by size, so that $\ell_0 \geq \cdots \geq \ell_{n - 1}$.

• The verifier samples a batching challenge $\alpha \gets \mathcal{T}_\tau$ and sends it to the prover. The verifier locally computes the batched sum claim:

• For each round index $i \in \{0, \ldots , \ell - 1\}$, where again we write $\ell \coloneqq \max_{j = 0}^{n - 1} \ell_j$:
  • The prover computes the round polynomial $$\begin{equation*}g_i(X) = \sum_{j = 0}^{j_i - 1} \alpha^j \cdot \sum_{v \in \mathcal{B}_{\ell_j - i - 1}} C_j(r_0, \ldots , r_{i - 1}, X, v_0, \ldots , v_{\ell_j - i - 2}).\end{equation*}$$ and sends it to the verifier. Here, the upper index $j_i$ of the sum is chosen to be the minimum among those $j \in \{0, \ldots , n\}$ for which $\ell_j \leq i$ holds. The point is that all of the polynomials indexed $j \in \{0, \ldots , j_i - 1\}$ have more than $i$ variables, so each expression $\sum_{v \in \mathcal{B}_{\ell_j - i - 1}} C_j(r_0, \ldots , r_{i - 1}, X, v_0, \ldots , v_{\ell_j - i - 2})$ makes sense! (It might happen that $\ell_j - i - 1 = 0$, in which case the boolean suffix $(v_0, \ldots , v_{\ell_j - i - 2})$ will be empty, but this is fine.)
  • The verifier checks whether $s^*_i \stackrel{?}= g_i(0) + g_i(1)$ holds.
  • The verifier samples $r_i \gets \mathcal{T}_\tau$ and sends it to the prover. The verifier moreover computes the updated sum claim: $$\begin{equation*}s^*_{i + 1} \coloneqq g_i(r_i).\end{equation*}$$
  • For each $j$ for which $\ell_j = i + 1$ holds on the nose—or equivalently, for each $j \in \{j_{i + 1}, \ldots , j_i - 1\}$—the prover nondeterministically sends the evaluation claim $$\begin{equation*}s_{j, \ell_j} = C_j(r_0, \ldots , r_i).\end{equation*}$$
  • Again for each $j$ for which $\ell_j = i + 1$ holds, the verifier mutates $s^*_{i + 1}$ as follows, using the information it just received: $$\begin{equation*}s^*_{i + 1} \mathrel{-}= \alpha^j \cdot s_{j, \ell_j}.\end{equation*}$$
• At the very end, i.e. after $\ell$ rounds, the verifier requires $s^*_\ell \stackrel{?}= 0$.
• The verifier outputs the reduced evaluation claims it received throughout the course of the protocol; namely, whereby, for each $j \in \{0, \ldots , n - 1\}$, $$\begin{equation*}s_{j, \ell_j} \stackrel{?}= C_j(r_0, \ldots , r_{\ell_j - 1}).\end{equation*}$$

Some Remarks

The above protocol is pretty cool and tricky; here, we record a few remarks.

• We note that the evaluation claims $s_{j, \ell_j} \stackrel{?}= C_j(r_0, \ldots , r_{\ell_j - 1})$ output by the verifier are front-loaded, in the sense that the prefixes are all common. That is, the various evaluation points share common initial substrings, though some are longer than others.
• It is an instructive exercise to check that this becomes equivalent to the standard batched sumcheck when $\ell_0 = \cdots = \ell_{n - 1}$ holds.
• It is an algorithmic invariant of the above loop that the only sumchecks "still in the running", as of the beginning of each round $i \in \{0, \ldots , \ell - 1\}$, are those for which $\ell_j > i$. In other words, each polynomial "still left" has more than $i$ variables. There is a slight subtlety, namely that we have to forbid 0-variable (constant) polynomials! We could accommodate those, but only by complicating the protocol above.

The security proof of our front-loaded sumcheck proceeds pretty similarly to how the standard batched sumcheck's does.