Skip to content
LumenaryAcademy
Verifiable 80 min

Interactive proofs and the sumcheck protocol

How a weak verifier, armed with a few random numbers, can check a huge computation it never performs.

Code tested · 6AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

DefinitionsH

What a proof system is

Fix a claim, written formally as "x∈Lx \in L" for some language LL: "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 PP and a verifier VV, that exchange messages about xx; at the end VV accepts or rejects.

Definition— interactive proof

An interactive proof for LL is a protocol between a prover PP and a probabilistic verifier VV that runs in polynomial time in ∣x∣|x|, such that:

  • Completeness: if x∈Lx \in L, the honest prover makes VV accept with probability at least 1−δ1 - \delta (often exactly 1).
  • Soundness: if x∉Lx \notin L, then for every prover strategy P∗P^*, however clever and however much computing power it has, VV accepts with probability at most ε\varepsilon, 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 VV is deterministic, the prover can predict every question VV 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.

ComputationC

A first random check: Freivalds' algorithm

Here is the simplest example of the idea, from randomised algorithms: a prover claims that C=ABC = AB for n×nn \times n matrices. Recomputing ABAB costs about n3n^3 multiplications with the school method. Rūsiņš Freivalds observed in 1977 that the verifier can instead pick a random vector rr and check whether

A(Br)=Cr,A(Br) = Cr,

which takes three matrix–vector products, about 3n23n^2 multiplications. If C=ABC = AB the check always passes. If C≠ABC \neq AB, then D=AB−CD = AB - C has some nonzero row, and the check passes only if that row happens to be orthogonal to rr.

Theorem— Freivalds' error bound

Work over a field F\mathbb{F} and let S⊆FS \subseteq \mathbb{F} be finite. If C≠ABC \neq AB and the entries of rr are chosen independently and uniformly from SS, then Pr⁡[A(Br)=Cr]≤1/∣S∣\Pr[A(Br) = Cr] \le 1/|S|.

Proof

Let D=AB−C≠0D = AB - C \neq 0, and pick an entry dij≠0d_{ij} \neq 0. The check passes only if row ii of DrDr is zero: dijrj=−∑k≠jdikrkd_{ij} r_j = -\sum_{k \neq j} d_{ik} r_k. Fix all rkr_k with k≠jk \neq j first; then exactly one value of rjr_j satisfies this equation, and rjr_j hits it with probability at most 1/∣S∣1/|S|.

∎

With 0/1 vectors the error is at most 1/21/2 per trial; with rr drawn from a prime field Fp\mathbb{F}_p it is at most 1/p1/p. The code below works modulo p=101p = 101, plants a single wrong entry among 40 00040\,000, and measures how often each kind of random vector lets it through.

python
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:,}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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 F101\mathbb{F}_{101} about one time in a hundred. Twenty independent 0/1 trials would push the error below one in a million. Meanwhile the check costs 120 000120\,000 multiplications instead of 8 000 0008\,000\,000, and the gap grows with nn.

Freivalds' check is not yet a proof system: the prover just sends CC. 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.

DefinitionsH

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 dd in one variable has at most dd 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 gg be a nonzero polynomial in vv variables of total degree at most dd over a field F\mathbb{F}, and let S⊆FS \subseteq \mathbb{F} be finite. If r1,…,rvr_1, \ldots, r_v are chosen independently and uniformly from SS, then

Pr⁡[g(r1,…,rv)=0]≤d∣S∣.\Pr\big[g(r_1, \ldots, r_v) = 0\big] \le \frac{d}{|S|}.

Proof

Induction on vv. For v=1v = 1, gg has at most dd roots. For v>1v > 1, write gg as a polynomial in x1x_1 whose coefficients are polynomials in the other variables: g=∑i=0kx1 i gi(x2,…,xv)g = \sum_{i=0}^{k} x_1^{\,i}\, g_i(x_2, \ldots, x_v) with gk≠0g_k \neq 0. Then gkg_k has total degree at most d−kd - k, so by induction Pr⁡[gk(r2,…,rv)=0]≤(d−k)/∣S∣\Pr[g_k(r_2, \ldots, r_v) = 0] \le (d-k)/|S|. If gk(r2,…,rv)≠0g_k(r_2, \ldots, r_v) \neq 0, then g(x1,r2,…,rv)g(x_1, r_2, \ldots, r_v) is a nonzero polynomial of degree kk in x1x_1, which vanishes at r1r_1 with probability at most k/∣S∣k/|S|. Adding the two bad events gives at most d/∣S∣d/|S|.

