A non-zero knowledge article about zero knowledge proofs
In the world of cryptocurrencies, there has been a long standing tension between law enforcers/ regulators and financial institutions/users over the pseudonymity of user addresses. Law enforcers want more transparency about contents of the blockchain ledgers (transactions) to deter illicit activity, whereas individuals and financial institutions want more privacy.
One of the solutions to this is a zero knowledge proof (ZKP).
“A zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.”
In essence, we have a prover and a verifier, and a conversation takes place between them where the prover proves a statement to the verifier without revealing anything about the statement.
We will show some examples of ZKPs without going into details about blockchains and cryptocurrencies. We will cover the application of ZKPs to crypto in a later article.
Examples
Let us go through some simple (and mathematical) examples:
- Suppose the verifier (V) is a senior member of a university and the prover (P) is a junior professor and both are number theorists. P claims to have proved the elusive Riemann Hypothesis (R.H.), and needs to convince V of the same to get tenure (a full-time job) at the university. However, out of fear of V stealing the credit of the proof, P will want a certain degree of security. ZKP guarantees this, so that P can prove R.H. to V without giving her any hints about the steps of the proof.
- Suppose P has solved a Sudoku puzzle, and she wants to convince V without giving her hints on how to solve the puzzle.
What kind of statements have a zero-knowledge proof?
It turns out that every statement which has a proof, has a ZKP!
Let us briefly explain what zero-knowledge means more concretely.
Something is zero knowledge if someone else could’ve generated the same conversation between the prover and the verifier, this implies nothing is learnt about the actual statement from the prover.
The 3-colouring problem
Now let us take an interactive example and showcase construction of a zero-knowledge proof.
Consider the statement below:
We want to prove that a particular map can be coloured with 3 colours.
A normal proof is easy by giving an example of a map which can be coloured with 3 colours, and colouring it. How do we construct a ZKP to ensure that V doesn’t know how P colours the map?
Think of the map below. If we wanted a normal proof to show that this can be coloured with 3 colours, we could easily colour it and show that it’s possible.
Now suppose P puts the colours in envelopes. Each envelope is a commitment or a promise. The promise also includes, say, the fact that the map is coloured using only the colours R, G and B. This is easy to check, and if V sees that any envelope has a colour other than R, G, B, she can discard the proof.
Suppose we now hide the colours and number each country in a map with a number i. Also, the envelope Ei contains the true colour of country i.
The interactive proof
The proof proceeds as follows:
- At each turn, V chooses a pair of neighbouring countries and challenges P to open envelopes of the corresponding pair of countries.
- If V sees either a colour outside RGB, or two envelopes having the same colour, then she discards the proof.
- If V sees the two envelopes having different colours, then this could’ve happened because P is cheating or because P actually has the true 3-colouring of the graph.
- Now we need to find the probability that P is not truthful in a given round. This can be done by converting the map to a graph (countries are vertices and bordering countries share an edge).
- We see the graph form of the map below. Here opening envelopes is equivalent to selecting an edge and checking colours of the two vertices connected by that edge
- Now the probability of P cheating and V detecting it is 1/E where E is the number of edges in the graph. (This is because if P is cheating, there is at least one edge with two nodes having the same colour. Probability of picking this edge is 1/E). Here E = 8, hence probability is ⅛.
- Now there’s one more detail which is very important. After every verification step, P recolours the map in such a way that the 3-colouring is still valid, but the colour assignments are changed.
Claim: If P has any one 3-colouring of a map, she automatically has 6.
This is because she can change the assignments in 3! (factorial) ways to get 6 total assignments (i.e permutation) - At each round, P randomly picks one of the 6 patterns, and then V starts the challenge. This doesn’t change the fact that the 3-colouring is still valid. Also, revealing two colours of the map in a particular assignment does not reveal any detail about the particular 3-colouring. Hence during each step of V, she not only sees two different colours, she sees two random different colours. This ensures that no knowledge is leaked about the proof during verification.
- Now V can repeat that as long as she likes, till she’s convinced (probabilistically) that P has the actual 3-colouring. The probability of P having successfully cheated at each verification step is (1–⅛) = ⅞ . Hence to reduce the chances of cheating to say 10%, V needs to repeat this step 17 times.
- After 50 rounds of verification, the chances of the proof being valid is 99.9%!
How do we present ZKP for more complex mathematical statements? Actually there’s a simple and efficient way to convert any formal mathematical statement (true or false) to a map!
Interested readers can check out the paper here: The complexity of theorem-proving procedures
That brings us to the end of this blog post, and I hope I have been able to impart non-zero knowledge about zero-knowledge proofs through this article :)
