ZK Fundamentals: Proof Systems

We cover Interactive Proofs (IP), Probabilistically Checkable Proofs (PCPs), Linear PCPs, Multi-prover Interactive Protocols (MIPs), and Interactive Oracle Proofs (IOPs)

This is the seventh article from our series exploring ZK fundamentals, zero knowledge proofs and related notions. Read the previous ones here:

ZK Fundamental series:
📚 Part I: Zero-Knowledge Proofs Explained
📚 Part II: Interactive Proofs
📚 Part III: Zero-Knowledge
📚 Part IV: The Fiat-Shamir Transform
📚 Part V: Succinctness
📚 Part VI: Intermediate Representations

Interactive proofs (IPs), multi-prover interactive proofs (MIPs), probabilistically checkable proofs (PCPs), and interactive oracle proofs (IOPs) — you have surely heard about the multitude of proof system models around.

In this article, we provide a detailed account of the most common models, how they compare to each other, and their strengths and weaknesses. For completeness, and at the risk of repeating some content from previous articles, we will start from the beginning: the classical proof.

The Classical Proof

We had elaborated on the definition of a statement and its proof in Part I of this series.

Our statements are expressed as membership in a set, which we call a language. Languages come in different classes, depending on their complexity, i.e., according to how difficult it is to decide whether a given element 𝑥 is in the set.

The complexity is measured as a function of the size of the element 𝑥, e.g., in the length of its bit representation. The class P consists of all languages where there is a polynomial-time algorithm to decide the membership of elements 𝑥 (the number of steps required is bounded by a polynomial function in the number of bits in the representation of 𝑥).

The class NP consists of languages where proofs of membership for an element 𝑥 can be given, which can be verified in polynomial time (again, in the size of 𝑥).

So, for an NP language 𝐿, for a given element 𝑥 ∈ 𝐿, we can provide a proof 𝑤 for membership in 𝐿, which can be verified in polynomial time.

Thus, the set of tuples (𝑥, 𝑤) (let us denote it by 𝑅ʟ) can be decided in polynomial time, and the language consists of all elements 𝑥 such that there is a 𝑤 with (𝑥, 𝑤) ∈ 𝑅ʟ.

So given 𝑥, although it might be difficult to check if 𝑥 ∈ 𝐿 directly, the prover might just send the proof (witness) 𝑤, and the verifier checks that (𝑥,𝑤) ∈ 𝑅ʟ.

But by now, we know that one can do better: with less communication cost (sending something much smaller than proof 𝑤) and less computational burden on the verifier.

Proofs versus Arguments

When it comes to succinctness, i.e., if the total communication cost and verifier’s work are less than they could be in the classical case, the soundness definition becomes crucial.

For a proof, in the case that we want to be safe against all possible malicious provers (even computationally unbounded ones), it can be shown that not much can be gained.

To gain efficiency (both in terms of the size of the proof and the verifier’s work), we have to relax the soundness requirement to hold only against efficient (computationally bounded) provers.

Such proof systems, introduced by Brassard, Chaum, and Crépeau, are called arguments, though by abuse of language, they are sometimes still called proofs.

Interactive Proofs (IPs)

We treated interactive protocols at length in Part II: Interactive Proofs. They were introduced by Goldwasser, Micali, Rackoff, and independently by Babai.

In these protocols, prover and verifier engage in an interaction with several rounds, sending each other messages.

The verifier has access to randomness (otherwise, the prover could just compute the verifier’s messages and send the whole transcript).

In the interactive proofs introduced by Babai, the verifier only sends random challenges (outcomes of random coin tosses), also called public-coin, independent of the messages sent by the prover. These are known as Arthur-Merlin Proofs.

Though at first, this seems like a big restriction, and the possibilities in the case that the verifier can send challenges depending on previous messages seem to be more general and powerful, Goldwasser and Sipser have proved that they are in fact equivalent.

Probabilistically Checkable Proofs (PCPs)

In Part IV: ZK Fundamentals: The Fiat-Shamir Transform, we discussed Probabilistically Checkable Proofs (PCPs) at length.

Intuitively, it is a way of writing down a proof in such a way that any blunder is spread evenly over its entirety so that random sampling of a few bits will be enough to catch it.

If a proof is largely correct, it is completely correct.

More precisely, for any language in NP, there is a way of writing proofs, and a corresponding verifier (with access to some randomness) such that, independently of the length of the proof (!) the verifier will access only a few bits of it and will accept a correct proof and reject any false claim with high probability.

With two parameters, we can specify the resources available to the verifier:

• The amount of randomness 𝑟(𝑛) available, and
• The number of bits of the proof that can be queried 𝑞(𝑛)

…both given as a function of the size 𝑛 of the input 𝑥.

With different configurations of these parameters, we can recover different complexity classes.

