In this note, we will explore two versions of the Sum-Check protocol: the vanilla protocol, as well as a useful generalization that we'll refer to as "Specialized Sum-Check".

The Sum-Check problem statement

Sum-check is an algorithm where the following statement is proven:

$$\sum _{x_1\in \{0,1\}}\dots \sum _{x_m\in \{0,1\}}g(x_1,\dots ,x_m)=C_1,$$

where

$g:{\mathbb{F}}^m\to \mathbb{F}$ is any m-variate polynomial, and

$C_1\in \mathbb{F}$ is the result of computing the sum. The polynomial

$g$ is public (i.e. known to both the prover and verifier). Hence, the verifier could compute that sum itself. However, we often don't want the verifier to have to do all this work. The main benefit of sum-check is that the verifier can be convinced that the statement is true with very little work, at the cost of more work for the prover.

Throughout this note, we will use the following as a short-hand for the above statement:

$$\sum _{(x_1,\dots ,x_m)\in \{0,1{\}}^m}g(x_1,\dots ,x_m)=C_1.$$

The Sum-Check Protocol

In this section, we present the algorithm. We will show why the algorithm properly proves the sum-check statement in the next section.

Sum-check is an interactive algorithm which can be made non-interactive using the Fiat-Shamir transform. The algorithm consists of

$m$ rounds, where in round

$i$, the prover sends a univariate polynomial

$s_i:\mathbb{F}\to \mathbb{F}$ to the verifier, and the verifier responds with a field element

$r_i{\in }_R\mathbb{F}$ sampled uniformly at random. After the last round, the verifier evaluates

$g$ at a single point, runs a final check, after which it is convinced that the statement is true.

Let's take a closer look at what happens in a round.

round 1

Prover

The prover constructs the univariate polynomial

$$s_1(x_1)=\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(x_1,x_2,\dots ,x_m).$$

In words,

$s_1:\mathbb{F}\to \mathbb{F}$ is defined as the sum of

$g$ over all variables except

$x_1$.

The prover sends

$s_1$ to the verifier.

Verifier

The verifier checks

$$s_1(0)+s_1(1)=C_1.$$

Then, the verifier samples

$r_1{\in }_R\mathbb{F}$ uniformly at random and sends it to the prover.

round 2

Prover

The prover constructs the univariate polynomial

$$s_2(x_2)=\sum _{(x_3,\dots ,x_m)\in \{0,1{\}}^{m-2}}g(r_1,x_2,x_3,\dots ,x_m).$$

The prover sends

$s_2$ to the verifier.

Verifier

The verifier checks

$$s_2(0)+s_2(1)=s_1(r_1).$$

Then, the verifier samples

$r_2{\in }_R\mathbb{F}$ uniformly at random and sends it to the prover.

round

$i$,

$3\le i\le m$

Prover

The prover constructs the univariate polynomial

$$s_i(x_i)=\sum _{(x_{i+1},\dots ,x_m)\in \{0,1{\}}^{m-i}}g(r_1,\dots ,r_{i-1},x_i,x_{i+1},\dots ,x_m).$$

The prover sends

$s_i$ to the verifier.

Verifier

The verifier checks

$$s_i(0)+s_i(1)=s_{i-1}(r_{i-1}).$$

Then, the verifier samples

$r_i{\in }_R\mathbb{F}$ uniformly at random and sends it to the prover.

Verifier last check

In round

$m$, the verifier received

$s_m(x_m)$ from the prover, and sampled

$r_m{\in }_R\mathbb{F}$. Now, the verifier checks

$$g(r_0,\dots ,r_m)=s_m(r_m)$$

Note that this is the only evaluation of

$g$ by the verifier in the entire protocol.

This completes the protocol. If the check passes, then the verifier is convinced that the original statement is true.

Sum-Check: Analysis

In this section, we will show why the protocol as described in the previous section is sound.

The first realization to make is that the protocol is recursive: each round reduces its statement to a new statement that can itself be proved using sum-check. That is, rounds are linked together by the following relationship: if the statement at round

$i+1$ is correct, then the statement at round

$i$ is correct.

Before we dive in further, let's introduce some useful notation. Given a function

$f(x_1,x_2):{\mathbb{F}}^2\to \mathbb{F}$, then the function

$f_{r_1}(x_2)$ is a function such that

$$f_{r_1}(x_2)=f(r_1,x_2).$$

That is,

$f_{r_1}:\mathbb{F}\to \mathbb{F}$ is a function of one less variable than

$f$. We say that the variable

$x_1$ is bound to

$f$ (with value

$r_1$) to yield the new function

$f_{r_1}$. Intuitively, all this does is fix the evaluation of the variable

$x_1$ to always be

$r_1$. Naturally, this is not limited to functions of 2 variables.

We are now ready to show why the sum-check protocol properly convinces the verifier that the sum-check problem statement being proved is true. Although not a formal proof, this will be in a format similar to a proof by induction: we will prove the recursive (or "inductive") case, and the base case. We move away from the formal proof format to help convey the intuition behind the proof rather than being formally correct. The recursive case covers how each round reduces its statement to a "smaller" statement, that is also provable using the sum-check protocol. The base case covers the part of the protocol after the last round is over.

Recursive case

To be more concrete, we will look at how the statement in round 1 is reduced to the statement in round 2. However, the idea is the same for every round.

Recall that the statement to prove in round 1 is:

$$\sum _{(x_1,\dots ,x_m)\in \{0,1{\}}^m}g(x_1,\dots ,x_m)=C_1,$$

while the statement to prove in round 2 is:

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}{g}_{r_1}(x_2,\dots ,x_m)=s_1(r_1).$$

There are three key things to notice:

1. the sum is over one less variable in round 2 than it was in round 1,
2. $g$ has been replaced with
   $g_{r_1}$,
3. the right-hand side is a scalar value (i.e.
   $s_1(r_1)\in \mathbb{F}$), which we can name
   $C_2$.

The statement in round 2 is a valid sum-check problem, to which we can apply the sum-check protocol!

Now, crucially, let's see why the statement in round 1 reduces to the statement in round 2. That is, if the statement in round 2 is true, then the statement in round 1 is true.

Assume that the second statement is true. That is,

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}{g}_{r_1}(x_2,\dots ,x_m)=s_1(r_1).$$

Then, since

$r_1$ was sampled uniformly at random, by the Schwartz-Zippel lemma,

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}{g}_{x_1}(x_2,\dots ,x_m)=s_1(x_1)\mathrm{\forall }{x}_1\in \mathbb{F}.$$

Or equivalently,

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(x_1,x_2,\dots ,x_m)=s_1(x_1)\mathrm{\forall }{x}_1\in \mathbb{F}.$$

That is, we can now treat the entire polynomials on the left-hand side and the right-hand side as equal. Then,

$$\begin{array}{rl}{s}_1(0)+s_1(1)& =(\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(0,x_2,\dots ,x_m))+(\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(1,x_2,\dots ,x_m))\\ & =\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(0,x_2,\dots ,x_m)+g(1,x_2,\dots ,x_m)\\ & =\sum _{(x_1,\dots ,x_m)\in \{0,1{\}}^m}g(x_1,\dots ,x_m),\end{array}$$

which is the left-hand side of the statement in round 1! Hence, the statement in round 1 can be written as

$s_1(0)+s_1(1)=C_1$. Unsurprisingly, this is exactly the check that the verifier does in the protocol!

To recap, when we assume that the statement in round 2 is true, then the statement in round 1 can be rewritten as

$s_1(0)+s_1(1)=C_1$. So after the verifier runs this check, all that is left to show is that the statement in round 2 is actually true (which will be carried out in the next round of the protocol). This is another way of saying that the statement in round 1 does indeed reduce to the statement in round 2, which was our initial goal.

Next, we will look at the base case, which occurs after round

$m$.

Base case

The statement left to prove after round

$m$ is:

$$g_{r_1,\dots ,r_m}=s_m(r_m)$$

That is, there is no more sum left, and all the variables are bound. Recall that in round

$m$, the verifier received the polynomial

$s_m$, and randomly sampled

$r_m{\in }_R\mathbb{F}$.

Now, this check is trivially done by the verifier. The verifier evaluates

$g(r_1,\dots ,r_m)$ to yield the left-hand side of the statement, and checks if it is equal to

$s_m(r_m)$.

Since this was the last statement to prove in the protocol, then the verifier is convinced that the original statement in round 1 is correct!

The Specialized Sum-Check protocol

We will now look at a specialization of the problem statement that turns out to be quite useful in practice. We call it a "specialization" because we make more assumptions about the structure of the inner sum than in the traditional sum-check protocol.

Problem statement

The sum-check problem statement can be specialized to:

$$\sum _{(x_1,\dots ,x_m)\in \{0,1{\}}^m}g(f_1(x_1,\dots ,x_m),\dots ,f_n(x_1,\dots ,x_m))=C_1,$$

where

$f_1,\dots ,f_n$ are multilinear polynomials. Notice that when

$f_i(x_1,\dots ,x_m)=x_i$, then we recover the vanilla problem statement explored in the previous sections.

The protocol

The protocol works exactly the same as the vanilla sum-check protocol. The

$s_i$ polynomials are defined similarly:

$$s_1(x_1)=\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g(f_1(x_1,x_2,\dots ,x_m),\dots ,f_n(x_1,x_2,\dots ,x_m)),$$

$$s_2(x_2)=\sum _{(x_3,\dots ,x_m)\in \{0,1{\}}^{m-2}}g({f_1}_{r_1}(x_2,x_3,\dots ,x_m),\dots ,{f_n}_{r_1}(x_2,x_3,\dots ,x_m)),$$

$$\cdots$$

Analysis

The argument for why the specialized sum-check protocol is sound is actually the same as for the previous one. We will briefly look at the recursive case, again by focusing on how the problem statement in round 1 reduces to the problem statement in round 2.

Assume that the problem statement in round 2 is true. That is,

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}g({f_1}_{r_1}(x_2,\dots ,x_m),\dots ,{f_n}_{r_1}(x_2,\dots ,x_m))=s_1(r_1),$$

This is actually the same state as in the vanilla problem. To make this a bit more clear, let's rewrite the summand slightly. We define

$h_{r_1}(x_2,\dots ,x_m)$ as

$$h_{r_1}(x_2,\dots ,x_m)=g({f_1}_{r_1}(x_2,\dots ,x_m),\dots ,{f_n}_{r_1}(x_2,\dots ,x_m))$$

Notice that

$h_{r_1}$ is nonlinear in all its variables. Then, we can rewrite the problem statement in round 2 as

$$\sum _{(x_2,\dots ,x_m)\in \{0,1{\}}^{m-1}}{h}_{r_1}(x_2,\dots ,x_m)=s_1(r_1).$$

Hopefully, it is now clear that since this is the same form as in the vanilla sum-check problem, then the exact same argument for the recursive case applies.

As for the base case, the verifier needs to check

$$g(f_1(r_1,\dots ,r_m),\dots ,f_n(r_1,\dots ,r_m))=s_m(r_m).$$

Efficient evaluation of round polynomials

$s_i$

This specialization is useful in practice, in part because there exists an efficient algorithm for the prover to construct the polynomials

$s_i$ at each round. We go over the algorithm in great detail in this note.