# A Tutorial on Interactive Proof Systems

Posted 2015/01/07. Last updated 2015/01/07.

## Before We Get Started

This post will introduce Interactive Proof Systems and show how they relate to the traditional complexity classes of **NP**, **PSPACE**, and **NEXPTIME**. It is meant to give the mathematical foundation which is often assumed or ignored when discussing Zero-Knowledge Proofs and is based on a tutorial paper I wrote for Princeton's Theory of Computation class, taught at the time by Prof. Robert Tarjan. It assumes some familiarity with Turing machines and the basic complexity classes, but hopefully you will find that this post is more or less self-contained. If you are interested in this material, I recommend Sipser's Introduction to the Theory of Computation if you are OK with some informal and handwavy arguments (the second edition is as good as the third). Moreover, Arora and Barak's Computational Complexity is excellent for a deeper understanding of the subject (with the added benefit that the authors have made available earlier drafts of the material freely available online). Finally, the Complexity Zoo page is fantastic if you want quick facts and references for the various complexity classes.

## The Essentials

Traditionally, the **NP** complexity class is defined as the set (*class*) of languages that are *decided* by non-deterministic polynomial-time Turing machines, but it can be equivalently (see Sipser's book for a proof) thought of as the set of languages that have a polynomial-time *verifier*:

### Definition 1 (Verifier, Certificate)

A *verifier* for a language *L* is a Turing machine *V*, such that *L = *{*w* | *V* accepts <*w,c*> for some string *c*}. *c* is called a *certificate* for *w*. We consider *V* to be polynomial time if it is polynomial in the length of *w* only.

We can thus think of **NP** as the set of languages *L* for which there is an all-powerful prover *P* that given *w* finds *c*, and then passes it to *V* which verifies (deterministically and in polynomial time in *|w|*) that *c* is a correct certificate (proof) of *w*'s membership in the language *L*. As an example, for the language of composite natural numbers, a certificate for *w* would be a pair of integers *(n,m)* such that *n,m>1* and *n·m=w*. Interactive proof systems extend this idea by allowing additional interaction between the the prover and the verifier and by adding randomness. As we show below, the randomness of the verifier is essential, while the randomness of the prover is not.

## Interactive Turing Machines And Protocols

Interactive Proof Systems were introduced by Goldwasser, Micali, and Rackoff in their seminal 1985 paper The Knowledge Complexity of Interactive Proof Systems. The definition of Turing machines is amended to allow for randomness and communication as follows:

### Definition 2 (Interactive Turing Machine, Coin Flip)

An *Interactive Turing Machine (ITM)* is a Turing machine that has:

• A read-only input tape

• A scratch tape

• A random tape

• A read-only communication tape

• A write-only communication tape

The random tape contains an infinite sequence of random bits, which are read left-to-right, and reading the next random bit is called *flipping a coin*.

By combining two ITMs, we can define a general two-party interactive protocol as follows:

### Definition 3 (Interactive Protocol, Prover, Verifier)

An *Interactive Protocol* is an ordered pair of ITMs *(P,V)*, called the *Prover* and the *Verifier* respectively such that:

• *P, V* share the same input tape

• *P*'s write-only communication tape is *V*'s read-only communication tape and vice-versa

• *P* is computationally unbounded, whereas *V*'s total internal computation time is polynomial in the length of the common input

• The two machines take turns being active, and *V* starts

• During an active state, the machine, after some internal computation using the input, scratch, random, and communication tapes writes to its write-only tape

• Termination occurs when *V* either accepts or rejects the input by outputting accept or reject in its write tape, and halting the protocol.

This definition makes it clear that only polynomially many messages can be exchanged, in polynomially many rounds, and each message is polynomially bounded in the input size, as *V*'s runtime would otherwise explode. In addition, *V* can only use polynomially many random bits. An Interactive Protocol for a language *L* (usually over {*0,1*}^{*}) with a high-enough probability of accepting *w* ∈ *L* and of rejecting *w* ∉*L* is called an *Interactive Proof System*:

### Definition 4 (Interactive Proof System)

The Interactive Protocol (*P,V*) is an Interactive Proof System (IPS) for language *L* if

• *w* ∈ *L* ⇒ Pr[(*P,V*) accepts *w*] ≥ ⅔

• *w* ∉*L* ⇒∀*P'*, Pr[(*P',V*) accepts *w*] ≤ ⅓