We denote the corresponding class by 𝑃𝐶𝑃(𝑟(𝑛), 𝑞(𝑛)). Allowing no randomness, but polynomially many queries (using which the verifier can in fact read a whole polynomially length proof), we clearly recover the class 𝑁𝑃 = 𝑃𝐶𝑃(0, 𝑝𝑜𝑦(𝑛)).

Allowing logarithmically many coin tosses does not add anything, as all the outcomes of logarithmically many coin tosses can be processed in polynomial time. So we have 𝑁𝑃 = 𝑃𝐶𝑃(𝑙𝑜𝑔(𝑛), 𝑝𝑜𝑦(𝑛)).

But the big surprise is that once we allow logarithmically many coin tosses, we can in return reduce the number of queries 𝑞(𝑛), so we only need to read a subset of the proof (determined by the coin tosses).

And in fact, constantly many queries, independent of the size of the input and the proof, are enough! 𝑁𝑃 = 𝑃𝐶𝑃(𝑙𝑜𝑔(𝑛), 𝑂(1)).

Linear Probabilistically Checkable Proofs (Linear PCPs)

PCPs create a redundant encoding of the proof, which allows it to be verified with a small number of queries.

Though the verifier is going to probe the proof string only at a few places, it is crucial that the prover fixes it in advance (the prover should not be able to adaptively choose the proof according to the queries).

This is achieved using a cryptographic commitment scheme (see Part V: Succinctness for details).

The prover is forced to commit to the whole proof, and afterward, only a small portion of the proof has to be revealed to the verifier (according to the queries). So, the proof is first expanded (through the redundant encoding), and afterward, only a small fraction is used.

Ishai, Kushilevitz, and Ostrovsky introduced Linear PCPs to combine these size-wise opposing steps of expansion and subsequent shrinking to come up with a more efficient scheme.

Moreover, as the full PCP machinery is quite complicated and its construction creates a heavy computational burden, a further aim while introducing Linear PCPs is to allow for a simpler argument without requiring the complexity of a full PCP.

A usual probabilistically checkable proof is a short (polynomial-sized) encoded proof, which the verifier can query at arbitrary points. So, we can think of it as an oracle, which, given one of polynomially many positions, returns the entry of the proof at the given point. Hence, a function that has a domain of polynomial size. For Linear PCPs, the domain is enlarged to a vector space of polynomial-size dimensions, so exponential cardinality, but in return, we restrict the oracle to a function that is linear. So how can a prover convince a verifier by just answering queries to a determined linear function?

The idea is as follows: rephrase the problem as an arithmetic satisfiability instance (see Part VI: Intermediate Representations).

So, the prover claims to know a solution to a bunch of quadratic equations in 𝑛 variables (considering quadratic equations is enough, think R1CS). We will “linearize” the solution vector of length 𝑛, as we want to work with linear objects.

As the quadratic equations involve not only the entries of the solution vector but also degree 2 terms consisting of products of two such entries, we form a new vector of length 𝑛+𝑛² containing all of these (we introduce new variables for each product).

Now the initial quadratic equations turn into linear equations in this extended set of variables. The oracle just allows computing linear combinations of these. So given a list of coefficients, it returns the corresponding linear combination of these 𝑛+𝑛² elements.

Once the verifier is confident that the oracle really gives a linear function by querying it at random points and their linear combinations, he can check that all quadratic equations in the initial variables are satisfied by linear queries to the oracle. And many such queries can be combined, as usual, by taking random linear combinations.

To realize this we need a mechanism for the prover to commit to a given linear function and open it at various points of the verifier’s choosing, along with corresponding proofs of correctness. This is done using homomorphic encryption.

For further details and further optimizations, we refer to the original article and remark that there are further improvements in a long list of subsequent articles. In particular, Linear PCPs underlie the extremely succinct and efficiently verifiable pairing-based SNARKs like Groth16.

Multi-prover Interactive Protocols (MIPs)

Multi-prover interactive protocol in action

If you think of an interactive proof with verifier challenges to the prover as an interrogation (trying to catch a fraudulent prover), then an efficient interrogation method to catch a lie in case there are more than one suspect is to question them separately, to check if their narratives are consistent and play them off against each other.

On the other hand, innocent suspects (honest provers) will have an easier task in convincing their interrogator by confirming each other’s narratives without communicating.

This idea was turned into a proof system by Ben-Or, Goldwasser, Kilian, and Wigderson, namely a Multi-prover Interactive Protocol (MIP).

In MIP the verifier communicates with several provers, who do not communicate with each other, in several rounds. The authors have shown in fact that 2 provers suffice in that it is as expressive as more than 2 provers, if we accept a polynomial size blow-up in the work done by the verifier.

Babai, Fortnow, and Lund have shown that any language in NEXP (“Nondeterministic EXPonential time”, the class of languages that can be decided by a non-deterministic Turing machine in exponential time) has a single round, 2 prover proof in this model. So MIPs are very expressive.

Let us try to understand what distinguishes these different proof systems.

