Primer: the sum-check protocol

This appendix gives a self-contained account of the sum-check protocol as a general interactive proof. It is background for Vega’s concrete sum-check building block, not a description of the protocol instances used by the implementation.

The sum being checked

Let \(g(X_1,\dots,X_\ell) \in \mathbb{F}[X_1,\dots,X_\ell]\) be a polynomial whose degree in each variable is bounded. The prover claims that \[ S \;=\; \sum_{\mathbf{x} \in \{0,1\}^\ell} g(\mathbf{x}). \] The verifier wants to check this claim without evaluating \(g\) on all \(2^\ell\) Boolean points. The protocol reduces the exponential-size sum to one evaluation of \(g\) at a random point \((r_1,\dots,r_\ell) \in \mathbb{F}^\ell\).

This setting is common when \(g\) is built from multilinear extensions. The sum-check protocol does not require \(g\) itself to be multilinear; it only needs a known degree bound for each univariate round polynomial.

Round polynomials

The protocol maintains a current claim \(C_{i-1}\). Initially \(C_0 = S\). In round \(i \in \{1,\dots,\ell\}\), the variables \(X_1,\dots,X_{i-1}\) have already been bound to verifier challenges \(r_1,\dots,r_{i-1}\). The prover sends the univariate polynomial \[ g_i(X) \;=\; \sum_{(x_{i+1},\dots,x_\ell) \in \{0,1\}^{\ell-i}} g(r_1,\dots,r_{i-1}, X, x_{i+1},\dots,x_\ell). \] For \(i=\ell\), the sum is over the empty set, so \[ g_\ell(X) \;=\; g(r_1,\dots,r_{\ell-1},X). \] The degree of \(g_i\) is at most the degree of \(g\) in variable \(X_i\), because the other variables are either fixed or summed over Boolean values.

The verifier checks the consistency equation \[ g_i(0) + g_i(1) \;=\; C_{i-1}. \] If it fails, the verifier rejects. If it holds, the verifier samples a fresh random challenge \(r_i \in \mathbb{F}\) and updates the claim to \[ C_i \;=\; g_i(r_i). \] After \(\ell\) rounds, the claim is \(C_\ell\), a claimed value for \[ g(r_1,\dots,r_\ell). \]

Final check

The verifier makes one oracle evaluation of \(g\) at the random point and accepts exactly when \[ g(r_1,\dots,r_\ell) \;=\; C_\ell. \] This final evaluation is the only place where the verifier needs access to \(g\) away from the Boolean hypercube. In deployed proof systems, the verifier often obtains this value through a polynomial commitment opening rather than by holding the whole polynomial.

Completeness and cost

Completeness is immediate from the definition of each round polynomial. If the initial claim \(S\) is correct and the prover sends the honest \(g_i\), then \[ g_i(0) + g_i(1) \] is exactly the previous sum with \(X_i\) left unbound, split into the two cases \(X_i=0\) and \(X_i=1\). The final value \(g_\ell(r_\ell)\) is exactly \(g(r_1,\dots,r_\ell)\).

The prover usually does work proportional to the table of values being summed, while the verifier checks only \(\ell\) low-degree univariate polynomials and one final evaluation. If every round polynomial has degree at most \(d\), the verifier’s round work is \(O(\ell \cdot d)\), plus the cost of the final oracle evaluation or commitment opening.

Soundness intuition

Suppose the claimed sum is false. A cheating prover may send a first polynomial \(h_1\) that passes \[ h_1(0) + h_1(1) = S \] even though \(h_1\) is not the honest round polynomial. Once the verifier sends a random \(r_1\), the next claim becomes \(h_1(r_1)\). For the prover to stay consistent with the true restricted sum, the false polynomial must agree with the honest polynomial at the sampled point.

By the Schwartz–Zippel lemma, two distinct univariate polynomials of degree at most \(d\) agree at a random field point with probability at most \(d/|\mathbb{F}|\). Across \(\ell\) rounds, a union bound gives cheating probability at most \[ \frac{\ell d}{|\mathbb{F}|} \] when every round has degree at most \(d\). More generally, the bound is \((d_1+\cdots+d_\ell)/|\mathbb{F}|\), where \(d_i\) is the degree bound in round \(i\).

A two-round example

Consider the Boolean predicate “exactly one bit is \(1\)” on two variables. Its indicator polynomial over \(\mathbb{F}\) is \[ g(X_1,X_2) \;=\; (1-X_1)X_2 + X_1(1-X_2) \;=\; X_1 + X_2 - 2X_1X_2. \] Over \(\{0,1\}^2\), it is \(1\) on \((1,0)\) and \((0,1)\), and \(0\) on the other two points. The claimed sum is therefore \(S=2\).

In round 1, the prover sends \[ g_1(X) = g(X,0) + g(X,1) = X + (1-X) = 1. \] The verifier checks \[ g_1(0)+g_1(1)=1+1=2=S \] and samples \(r_1\). The updated claim is \(C_1=g_1(r_1)=1\).

In round 2, the prover sends \[ g_2(X) = g(r_1,X) = r_1 + X - 2r_1X = r_1 + (1-2r_1)X. \] The verifier checks \[ g_2(0)+g_2(1)=r_1 + (1-r_1)=1=C_1 \] and samples \(r_2\). The updated claim is \[ C_2 = g_2(r_2)=r_1+r_2-2r_1r_2. \] The final oracle evaluation is \[ g(r_1,r_2)=r_1+r_2-2r_1r_2, \] which equals \(C_2\), so the verifier accepts.

Sending the round polynomial

A round polynomial can be transmitted by coefficients or by enough evaluations to interpolate it. For a degree-\(d\) polynomial, \(d+1\) field elements are sufficient. Implementations may compress the message further: the consistency check \(g_i(0)+g_i(1)=C_{i-1}\) already constrains the polynomial, so one of the \(d+1\) values is redundant and only \(d\) need to be sent.

The interactive verifier’s random challenges can be made non-interactive with Fiat–Shamir: the prover absorbs each round polynomial into the transcript, then derives \(r_i\) by hashing the transcript. Vega’s exact transcript schedule is specified in The transcript schedule.

Vega’s concrete sum-check construction is described in The sum-check protocol. Its use inside folding is described in NeutronNova folding.