where the probabilities are taken over the randomness used by the prover and verifier.

*V* must **reject with a high probability for all possible provers**, because *V* has no guarantees that it is communicating with an honest party. Note that the given probabilities fix *w*, so by **repeating the interaction** *m* times, and accepting iff at least ⌊*m*/2⌋ individual runs were accepted, we can increase the accept probability of *w* ∈ *L* to at least 1-2^{-Ω(m)} by the Chernoff bound. The case where *w* ∉*L* is slightly more subtle, because we wish to show that for *all* Interactive Turing Machines *P'*, *any* interaction succeeds with probability at most ⅓, *regardless* of what happened in the previous interactions with *P'* (the prover strategy may depend on these previous interactions). However, by the definition, this probability is at most ⅓ even for the provers that know everything about previous interactions, so again by the Chernoff bound we get that if *w* ∉*L*, the accept probability is at most 2^{-Ω(m)}. In particular, taking *m*=O(*n ^{s}*) for some

*s>0*means we have polynomially many interactions, and probabilities at least 1-2

^{-ns}and at most 2

^{-ns}respectively. Thus, we can say that, intuitively, an IPS for a language

*L*consists of an "honest" prover and an "honest" verifier such that when

*w*∈

*L*, the prover can convince the verifier of this fact with very high probability, but when

*w*∉

*L*,

*no prover*can wrongly convince the verifier, except with very low probability.

The fractional **constants are not important**, and, using the same argument with Chernoff bounds, we can replace them by any values strictly in (½, 1) and (0, ½) respectively. This same argument also shows why we **can use constants** instead of using the original definition where ∀*k* and all sufficiently large *w*, the probabilities are ≥ 1-|*w*|^{-k} and ≤ |*w*|^{-k} respectively.

It should be noted that **we cannot replace** ⅓ **with** 0: having perfect *soundness* reduces the class to **NP**. Indeed, the certificate for a verifier (in the **NP** sense) is basically a transcript of a successful interaction with the prover, and there is no certificate that can convince the verifier of a false membership, concluding the proof. The interested reader may wish to compare this proof to the one showing that the randomness of the verifier is essential, as the core ideas are very similar.

Surprisingly, however, **replacing** ⅔ **with** 1 **does not change the complexity class**, i.e. having perfect *completeness* is no more restrictive. This result was originally proven in 1989 by using the fact that public coin and private coin proofs are essentially the same, but is somewhat complicated. The proof we give below that **IP**=**PSPACE** provides a much more elegant explanation.

Finally, we should remark that **fixing the verifier V, but having a different prover P_{w} for all w ∈ L does not change the complexity class** either. Indeed, the prover

*P*is computationally unbounded, and can thus find and simulate each of the smaller provers, which can be assumed to be deterministic.

*P*can also easily simulate the interaction with

*V*, as

*V*'s randomness and the total length of the messages exchanged are bounded, so

*P*could simply enumerate all possibilities, and ensure that the completeness condition is satisfied.

With these remarks in hand, we can finally define the **IP** class:

### Definition 5 (The **IP** Class)

The Interactive Polynomial (**IP**) time class is the class of languages that have an Interactive Proof System. For polynomial *q(n)*, we also denote by **IP**[*q*] the class of languages that have an IPS with *q(n)* rounds for *w* with *|w|=n* (whether *w* ∈ *L* or not).

## Coin Tosses Are Essential… But Only For The Verifier

The **non-determinism of the verifier is essential** to make the **IP** class non-trivial. Indeed, suppose for the language *L*, there is an IPS (*P,V*), where *V* does not use any randomness. Then, on input *w*, at each step of the communication, after *P* sends out it’s *i*-th message *m _{i}*, it already knows

