These are my scribe notes for the talk and are loosely based on Chapter 4 of Justin Thaler’s new textbook (Thaler, 2022).
The notes for this document all follow a common theme. I have a prover and a verifier. The verifier wants to perform some computation, say it wants to know the product of two matrices A and B over a large finite field. The computation will most often be described by some shallow arithmetic circuit, where the inputs are provided by the verifier. We will assume that the verifier always has less resources than needed to solve the problem by themselves, and therefore they need to delegate computation to someone else - the prover. Now as the verifier is not computing the answer to his own question, it must be able to verify1 what the prover sends him is correct.
NOTE: These algorithms are not the most efficient ways to solve the problem in itself, but they are efficient ways of someone convincing me (the verifier) that they(the prover) did in fact give me the correct answer for the problem. How they did so isn’t my problem. What we are really after, is instances where verification is cheaper than the computation itself. Of course, it is ideal if the delegated computation itself is efficient, so we can deploy such algorithms in the real world (referred to later in the document as doubly efficient proofs).
The purpose of the sum-check protocol is for prover to provide the verifier with the sum of a polynomial l-variate polynomial g evaluated for all possible boolean values.
\begin{equation} H:= \sum_{b_1 \in \{ 0, 1\}}\sum_{b_2 \in \{ 0, 1\}}\dots\sum_{b_l \in \{ 0, 1\}} g(b_1, \dots, b_l) \end{equation}
Note if there was no prover then the verifier could do this computation in 2^l time if they had oracle access to g. By having a prover, we can reduce the verifiers’ runtime to O(l+ cost of evaluating g at a single point ). However it is important to remember that we have not removed the burden of computation, but simply delegated it to someone else, in this case the prover. The sum-check algorithm proceeds as follows (the info communicated is shown in bold):
V given oracle access to l-variate polynomial of degree at most d, g: \mathbb{Z}_p^l \rightarrow \mathbb{Z}_p. Goal is to compute:
\begin{equation} H:= \sum_{b_1 \in \{ 0, 1\}}\sum_{b_2 \in \{ 0, 1\}}\dots\sum_{b_l \in \{ 0, 1\}} g(b_1, \dots, b_l) \end{equation}
Right at the start, the prover P sends an answer C_1. V must check if C_1 = H. This is the game.
P sends the uni-variate polynomial s_1(X): \mathbb{Z}_p \rightarrow \mathbb{Z}_p to V which it claims to be H_1(X) where \begin{equation} H_1(X) = \sum_{b_2 \in \{ 0, 1\}}\dots\sum_{b_l \in \{ 0, 1\}} g(X_1, b_2 \dots, b_l) \end{equation}
V checks C_1 = s_1(0)+s_1(1). If this test does not hold then V outputs \mathsf{Reject}. If H_1(X) = s_1(X), then the verifier can be convinced C_1 is good and the prover behaved appropriately. But the verifier must check if indeed H_1(X) = s_1(X)? The rest of the protocol is all about the verifier convincing themselves that s_1(X) = H_1(X).
Communication: V sends to P, r_1 \xleftarrow{R} \mathbb{Z}_p.
P responds with another univariate polynomial which they claim to be s_2(X_2; r_1).
\begin{equation} s_2(X_2; r_1) = \sum_{b_3 \in \{ 0, 1\}}\dots\sum_{b_l \in \{ 0, 1\}} g(r_1, X_2, b_3 \dots, b_l) \end{equation}
V verifies whether s_1(r_1) = s_2(0; r_1) + s_2(1; r_1). If this check fails, V outputs \mathsf{Reject}. Otherwise, it sends P r_2 \xleftarrow{R} \mathbb{Z}_p
Now for 2 < j < l this process repeats, where P sends to V another uni-variate polynomial s_j(X_j; r_1, \dots, r_{j-1}) which is supposed to equal (but may not if P is corrupt)
\begin{equation} s_j(X_j; r_1, \dots, r_{j-1}) = \sum_{b_{j+1} \in \{ 0, 1\}}\dots\sum_{b_l \in \{ 0, 1\}} g(r_1, \dots,r_{j-1}, X_j, b_{j+1}, \dots, \dots, b_l) \end{equation}
Again which V checks whether s_{j-1}(r_{j-1}; r_1, \dots, r_{j-2}) = s_j(0; r_1, \dots, r_{j-1}) + s_j(1; r_1, \dots, r_{j-1}) If any of these checks fail, V outputs \mathsf{Reject}.
In the l’th round P sends to V a univariate polynomial s_l(X_l; r_1, \dots, r_{l-1})
V checks that s_{l-1}(r_{l-1}; r_1, \dots, r_{j-2}) = s_l(0; r_1, \dots, r_{l-1}) + s_l(1; r_1, \dots, r_{l-1}). If the check does not go through, then V outputs \mathsf{Reject}.
V picks r_l \xleftarrow{R} \mathbb{Z}_p and sends to the oracle g(r_1, \dots, r_l) and checks if s_l(r_l; r_1, \dots, r_{l-1}) = g(r_1, \dots, r_l).
The sum-check protocol is an interactive proof system for L with completeness error \delta_c = 0 and soundness error \delta_s \leq \frac{ld}{|F|}.
The completeness proof is by construction. If s_1(X) = H(X) then C_1 = H.
Assume that the prover is corrupt and sent bad messages but the verifier accepts. Accepting implies that all of the s_{j-1}(r_{j-1}; r_1, \dots, r_{j-2}) = s_{j}(0; r_1, \dots, r_{j-1}) + s_{j}(0; r_1, \dots, r_{j-1}) checks passed.
Since s is a univariate polynomial with degree at most d (s_j could be a lower degree polynomial for a particular X_j), this check erroneously passes if both sides of the equation are 0 i.e. we have sampled a root for both sides, which by Schwartz-Zippel happens with probability at most \frac{d}{|F|}. There are l rounds so applying union bound, we get the total probability of an accidental pass is at most \frac{ld}{|F|}. \square
Communication: For each round of r \in l, the prover sends a polynomial of degree deg_r(g), thus sends to the verifier deg_r(g) + 1 finite field elements. The verifier sends 1 element per round. So the total communication is O\Big(l + \sum_{r=1}^l deg_r(g) \Big).
Computation For Verifier: O\Big(l + \sum_{r=1}^l deg_r(g) \Big) + T; l rounds of 1 univariate polynomial evaluation and 1 random sample. Finally the time taken to do one oracle evaluation.
Computation For Prover: At each round r \in [0, l], the number of possible possible x’s to sum over is 2^{l-i} and each evaluation takes time to evaluate a polynomial of deg_r(g)+1. So total time is O\Big(\sum_{r=1}^l2^{l-i}(deg_r(g)+1)\Big)
The verifier does not need to know what g is. All they need is oracle access to one call for g(x_1, \dots, x_l) and they need to know an upper bound for deg(s_j(x)) for j \in [l], so they can verify the degree of the univariate polynomials that the prover sends.
The prover on the other hand must know the details of g exactly.