Motivation
A verifier may be unable to add exponentially many values one by one, yet it can ask an unrestricted prover for a short summary and test that summary at a random point. The sum-check protocol makes this idea precise for a polynomial over a finite field. Its power comes from two facts: a false polynomial identity of bounded degree has few roots, and the verifier chooses each challenge after seeing the prover's current message.
Definition 9.2.1
(The sum-check problem)
Let be a finite field of size , let , and let have degree at most in each variable separately. The verifier receives a claimed value and a representation of as an arithmetic circuit. The question is whether
where the sum is in .
The degree bound is part of the problem promise or is verified by a syntactic degree certificate; it is not inferred merely by sampling the circuit. The probability analysis first treats an ideal uniform sample from an arbitrary finite field. For the standard fixed-fair-bit interactive-proof consequence below, we restrict to represented by a supplied irreducible binary polynomial: a uniform -bit string is then an exact uniform field element. Examples over illustrate ideal field sampling, not an exact fixed-length fair-bit sampler. Field arithmetic is assumed efficient, and is polynomially bounded, so a list of coefficients is a polynomial-size message.
For a syntactic certificate, assign each input variable degree one in itself and zero in the others, and assign constants degree zero. At an addition gate take the coordinatewise maximum of the two incoming bounds; at a multiplication gate add them. Induction gives an upper bound on each variable's degree. If all output bounds are at most , the promise is certified. Cancellation may make the true degree smaller than this bound, so the test is sufficient rather than necessary.
One round of the protocol
Set the current claim . In round , after the previous random challenges have been chosen, the prover sends coefficients of a univariate polynomial of degree at most . The verifier checks
If the equality fails, it rejects. Otherwise it samples a fresh uniform , sends that challenge to the prover, and sets . After round , the verifier computes using the circuit and accepts exactly when equals that value. A message with more than coefficients is rejected rather than treated as a lower-degree polynomial.
The prover may be computationally unbounded and may choose later messages after seeing the earlier challenges. It cannot see before sending . The verifier does not enumerate the Boolean inputs; it evaluates a circuit once at the final random point and performs polynomially many field operations on the messages.
Concept lensAlgorithmic
Each round is a reduction to one fewer Boolean variable
Write , so is the claimed sum and . Round replaces the claim "" by the claim "". The identity is exactly what the test examines. The random then replaces the two points by one point. After rounds the claim concerns , which the verifier computes itself.
Worked example 9.2.2
(An honest two-variable transcript over F13)
Let and . Its Boolean sum is . In the first round the honest polynomial is
The verifier checks . If its first challenge is , the new claim is . The second honest message is ; its values at zero and one sum to . If , the last claim is , matching in .
Common mistake
(The prover's polynomial is not trusted)
The verifier checks the message length and the claimed sum relation, but it does not know that is the honest partial sum. A dishonest prover may send any allowed polynomial, chosen using the entire previous transcript. Soundness must hold for every such strategy, not just for an honest prover that makes an isolated arithmetic error.
Completeness and adaptive soundness
Theorem 9.2.3
(Sum-check correctness)
If is the Boolean sum of , an honest prover makes the verifier accept for every sequence of challenges. If is false, every prover strategy causes acceptance with probability at most .
Proof
(Proof)
For completeness, in round the honest prover sends
At the sum has one term, with no remaining Boolean variables. Each has degree at most in . Splitting the remaining Boolean sum according to or gives when the current claim is correct. The update makes the correct partial sum after fixing . At the last round it equals , so the verifier accepts.
For soundness, fix any transcript up to the moment just before round 's fresh random challenge, including the prover's chosen polynomial . Define the true partial-sum polynomial by the same formula. Suppose the current claim is false but the verifier's sum check passes. Then cannot equal , since their values at zero and one would otherwise sum to the true previous partial sum. The nonzero polynomial has degree at most and at most roots in . Thus, conditional on this entire past transcript, the fresh uniform makes the false claim become correct with probability at most .
Initially the claim is false. If it never becomes correct, the final comparison with rejects. For acceptance to occur, there must be a first round where a false claim becomes correct. The conditional probability of that event in each round is at most , regardless of the adaptive strategy or earlier challenges. Summing over at most possible first rounds gives acceptance probability at most . Early rejection only decreases that probability.
Proof X-ray
Where the degree bound and the order of messages are spent
The argument has one idea and two hypotheses. The idea is to look for the first round at which a false claim becomes correct. While the claim is false, the honest polynomial cannot pass the check, since is the true partial sum; so a message that passes differs from , and is a nonzero polynomial. The degree bound caps its number of roots at . The order of messages makes those roots a set already fixed when is drawn, so a uniform lands on one with probability at most whatever the history. The proof closes with a union bound over the rounds that could be the first to repair the claim; if no round does, the last claim is still false and the final circuit evaluation rejects. Drop the degree bound and may have roots: over the message against vanishes at all twelve nonzero challenges, as the example below shows.
The root bound applies to a nonzero univariate polynomial, not directly to the multivariate circuit. Fixing earlier variables and summing over later Boolean choices turns each round into a univariate comparison. The proof also uses the order of messages: if the prover could choose after seeing , the conditional root-count argument would not apply.
Counterexample mode
A predictable challenge lets the prover cheat
A tempting simplification is that the challenges need not be random: the verifier could use the fixed point . Take , , , and the false claim . The prover sends . Then , and the verifier's final value is , so it accepts a false claim with probability one. The proof needs to be uniform and chosen after is fixed; a challenge the prover can predict is no better than one it sees first.
Worked example 9.2.4
(The field size controls the soundness bound)
For , and , a false sum is accepted with probability at most . This is a bound against every adaptive prover, not a claim that some prover attains exactly . If the same degree and round count were used over a field with only two elements, the bound would give no useful soundness guarantee. Choosing makes the bound at most .
A multivariate root bound
The sum-check proof only needed a univariate root bound in each round. A related multivariate result is useful in other randomized identity tests. Here total degree is the maximum, over nonzero monomials, of the sum of their exponents.
Proposition 9.2.5
(Finite-field polynomial identity bound)
Let be nonzero with total degree at most . If are independent uniform elements of a finite field of size , then
When the bound may be at least one and then gives no useful information.
Proof
(Proof)
Induct on the number of variables. For one variable, the assertion is the usual bound of at most roots for a nonzero degree- polynomial; a nonzero constant has no roots. For the inductive step, write
with . Every monomial in has total degree at most . By induction, the probability that vanishes at the first random values is at most . If it does not vanish, the resulting univariate polynomial in is nonzero of degree and vanishes with probability at most over the fresh last value. Adding these bounds gives . The case is included: once the nonzero coefficient is fixed, the resulting constant has no root.
Worked example 9.2.6
(A two-variable zero set)
Over , let . It has total degree two and vanishes when or . There are such pairs: the intersection was counted twice. Its zero probability is , below the general bound . The bound need not be exact, and a nonzero polynomial can vanish on some random inputs without being the zero polynomial.
Repetition against an adaptive prover
If , running the protocol times with fresh independent challenges and accepting only if every run accepts gives soundness at most . The prover may adapt its later messages to all earlier transcripts. Nevertheless, conditioned on any history before a new run, the current false claim and the prover's resulting strategy still satisfy the same single-run soundness bound. Multiplying the conditional probabilities of reaching and passing successive runs gives the bound. Perfect completeness is preserved because the honest prover passes every run. Communication and verifier time grow by a factor of , so polynomially many repetitions remain efficient under the stated conventions.
Worked example 9.2.7
(A product polynomial)
Let over . Its Boolean sum is one, since only contributes. The first honest message is . If the verifier chooses , the claim becomes five. The second message is , whose values at zero and one sum to five. With , the verifier checks the final value . Each message has degree one, and the protocol evaluates the original circuit only at the final pair.
Why the degree restriction is necessary
Proposition 9.2.8
(A high-degree cheating message)
Without enforcing the degree bound on prover messages, the final random evaluation need not give a useful soundness guarantee, even when the true polynomial is identically zero.
Proof
(Proof by example)
Take one variable over , let and falsely claim . A dishonest prover sends . Its initial check passes because . For every nonzero , Lagrange's theorem gives , so . The verifier therefore accepts with probability even though the true sum is zero. The message has degree twelve and would be rejected when the allowed degree is .
Worked example 9.2.9
(The field sum is not automatically the integer count)
Let be a Boolean formula's indicator polynomial on Boolean inputs over . If exactly three Boolean assignments satisfy the formula, the sum in is , not the integer three. A sum-check transcript verifies the stated field sum. Recovering an exact integer count, or using arithmetization to prove an interactive characterization of a complexity class, requires further choices and arguments.
Proposition 9.2.10
(An interactive protocol for the promised sum problem)
Under the stated polynomial-message conventions, the promise problem over a supplied binary extension field with and a valid individual-degree bound has a fixed-fair-bit public-coin interactive protocol with perfect completeness and soundness error at most .
Proof
(Proof)
The verifier sends one independently sampled -bit field element after each polynomial message, then evaluates the input circuit once. The coefficient lists have length at most in each of rounds, so communication and verifier time are polynomial under the stated representation and size bounds. Completeness is exact, while the sum-check theorem bounds false-claim acceptance by . These conclusions apply to promised inputs; a field or degree promise that the verifier cannot check is not silently treated as an arbitrary well-formed language instance.
The full theorem uses additional arithmetization, quantifier and degree-control machinery that is not proved here. Sum-check is one component, not a standalone proof of that characterization. The field representation, efficient sampling, degree bound and polynomial message lengths are all part of the protocol's stated setting.
Practice and solutions
Quick check
(For over , compute its sum over the four Boolean pairs.)
Evaluate at .
Solution · Answer
The values are , whose sum is in .
Quick check
(Why is the honest polynomial in each round of degree at most ?)
What happens to the degree when variables are fixed or summed out?
Solution · Answer
Fixing earlier variables and substituting zero or one for later variables cannot increase the degree in the remaining variable. Adding the resulting polynomials also cannot increase their maximum degree.
Quick check
(If a false current claim passes the prover's sum check, why must the sent polynomial differ from the true partial-sum polynomial?)
What do the true polynomial's values at zero and one add up to?
Solution · Answer
The true polynomial's values at zero and one sum to the true previous partial sum. If the current claim is false while the sent polynomial's two values sum to it, the sent polynomial cannot equal the true one.
Quick check
(What is the soundness bound for , and a field of size ?)
Use .
Solution · Answer
The bound is .
Quick check
(In the high-degree cheating example, why does the verifier accept for every nonzero challenge?)
Evaluate in .
Solution · Answer
Every nonzero element of satisfies , so . The initial false-sum check was arranged to pass.
Quick check
(Does verifying a sum in reveal the exact integer number of satisfying assignments?)
Which counts have the same value modulo two?
Solution · Answer
No. It gives the count modulo two. Distinct counts such as one and three have the same value in .