*V*’s response,

*n*, as

_{i}*V*is deterministic. As a result, there exists a single-round IPS (

*P',V'*) for

*L*, where

*P'*simulates the interaction between

*P*and

*V*and sends the entire message history to

*V'*(which is polynomial in length by definition), and

*V'*simply simulates

*V*on the exchanged message history and checks that the transcript is valid.

What this means is that if *w* ∈ *L*, there must be at least one *c* (sent to *V'* by *P'*), such that *V'* accepts on (*w, c*), else the accept probability would be 0. In addition, if *w* ∉ *L*, there can’t be any *c* such that *V'* accepts (*w, c*). Indeed, if it were so, a cheating prover could always send *c* to *V'*, and in that case the probability of accepting would be 1 > ⅓, contradicting the definition of an IPS. This shows that *V'* is a verifier for *L* in the **NP** sense, establishing that the set of languages in **IP** with a deterministic verifier, denoted as **dIP**, is such that **dIP** ⊆ **NP**. But by the introductory remarks, we also have that **NP** ⊆ **dIP**, concluding the proof that **dIP** = **NP**.

However, **the prover can be deterministic**. Suppose we have a different prover *P _{w}* for each

*w*. Then, fixing

*w*and the prover's randomness

*r*, and simulating the interaction with

*V*over all values of

*V*’s randomness (which we can do, as the randomness is bounded), we get that for each

*r*, we have a probability

*p*that

_{r}*V*accepts. Out of all such

*r*, there must exist at least one

*r'*with

