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 , the prover provides the verifier with the following sum:
Without a prover, the verifier has to perform evaluations of g to verify the statement, which is a very large runtime. With the sumcheck protocol, the verifier's runtime is.
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