∎

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 ff and gg are the same polynomial, evaluate f−gf - g at a random point. If they differ, a random point exposes the difference with probability at least 1−d/∣S∣1 - d/|S|. 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, (a2+b2)(c2+d2)=(ac−bd)2+(ad+bc)2(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2, 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.

python
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})")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
DefinitionsH

Multilinear extensions

Proof systems need to turn data into polynomials, so that Schwartz–Zippel can be applied to the data. A table of 2v2^v values is naturally a function f:{0,1}v→Ff : \{0,1\}^v \to \mathbb{F}, indexed by vv-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 f:{0,1}v→Ff : \{0,1\}^v \to \mathbb{F} there is exactly one multilinear polynomial f~:Fv→F\tilde f : \mathbb{F}^v \to \mathbb{F} that agrees with ff on {0,1}v\{0,1\}^v, its multilinear extension (MLE):

f~(x)=∑w∈{0,1}vf(w) χw(x),χw(x)=∏i=1v(xiwi+(1−xi)(1−wi)).\tilde f(x) = \sum_{w \in \{0,1\}^v} f(w)\, \chi_w(x), \qquad \chi_w(x) = \prod_{i=1}^{v} \big(x_i w_i + (1 - x_i)(1 - w_i)\big).

Each χw\chi_w is 1 at ww and 0 at every other point of the cube, so the sum agrees with ff there. Uniqueness: the difference of two such polynomials is multilinear and vanishes on the whole cube, and a multilinear polynomial that vanishes on {0,1}v\{0,1\}^v is zero (induct on vv, as in the proof above).

Evaluating f~\tilde f at a point does not require the 2v2^v-term sum to be computed naively. Because f~\tilde f is linear in x1x_1,

f~(r1,x2,…,xv)=(1−r1) f~(0,x2,…,xv)+r1 f~(1,x2,…,xv),\tilde f(r_1, x_2, \ldots, x_v) = (1 - r_1)\, \tilde f(0, x_2, \ldots, x_v) + r_1\, \tilde f(1, x_2, \ldots, x_v),

so fixing the first variable folds a table of 2v2^v values into a table of 2v−12^{v-1} values, one multiplication per entry. Folding vv times leaves the single value f~(r)\tilde f(r), for about 2v2^v multiplications in all: linear in the size of the table.

f(0,0) = 4f(1,0) = 6f(0,1) = 1f(1,1) = 94.53f̃(1/4, 1/2) = 3.75first fold: x₁ = 1/4second fold:x₂ = 1/2
Folding a table of four values, f(0,0) = 4, f(1,0) = 6, f(0,1) = 1, f(1,1) = 9, to evaluate its multilinear extension at (r₁, r₂) = (1/4, 1/2). The first fold interpolates along each horizontal edge, the second along the vertical line between the results. Over a finite field the same formulas work for any r, including values that lie 'outside' the square.
ExplanationH

The sumcheck protocol

Now the main event. Let g(x1,…,xv)g(x_1, \ldots, x_v) be a polynomial over a prime field Fp\mathbb{F}_p with degree at most dd in each variable. The prover claims

H=∑b1∈{0,1}∑b2∈{0,1}⋯∑bv∈{0,1}g(b1,…,bv).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).

Computing HH directly needs 2v2^v evaluations of gg. The sumcheck protocol of Lund, Fortnow, Karloff and Nisan (1990) lets the verifier check the claim with vv short messages, O(vd)O(vd) field operations, and a single evaluation of gg 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 c0=Hc_0 = H. In round j=1,…,vj = 1, \ldots, v:

  1. The prover sends a univariate polynomial sj(X)s_j(X) of degree at most dd (as its d+1d + 1 values at 0,1,…,d0, 1, \ldots, d), claimed to equal gj(X)=∑b∈{0,1}v−jg(r1,…,rj−1,X,b).g_j(X) = \sum_{b \in \{0,1\}^{v-j}} g(r_1, \ldots, r_{j-1}, X, b).
  2. The verifier checks that sj(0)+sj(1)=cj−1s_j(0) + s_j(1) = c_{j-1}, rejecting otherwise.
  3. The verifier picks rj∈Fpr_j \in \mathbb{F}_p uniformly at random, sends it, and sets cj=sj(rj)c_j = s_j(r_j).

Finally the verifier evaluates g(r1,…,rv)g(r_1, \ldots, r_v) itself and accepts if and only if it equals cvc_v.