*p*≥ ⅔, else (

_{r'}*P,V*) would accept with probability < ⅔. Thus, we can use the prover

*P'*which simulates

_{w}*P*with a randomness of

_{w}*r'*, and is thus deterministic. Combining each individual prover to an all-around prover that is still deterministic shows that the prover’s non-determinism is truly non-essential.

## Coin Tosses Can Be Public

Up until now, both verifier and prover did not reveal the outcome of their coin tosses. As a matter of fact, we cannot send the prover's coin tosses across, because they might not be polynomially bounded, but we can introduce a class where the verifier sends its coin tosses to the prover instead of a message. This was done by Babai (also in 1985), and lead to the complexity class **AM**:

### Definition 6 (**AM**, Public Coins)

For every polynomial *q(n)*, we define the class **AM**[*q*] as the subset of **IP**[*q*] where the verifier's messages are the random bits used. That is to say, only the coin flips are sent across and no coin flip is allowed if it is not sent across. These are called *public coin* or *Arthur-Merlin* proofs, where Arthur is the verifier and Merlin the prover. The class **AM** is defined to be **AM**[2], which means that the verifier sends the random bits, receives the prover's response and then deterministically accepts/rejects.

There is a related notion of the hierarchy classes **MA**, where the prover Merlin moves first, but we won't discuss it further, as they can be reduced to **AM** interactions with an extra "dummy" round, though it is unknown whether **AM**≟**MA**. Note that, as before, we can still require perfect completeness (i.e. making Arthur accept with probability 1) without changing the two complexity classes.

As Babai also showed in his original paper, we have that for any fixed *k* ≥ 2, **AM**[k] = **AM**[2], by showing that **AM**[k + 1] ⊆ **AM**[k], as the reverse direction is trivial. An even more surprising result due to Goldwasser and Sipser is that every private coin proof in **IP** has a public coin proof with just two more rounds of interactions. Because **AM**[*poly*] is by definition a subset of **IP**, this shows that **AM**[*poly(n)*] = **IP**.

The crux of the proof lies in the fact that for every function *q* : ℕ → ℕ computable in polynomial time, we have that **IP**[*q*] ⊆ **AM**[*q* + 2]. Though the actual proof is very technical and beyond the scope of this introductory post, the basic idea is quite elegant. As explained above, we can assume that the prover is deterministic, and that the private-coin verifier's random strings are bounded in length by *q*(*n*). Convincing the verifier that *w* ∈ *L* in the private-coin version essentially comes down to showing that the set of accepting strings has size more than ½ of the original set (i.e. size strictly more than 2^{q(n)-1}). The "game" between the prover and the verifier then can be rephrased as follows: given a set *S* ⊆ {0,1}^{m}, and a common number *K*, the prover tries to convince the verifier that |*S*| ≥ *K*, and the verifier needs to reject with high probability if |*S*| ≤ *K*/2. Goldwasser and Sipser then use *pairwise independent hash functions* to make concrete the protocol for proving the size of the set, but there is considerable detail in establishing completeness and soundness, and even more subtlety in showing that we can do this in a way that only increases the number of rounds by 2.

## It's Just Polynomial Space

An interesting and perhaps somewhat unexpected theorem due to Shamir is that **IP** = **PSPACE**. The proof we present here in detail, however, is the one given in the Sipser and Arora/Barak books mentioned previously.

**IP** ⊆ **PSPACE**

First off, we prove that **IP** ⊆ **PSPACE**. The proof, although slightly technical uses a very simple idea: because the messages exchanged are polynomial in length, the entire tree of interactions can be explored in polynomial space, and for each fixed *w*, we can find the maximum probability that any prover can convince the verifier that *w* ∈ *L* (We are using the equivalent version of an IPS, where we have a distinct prover per *w*). Then, if this probability is ≥ ⅔, we declare that *w* ∈ *L*, and if it isn't (and is then forced to be ≤ ⅓, else this verifier does not give rise to an IPS), then *w* ∉ *L*.

To formalize this argument, given a language *L* ∈ **IP**, we suppose that the verifier *V* exchanges exactly *p* = *p*(|*w*|) messages, where we add dummy messages if necessary. We define Pr[*V* accepts *w*] = max_{P} Pr[(*P, V*) accepts *w*]. By definition, this is ≥ ⅔ if *w* ∈ *L* and ≤ ⅓ otherwise. We claim that given *V* only, which we can simulate as it is polynomial time, we can calculate this probability and thus decide *L* in polynomial space. The idea now is that given the exchanged messages *M _{j}* =

*m*

_{1}#…#

*m*, we can calculate the probability that (

_{j}*P,V*) accepts assuming they have exchanged

*M*, and thus working backwards we can calculate the probability of accepting, starting without any message exchanges.

_{j}We thus write (*P,V*)(*w,r,M _{j}*) = accept if we can extend

*M*with

_{j}*m*, …,

_{j+1}*m*such that:

_{p}• For 0 ≤

*i*<

*p*, and

*i*even,

*V*(

*w, r, m*

_{1}#…#

*m*) =

_{i}*m*

_{i+1}• For

*j*≤

*i*<

*p*, and

*i*odd,

*P*(

*w, m*

_{1}#…#

*m*) =

_{i}*m*

_{i+1}•

*m*= accept.

_{p}This essentially says that given the randomness *r*, the verifier's messages are consistent, and we (deterministically) extend the prover's messages, until we have reached the end and have accepted. Then, we can define Pr[(*P, V*) accepts *w* starting at *M _{j}*] = Pr

_{r}[(

*P, V*)(

*w, r, M*) = accept], where the probability is taken over all strings of randomness

_{j}*r*that are consistent with

*M*, or 0 if no such strings exist. Then, we can define Pr[

_{j}*V*accepts

*w*starting at

*M*] = max

_{j}_{P}Pr[(

*P, V*) accepts

*w*starting at

*M*].

_{j}For *M _{j}*, where 0 ≤

*j*<

*p*, we define

*N*as follows:

_{Mj}• 1, if

*j*=

*p*, and

*M*is consistent with

_{p}*V*'s messages for some

*r*and

*m*= accept

_{p}• 0, if

*j*=

*p*, but the above is not true

• max

_{mj+1}

*N*, if

_{Mj+1}*j*<

*p*is odd

• ∑

_{mj+1}Pr

_{r}[

*V*(

*w, r, M*) =

_{j}*m*] ·

_{j+1}*N*, if

_{Mj+1}*j*<

*p*is even.

If *M*_{0} represents the empty message stream, we wish to show that *N _{M0}* is computable in polynomial space and that it represents the probability that

*V*accepts

*w*. The first part is easy: knowing the values at

*j + 1*, calculating the values at

*j*either requires taking a maximum, or a weighted-average. The maximum is easy, and the weighted average simply requires going over all strings of randomness (whose lengths are polynomially bounded), seeing which ones are consistent, and checking the fraction of the remaining ones that cause to verifier to output

*m*. This does not require storing many values at a time: we can be averaging/maximizing for the next level as we are computing, and the depth of the recursion is polynomial, so this only requires polynomial space, as desired.

_{j+1}The second claim is proven by backwards induction, that is to say, for all 0 ≤ *j* ≤ *p*, and every *M _{j}*, we must show that

*N*= Pr[

_{Mj}*V*accepts

*w*starting at

*M*]. Indeed, the base case

_{j}*j*=

*p*is by definition is correct. Assuming we have it for

*j + 1*and all

*M*, we must take cases:

_{j+1}If *j* is even:

*N _{Mj}* =

∑

*Pr*

_{mj+1}_{r}[

*V*(

*w, r, M*) =

_{j}*m*] ·

_{j+1}*N*=

_{Mj+1}∑

*Pr*

_{mj+1}_{r}[

*V*(

*w, r, M*) =

_{j}*m*] · Pr[

_{j+1}*V*accepts

*w*starting at

*M*] =

_{j+1}Pr[

*V*accepts

*w*starting at

*M*],

_{j}where the first and last equalities are by definitions and the second by the induction hypothesis.

If *j* is odd:

*N _{Mj}* =

max

_{mj+1}

*N*=

_{Mj+1}max

_{mj+1}Pr[

*V*accepts

*w*starting at

*M*] =

_{j+1}Pr[

*V*accepts

*w*starting at

*M*],

_{j}where the first and second equalities are as above. The third comes from observing that it is ≤, as the prover that maximizes the probability at

*j*needs to send an

*m*maximizing the probability at

_{j+1}*j + 1*. But it is also ≥, as sending anything else but the maximizing

*m*can only lower the resulting probability.

_{j+1}This concludes the proof that **IP** ⊆ **PSPACE**.

**PSPACE** ⊆ **IP**

We now wish to show that **PSPACE** ⊆ **IP**. We know that 3-CNF TQBF is complete in polynomial space, so it suffices to show that 3-CNF TQBF has an IPS. The proof relies on a beautiful concept called *arithmetization*. The variables *x _{i}* can be thought of as taking the truth values 0, 1 over some finite field

**F**. Then,

*x*∧

_{i}*x*is true iff

_{j}*x*·

_{i}*x*= 1 and ¬

_{j}*x*is true iff 1 -

_{i}*x*= 1 in the field. Thus, given a clause of the form

_{i}*x*∨

_{1}*x*

_{2}∨

*x*

_{3}, the polynomial 1-(1-

*X*

_{1})

*X*

_{2}

*X*

_{3}is 1 iff the {0,1}

^{3}assignment to

*X*makes the clause true and 0 otherwise.

_{1}, X_{2}, X_{3}Thus, if the original formula has *m* clauses in *n* variables, for the *j*-th clause, we can define the polynomial *p _{j}*(

*X*

_{1}, …,

*X*) as above (which only depends on three variables), and we can define the overall polynomial

_{n}*P*(

_{Φ}*X*

_{1}, …,

*X*) = ∏

_{n}_{0 ≤ j ≤ m}

*p*(

_{j}*X*

_{1}, …,

*X*), whose value is 1 on satisfying assignments and 0 otherwise. This is the

_{n}*arithmetization*of the boolean formula, and the crux of the IPS is that allowing this polynomial to be evaluated over

**F**

^{n}(as opposed to {0,1}

^{n}) gives the prover its required power.

Now, given a formula in alternating 3-CNF TQBF (which, again, is PSPACE complete) of the form
*Ψ* = ∀ *x*_{1} ∃ *x*_{2} … ∃ *x _{n}*

*Φ*(

*x*

_{1}, …,

*x*),

_{n}*Ψ*∈ TQBF iff

∏

_{b1 ∈ {0,1}}∑

_{b2 ∈ {0,1}}… ∑

_{bn ∈ {0,1}}

*P*(

_{Φ}*b*

_{1}, …,

*b*) ≠ 0

_{n}Because the above formula is only evaluated over {0,1}, we always have *x ^{k}* =

*x*for

*k*≥ 1.

As a result, the *linearization polynomial*
*L _{Xi}*(

*p*)(

*X*

_{1}, …,

*X*) =

_{n}*X*·

_{i}*p*(

*X*

_{1}, …,

*X*, 1,

_{i-1}*X*, …,

_{i+1}*X*) + (1-

_{n}*X*) ·

_{i}*p*(

*X*

_{1}, …,

*X*, 0,

_{i-1}*X*, …,

_{i+1}*X*)

_{n}is both linear in

*X*and agrees with

_{i}*p*when

*X*∈ {0,1}. In addition, we have that

_{i}∀

*X*

_{i}*p*(

*X*

_{1}, …,

*X*) =

_{n}*p*(

*X*

_{1}, …,

*X*, 0,

_{i-1}*X*, …,

_{i+1}*X*) ·

_{n}*p*(

*X*

_{1}, …,

*X*, 1,

_{i-1}*X*, …,

_{i+1}*X*), and

_{n}∃

*X*

_{i}*p*(

*X*

_{1}, …,

*X*) =

_{n}*p*(

*X*

_{1}, …,

*X*, 0,

_{i-1}*X*, …,

_{i+1}*X*) +

_{n}*p*(

*X*

_{1}, …,

*X*, 1,

_{i-1}*X*, …,

_{i+1}*X*)

_{n}so that the original product/sum value is non-zero iff

∀

*x*

_{1}

*L*∃

_{X1}*x*

_{2}

*L*…∃

_{X2}*x*

_{m}*L*

_{Xn}*P*

_{Φ}(

*X*

_{1}, …,

*X*) ≠ 0.

_{n}It is clear that the size of this expression was only expanded by *O*(*n*^{2}), and the original polynomial *P* only requires *O*(*m*) space (before we expand it), as it uses *m* cubic polynomials.

Now, we inductively describe the protocol. Initially, the prover chooses a prime *p* ∈ (2^{n+m},2^{2(n+m)}] and sends it to the verifier (after a dummy "hello" message by the verifier). The verifier then either deterministically or probabilistically in polynomial time checks that *p* is prime. We suppose that for polynomial *g*(*X*_{1}, …, *X _{k}*), the prover is able to convince the verifier that

*g*(

*a*

_{1}, …,

*a*) =

_{k}*C*for any

*a*

_{1}, …,

*a*,

_{k}*C*with probability 1 when the claim is true and less than ε when the claim is false, where the equality is over

**F**

_{p}. We define the polynomial

*U*(

*X*

_{1}, …,

*X*) =

_{l}*O*

*X*

_{o}*g*(

*X*

_{1}, …,

*X*), where

_{k}*O*is one of ∃, ∀,

*L*and the number of variables

*l*is

*k - 1, k - 1, k*respectively in these cases.

Denoting by *d* an upper bound on the degree of *x _{i}* in

*U*, we show that the prover can convince the verifier that

*U*(

*a*

_{1}, …,

*a*) =

_{l}*C'*with probability 1 for any

*a*

_{1}, …,

*a*,

_{l}*C'*when the claim is true, and with probability at most ε +

*d/p*if it is false. By renaming if necessary, we can assume

*i*= 1. The prover sends across a polynomial

*s*(

*X*

_{1}) (which has degree ≤

*d*) and which is supposed to equal

*g*(

*X*

_{1},

*a*

_{2}, …,

*a*), and the verifier checks the following:

_{k}
• If *O* = ∃, the verifier checks that *s*(0) + *s*(1) = *C'*

• If *O* = ∀, the verifier checks that *s*(0) · *s*(1) = *C'*

• If *O* = *L*, the verifier checks that *a*_{1}*s*(0) + (1 - *a*_{1})*s*(1) = *C'*.

If the check doesn't work, then it rejects, otherwise, the verifier randomly picks *a* ∈ **F**_{p} and asks the prover to prove that *s*(*a*) = *g*(*a*, *a*_{2}, …, *a _{k}*).

Clearly, if the prover is honest, all these claims will go through, so the prover convinces the verifier with probability 1. If the claim that *U*(*a*_{1}, …, *a _{l}*) =

*C'*is false, then if the prover actually returns

*g*(

*X*

_{1},

*a*

_{2}, …,

*a*), the verifier will always reject. So the prover must lie, and return some

_{k}*s*'(

*X*

_{1}) ≠

*s*(

*X*

_{1}).

Because the polynomial *f*(*X*_{1})=*s*'(*X*_{1})-*s*(*X*_{1}) is non-zero and has degree at most *d* by assumption, it has at most *d* roots. But when *V* picks *a* ∈ **F**_{p}, Pr_{a}[*s*(*a*) ≠ *s*'(*a*)] ≥ 1-*d/p*. Thus, overall, the probability that *V* rejects is at least (1 - *d/p*)·(1 - ε) = 1-(ε +*d/p*) + ε*d/p* ≥ 1-(ε + *d/p*), thus *V* accepts with probability at most ε + *d/p*, as desired. It should be noted that these claims over the finite field hold because *p* is chosen to be large enough, and would not necessarily work in any general field.

