# The Sum-check Protocol

*Adapted from the Thaler13 exposition. For a detailed introduction to sumcheck see Chapter 4.1 of the textbook.*

Suppose we are given a $v$-variate polynomial $g$ defined over a finite field $F$. The purpose of the sumcheck protocol is to compute the sum:

$H:=b_{1}∈{0,1}∑ b_{2}∈{0,1}∑ ⋯b_{v}∈{0,1}∑ g(b_{1},…,b_{v}).$

In order to execute the protocol, the verifier needs to be able to evaluate $g(r_{1},…,r_{v})$ for a randomly chosen vector $(r_{1},…,r_{v})∈F_{v}$. Hence, from the verifier's perspective, the sum-check protocol *reduces* the task
of summing $g$'s evaluations over $2_{v}$ inputs (namely, all inputs in ${0,1}_{v}$) to the task of evaluating $g$
at a *single* input in $(r_{1},…,r_{v})∈F_{v}$.

The protocol proceeds in $v$ rounds as follows. In the first round, the prover sends a polynomial $g_{1}(X_{1})$, and claims that

$g_{1}(X_{1})=x_{2},…,x_{v}∈{0,1}_{v−1}∑ g(X_{1},x_{2},…,x_{v}).$

Observe that if $g_{1}$ is as claimed, then $H=g_{1}(0)+g_{1}(1)$. Also observe that the polynomial $g_{1}(X_{1})$ has degree $deg_{1}(g)$, the degree of variable $x_{1}$ in $g$. Hence $g_{1}$ can be specified with $deg_{1}(g)+1$ field elements. In our implementation, $P$ will specify $g$ by sending the evaluation of $g_{1}$ at each point in the set ${0,1,…,deg_{1}(g)}$. (Actually, the prover does *not* need to send $g_{1}(1)$, since since the verifier can *infer* that $g_{1}(1)=H−g_{1}(0)$, as if this were not the case, the verifier would reject).

Then, in round $j>1$, $V$ chooses a value $r_{j−1}$ uniformly at random from $F$ and sends $r_{j−1}$ to $P$. We will often refer to this step by saying that variable $j−1$ gets bound to value $r_{j−1}$. In return, the prover sends a polynomial $g_{j}(X_{j})$, and claims that

$g_{j}(X_{j})=(x_{j+1},…,x_{v})∈{0,1}_{v−j}∑ g(r_{1},…,r_{j−1},X_{j},x_{j+1},…,x_{v}).(1)$

The verifier compares the two most recent polynomials by checking that $g_{j−1}(r_{j−1})=g_{j}(0)+g_{j}(1)$, and rejecting otherwise. The verifier also rejects if the degree of $g_{j}$ is too high: each $g_{j}$ should have degree $deg_{j}(g)$, the degree of variable $x_{j}$ in $g$.

In the final round, the prover has sent $g_{v}(X_{v})$ which is claimed to be $g(r_{1},…,r_{v−1},X_{v})$. $V$ now checks that $g_{v}(r_{v})=g(r_{1},…,r_{v})$ (recall that we assumed $V$ can evaluate $g$ at this point). If this test succeeds, and so do all previous tests, then the verifier accepts, and is convinced that $H=g_{1}(0)+g_{1}(1)$.