ProverVerifierclaim H, and s₁(X) of degree ≤ drandom r₁s₂(X)random r₂⋮s_v(X)s₁(0) + s₁(1) = H ?s₂(0) + s₂(1) = s₁(r₁) ?s_v(0) + s_v(1) = previous claim ?pick r_v; one evaluation:s_v(r_v) = g(r₁, …, r_v) ?
The sumcheck protocol for v variables. Each round, the prover sends a low-degree univariate polynomial, the verifier checks it against the previous claim and replies with a fresh random field element. The claim shrinks by one variable per round until the verifier can check it with one evaluation of g.

If the prover is honest, every check passes: gj(0)+gj(1)g_j(0) + g_j(1) is the sum over one more Boolean variable, which is precisely gj−1(rj−1)g_{j-1}(r_{j-1}). Why can't a liar pass?

Theorem— Soundness of sumcheck

If HH is not the true sum, then whatever the prover does, the verifier accepts with probability at most vd/pvd/p.

Proof

Since the true g1g_1 satisfies g1(0)+g1(1)=g_1(0) + g_1(1) = (the true sum) ≠H\neq H, a prover that passes the first check must send s1≠g1s_1 \neq g_1. In general, call round jj lucky if sj≠gjs_j \neq g_j but sj(rj)=gj(rj)s_j(r_j) = g_j(r_j). Two different polynomials of degree at most dd agree on at most dd points, and rjr_j is chosen after sjs_j is sent, so a round is lucky with probability at most d/pd/p. If no round is lucky, the false claim propagates: sj≠gjs_j \neq g_j and cj=sj(rj)≠gj(rj)c_j = s_j(r_j) \neq g_j(r_j), which forces sj+1≠gj+1s_{j+1} \neq g_{j+1} for the next check to pass, and in the last round cv≠gv(rv)=g(r1,…,rv)c_v \neq g_v(r_v) = g(r_1, \ldots, r_v), so the final check fails. By the union bound over vv rounds, the probability of acceptance is at most vd/pvd/p.

∎

A worked example: counting triangles. Let AA be the adjacency matrix of a graph on n=2mn = 2^m vertices, viewed as a function A(x,y)A(x, y) of two mm-bit vertex labels. The number of triangles is one sixth of

∑x,y,z∈{0,1}mA~(x,y) A~(y,z) A~(x,z),\sum_{x, y, z \in \{0,1\}^m} \tilde A(x, y)\, \tilde A(y, z)\, \tilde A(x, z),

a sum of g(x,y,z)=A~(x,y)A~(y,z)A~(x,z)g(x, y, z) = \tilde A(x, y)\tilde A(y, z)\tilde A(x, z) over v=3mv = 3m Boolean variables, with degree at most 3 in each. Each factor is multilinear in all 3m3m 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 g(r)g(r), which is three evaluations of A~\tilde A, each costing O(n2)O(n^2) by folding the adjacency matrix. So the verifier spends O(n2)O(n^2) time, which is just reading the input, and never counts a triangle; the honest prover spends O(n3)O(n^3), about what counting triangles naively costs anyway.

The program below does this over Fp\mathbb{F}_p with p=231−1p = 2^{31} - 1 for a graph on 8 vertices, prints the first rounds of an honest run (field elements near pp are small negative numbers: 2147483641≡−62147483641 \equiv -6), and then lets a lazy liar claim one triangle too many.

python
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)))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The liar passes all nine consistency checks, because it always adjusts sj(0)s_j(0) 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 gjg_j by a multiple of some fixed q(X)q(X) of degree dd with q(0)+q(1)=1q(0) + q(1) = 1, so the consistency check passes, and hope that rjr_j is one of the dd roots of qq. 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.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Costs. The prover sends v(d+1)v(d+1) field elements; the verifier does O(vd)O(vd) field operations plus one evaluation of gg. For a product of kk multilinear tables, the honest prover's work is about k(k+1)⋅2vk(k+1) \cdot 2^v 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.

ExplanationH

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 DD and size SS 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 DD), and let Vi(z)V_i(z) be the value of gate zz in layer ii. Each gate is the sum or product of two gates in the layer below, so with add~i(z,a,b)\widetilde{\mathrm{add}}_i(z, a, b) and mult~i(z,a,b)\widetilde{\mathrm{mult}}_i(z, a, b) the multilinear extensions of the circuit's wiring (1 if gate zz adds, respectively multiplies, gates aa and bb),