Thus, because we have a recursion depth of *O*(*n*^{2}), our *d* is bounded above by 3*m*, and because *p* is exponential in *n + m*, the accept probability is very close to 0. The recursion depth is polynomial, at each step, the bits of randomness required is linear in *n + m*, and we only need to evaluate and send across a polynomial amount per stage, so this is really an IPS, concluding the proof that **PSPACE** ⊆ **IP**.

In particular, this also means that every language *L* ∈ **IP** has an IPS of perfect completeness. Indeed, because we also have that *L* ∈ **PSPACE**, there is a polynomial time *f* such that *w* ∈ *L* iff *f*(*w*) ∈ TQBF, and thus we can run the above protocol to get the verifier to accept with probability 1, as desired.

## One More Prover Gives Power… But Even More Do Not

The natural extension to the interactive proof model involves having more than 2 provers (which cannot communicate) trying to convince a single verifier of a string's membership in a language. Though this idea was initially introduced for the purpose of Zero-Knowledge Proofs for **NP** sets, in this section we discuss yet another result by Babai (et al.). First we need to generalize the single-prover definition:

### Definition 7 (*k*-Prover Interactive Protocol)

• *P*_{1}, …, *P _{k}* are computationally unbounded Turing machines

•

*V*is a probabilistic, polynomial time Turing machine

