The Sum-Check Protocol
Suppose we are given a -variate polynomial defined over a finite field .
The purpose of the sum-check protocol is to compute the sum:
What does the verifier gain by using the sum-check protocol?The verifier could clearly compute on her own by evaluating at inputs (namely, all inputs in ), but we are thinking of as an unacceptably large runtime for the verifier. Using the sum-check protocol, the verifier's runtime will be
This is much better than the evaluations of required to compute unassisted. It also turns out that the prover in the sum-check protocol can compute all of its prescribed messages by evaluating at inputs in . This is only a constant factor more than what is required simply to compute without proving correctness.
For presentation purposes, we assume that the verifier has oracle access to , i.e., can evaluate for a randomly chosen vector with a single query to an oracle.
1Description of Sum-Check Protocol
At the start of the protocol, the prover sends a value claimed to equal the value defined in (1). In the first round, sends the univariate polynomial claimed to equal
checks that
and that is a univariate polynomial of degree at most , rejecting if not. Here, denotes the degree of in variable
chooses a random element , and sends to . In the th round, for sends to a univariate polynomial claimed to equal
checks that is a univariate polynomial of degree at most , and that , rejecting if not.
chooses a random element , and sends to In Round sends to a univariate polynomial claimed to equal
checks that is a univariate polynomial of degree at most , rejecting if not, and also checks that
chooses a random element and evaluates with a single oracle query to . checks that , rejecting if not. If has not yet rejected, halts and accepts.
Description of the Start of The Protocol
At the start of the sum-check protocol, the prover sends a value claimed to equal the true answer (i.e., the quantity defined in (1)). The sum-check protocol proceeds in rounds, one for each variable of . At the start of the first round, the prover sends a polynomial claimed to equal the polynomial defined as follows:
is defined to ensure that
Accordingly, the verifier checks that , i.e., the verifier checks that and the claimed answer are consistent with Equation (3).
Throughout, let denote the degree of variable in . If the prover is honest, the polynomial has degree . Hence can be specified with field elements, for example by sending the evaluation of at each point in the set , or by specifying the coefficients of .
The Rest of the Round 1
Recall that the polynomial sent by the prover in round 1 is claimed to equal the polynomial defined in (2). The idea of the sum-check protocol is that will probabilistically check this equality of polynomials holds by picking a random field element , and confirming that
Clearly, if is as claimed, then this equality holds for all (i.e., this probabilistic protocol for checking that as formal polynomials is complete).
Meanwhile, if , then with probability at least over the verifier's choice of , Equation (4) fails to hold. This is because two distinct degree univariate polynomials agree on at most inputs. This means that this protocol for checking that by checking that equality holds at a random input is sound, so long as .
The remaining issue is the following: can efficiently compute both and , in order to check that Equation (4) holds?
Since sends an explicit description of the polynomial , it is possible for the to evaluate in time.
In contrast, evaluating is not an easy task for , as is defined as a sum over evaluations of . This is only a factor of two smaller than the number of terms in the sum defining .
Fortunately, Equation (4) expresses as the sum of the evaluations of a -variate polynomial over the Boolean hypercube (the polynomial being that is defined over the variables . This is exactly the type of expression that the sum-check protocol is designed to check. Hence, rather than evaluating on her own, instead recursively applies the sum-check protocol to evaluate
Recursive Description of Rounds
The protocol thus proceeds in this recursive manner, with one round per recursive call. This means that in round , variable gets bound to a random field element chosen by the verifier.
This process proceeds until round , in which the prover is forced to send a polynomial claimed to equal
When the verifier goes to check that , there is no need for further recursion: since the verifier is given oracle access to can evaluate with a single oracle query to .
Iterative Description of the Protocol
Unpacking the recursion described above, here is an equivalent description of what happens in round of the sum-check protocol.
At the start of round , variables have already been bound to random field elements , and chooses a value uniformly at random from and sends to . In return, the prover sends a polynomial , and claims that
The verifier compares the two most recent polynomials by checking , and rejecting otherwise. The verifier also rejects if the degree of is too high: each should have degree at most , the degree of variable in .
In the final round, the prover has sent which is claimed to be now checks that (recall that we assumed has oracle access to ). If this check succeeds, and so do all previous checks, then the verifier is convinced that
2Example Execution of the Sum-Check Protocol
Let .
The sum of 's evaluations over the Boolean hypercube is .
When the sum-check protocol is applied to , the honest prover's first message in the protocol is the univariate polynomial equal to:
The verifier checks that , and then sends the prover . Suppose that . The honest prover would then respond with the univariate polynomial
The verifier checks that , which amounts in this example to confirming that indeed, both the left hand side and right hand side equal 69 .
The verifier then sends the prover . Suppose that .
The honest prover would respond with the univariate polynomial .
The verifier picks a random field element and confirms that by making a oracle query to .
3Completeness and Soundness
Let be a -variate polynomial of total degree at most in each variable, defined over a finite field . For any specified , let be the language of polynomials (given as an oracle) such that
The sum-check protocol is an interactive proof system for with completeness error and soundness error .
Completeness is evident: if the prover sends the prescribed polynomial at all rounds , then will accept with probability 1.
We offer two proofs of soundness, the first of which reasons in a manner analogous to the recursive description of the protocol, and the second of which reasons in a manner analogous to the iterative description.
Inductive Proof of Soundness
One way to prove soundness is by induction on .
In the case , 's only message specifies a degree univariate polynomial If , then because any two distinct degree univariate polynomials can agree at most inputs, with probability at least over the choice of , and hence 's final check will cause to reject with probably at least
Assume by way of induction that for all -variate polynomials, the sum-check protocol has soundness error at most
Let Suppose sends a polynomial in Round Then because any two distinct degree univariate polynomials can agree at most inputs, with probability at least
Conditioned on this event, is left to prove the false claim in Round 2 that . Since is a -variate polynomial of total degree , the inductive hypothesis implies that will reject at some subsequent round of the protocol with probability at least Therefore, will reject with probability at least
Non-Inductive Proof of Soundness.
A second way to prove soundness conceptually follows the iterative description of the sum-check protocol.
Specifically, if , then the only way the prover can convince the verifier to accept is if there is at least one round such that the prover sends a univariate polynomial that does not equal the prescribed polynomial
and yet .
For every round and both have degree at most , and hence if , the probability that is at most . By a union bound over all rounds, we may conclude that the probability that there is any round such that the prover sends a polynomial yet is at most .
4Discussion of costs
denotes the cost of an oracle query to
Communication: field elements Rounds: time: time: if for all
There is one round in the sum-check protocol for each of the variables of .
The total prover-to-verifier communication is field elements, and the total verifier-to-prover communication is field elements (one per round).
In particular, if for all , then the communication cost is field elements.
The running time of the verifier over the entire execution of the protocol is proportional to the total communication, plus the cost of a single oracle query to to compute