V~i(z)=∑a,b(add~i(z,a,b)(V~i+1(a)+V~i+1(b))+mult~i(z,a,b) V~i+1(a) V~i+1(b)).\tilde V_i(z) = \sum_{a, b} \Big( \widetilde{\mathrm{add}}_i(z, a, b)\big(\tilde V_{i+1}(a) + \tilde V_{i+1}(b)\big) + \widetilde{\mathrm{mult}}_i(z, a, b)\, \tilde V_{i+1}(a)\, \tilde V_{i+1}(b) \Big).

A claim about V~i\tilde V_i at one random point is a sum, so sumcheck reduces it to a claim about V~i+1\tilde V_{i+1} at two random points, which a little extra algebra combines into one. After DD rounds of this, the claim is about V~D\tilde V_D, 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 O(n+Dlog⁡S)O(n + D \log S) for input size nn, and later work brought the prover to time linear in SS. 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 DD, 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.

ExplanationH

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 g(r)g(r) is the one step the verifier cannot do cheaply when gg 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 misconceptionsH

Common misconceptions

Misconception

"A probabilistic proof is weaker than a real proof." A soundness error of 2−1002^{-100} 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 gg." The verifier must evaluate gg once, at a random point it chooses. For triangle counting that costs O(n2)O(n^2); 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 1/∣S∣1/|S| 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 vd/∣F∣vd/|\mathbb{F}|. Modern systems compute on small fields for speed and draw challenges from extension fields for soundness.

History & global context

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

Exercises

1. Interactive proofs and the sumcheck protocol

Warm-upHuman

A lazy verifier ignores the prover and always outputs accept. Which properties of a proof system does it have?

Choose one

2. Interactive proofs and the sumcheck protocol

Warm-upHuman

Freivalds' check with a random 0/1 vector lets a wrong product C≠ABC \neq AB through with probability at most 1/21/2. 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 10−910^{-9}?

3. Interactive proofs and the sumcheck protocol

CoreHuman

Over F11\mathbb{F}_{11}, let f:{0,1}2→F11f : \{0,1\}^2 \to \mathbb{F}_{11} be given by f(0,0)=3f(0,0) = 3, f(0,1)=5f(0,1) = 5, f(1,0)=2f(1,0) = 2, f(1,1)=7f(1,1) = 7. Compute f~(2,3)\tilde f(2, 3), the value of its multilinear extension at (x1,x2)=(2,3)(x_1, x_2) = (2, 3), as an integer from 0 to 10.

4. Interactive proofs and the sumcheck protocol

CoreHuman

A sumcheck proof is run for a polynomial gg in v=20v = 20 variables with degree at most d=3d = 3 in each variable. In each round the prover sends its polynomial as its values at 0,1,…,d0, 1, \ldots, d. How many field elements does the prover send in all the rounds together (not counting the claimed sum HH)?

5. Interactive proofs and the sumcheck protocol

CoreHuman

Why does an interactive proof with a deterministic verifier prove nothing beyond NP?

Choose one

6. Interactive proofs and the sumcheck protocol

StretchHuman

A team runs sumcheck for v=30v = 30 variables and degree d=3d = 3, drawing every challenge from Fp\mathbb{F}_p with p=231−1p = 2^{31} - 1. Which statements are true? Select all that apply.

Choose all that apply

7. Interactive proofs and the sumcheck protocol

CoreComputational

Write mle_eval(table, point, p), which returns the value modulo the prime p of the multilinear extension of table at point.

  • table has 2v2^v entries, f(b)f(b) for b∈{0,1}vb \in \{0,1\}^v, with the first variable as the most significant bit of the index: table[0b101] is f(1,0,1)f(1, 0, 1).
  • point is a list of vv field elements.

Use folding, so that the running time is O(2v)O(2^v). The tests compare your function with the 2v2^v-term Lagrange formula for random tables up to v=6v = 6.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Interactive proofs and the sumcheck protocol

StretchComputational

Implement the sumcheck verifier. verify_sumcheck(p, claim, rounds, challenges, g_at_r) receives:

  • the prime p and the claimed sum claim;
  • rounds, where rounds[j] is the prover's polynomial in round j+1j+1, given as its values [s(0), s(1), ..., s(d)];
  • challenges, where challenges[j] is the random rj+1r_{j+1} the verifier sent in that round;
  • g_at_r, the verifier's own evaluation g(r1,…,rv)g(r_1, \ldots, r_v).

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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources