Maths & Logic for Zero-knowledge Proofs (simplified) — Part 2

A primer for understanding the mathematical insights used to build ZK.

The purpose of this series is to follow the trail of insights that led to the development of various zero-knowledge protocols. The series will focus on real-life applications and implications of these protocols.

Before reading this article, go to part 1.

Questions to Answer

- How do we measure the efficiency of a problem or algorithm? (Read 1 and 3)

- How can inefficient problems actually help us? (Read 2)

1. Computational Complexity

In the last post, we said that the three criteria we care about when designing a verification process (or proof system) are: completeness, soundness and efficiency.

Let’s dig a little deeper into this concept of efficiency.

Last time we said that a verification function is said to be efficient if its running time is “fast” (i.e. function stops after a reasonable number of steps = polynomial(|x|) steps, where |x| is the length of input). Now, all mathematical problems can be categorised as per how “easy (fast)” or “hard (slow)” it is to solve and verify them. This categorisation is called computational complexity.

Let’s imagine there is a picture jigsaw puzzle with lots of pieces, and you have two functions: one to solve the puzzle (put the pieces together) and the other to verify that the solution is correct (picture on the solved puzzle matches the one on the box). We can categorise the different types of jigsaw puzzles as per the following computation complexity:

P (Polynomial):

Both solving and verification is easy. With the given number of puzzle pieces (n), you are easily able to put the pieces together as well as verify the picture. Both actions takes you maximum of polynomial(n) steps.

NP (Non-deterministic Polynomial):

Solving is hard, but verification is easy. Think of a super big jigsaw puzzle that’s hard to solve. But if someone tells you where all the pieces go, you can compare the solved puzzle with the picture on the box and verify if they’re right pretty fast (polynomial(n)). But if you tried to solve it yourself, it would have taken you a very very long time (super-polynomial(n)).

NP-Complete :

An unique type of NP puzzle to which any other NP puzzle can be converted into within polynomial(n) time.Which means, if you are able to solve this, then any other hard NP puzzle can be converted into this NP-Complete puzzle and solved.

PPT (Probabilistic Polynomial):

Now that we realise that there are categories of puzzles where solving is hard, we need to figure out new ways to solve rather than going through all the possible combinations of the puzzle pieces and verifying it (brute-force).

One way to do this is to add a little bit of randomness ingenuity while solving the problem. This randomness allows us to quickly solve problems which otherwise would have been hard.

Let’s take a new example to understand this. Say we have a number N and we are trying to figure out if it is a prime number (can be divided only by itself and 1). If we wanted to brute-force it, we could take every number from 1 to N and see if N is divisible by it or not. But doing this would take ridiculously long time if N is a very large number. Instead, we can introduce some randomness and get a probabilistically accurate answer.

1. Select a random number R which is between 1 and N-1.
2. Now plug in the above values in the formula

Repeat steps 1~2 multiple times (say 10 times).

4. Checking the Result: If, for each of the 10 repetitions, the answer to above formula was 1, then you can say “N is probably prime” (thanks to Fermat’s Little Theorem). Since you are only checking the result for some values of R, you can only say that you probably have the right answer. You can increase your probability by increasing the number of repetitions.

This way you can guess and solve the problem in polynomial time, without actually solving the problem.

BPP (Bounded Probabilistic Polynomial):

Let’s expand the problem of finding if N is a prime number. Suppose we have 200 numbers and we need to check each number for its primality. If using the above formula, we succeed more than 1/2 of the times (i.e. we guess correctly for more than 100 numbers), our formula is BPP. We allow ourselves some room for error (less than 1/2), but in exchange, we are getting a fast (polynomial time) formula that is correct most of the time.

2. Why computational complexity is relevant

But WHY do we care about the complexity of solving and verifying a problem?

Insight: The verification procedure is “easy” (i.e., polynomial-time), whereas coming up with proofs may be “difficult” [1]. This asymmetry allows us to design zero-knowledge protocols.

3. Examples of computational complexity

Let’s look at 3 examples of mathematical problems and check their computational complexity.

1. Boolean Satisfiability (SAT) : Imagine you have 10 switches and these are connected to 5 light bulbs. You also have some rules like “Switch A and B must be ON for Light bulb 1 to be ON” , “If Switch C is OFF, then Switch D must be ON”, etc. Boolean Satisfiability problem tries to find a combination of switches, so that all the 5 light bulbs can be turned ON.

Source [2] + Personal notes

2. Linear Equations (LIN) : Any problem where you’re trying to find the missing number(s) that makes both sides of the equation balance out. For example, 2x + 3 = 9.

Source [2] + Personal notes

3. Quadratic Residuosity (QR) : Find quadratic residue of N = 7.

For i = 1 to 6, calculate i² mod N.

i = 1, 1² mod 7 = 1

i = 2, 2² mod 7 = 4

i = 3, 3² mod 7 = 2

i = 4, 4² mod 7 = 2

i = 5, 5² mod 7 = 4

i = 6, 6² mod 7 = 1

1, 2, 4 are residue and 3, 5, 6 are non-residue of N = 7.

Source [2] + Personal notes

Here is how the above three problems fare on computational complexity:

Source [2] + personal notes

But what happens when even the verification process becomes hard?

Find out answer in part 3 which introduces Interactive Proofs.

Sources :

[1] Goldreich, O. (2001, January 1). Foundations of Cryptography: Basic Tools.

[2] The 9th BIU Winter School on Cryptography | BIU Cyber Center. (2018, August 5). The 9th BIU Winter School on Cryptography | BIU Cyber Center. https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/