• All TMs have a read-only input tape, a scratch tape and a random tape

• All provers

*P*share an infinite read-only random tape of 0s and 1s

_{i}• Each

*P*has a read-only and a write-only tape to communicate with

_{i}*V*and vice-versa.

This definition means that even though the provers can "coordinate" through their common random tape, they can't communicate once the interaction with *V* has begun. Of course, for the definition to be precise, the Turing machine definition also needs to be amended, but this is done similarly to the definition of ITMs. The extension for a *k*-prover interactive proof system is thus natural:

### Definition 8 (*k*-Prover Interactive Protocol)

We say that the language *L* ⊆ {*0,1*}^{*} has a *k*-prover IPS if there exists *V* such that:

• ∃ *P*_{1}, …, *P _{k}* such that (

*P*

_{1}, …,

*P*,

_{k}*V*) is a

*k*-prover interactive protocol and ∀

*w*∈

*L*, Pr[

*V*accepts

*w*] ≥ ⅔

• ∀

*P*

_{1}', …,

*P*' such that (

_{k}*P*

_{1}', …,

*P*',

_{k}*V*) is a

*k*-prover interactive protocol and ∀

*w*∉

*L*, Pr[

*V*accepts

*w*] ≤ ⅓.

We can thus define the relevant complexity class:

### Definition 9 (The **MIP** Class)

The Multi-Prover Interactive Polynomial (**MIP**) time class is the class of languages that have a 2-prover Interactive Proof System. For polynomial *q*(*n*), we also denote as **IP**_{q} the class of languages that have an interactive proof system with *q*(|*w*|) provers on input *w*.

The first interesting result regarding this complexity class is that adding additional provers does not benefit us, i.e. **IP**_{q} = **MIP**. The idea is that one prover *P*_{1}' can simulate all the individual provers *P*_{1}, …, *P _{q}*, while a second prover

*P*

_{2}' can be used to simulate a specific prover, which is chosen randomly. This way, the second prover

*P*

_{2}' can be used to check the non-collusion property of the system, verifying the transcript provided by

*P*

_{1}'. Even though in the original paper this is only proven for fixed

*q*(

*n*) =

*k*≥ 2, it can be easily seen that repeating the sub-protocol sufficiently many polynomial times, the more general result follows.

The second very interesting result is that adding the second prover does in fact give us additional power under reasonable hierarchy assumptions. That is to say, **MIP** = **NEXPTIME**. The proof given by Babai is very lengthy and technical (unlike the above result which can be proven in less than half a page and just consists of formalizing the given idea), and even showing that **MIP** ⊆ **NEXPTIME** is not as straightforward as its **IP** ⊆ **PSPACE** counterpart. This result was first shown by Fortnow et al., and the key step is that a language *L* has a multi-prover IPS iff it is accepted by some probabilistic oracle. Then the non-deterministic exponential time machine guesses the values of the oracles on all relevant length strings (which are polynomially bounded), and accepts if more than half are satisfied, in a similar idea as the one used for transforming private-coin proofs to public coin proofs.

