Interactive Proofs

Here are two graphs. Same number of vertices, same number of edges, but not the same graph: no relabeling of vertices turns one into the other. Can you prove it?

With a short classical proof, you're stuck. Proving two graphs the same is easy, just show the mapping; that is an NP certificate. But proving them different? There is no short certificate anyone knows how to write. And yet a five-minute conversation can do what no short written proof can.

The quiz#

The verifier has two graphs, $G_0$ and $G_1$. The prover claims they are not isomorphic, and the verifier doesn't trust the prover. So the verifier secretly picks one at random, $G_b$, shuffles its vertices with a random permutation, sends the scramble over, and asks: which graph did I start from?

This is a quiz. The verifier already knows the answer. The question is whether the prover does too. If the graphs really are non-isomorphic, the scrambled graph is isomorphic to exactly one of them, and an all-powerful prover can check both and answer correctly every time. But if the graphs are actually isomorphic, a random permutation of $G_0$ has exactly the same distribution as a random permutation of $G_1$. The prover has no information about $b$, and any strategy succeeds with probability at most $\frac{1}{2}$. Repeat: ten rounds, and a cheating prover's odds fall below one in a thousand.

The verifier used two things classical proofs don't have. Randomness created a challenge it already knew the answer to. Interaction forced the prover to demonstrate knowledge instead of handing over a certificate.

The definition#

Goldwasser, Micali, and Rackoff introduced the model in 1985. The prover $P$ is computationally unbounded; the verifier $V$ is a probabilistic polynomial-time machine; they exchange messages for some number of rounds. Completeness: on a yes-instance, the honest prover makes the verifier accept with probability at least $\frac{2}{3}$. Soundness: on a no-instance, no prover, however powerful, makes the verifier accept with probability more than $\frac{1}{3}$. As with BPP, the constants are arbitrary; any gap amplifies by repetition. The definition is asymmetric, and the asymmetry is the point. Completeness needs one specific prover to succeed; soundness must hold against every possible prover. IP is the class of languages with interactive proofs over polynomially many rounds.

After the definition came a consensus about its limits. Babai independently introduced Arthur-Merlin games, where the verifier's coins are public, and proved that any constant number of rounds collapses to AM; Goldwasser and Sipser showed hiding the coins doesn't help. So constant-round interaction gives AM, believed to sit inside the polynomial hierarchy, not far above NP. Most researchers expected that was the whole story: IP was probably just AM.

In 1990, Lund, Fortnow, Karloff, and Nisan shattered that expectation. With a technique called the sum-check protocol, they proved that counting the satisfying assignments of a Boolean formula, a sharp-P-complete problem, has an interactive proof; co-NP is therefore inside IP, and if the polynomial hierarchy doesn't collapse, IP extends far beyond AM. Within weeks, Shamir pushed the technique to the full answer: IP equals PSPACE. Every problem solvable in polynomial space, a class containing NP, co-NP, and the entire polynomial hierarchy, has an interactive proof.

Arithmetization#

The proof rests on one algebraic idea: lift Boolean formulas into polynomials. A Boolean formula lives on the hypercube, just zeros and ones, and checking every point would take exponential time. But over a larger domain, two distinct low-degree polynomials can agree on only a few points, so evaluating at a random point exposes a fake almost surely. That is the crack the verifier exploits.

Work over a finite field $F_q$, the integers modulo a large prime. Translate the formula: $\neg x$ becomes $1-x$, $x\wedge y$ becomes $x·y$, and $x\vee y$ becomes $1-(1-x)(1-y)$. On zero-one inputs these agree with the logic, but the polynomial is defined over all of $F_{q^n}$. Quantifiers translate too: an existential becomes a sum over $x_i\in \{0,1\}$, a universal becomes a product. A quantified Boolean formula becomes nested sums and products of a polynomial over a finite field.

The sum-check protocol#

Now the engine. Think of it as an audit: the prover claims a huge sum, far too large for the verifier to compute directly. The verifier forces the prover to break the sum down one variable at a time, checking a random spot at each step; any fudged line is almost certainly caught.

Both parties know a polynomial $p$ in $n$ variables over $F_q$. The prover claims a value $H$ for

$$H=\sum _{x\in \{0,1{\}}^n}p(x_1,\dots ,x_n)$$

