ZK Fundamentals: What is a proof?

This is the first 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

We are starting a new blog series where we will explore zero knowledge proofs and related notions.

Rather than keeping the exposition at a leisure and superficial level, we will try to dive deep and get a thorough understanding of the concepts involved. You might have read about the Ali Baba cave, “Where is Waldo/Wally”, and the “colorblind friend”. If not, this might be great places to start:

📙 Quisquater, JJ. et al. (1990). How to Explain Zero-Knowledge Protocols to Your Children. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89

📙 Murtagh, “Where’s Waldo? How to Mathematically Prove You Found Him without Revealing Where He Is”. Scientific American

These are wonderful examples capturing the main ideas and important aspects involved in ZK. If these do not allay your thirst and you feel you want to know more, well then welcome — you’ve come to the right place!

Read the masters!

You often hear the advice to read the masters. This applies here too (maybe with the difference that “read” has to be augmented by “watch and listen”, as there is also great audio and video content on the topic).

If you are looking for the original articles and books on this subject, you can find a nice collection here:

📙 Zero Knowledge Canon, Part 1 & 2

Be advised however, that it is a very long (i.e. think of classic in the vein of a Proust novel, but rest assured it won’t be lost time), still ongoing (you won’t be alone in case you feel overwhelmed by the sheer volume of recent breakthrough results in the field) and very exciting journey.

So without further ado, let’s start!

What is a proof?

Before talking about our protagonist, zero-knowledge proofs, we will start by formalizing what we mean by a proof.

The notion of a proof (just as the notion of a computation) goes back at least to antiquity — think Euclid. We have an intuitive idea what we mean by it, but capturing that intuition and formalizing it is difficult.

The aim is to convince someone about the truth of a given statement. It could be a statement like “17 is a prime number”, it could also be about a computation, like “3+5=8”, i.e., for the computation addition on input 3 and 5 the output is 8.

In any case, a first step of the formalization would be to rephrase the statement in terms of set membership. We can for instance form the set
P R I M E S = {2, 3, 5, 7, 11, …} of all prime numbers. The statement above can then be rephrased as 8 ∈ P R I M E S.

For the addition example, we just form the set of all possible right addition operations (say in the integers), i.e., we form the set of all triples of integers (a, b, c) such that a + b = c:

A D D = {(a, b, c) ∈ ℤ³ | a + b = c }.

The statement above then turns into (3, 5, 8) ∈ A D D.

Understanding membership in the set is then equivalent to verifying the truth of the statement or the computation. Such a given set is called a Language L.

Mind your Language

The question of how computationally difficult it is to decide membership (x ∈ L) depends a lot on the language; understanding different classes of languages and their relation is basically what complexity theory is about (there is a whole hierarchy of languages).

Computation and difficulty of computation are two further notions that we would now need to formalize. We will leave the notion of a computation a bit vague. You can think of an algorithm, or a Turing machine.

The difficulty of a computation is the number of basic steps the algorithm does (moves of the Turing machine) or the time needed. This is of course a function of the size of the input — it can be anticipated that deciding primality for a few digit number will be easier then for a number in cryptographic range.

The difficulty is given by the dependence of the number of computational steps of the fastest algorithm as a function of the input size. Here the input size is the size of the representation of the input. In the case of integers it would for instance be the number of digits in its representation (so basically the logarithm of the number).

Let us just remark that it is crucial how you represent the input (representing numbers in terms of their factors, factorization becomes trivial for instance). You might have seen the expression 1^λ in some cryptography papers. Here λ is the security parameter and the notation indicates that this input should be written in base 1 representation, i.e., as many 1’s as λ. So it is a way to express that complexity is expressed as a function of λ, rather than a function of its representation, i.e. its logarithm.

The class of languages where membership can be decided in a number of steps which is expressed as a polynomial in the input size is denoted by P (stands for polynomial time). These are in some sense easy problems. They have efficient, polynomial time solutions. Addition above falls into this class. Addition as learned in primary school proceeds digit by digit and the number of steps is hence a linear function (i.e. a polynomial) in the size of (a, b, c) (total number of digits). To decide if P R I M E S is in P (can we decide primality in time polynomial in the size of the number) is a much more difficult problem, resolved positively only around 20 years ago by Agrawal, Kayal and Saxena.