The reverse direction (that **NEXPTIME** ⊆ **MIP**) proven by Babai et al. used the fact that every *L* ∈ **NEXPTIME** can be transformed into a 3-CNF with exponentially many clauses and variables (also known as "SUCCINCT 3SAT"). The crux of the argument is then a modified version of the arithmetization argument we presented in the **PSPACE** ⊆ **IP** proof, but with a lot of technicalities. For instance, it is neccesary to "test whether a function in *n* variables over ℤ, given as an oracle, is multilinear over a large interval". As the authors put it in the paper, the problem essentially exists when the provers can "gain an advantage by having the [arithmetization] function *A* not multilinear", as their protocol heavily relies on that fact. Even though the actual proof is complicated and relies on combinatorics to calculate eigenvalues and prove some bounds on graphs, the end result is that there exists a probabilistic polynomial-time Turing machine that given access to *A* as an oracle, always accepts if *A* is a "nice" multilinear function, and rejects with high probability if *A* cannot be approximated by a multilinear function on a "large" fraction of the domain, which is sufficient to proof soundness of the constructed protocol.

## Putting It All Together

In this post, we discussed how Interactive Proof Systems can have perfect completeness, but not perfect soundness, even though we can get arbitrarily close. Moreover, we discussed that we can have different provers for each *w*, which can also be deterministic. However, the verifiers must use randomness, since **dIP** = **NP**, even though these coin tosses can be made public, because **AM**[*poly*] = **IP**. Though we only glanced over this fact, we proved in great detail that **IP** = **PSPACE** by using the ideas of simulation, arithmetization, and linearization. Finally, we gave insights into why an extra (non-colluding) prover adds power, and also why even more do not, so that **IP**_{q} = **MIP** = **NEXPTIME**.

Overall, Interactive Proof Systems are truly remarkable, with the resulting complexity classes being closely related to many "traditional" classes, and it is unfortunate that they are often ignored or assumed as background when discussing Zero-Knowledge Proofs, a topic for another post.