Introduction to ZK Jargon


Part 1: What does it mean to prove?

This article aims to be a gentle introduction to the notions of decision problems, relations, languages and the complexity class. We follow a running example and rephrase it each time we cover a new term.

Decision Problems

In mathematics, a statement is either TRUE or FALSE. However, deciding whether a statement is true or false is not always easy. Consider for example the following statements:

  • Statement 1: the number is even.
  • Statement 2: the number can be factored.

We can quickly check that Statement 1 is TRUE, but what about Statement 2? To our knowledge, the best way to decide Statement 2 is just to try factoring . If we succeed, the statement is TRUE, but we might be trying for a long time, with no guarantee of ever succeeding!

What if we are given additional information? Let’s say we were magically handed (or by luck stumbled upon) the numbers and . We can try to multiply them together and find that indeed . We can now decide Statement 2 ✅.

Notice that with the additional information, we only needed to perform one multiplication; much less work than trying out all the potential factorizations. In a way, this additional information was in fact a proof that Statement 2 is TRUE.

Answer #1 (informal): proving means giving auxiliary information about a statement to decide that it is true.

We can also rephrase this answer in the form of a condition: a provable statement is one that can be easily decided provided the right information. In complexity theory, this corresponds to the class .

Relations

The discussion above is formalised by the notions of relations and languages:

  • A relation is a set of ordered pairs . When talking about relations (provable statements) we refer to the first item, , as an instance, and the second, , as a witness.

Example: factors. Let’s define a relation that we will call . An instance of this relation is an integer, and a witness is an unordered list of integers greater than 1. We will say that the pair is in if and only if contains more than one element and the product of all the elements in is equal to .

For example, the instance has the witness . The instance has multiple witnesses: including , and .

We can now recast Statement 2 in terms of :

  • Statement 2 (with jargon, part 1): there exist a witness such that is in .

As we saw above, finding such a witness ourselves is a lot of work. However, given the candidate witness , we can quickly check that the pair is in .

Languages

Rather than always having to say “the instance has a witness such that ”, we use the shorter form “the instance is satisfiable”. Note that the relation which satisfies isn’t explicitly stated and must be made clear from the context.

We can collect all the satisfiable instances of a relation in a set:

  • the language defined by a relation is the set of all satisfiable instances for . We often write or .

Example: factors. As we have seen, and are in . On the other hand, prime numbers such as or cannot be expressed as a product of integers. Therefore, they are not in .

Once again we can rephrase Statement 2 in terms of the language defined by :

  • Statement 2 (with jargon, part 2): is in .

Answer #2 (same as before, in jargon): proving means giving evidence that an instance is indeed in the language defined by some relation .

More examples. As an exercise, try to cast a Sudoku as a relation and identify the instance, witness and language. What about the relation , defined for some function as all pairs such that ? What happens when we pick to be (i) a polynomial or (ii) a hash function?


Up next: probabilistic and interactive proofs

So far we have only considered the trivial proof system: sending the witness.

In some cases, this is not desirable. Sometimes the witness is private and should remain so. Other times, the witness is just too big to be sent or for the verifier to process. These cases motivate the need for more elaborate (and powerful) proof systems. We discuss these systems more formally in the next article.