a sum of $2^n$ terms. In round one, the prover sends a univariate polynomial $g_1\left(t\right)$, claimed to equal the sum of $p$ with the first variable set to $t$ and the rest summed over the Boolean cube. The verifier checks $g_1\left(0\right)+g_1\left(1\right)=H$, which must hold because summing both values of $x_1$ accounts for every term; if it fails, reject. Then the verifier picks a random field element $r_1$, reducing the claim to the value of $g_1\left(r_1\right)$, a statement of the same shape in one fewer variable. Each round pins down one more variable, until after $n$ rounds the verifier checks the final claim by evaluating $p(r_1,\dots ,r_n)$ itself.

Why is this sound? A lying prover has sent a polynomial different from the true one, and two distinct polynomials of degree $d$ agree on at most $d$ points. The chance the random challenge lands on a point of agreement is at most $\frac{d}{q}$, so over $n$ rounds the total cheating probability is at most $\frac{nd}{q}$. Choose $q$ much larger than $nd$ and the protocol is sound.

Pause and try: why do two distinct degree-d polynomials agree on at most d points?

Let $g$ and $h$ be distinct univariate polynomials of degree at most $d$. Their difference $g-h$ is nonzero with degree at most $d$, so it has at most $d$ roots, and every point of agreement is a root. A uniformly random challenge from a field of size $q$ hits one with probability at most $\frac{d}{q}$.

Taming the degree#

One direction of IP equals PSPACE is straightforward: the whole interaction can be simulated in polynomial space, computing the optimal prover strategy by exhaustive search over responses. The hard direction is giving an interactive proof for TQBF, true quantified Boolean formulas, the PSPACE-complete problem of deciding sentences like: for all $x_1$, there exists $x_2$, for all $x_3$, and so on.

Arithmetize, and the quantifiers become alternating sums and products. The sum-check protocol handles sums beautifully, but products are a wall. Taking the product over $x_i\in \{0,1\}$ multiplies two polynomials, doubling the degree in the remaining variables; after many quantifiers the degree grows exponentially, and sum-check soundness needs degree small compared to the field size.

Shamir found the way through; Alexander Shen soon simplified it to the version everyone teaches. After each quantifier, apply a linearization operator: for variable $x_i$, replace $p$ with the unique polynomial linear in $x_i$ that agrees with $p$ at $x_i=0$ and $x_i=1$, namely

$$(1-x_i)·p(\dots ,0,\dots )+x_i·p(\dots ,1,\dots )$$

On Boolean inputs this changes nothing, but the degree in $x_i$ drops to one. Checking the linearization at a random point reduces to evaluating $p$ at two points, and those evaluations are sums, exactly what sum-check handles. So the protocol interleaves: a quantifier via sum-check, then linearize and verify via more sum-check rounds, then the next quantifier. Each new quantifier also relinearizes every variable before it, so the round count is $O\left(n^2\right)$, still polynomial. TQBF has an interactive proof, so IP equals PSPACE.

What it means#

A polynomial-time verifier, a machine that cannot solve NP-hard problems on its own, can verify any computation a polynomial-space machine could perform, just by having a conversation. Interaction and randomness together give verification power far beyond either alone.

The result connects outward. In 1988, Ben-Or, Goldreich, Goldwasser, and others proved that if one-way functions exist, every language in IP has a computational zero-knowledge proof: every PSPACE problem can be verified without revealing anything about how the answer was found. The proof also broke a barrier. Fortnow and Sipser had constructed an oracle relative to which co-NP is not in IP, so the theorem cannot hold in all oracle worlds; by exploiting algebraic structure instead of treating computation as a black box, Shamir's proof became the first major theorem to provably break through relativization. Related algebraic techniques underlie the PCP theorem and hardness of approximation. And because sum-check is public-coin, the Fiat-Shamir transform can make it non-interactive, the pipeline from Shamir's 1990 result to modern SNARKs, which underpin real-world verifiable computation today.

Computation, proof, and interaction: three ideas that turn out to be the same idea.

If you remember three things#

1. Randomness plus interaction verifies what no short certificate can: the graph non-isomorphism quiz catches a cheating prover with probability $\frac{1}{2}$ per round, amplified by repetition.
2. Arithmetization lifts Boolean claims to low-degree polynomials over $F_q$, where the sum-check protocol audits a $2^n$-term sum in $n$ rounds with cheating probability at most $\frac{nd}{q}$.
3. Linearization tames the degree blowup from universal quantifiers, proving IP equals PSPACE: the first major non-relativizing theorem, and the ancestor of modern SNARKs.