Proving systems

https://www.zkcamp.xyz/blog/information-theory

The Evolution of Proof Systems

Now that you have a basic vocabulary of proof systems, let’s take a look at how they’ve evolved over the last 30 years. We’ll use a classic computer science problem, the graph coloring problem, to understand how a person (i.e., the prover) would prove their solution to another person (i.e., the verifier) using each system.

The graph coloring problem is pretty straightforward. Given an undirected graph, the objective is to assign colors to its vertices such that no two adjacent vertices share the same color.

Nondeterministic Polynomial-time (“NP”)

• First up, let’s take a look at the classic mathematical proof known as “nondeterministic polynomial-time” (NP).

• If a problem is NP, it means a polynomial-time algorithm or proof system exists that can check if the efficient solution is correct.

• In other words, NP defines the set of problems for which efficient solutions exist, and proof systems provide us with a framework for checking the validity of solutions for such problems.

But let’s see that in action. How would we generate an NP proof for the graph coloring problem?

In this case, the prover simply provides a potential coloring assignment for the graph, and the verifier checks its validity by verifying all the vertices and ensuring no two adjacent vertices have the same color. That’s it!

Interactive Proof (IP)

In 1985, Goldweisser and Micali introduced a revolutionary idea: a “prover” and “verifier” can interact to verify the validity of a statement. This idea of an interactive proof (IP) was so influential that, decades later, they won the Turing Award (2012).

It’s pretty simple. First, the prover tries to convince the verifier of the correctness of a statement. The verifier challenges the prover with a series of “random” questions. The prover responds. This happens for many rounds until the verifier is convinced that the prover’s statement is true.

Most importantly, IP lets us use probabilistic verification. For instance, over many rounds, the prover can convince the verifier with a high probability that she is being honest. So, IP is probabilistic, as opposed to a classical mathematical proof, which is deterministic.

Probabilistic Checkable Proofs (PCP)

• A probabilistic checkable proof (PCP) is another evolution of the classical NP proof system. The key difference? It isn’t interactive.

• Instead, with PCP, a proof is transformed into a fixed-size format called a "proof transcript." The verifier can randomly query a small number of bits in the transcript to verify the proof.

• A “random oracle” gives PCP the ability to query the proof transcript randomly! That way, the prover can’t predict queries ahead of time. In the case of PCPs, when we say we have access to a “random oracle”, it means we have access to the proof transcript and a source of randomness such that the verifier can access random parts of the proof transcript.

• Overall, PCPs are pedagogically useful — but they aren’t efficient in practice because the proofs are large and query complexity is high.

So how would we generate a PCP proof for the Graph Coloring problem?

The prover constructs a proof transcript that encodes the coloring assignment. The verifier queries for the vertices of the graph using the randomness provided by the oracle, and gets access to the color at those vertices via the oracle. Based on the results of the queries, the verifier can choose to either accept or not accept. Note that there is NO interaction in this case. The prover simply generates the proof transcript once, and the verifier uses random queries via the oracle to validate the proof.

Interactive Oracle Proof (IOP)