Let us also remark that some languages are undecidable. For such a language there is no algorithm that is ensured to terminate and decide membership in the language. An example would for instance be the language consisting of representations of all polynomial equations over the integers that have a solution. This is known as Hilbert’s 10th problem, or the Matiyasevich–Robinson–Davis–Putnam Theorem.

The class N P

Coming back to proofs: when it comes to proving a statement, the situation is slightly different. We don’t want to decide in an efficient manner if an element is a member of a language, but we want to prove it to someone in an efficient way.

Deciding that it is a member might be difficult, but to reveal this fact to another party could be easy. Consider for instance the problem of graph coloring: Given a graph with n vertices and a certain number of colors, say 3 for simplicity, is it possible to assign colors to the vertices in such a way that adjacent vertices (vertices connected by an edge) have different colors.

It is not known if this can be decided in an efficient way, i.e. if the language of 3-colorable graphs is in P. However, if you want to convince someone that a graph is 3-colorable, this is easy to do by just providing a proper coloring, which the other party can efficiently check (just check if all adjacent vertices are assigned different colors).

3-coloring of a graph (source: Wikipedia)

Note that finding the coloring in the first place might have been difficult, but checking one is not. The class of such problems (languages) is called
N P, nondeterministic polynomial time. So a language L is in N P if given x we can prove to another party that x ∈ L in polynomial time by providing a “proof” (in the example above a coloring). This proof is called a witness.

Clearly such a proof can only have size polynomial in the size of x, as otherwise even just reading the proof would not be possible for the other party in polynomial time. So if you want to see the formal definition: a language L is in N P if there exists a language R in P consisting of encoded claim-proof pairs (x, w), such that x ∈ L if and only if there exists a w (of size polynomial in the size of x) such that (x, w) ∈ R.

The class N P is hence the class of problems that can be efficiently verified. Clearly P ⊆ N P: if it can be decided if x ∈ P efficiently, we can leave that task to the verifier. Forget about w (don’t provide a proof) and let L = R (verification is done by just letting the verifier decide by itself).

The converse inclusion is not so clear and boils down to the question: Can every problem that is verified quickly also be decided quickly?

This forms one of the biggest open problems in computer science and the Clay Foundation offers a $1.000.000 prize to whoever can solve it: P vs NP (you might especially want to check out the article by Cook describing the problem).

Source: XKCD

The 3-coloring problem we mentioned above is in fact a particular problem in N P: it is N P complete. So any other problem in the class N P can be reduced (efficiently) to an instance of 3-coloring and hence resolving 3-coloring resolves all other problems in the class N P. We will come back to this later on.

Each language in N P has an efficient verification procedure, whereas providing a proof might not be easy. So the burden of proof lies with the party making the claim, and this burden might be much heavier than the verification of the proof.

Preview: Interactive Proofs

The notion of proof as we know it mathematically or as described above using the class N P is very static in nature. We read Euclid’s proof from his Elements and convince ourselves of the truth of the statement. Or the party making the claim (let’s call it the prover) provides a proof, sends it to the other party (let’s call it the verifier) and the verifier convinces itself of the correctness with an efficient verification method. There is not much interaction between Euclid and us, or between the prover and the verifier. This does not, however, capture another common more dynamic interpretation of a proof.

When you make a claim (say in a discussion, in court or in a Ph.D. thesis), it is subjected to detailed examination and you have to defend it against your adversaries. If you stand up under all the scrutiny and satisfiably respond to all challenges, you will have convinced the other party of your claim. This also agrees with the latin root of proof, namely probare, meaning to test or to probe. Rather than a static object, such a proof is a dynamic/interactive process.

This idea of a proof is captured by Interactive Proofs, introduced in 1985 by Shafi Goldwasser, Silvio Micali, Charles Rackoff (The knowledge complexity of interactive proof-systems) and independently by László Babai (Trading group theory for randomness). In interactive proof systems there are two parties, a prover and a verifier, interacting through message exchanges, to decide if a given element x is in a language L.

A more formal definition and further details are to follow. However for some suspense and a cliffhanger, let’s stop at this point. Next time we will plunge directly into interactive proofs.

Want to learn more about Veridise?

Twitter | Lens Protocol | LinkedIn | Github | Request Audit