The Sum-Check Protocol
Articles based on Justin Thaler's Proofs, Arguments, and Zero-Knowledge
The sum-check protocol is an interactive proof which can be leveraged in the design of SNARKs. The protocol on its own is information-theoretically secure1 because it does not involve cryptographic operations - only field additions and multiplications. When applied to SNARK design however, the sum-check protocol is combined with cryptographic primitives in order to yield an argument.2
The ultimate goal of the sum-check protocol in SNARK design is to reduce a claim made by a prover to a set of operations that can be executed efficiently by a corresponding verifier. In this article, we will learn the inner workings of the sum-check protocol while also touching on its practical applications.
Hypothetical Context
Before we drill into the mathematical definition of the sum-check protocol, lets try to understand the protocol at a high level in the context of a hypothetical arithmetic circuit, a prover P and a verifier V.3
P wants to convince V that some circuit was executed correctly with a specific witness and that they know a multivariate polynomial f which represents this execution. The polynomial f was derived from an algebraic representation of the circuit which contains M constraints and N variables. Somehow, V must be convinced that f is the reduction of M many constraint polynomials that evaluate to 0 when paired up with their corresponding variables from the execution trace.
Because we want our interactive proof to be succinct,4 we need V’s runtime to be much more efficient than the runtime exhibited by P’s construction of the proof for f. This efficiency can be achieved through the sum-check protocol, which allows P’s claim about M constraints to be reduced to a single claim about a random linear combination of those constraints. The randomness in this linear combination is provided by V and it allows the protocol to leverage the probabilities involved in the Schwartz-Zippel lemma which we have covered extensively in previous articles.
If the number of constraints M is equal to 2ᵐ, then the sum-check protocol involves m many rounds of interaction between P and V.5 V must also compute an evaluation of f at the end of the protocol, meaning that V’s runtime is O(m+z) where z is the cost to evaluate f at a single input in the relevant field. This is a drastic improvement from O(2ᵐ) which is P’s runtime when computing the polynomial f.
The Protocol
Now that we have some high level context for the sum-check protocol in SNARKs, lets define the protocol precisely as an interactive proof.
As above, the prover P has a v-variate polynomial f defined over a finite field Fp.
P claims to know the sum of the evaluations of all Boolean inputs (the Boolean hypercube) over f.6
P sends this sum S to V.
The remainder of the protocol is designed to reach a stage where V can confirm the correctness of S, to a sufficiently high probability of success, through a single evaluation of f. To reach this final stage however, V and P must execute v rounds of communication, each of which involve a single low degree univariate polynomial derived from f.
The v number of rounds of the protocol proceed as follows.
Round 1
Firstly, P sends the univariate polynomial g₁(X₁) which is claimed to be the sum of f over a subset of the entire set of variables, namely (x₂,…,xᵥ):
Lets compare this equation to the one for S. The difference is that the first variable x₁ of our v-variate polynomial has been replaced with a fixed variable X₁. The value of X₁ in our domain is either 0 or 1, so V is able to verify the following:
At this point, V has been able to compute the claimed sum of f over the Boolean hypercube much more efficiently than P did. However, V is not yet convinced that the claimed sum is in fact the correct sum. The remainder of the protocol will allow V to be convinced of the correctness of S.
V must also check that g₁ is a univariate polynomial of degree less than or equal to the degree of x₁ in f.
V then selects a random element r₁ from Fp and sends it to P.
Remaining Rounds
The process from round 1 is repeated for all remaining variables (x₂,…,xᵥ).
For each of the ith rounds, P sends a univariate polynomial gᵢ(Xᵢ) claimed to equal:
V checks that gᵢ is a univariate polynomial of degree less than or equal to the degree of xᵢ in f.
V checks that the evaluation of the previous univariate polynomial and corresponding random element is equal to the sum of evaluations of gᵢ over Boolean inputs for Xᵢ:
V selects another random element rᵢ from Fp and sends it to P.
Final Round
During the final round, V will gain access to gᵥ which is confirmed to be a univariate polynomial of sufficiently low degree equal to:
V then selects a final random element rᵥ and confirms the following equality:7
If this check succeeds, then V is convinced as to the correctness of P’s original statement that the evaluation of f over all Boolean inputs is equal to S.
Minimal Worked Example
Lets walk through a worked example of the sum-check algorithm to improve our understanding of the protocol.
We define the multivariate polynomial f as follows:8
The sum of the evaluations of f over the Boolean hypercube is S=18:
The first univariate polynomial g₁ provided by the prover is as follows:
The verifier checks that g₁ is a univariate polynomial of degree at most 1 and that the sum of its evaluations over Boolean inputs is equal to S=18.
The verifier selects a random r₁=3. The prover responds with a second univariate polynomial g₂:
The verifier checks that g₂ is a univariate polynomial of degree at most 2 and that the sum of its evaluations over binary inputs is equal to g₁(r₁):
The verifier selects a random r₂=2. The prover responds with a third univariate polynomial g₃:
The verifier checks that g₃ is a univariate polynomial of degree at most 3 and that the sum of its evaluations over binary inputs is equal to g₂(r₂):
The verifier selects a random r₃=1 and confirms that f(r₁,r₂,r₃)=g₃(r₃):
After this final check, the verifier is convinced that the original claim by the prover that S=18 is in fact correct.
Example in Rust
The above worked example can be executed from the Rust crate found here:
$ cargo run -p sumcheck
Defined: f = a + 2b^2 + 3ac^3
Round 1: g_1 = 4 + 10x r_1 = 3
Round 2: g_2 = 15 + 4x^2 r_2 = 2
Round 3: g_3 = 11 + 9x^3 r_3 = 1
Finalized: g_3(r_3) = 20The crate is factored to be an approachable learning resource. For example, instead of random values, the code uses the r₁, r₂, and r₃ from the worked example above. The protocol round functions are also factored to reflect the iterative breakdown covered in this article. So if you are interested in getting a better understanding of the protocol, a look into the code and its explanatory comments should be very helpful.
Sum-Check in Snark Design
Justin Thaler refers to the sum-check protocol as a “hammer in the design of efficient interactive proofs”.9 In Chapter 4 of the book, Thaler shows how the sum-check protocol can be used to implement application-specific interactive proofs. This includes interactive proofs for triangle counting, matrix multiplication, and Boolean circuit satisfiability.
The sum-check protocol is leveraged by many modern SNARK systems both as a fundamental component to GKR and as a stand-alone building block in its own right.
Information-theoretic secure systems are secure against adversaries with infinite compute and time. This is in contrast to systems whose security relies on the computational cost of cryptanalysis.
Cryptographic primitives such as checksums involved in the Fiat-Shamir transformation and witness commitments.
Note that the sum-check protocol is just one component of the proof system in this hypothetical scenario. But we can ignore the other components for now.
Remember that SNARKs require verifier time complexity to be logarithmic to the circuit size.
A circuit can easily have a billion constraints.
In the previous article about multilinear extensions we introduced the concept of the Boolean hypercube.
In the formal definition of the sum-check protocol, the verifier requires an oracle query to f for this step. In practice, the verifier would either be able to efficiently evaluate f(r₁,…,rᵥ) or would have to ask the prover to perform the evaluation and provide a proof for the claimed evaluation.
Note that we have replaced the X₁, X₂, and X₃ notation with a, b, and c here simply for readability.