Checking without redoing
A rollup operator claims that it executed ten thousand transactions correctly and that the new state root is a particular 32-byte value. A phone app receives a medical model's diagnosis computed on a cloud server. A university's grading service says it ran a student's code on 400 hidden tests. In each case one party, the prover, did a large computation, and another party, the verifier, wants to be sure the answer is right without doing the computation again. Re-execution is exactly what the verifier cannot afford: the phone is too weak, and on Ethereum every step of re-execution costs gas paid by everyone. Optimistic rollups sidestep the problem with fraud proofs and a challenge period (Scaling: rollups and data availability); this level is about the other answer.
That answer is a proof that is much faster to check than the computation it vouches for. This lesson builds the first mathematical tools for it. They come from complexity theory of the 1980s and early 1990s, and they share one surprising idea: a verifier who is allowed to ask random questions can be convinced of things it could never check deterministically, while being fooled only with a probability so small it can be ignored. By the end you will have run the sumcheck protocol, the engine inside many of the fastest proof systems of 2026, and caught a lying prover with it.
What a proof system is
Fix a claim, written formally as "" for some language : "this graph has 3 triangles", "this program outputs 42 on that input", "this state root follows from that block". A proof system is a pair of algorithms, a prover and a verifier , that exchange messages about ; at the end accepts or rejects.
Definition— interactive proof
An interactive proof for is a protocol between a prover and a probabilistic verifier that runs in polynomial time in , such that:
- Completeness: if , the honest prover makes accept with probability at least (often exactly 1).
- Soundness: if , then for every prover strategy , however clever and however much computing power it has, accepts with probability at most , the soundness error.
The costs that matter are the verifier's time, the prover's time, the number of rounds and the total communication.
Soundness quantifies over all provers, including ones with unlimited computing power. Later in this level we relax that to provers that run in polynomial time and cannot break a cryptographic assumption; such systems are called arguments, and the "A" in SNARK stands for one (Arithmetisation and SNARKs). Everything in this lesson is unconditional: no cryptography at all, only probability and algebra.
NP certificates versus interactive proofs. You already know one kind of proof system from hard problems: an NP certificate. To prove that a graph has a 3-colouring, hand over the colouring; the verifier checks every edge, deterministically, and is never fooled. That works well when a short certificate exists and checking it is cheap. It is useless for claims like "this graph has exactly 3 triangles", or "this program ran for a billion steps and printed 42": the natural certificate is the whole computation, and checking it means redoing it.
Interaction alone does not help. If is deterministic, the prover can predict every question will ask, so it could have written the whole conversation down in advance and sent it as a single certificate: deterministic interactive proofs prove exactly the NP statements. Randomness is what changes the picture. A question the prover cannot predict forces the prover to be ready for all questions at once, and that is a far stronger constraint than being ready for one.
A first random check: Freivalds' algorithm
Here is the simplest example of the idea, from randomised algorithms: a prover claims that for matrices. Recomputing costs about multiplications with the school method. Rūsiņš Freivalds observed in 1977 that the verifier can instead pick a random vector and check whether
which takes three matrix–vector products, about multiplications. If the check always passes. If , then has some nonzero row, and the check passes only if that row happens to be orthogonal to .
Theorem— Freivalds' error bound
Work over a field and let be finite. If and the entries of are chosen independently and uniformly from , then .
Proof
Let , and pick an entry . The check passes only if row of is zero: . Fix all with first; then exactly one value of satisfies this equation, and hits it with probability at most .
∎
With 0/1 vectors the error is at most per trial; with drawn from a prime field it is at most . The code below works modulo , plants a single wrong entry among , and measures how often each kind of random vector lets it through.
import numpy as np
p = 101 # a toy prime field F_101: for learning only
rng = np.random.default_rng(2026)
n = 200
A = rng.integers(0, p, (n, n))
B = rng.integers(0, p, (n, n))
C = (A @ B) % p # the prover's claimed product (correct)
C_bad = C.copy()
C_bad[17, 42] = (C_bad[17, 42] + 1) % p # one wrong entry out of 40,000
def freivalds(A, B, C, r):
"""Accept iff A(Br) = Cr (mod p): three matrix-vector products, about 3n^2 multiplications."""
return np.array_equal((A @ ((B @ r) % p)) % p, (C @ r) % p)
trials = 10000
for name, vectors in [("random 0/1 vector", lambda: rng.integers(0, 2, n)),
("random vector in F_101", lambda: rng.integers(0, p, n))]:
honest = all(freivalds(A, B, C, vectors()) for _ in range(200))
fooled = sum(freivalds(A, B, C_bad, vectors()) for _ in range(trials))
print(f"{name:24} honest C always accepted: {honest} "
f"wrong C accepted {fooled}/{trials} = {fooled / trials:.4f}")
print(f"\nmultiplications: recompute AB = {n**3:,} Freivalds check = {3 * n * n:,}")The 0/1 vectors let the bad product through about half the time, exactly as the bound predicts for a single wrong entry, and vectors over about one time in a hundred. Twenty independent 0/1 trials would push the error below one in a million. Meanwhile the check costs multiplications instead of , and the gap grows with .
Freivalds' check is not yet a proof system: the prover just sends . But it shows the pattern we will reuse. The verifier reduces "these two big objects are equal" to "these two random fingerprints are equal", and algebra guarantees that unequal objects rarely have equal fingerprints.
Polynomial identity testing and the Schwartz–Zippel lemma
The workhorse behind every random check in this level is a fact about polynomials. A nonzero polynomial of degree in one variable has at most roots, so a random point of a large field is very unlikely to be one of them. The same holds with many variables.
Theorem— Schwartz–Zippel lemma
Let be a nonzero polynomial in variables of total degree at most over a field , and let be finite. If are chosen independently and uniformly from , then
Proof
Induction on . For , has at most roots. For , write as a polynomial in whose coefficients are polynomials in the other variables: with . Then has total degree at most , so by induction . If , then is a nonzero polynomial of degree in , which vanishes at with probability at most . Adding the two bad events gives at most .
∎
The lemma (published independently by Jacob Schwartz, Richard Zippel, and Richard DeMillo with Richard Lipton around 1978–1980) gives polynomial identity testing: to decide whether two expressions and are the same polynomial, evaluate at a random point. If they differ, a random point exposes the difference with probability at least . No known deterministic polynomial-time algorithm does this for polynomials given as arbitrary arithmetic formulas; finding one is a famous open problem.
Here is an identity that Brahmagupta stated in the 7th century, , tested at random points, together with a version containing one sign error. Over a small field we can also count exactly how many points fail to expose the typo.
import random
from itertools import product
# Brahmagupta's identity (7th century): (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2.
def lhs(a, b, c, d, p):
return (a * a + b * b) * (c * c + d * d) % p
def rhs(a, b, c, d, p):
return ((a * c - b * d) ** 2 + (a * d + b * c) ** 2) % p
def rhs_typo(a, b, c, d, p): # one sign wrong: + instead of -
return ((a * c + b * d) ** 2 + (a * d + b * c) ** 2) % p
def identity_test(f, g, p, trials, rng):
"""Schwartz-Zippel: evaluate both sides at random points of F_p^4."""
for _ in range(trials):
x = [rng.randrange(p) for _ in range(4)]
if f(*x, p) != g(*x, p):
return "different"
return "probably equal"
rng = random.Random(7)
P = 2**61 - 1 # a large prime: one trial errs with prob <= 4/P
print("true identity :", identity_test(lhs, rhs, P, 5, rng))
print("typo version :", identity_test(lhs, rhs_typo, P, 5, rng))
# How often does a single random point fail to expose the typo? Count exactly over a small field.
for p in [13, 31]:
agree = sum(lhs(*x, p) == rhs_typo(*x, p) for x in product(range(p), repeat=4))
print(f"F_{p}: the two sides agree at {agree} of {p**4} points = {agree / p**4:.4f}"
f" (Schwartz-Zippel bound d/p = 4/{p} = {4 / p:.4f})")Multilinear extensions
Proof systems need to turn data into polynomials, so that Schwartz–Zippel can be applied to the data. A table of values is naturally a function , indexed by -bit strings. The most economical polynomial that agrees with it is multilinear.
Definition— multilinear extension
A polynomial is multilinear if it has degree at most 1 in each variable. For every there is exactly one multilinear polynomial that agrees with on , its multilinear extension (MLE):
Each is 1 at and 0 at every other point of the cube, so the sum agrees with there. Uniqueness: the difference of two such polynomials is multilinear and vanishes on the whole cube, and a multilinear polynomial that vanishes on is zero (induct on , as in the proof above).
Evaluating at a point does not require the -term sum to be computed naively. Because is linear in ,
so fixing the first variable folds a table of values into a table of values, one multiplication per entry. Folding times leaves the single value , for about multiplications in all: linear in the size of the table.
The sumcheck protocol
Now the main event. Let be a polynomial over a prime field with degree at most in each variable. The prover claims
Computing directly needs evaluations of . The sumcheck protocol of Lund, Fortnow, Karloff and Nisan (1990) lets the verifier check the claim with short messages, field operations, and a single evaluation of at a random point. The idea is to peel off one variable per round, each time replacing a claim about a sum with a claim about a smaller sum at a random point.
Definition— sumcheck protocol
Set . In round :
- The prover sends a univariate polynomial of degree at most (as its values at ), claimed to equal
- The verifier checks that , rejecting otherwise.
- The verifier picks uniformly at random, sends it, and sets .
Finally the verifier evaluates itself and accepts if and only if it equals .
If the prover is honest, every check passes: is the sum over one more Boolean variable, which is precisely . Why can't a liar pass?
Theorem— Soundness of sumcheck
If is not the true sum, then whatever the prover does, the verifier accepts with probability at most .
Proof
Since the true satisfies (the true sum) , a prover that passes the first check must send . In general, call round lucky if but . Two different polynomials of degree at most agree on at most points, and is chosen after is sent, so a round is lucky with probability at most . If no round is lucky, the false claim propagates: and , which forces for the next check to pass, and in the last round , so the final check fails. By the union bound over rounds, the probability of acceptance is at most .
∎
A worked example: counting triangles. Let be the adjacency matrix of a graph on vertices, viewed as a function of two -bit vertex labels. The number of triangles is one sixth of
a sum of over Boolean variables, with degree at most 3 in each. Each factor is multilinear in all variables (it simply ignores the ones it does not mention), so the prover can compute every round by folding three tables. At the end the verifier needs , which is three evaluations of , each costing by folding the adjacency matrix. So the verifier spends time, which is just reading the input, and never counts a triangle; the honest prover spends , about what counting triangles naively costs anyway.
The program below does this over with for a graph on 8 vertices, prints the first rounds of an honest run (field elements near are small negative numbers: ), and then lets a lazy liar claim one triangle too many.
import random
p = 2**31 - 1 # the Mersenne prime 2^31 - 1: a toy field, far too small for real security
def fold(table, r):
"""Fix the first variable of a multilinear table to r: (1 - r)*T[0, rest] + r*T[1, rest]."""
h = len(table) // 2
return [(table[i] + r * (table[h + i] - table[i])) % p for i in range(h)]
def mle(table, point):
"""Evaluate the multilinear extension of a table of 2^v values at a point of F_p^v."""
for r in point:
table = fold(table, r)
return table[0]
def interpolate(evals, r):
"""Value at r of the polynomial of degree < len(evals) with values evals at 0, 1, 2, ..."""
total = 0
for i, y in enumerate(evals):
num = den = 1
for j in range(len(evals)):
if j != i:
num, den = num * (r - j) % p, den * (i - j) % p
total += y * num * pow(den, -1, p)
return total % p
# The input: an undirected graph on 8 vertices (3 bits per vertex), as an adjacency matrix.
n, bits = 8, 3
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (4, 6), (6, 7), (2, 5)]
adj = [[0] * n for _ in range(n)]
for a, b in edges:
adj[a][b] = adj[b][a] = 1
A = [adj[x][y] for x in range(n) for y in range(n)] # A(x, y) on {0,1}^6
# g(x, y, z) = A(x,y) A(y,z) A(x,z) on {0,1}^9; its sum is 6 times the number of triangles.
cube = [(x, y, z) for x in range(n) for y in range(n) for z in range(n)]
factors = [[adj[x][y] for x, y, z in cube], [adj[y][z] for x, y, z in cube],
[adj[x][z] for x, y, z in cube]]
k, v = len(factors), 3 * bits # degree <= 3 in each of 9 variables
def run_sumcheck(claim, prover_round, rng, verbose=False):
tables, rs = [list(f) for f in factors], []
for j in range(v):
s = prover_round(tables, claim) # s(0), s(1), ..., s(k)
if (s[0] + s[1]) % p != claim:
return f"rejected in round {j + 1}: s(0) + s(1) != claim"
r = rng.randrange(p) # the verifier's fresh random challenge
claim = interpolate(s, r)
if verbose and j < 3:
print(f" round {j + 1}: s(0..3) = {s}, r = {r}")
rs.append(r)
tables = [fold(t, r) for t in tables]
rx, ry, rz = rs[:bits], rs[bits:2 * bits], rs[2 * bits:]
final = mle(A, rx + ry) * mle(A, ry + rz) * mle(A, rx + rz) % p # the verifier reads only A
return "accepted" if final == claim else "rejected at the final check"
def honest_round(tables, claim):
h = len(tables[0]) // 2
s = []
for t in range(k + 1):
total = 0
for i in range(h):
prod = 1
for T in tables:
prod = prod * (T[i] + t * (T[h + i] - T[i])) % p # the line through T[0,i], T[1,i]
total += prod
s.append(total % p)
return s
def lazy_liar(tables, claim):
"""Compute the true s, then shift s(0) so that s(0) + s(1) matches the (false) claim."""
s = honest_round(tables, claim)
s[0] = (claim - s[1]) % p
return s
H = sum(a * b * c for a, b, c in zip(*factors))
print("true sum H =", H, "-> triangles:", H // 6)
print("honest prover, claim H:")
print(" verdict:", run_sumcheck(H, honest_round, random.Random(1), verbose=True))
print("cheating prover, claim H + 6 (one triangle too many):")
print(" verdict:", run_sumcheck(H + 6, lazy_liar, random.Random(2)))The liar passes all nine consistency checks, because it always adjusts to fit the current claim. That does not help: its polynomials are wrong, so the false claim survives every round and is caught by the one evaluation at the end.
How lucky can a cheater get? The best strategy follows the proof: in each round, send a polynomial that differs from the true by a multiple of some fixed of degree with , so the consistency check passes, and hope that is one of the roots of . If it is, the new claim is true, and the cheater can play honestly from then on. The next program plays this strategy thousands of times over tiny fields.
import random
def cheating_success(p, v=6, k=3, trials=4000, seed=5):
"""The best cheating strategy against sumcheck for a product of k multilinear tables in v
variables over F_p: claim a wrong sum, and in each round send s = (true polynomial) + D*q,
where q has degree k, roots 2, 3, ..., k+1 and q(0) + q(1) = 1. If the verifier's random r
is a root of q, the claim becomes true again and the cheater plays honestly from then on."""
rng = random.Random(seed)
roots = range(2, k + 2)
def q_raw(t):
out = 1
for m in roots:
out = out * (t - m) % p
return out
c0 = pow((q_raw(0) + q_raw(1)) % p, -1, p)
q = [c0 * q_raw(t) % p for t in range(k + 1)] # q(0), ..., q(k)
def interpolate(evals, r):
total = 0
for i, y in enumerate(evals):
num = den = 1
for j in range(len(evals)):
if j != i:
num, den = num * (r - j) % p, den * (i - j) % p
total += y * num * pow(den, -1, p)
return total % p
wins = 0
for _ in range(trials):
tables = [[rng.randrange(p) for _ in range(2**v)] for _ in range(k)]
true_sum = sum(a * b * c for a, b, c in zip(*tables)) % p
claim = (true_sum + 1) % p # a false claim
point = []
for _ in range(v):
h = len(tables[0]) // 2
g = []
for t in range(k + 1):
total = 0
for i in range(h):
prod = 1
for T in tables:
prod = prod * (T[i] + t * (T[h + i] - T[i])) % p
total += prod
g.append(total % p)
D = (claim - g[0] - g[1]) % p # zero once the cheater is back on track
s = [(g[t] + D * q[t]) % p for t in range(k + 1)] # passes the check s(0) + s(1) = claim
r = rng.randrange(p)
claim = interpolate(s, r)
point.append(r)
tables = [[(T[i] + r * (T[h + i] - T[i])) % p for i in range(h)] for T in tables]
final = tables[0][0] * tables[1][0] * tables[2][0] % p # the verifier's own evaluation
wins += final == claim
return wins / trials
v, k = 6, 3
print(" p cheater wins exact 1-(1-k/p)^v bound v*k/p")
for p in [11, 101, 1009]:
print(f"{p:5} {cheating_success(p, v, k):12.4f} {1 - (1 - k / p) ** v:17.4f} {v * k / p:13.4f}")Costs. The prover sends field elements; the verifier does field operations plus one evaluation of . For a product of multilinear tables, the honest prover's work is about multiplications in total, because the tables halve every round: linear in the size of the sum, with a small constant. That last property is rare and precious. Most proof systems make the prover pay a large multiple of the original computation; sumcheck-based provers pay a small one.
From sums to whole computations: GKR, and IP = PSPACE
Sumcheck verifies one sum. Real computations are circuits. The GKR protocol of Goldwasser, Kalai and Rothblum (2008) verifies a layered arithmetic circuit of depth and size by applying sumcheck once per layer, from the output down to the input.
Number the layers from the output (layer 0) to the input (layer ), and let be the value of gate in layer . Each gate is the sum or product of two gates in the layer below, so with and the multilinear extensions of the circuit's wiring (1 if gate adds, respectively multiplies, gates and ),
A claim about at one random point is a sum, so sumcheck reduces it to a claim about at two random points, which a little extra algebra combines into one. After rounds of this, the claim is about , the multilinear extension of the input, which the verifier evaluates itself in linear time. For circuits with regular wiring, the verifier's cost is about for input size , and later work brought the prover to time linear in . GKR is doubly efficient: the honest prover is not much slower than just evaluating the circuit, and the verifier is far faster than evaluating it. The price is that verifier time grows with the depth , so GKR suits wide, shallow computations, and it needs no cryptography at all.
Sumcheck's original purpose was more dramatic. Around the turn of 1990, Lund, Fortnow, Karloff and Nisan used it to give interactive proofs for counting problems (#P), and therefore for every problem in the polynomial hierarchy; within weeks Adi Shamir extended the technique to prove IP = PSPACE: every problem solvable in polynomial space — including deciding the winner of generalised board games, and evaluating quantified Boolean formulas — has an interactive proof with a polynomial-time verifier. Interaction plus randomness is enormously more powerful than a static certificate, assuming (as everyone believes) that PSPACE is larger than NP. (See computational complexity for the classes.) The provers in those proofs need exponential time; the point of GKR, in the title of its paper, was to bring interactive proofs to "muggles" whose provers run in polynomial time.
The professional view: sumcheck in 2026
For two decades after 1992, sumcheck was taught as theory. Two things changed. First, practical implementations, beginning with the work of Cormode, Mitzenmacher and Thaler around 2012, showed that GKR-style provers could run on real data. Second, sumcheck turned out to combine perfectly with the cryptographic tools of the next lessons:
- The final evaluation is the one step the verifier cannot do cheaply when encodes a big witness that the verifier does not have. Systems replace it with a polynomial commitment: the prover commits to the multilinear polynomial in advance and later proves the single evaluation (Arithmetisation and SNARKs).
- Interaction is removed with the Fiat–Shamir transform: because sumcheck is public-coin (the verifier's messages are just random numbers), the challenges can be computed by hashing the transcript so far, giving a non-interactive proof (Zero knowledge).
Sumcheck-based or "multilinear" systems include Spartan (2019), HyperPlonk (2022), the lookup argument Lasso and the zkVM Jolt built on it (2023), and Binius over binary fields (2023); several production zkVMs and provers adopted multilinear designs in 2024–2025, and verifiable-database systems such as Space and Time's Proof of SQL prove query results with sumcheck. The folding inner loop you ran above — read two halves of a table, combine, write half as much — is memory-bound and embarrassingly parallel, which is why these provers map well onto GPUs. Thaler's book is the standard reference; chapters 3 and 4 treat exactly this lesson's material with full proofs.
Note
Everything in this lesson used toy parameters: fields of 31 or 61 bits, small graphs, Python integers. Real implementations use carefully chosen fields and extension fields for the challenges, constant-time arithmetic, and audited code. Treat the programs here as learning tools, never as security software.
Common misconceptions
Misconception
"A probabilistic proof is weaker than a real proof." A soundness error of is far smaller than the probability that the verifying computer suffers an undetected hardware fault during the check. Errors also shrink exponentially with repetition or with field size. What matters is that the probability is over the verifier's coins and holds for every prover, not over some assumed distribution of inputs.
Misconception
"Sumcheck verifies a sum without ever looking at ." The verifier must evaluate once, at a random point it chooses. For triangle counting that costs ; for a SNARK, the evaluation is replaced by a commitment opening. Forgetting the final check leaves a protocol that any liar passes, as the lazy liar above would have.
Misconception
"Freivalds' check proves the product correct." It proves it correct with high probability, and the error is one-sided: a correct product always passes, and a wrong one passes with probability at most per trial. Repetition with fresh randomness multiplies the error probabilities only if the trials are independent; reusing the same vector does not help.
Misconception
"The bigger the field the slower, so use the smallest field that holds the data." The data may fit in a small field, but soundness depends on where the challenges live: the bound is . Modern systems compute on small fields for speed and draw challenges from extension fields for soundness.
A short history
Interactive proofs were defined in 1985, independently, by Shafi Goldwasser, Silvio Micali and Charles Rackoff (whose paper also introduced zero knowledge) and by László Babai (whose public-coin "Arthur–Merlin games" are the model sumcheck lives in). Freivalds' matrix check dates from 1977 and the Schwartz–Zippel lemma from 1978–1980. Sumcheck appeared at the end of 1989 and led within weeks to IP = PSPACE (both published in 1990 and, in journal form, 1992); probabilistically checkable proofs and the PCP theorem followed in 1992. Goldwasser, Kalai and Rothblum introduced the GKR protocol in 2008. Practical implementations came in the 2010s, and sumcheck moved to the centre of practical SNARK design in the 2020s. Goldwasser and Micali received the Turing Award in 2012, in part for this line of work.
Exercises
1. Interactive proofs and the sumcheck protocol
Warm-upHumanA lazy verifier ignores the prover and always outputs accept. Which properties of a proof system does it have?
2. Interactive proofs and the sumcheck protocol
Warm-upHumanFreivalds' check with a random 0/1 vector lets a wrong product through with probability at most . You repeat it with independent fresh vectors and accept only if every trial passes. What is the smallest number of trials that guarantees an error probability of at most ?
3. Interactive proofs and the sumcheck protocol
CoreHumanOver , let be given by , , , . Compute , the value of its multilinear extension at , as an integer from 0 to 10.
4. Interactive proofs and the sumcheck protocol
CoreHumanA sumcheck proof is run for a polynomial in variables with degree at most in each variable. In each round the prover sends its polynomial as its values at . How many field elements does the prover send in all the rounds together (not counting the claimed sum )?
5. Interactive proofs and the sumcheck protocol
CoreHumanWhy does an interactive proof with a deterministic verifier prove nothing beyond NP?
6. Interactive proofs and the sumcheck protocol
StretchHumanA team runs sumcheck for variables and degree , drawing every challenge from with . Which statements are true? Select all that apply.
7. Interactive proofs and the sumcheck protocol
CoreComputationalWrite mle_eval(table, point, p), which returns the value modulo the prime p of the multilinear extension of table at point.
tablehas entries, for , with the first variable as the most significant bit of the index:table[0b101]is .pointis a list of field elements.
Use folding, so that the running time is . The tests compare your function with the -term Lagrange formula for random tables up to .
8. Interactive proofs and the sumcheck protocol
StretchComputationalImplement the sumcheck verifier. verify_sumcheck(p, claim, rounds, challenges, g_at_r) receives:
- the prime
pand the claimed sumclaim; rounds, whererounds[j]is the prover's polynomial in round , given as its values[s(0), s(1), ..., s(d)];challenges, wherechallenges[j]is the random the verifier sent in that round;g_at_r, the verifier's own evaluation .
Return True if every check of the protocol passes and False otherwise. A helper interpolate(evals, r, p) is provided. The tests generate honest transcripts and then tamper with them in several ways.
Further reading and resources
- Proofs, Arguments, and Zero-Knowledge · Justin ThalerThe free monograph this level leans on. Chapters 2–4 cover Freivalds, fingerprinting, sumcheck and GKR in depth.
- The knowledge complexity of interactive proof-systems · Shafi Goldwasser, Silvio Micali and Charles Rackoff · 1985The paper that defined interactive proofs (and zero knowledge).
- Trading group theory for randomness · László Babai · 1985Arthur–Merlin games, the public-coin model that sumcheck lives in.
- Fast probabilistic algorithms for verification of polynomial identities · Jacob T. Schwartz · 1980
- Algebraic methods for interactive proof systems · Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan · 1992The paper that introduced the sumcheck protocol.
- IP = PSPACE · Adi Shamir · 1992
- Delegating computation: interactive proofs for muggles · Shafi Goldwasser, Yael Tauman Kalai and Guy N. Rothblum · 2015The GKR protocol (first presented at STOC 2008).
- Spartan: efficient and general-purpose zkSNARKs without trusted setup · Srinath Setty · 2019One of the first modern SNARKs built around sumcheck.