This is the fifth article from our series exploring ZK fundamentals, zero knowledge proofs and related notions.
ZK Fundamental series:
📚 Part I: What is a proof?
📚 Part II: Interactive Proofs
📚 Part III: Zero-Knowledge
📚 Part IV: The Fiat-Shamir Transform
📚 Part V: Succinctness
📚 Part VI: Intermediate representations
Up until now we have seen the power of interaction and randomness together with the probability to err. They are more expressive as the corresponding languages are larger (IP = PSPACE rather than NP) and allow features not possible in the classical situation. We defined zero-knowledge and saw under which security assumption/in which model all of this can be rendered non-interactive. Now it is time to talk about efficiency.
When we talk about efficiency, we can think of several measures: the workload of the prover, the workload of the verifier, the communication needed etc.
In the first interactive proofs the prover was computationally unbounded and had to convince a weak verifier. We were not too concerned about the workload of the prover. In practice, we want the computational burden on the prover not to be bigger than performing the computation itself. If and how this is possible is another story. Today we will be more concerned with the workload of the verifier and more prominently the total communication.
To be convinced by a classical NP proof that an instance x is in a language L we would have to read the witness w and check that the defining relation R(x, w) holds. This verification should be done in polynomial time (so in particular the size of the witness w can be at most polynomial in the size of x, otherwise just reading it would take superpolynomial time).
The communicated proof is w in this case. The question is: can one save on the size of the communication? If this is the case we will say that the proof is succinct. Of course we have to pay a price for succinctness, which is soundness: we allow the verifier to accept wrong proofs with some small probability.
This again sounds a bit counterintuitive: how can a verifier be convinced without “reading through the whole proof”? After all, it is enough to have one tiny bug in some corner of a long proof to render it all incorrect (as so many “proofs” of the Riemann Hypothesis). The key lies in the probability to err. Let’s go over an example.
3-coloring again
Consider the problem of 3 coloring a graph: a graph is called 3-colorable if we can color its vertices with 3 different colors (assigning one of the three colors to each of the vertices) in a way that any two vertices connected by an edge have different colors.
We can define the language 3COL consisting of all graphs that are 3-colorable. Clearly 3COL is in NP. Given a graph, to prove it is 3 colorable we can just give a coloring. A witness is just a valid assignment of colors to its vertices.
We have to go through the color assignment to all of the vertices in order to be convinced that it is valid. Can we do with less than all the vertices? In theory, yes. Say there are e edges. We can randomly pick one of them and check if the colors assigned to the two vertices it connects are distinct. If the graph is not 3-colorable, then for each purported coloring (proof) there will be at least one edge connecting two vertices of the same color, which will be detected with probability 1/e, so falsely accept a false proof with probability (soundness error) at most (e — 1)/e. We can make this probability as small as we want, by repeating the process, i.e. by checking several edges. What we are basically doing is to poke the proof at one or several points to convince ourselves (with high probability) that it is correct.
Note that the randomness of the verifier is crucial here. Otherwise, if the requests from the verifier were predictable, the prover would just need to arrange the coloring so that it works for those queries (it is easy to pass an exam where you know the questions beforehand!).
There are, however, two somewhat displeasing aspects that we want to elaborate on.
1. How to do this?
The first one is more practical: how do we realize this? If the prover sends the whole assignment at the beginning, the verifier would have to read through it before checking certain points. If the verifier goes through the burden of reading it all, he might as well just check it, as not much is saved.
If, on the other hand, the verifier just requests color assignments sequentially, the prover would have a much easier job, as he could just randomly respond with two distinct colors each time, just making sure to stay consistent with the previous queries.
We need a gadget that would allow the prover to commit to the assignment initially (like putting it into a sealed box), and allow him to reveal certain parts of it individually (for instance by opening little windows on it) according to requests from the verifier.
The verifier should be convinced that the partial view he is seeing is consistent with what has been committed to before. This can be achieved through cryptography. For those familiar with these notions, the prover could just provide a Merkle root of the vector of color assignments to the verifier.
For each query from the verifier the prover can just provide the corresponding color and an opening proof. The prover just provides the Merkle root and opening proofs, which are each logarithmic in the size of the whole vector. So we really seem to have realized succinctness!
As we are using a hash function in the Merkle tree, a malicious prover who can create collisions for the hash functions would be able to convince the verifier of false claims. In particular now things are only sound in the case of computationally bounded provers. This is roughly the idea in the paper by Kilian (we will come back to it in a bit). And, as we know by now from the last article, all of this can be rendered non-interactive using the Fiat-Shamir transform.
2. How short can it get?
The soundness obtained above is not the best, to say the least. In particular, as the size of the graph increases and the number of edges increase, for a given number of queries the probability of rejecting a false claim tends to zero. Can we do better than that?
Clearly as the number of queries (the length of the proof) increases, the soundness error decreases. Тhere is a tradeoff between the total communication and the soundness error. So the question is how far can we reduce the number of queries, while ensuring a given level of soundness. And here comes the part that will knock your socks off.
The PCP Theorem
The PCP Theorem states that reading just three bits from the proof suffices, ensuring a soundness error of at most 1/2. 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 3 bits of it, and will accept with probability 1 any correct proof, and reject with probability 1/2 any false claim. The soundness error of 1/2 can be made arbitrarily small by repetition. Sounds surreal, right? Wonders will never cease, especially not in this domain!
PCP stands for Probabilistically Checkable Proof and is the culmination of ingenious contributions from many people in the 80’s and 90’s. It was proven by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 and is considered the crown jewel of complexity theory.
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.
And now that we have seen how using cryptography we can create a setup where the verifier inquires about different bits (to which the prover has committed through a Merkle Tree), and that we can write the proof in a way that very few bit queries are enough to convince the verifier of the statement using the PCP Theorem. We can essentially combine the two: given an instance x and a witness w, using the PCP Theorem the prover creates a proof \pi (which will be not much longer than w itself, just polynomially longer), puts it at the leaves of a Merkle Tree and send the root hash to the verifier.
The verifier (using his randomness) decides which bits to query, and sends them to the prover, to which the prover answers with query results and opening profs, proving that the query results indeed are in agreement with the initial root hash that has been sent. A nice and very succinct proof, as proposed by Kilian. Combining this with ideas for the Fiat-Shamir transform, we can turn the PCP into a non-interactive proof. The corresponding construction in this setting is due to Micali.
A side note: How powerful are PCPs?
As we had seen, interactive proofs (IP) seems to be way more expressive than NP. You might be wondering what about PCP? For this we have to first introduce two parameters, which specify the resources available to the verifier.
We can restrict the verifier in two ways: the amount of randomness r available to him, and the number of bits of the proof that he can query q. Of course these could be given as a function of the size n of the input x (above the randomness was constant 3, hence independent of n). So we should rather denote them by r(n) and q(n). Restricting these two resources has turned out to be the most natural and fertile thing to do.
We denote the corresponding class by PCP(r(n), q(n)). By a result by Babai, Fortnow and Lund we have PCP(poly(n), poly(n)) = NEXPTIME, the class of languages that can be decided by a non-deterministic Turing machine in exponential time. So by the power of randomness one can do with polynomially many queries, rather than exponentially many in the case of NEXPTIME.
A series of several beautiful results lead to the full PCP theorem. NP = PCP(0, poly(n)) is quite clear, as without randomness and polynomially many queries the verifier can just process the whole witness as usual. Allowing logarithmically many coin tosses also does not add anything, as all the outcomes of logarithmically many coin tosses can be processed in polynomial time (there are a total of 2 to the power logarithmically outcomes). So we have NP = PCP(log(n), poly(n)).
Reducing the number of queries q(n) would clearly give an interesting subset of problems, those which can be probabilistically verified by just querying q(n) bits, so only a subset. Now the big surprise is that this is possible for all problems in NP and that it can be done with constantly many queries: NP = PCP(log(n),O(1)). This gives a new and very fruitful characterization of the complexity class NP.
PCPs everywhere
Although mesmerized by the power of the PCP Theorem, you might be wondering if it deserves being talked about at this length in an articles in this domain. After all this is not a post about complexity theory.
It turns out that PCPs are necessary for succinct arguments, as Rothblum and Vadhan answer the question “Are PCPs inherent in efficient arguments?” in the affirmative. They show that every succinct argument for which security is proven using a black-box reduction to a falsifiable assumption contains a PCP in the sense that there is a way to obtain an equivalent PCP from it.
Alternatively, if rather than reducing to a falsifiable assumption in the standard model you have an unconditionally secure succinct argument in the random oracle model, then you can transform it into an interactive oracle proof, an interactive generalization of a PCP. This was shown by Chiesa and Yogev in their paper “Barriers for Succinct Arguments in the Random Oracle Model”. So once you have succinctness you are bound to have a PCPs or its generalization.
A first SNARK
With the idea of the seminal Kilian and Micali papers above, we have in fact outlined the construction of a first SNARK.
With the cryptographic instantiation the resulting proof system is only computationally sound. So it is only secure under the assumption of a computationally bounded prover (in this case we assume the prover cannot find collisions for Hash functions for instance).
Such proof systems are called argument. We have seen that the resulting proof is short. We just have to provide the query results and the Merkle openings, so the proofs are logarithmic in size. Hence shorter than the full witness, i.e. succinct.
Using the idea of a Fiat-Shamir Transform (à la Micali) we can make everything non-interactive. This is hence a Succinct Non-Interactive Argument of Knowledge a.k.a. a SNARK. In theory the resulting SNARK is very good. The proofs are short, the verifier workload is little. However in practice it turns out to be not too efficient. The PCP construction, though explicit and polynomial time, is just to complex. As a remedy, Ishai, Kushilevitz, and Ostrovsky defined Linear PCPs, which combined with homomorphic encryption give very efficient SNARKS. This started the line of research that lead to the famous Groth16 paper. The beginning of a very exciting story, just the right time to stop.
Want to learn more about this? Follow us:
Twitter | Lens Protocol | LinkedIn | Github | Request Audit
