Home > Resources > papers > LFKN92-Sumcheck

Algebraic Methods for Interactive Proof Systems

DOI: 10.1145/146585.146605 · URL: https://dl.acm.org/doi/10.1145/146585.146605

Summary

Introduces the sumcheck protocol, showing that any language in the polynomial hierarchy has an interactive proof system. The sumcheck protocol lets a prover convince a verifier that the sum of a multilinear polynomial over all Boolean inputs equals a claimed value, using only O(n) rounds and a single evaluation of the polynomial at a random point. Together with Shamir's result, this established IP = PSPACE. The sumcheck protocol is now a core building block of modern transparent ZKP systems (GKR, Spartan, HyperPlonk, Libra).

Used by

• SumcheckProofs

Related resources

• Fast Probabilistic Algorithms for Verification of Polynomial Identities (paper, 1980)
• HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates (Chen et al. 2023) (paper, 2023)
• Proofs, Arguments, and Zero-Knowledge (book, 2023)
• Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup (Setty 2020) (paper, 2019)