A sum-check protocol is a cryptographic protocol for the construction of interactive proof systems, used widely in zero-knowledge protocols.
History The sum-check protocol was created by Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan and formalized in 1990.
Concept In an interactive proof, the goal is for a verifier V to offload an expensive computation to an untrusted prover P. The sum-check protocol allows the prover to convince the verifier that the sum of a multivariate polynomial is equal to a known value. The goals of the sum-check protocol are to make the verifier run in time linear to the input size, to keep the proof logarithmically small, and to keep the prover efficient. For a v-variate polynomial g defined over a finite field F {\displaystyle \mathbb {F} } , the prover provides the verifier with the following sum:
H := ∑ b 1 ∈ { 0 , 1 } ∑ b 2 ∈ { 0 , 1 } ⋯ ∑ b v ∈ { 0 , 1 } g ( b 1 , … , b v ) . {\displaystyle H:=\sum _{b_{1}\in \{0,1\}}\sum _{b_{2}\in \{0,1\}}\cdots \sum _{b_{v}\in \{0,1\}}g(b_{1},\ldots ,b_{v}).}
Without a prover, the verifier has to perform 2 n {\displaystyle 2^{n}} evaluations of g to verify the statement, which is a very large runtime. With the sumcheck protocol, the verifier's runtime is O ( v + [the cost to evaluate g at a single input in F v ] ) {\displaystyle O(v+{\text{[the cost to evaluate }}g{\text{ at a single input in }}\mathbf {F} ^{v}])} .
Limitations
Proof size The sum-check protocol leads to proofs that are of at least logarithmic length.
Zero-knowledge and succinctness The protocol is not zero-knowledge by itself, and like all interactive proofs, it is not succinct for NP statements. zk-SNARK proofs combine the sum-check protocol with commitment schemes to obtain zero-knwoledge and succinct arguments.
See also Cryptographic protocol Interactive proof systems Zero-knowledge proof
References
External links Thaler, Justin (July 18, 2023). "3.1, 4.1, 4.2". Proofs, Arguments, and Zero-Knowledge (PDF). Georgetown University. Tauman Kalai, Yael (2023). "Lecture 1: Interactive Proofs and the Sum-Check Protocol". MIT OpenCourseWare, Advanced Topics in Cryptography. Archived from the original on 20 March 2025. Retrieved 2025-08-25.