Compare for instance a 2 prover 1 round MIP with a 2 round IP, which by definition has only one prover. In the case of the IP with 2 rounds, in the second round the prover will have seen the first message by the verifier and his own response.

Hence, he can adaptively choose his behavior in the second round. The two non-communicating provers in the MIP do not have that luxury. It is this non-adaptivity of the MIP provers that makes it easier to catch them in a lie.

At the other end of the spectrum would be the PCP. Here the whole proof string is fixed a priori. So no adaptive strategy is possible in any of the queries, as the response will definitely be independent of all previous queries.

The relation between MIP and PCP goes beyond the non-adaptivity aspect: the class of languages with a Multi-prover interactive proof is given by

𝑃𝐶𝑃(𝑝𝑜𝑙𝑦(𝑛), 𝑝𝑜𝑙𝑦(𝑛))

A MIP can be turned into a PCP and vice versa, however with some overhead.

Let us show the idea of one direction: given an MIP with 𝑘 rounds and 𝑝 provers, we need a way to encode everything in a single long proof string. The PCP oracle will just simulate all provers.

The response for an interaction of 𝑗 rounds with prover 𝑖 on input 𝑥 where messages 𝑚₁, 𝑚₂, …, 𝑚ⱼ have been sent from the verifier, is defined to be the response of the query to the PCP on input (𝑖,𝑗,𝑚₁,𝑚₂,…, 𝑚ⱼ).

The assumption that the provers cannot communicate is a powerful one. As you might remember from Part III: Zero-Knowledge, Goldreich, Micali, and Wigderson have shown that every language in NP has a computational zero-knowledge proof under the assumption that one-way functions exist. Moreover, Fortnow and Boppana, Hastad, Zachos have shown that perfect zero knowledge is impossible, unless the polynomial hierarchy collapses.

MIPs replace the intractability assumption by a physical restriction, namely that the provers cannot communicate with each other. Ben-Or, Goldwasser, Kilian, and Wigderson show that in this model, all NP languages have perfect zero-knowledge proofs, without the need of any intractability assumptions.

Interactive Oracle Proofs (IOPs)

Interactive Oracle Proofs (IOPs) enable verifying a proof by random queries to parts of the proofs. The verifier doesn’t need to read the entire proof.

Interactive Oracle Proofs were introduced by Ben-Sasson, Chiesa, Spooner, and independently by Reingold, Rothblum, Rothblum (under the name Probabilistically Checkable Interactive Proofs).

They naturally combine IPs and PCPs: the prover and verifier interact as in an IP, but the verifier probabilistically queries the prover’s responses as in a PCP.

Unlike a PCP, it allows several rounds of interaction, while at the same time enjoying the expressive power of a PCP. It is a multi-round protocol with a PCP at each round.

As in an IP, the verifier sends a challenge, for which the prover responds with a PCP. This is repeated several times, and at the end, the verifier does random queries to all of the received PCPs. If the verifier would read the responses entirely, we would get an IP; without a first challenge and a single round, we would get a PCP.

Just as before, we can turn this non-interactive and succinct.

In the case of the PCP, the prover was sending a Merkle root hash as a commitment and use it as a random challenge to render the protocol non-interactive. We will do the same now, repeating for each round and feeding the Merkle roots into a hash chain, à la Kilian-Micali and Fiat-Shamir.

So, we obtain a SNARK that is unconditionally secure in the random oracle model. All of this can also be turned zero-knowledge. IOPs and the resulting systems still have all the nice properties from before, with the big advantage that they allow us to stay away from the monstrous PCP construction doing all the proof at once.

Variations: Linear IOPs and Polynomial IOPs (PIOPs)

As in the case of PCPs, we can obtain variations of PCPs by specifying the nature of possible probabilistic queries to PCPs returned by the prover. In analogy with Linear PCPs, in Linear IOPs, in each round, the prover sends a linear PCP (the verifier can query a linear function).

Polynomial IOPs are a special case of this: Given a polynomial (univariate or multivariate), evaluating it at a given point can be expressed as an inner product of the coefficient vector with a suitable vector obtained from the coordinate(s) of the evaluation point.

Hence, evaluating at a point can be seen as a linear query as well, and we obtain Polynomial IOPs, where the proof is a polynomial (with potentially a large number of coefficients) and probing the proof at certain locations translates to evaluating the polynomial at certain points. So, the verifier obtains only the values of the polynomial at a given number of points, rather than the long list of its coefficients (as such, the verifier does not read the whole proof).

Though we could only touch on the main ideas, hopefully, this should have given you an impression of the big variety of proof systems out there. Each of them comes with their own strengths and weaknesses, assumptions, and distinguishing features.

Judging from the dazzling advances in the past couple of decades, it is fair to guess that many more are just waiting to be discovered. The frequency with which new ideas and ingenious new constructions come into being shows that the future has lots in store for us.

Author: Alp Bassa, Research Scientist at Veridise

Want to learn more about Veridise?

Twitter | Lens | LinkedIn | Github | Request Audit