Two balls and the colour-blind friend
Zero-knowledge proof cryptography is something that I have lots of interest in. It’s a type of cryptography that allow a prover to prove to a verifier that a certain statement is true, without revealing anything else apart from that statement. ZK-SNARKS, a variant of zero-knowledge proofs, is being built into Ethereum (it already exists in zCash). In this blog post I’ll refer to a very simple story that explain how zero-knowledge proofs work.
The reason why this type of cryptography is interesting, is because it will allow us to built completely new types of applications. With most traditional types of cryptography you can only do one of either (a) for something only you know, keep it unknown to others or (b) for something everyone knows, prove that you own it. That is, you can’t keep something private while at the same time publicly prove that you own it. But with zero-knowledge proofs this is possible.
Example use cases
Imagine if government voting was done with zero-knowledge proofs. Then, I could prove to an auditor that I voted on one of the eligible parties, without disclosing what party I voted for.
Imagine if digital passports and border controls was done with zero-knowledge proofs. Then, I could prove to border control that I have eligible criteria to enter a country, without disclosing my full identity.
Two balls and the colour-blind friend
Here’s a simple illustration of how zero-knowledge proofs work, taken from Wikipedia:
Imagine your friend is colour-blind and you have two balls: one red and one green, but otherwise identical. To your friend they seem completely identical and he is skeptical that they are actually distinguishable. You want to prove to him they are in fact differently-coloured, but nothing else, thus you do not reveal which one is the red and which is the green. Here is the proof system. You give the two balls to your friend and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. This ball is then placed behind his back again and then he chooses to reveal just one of the two balls, switching to the other ball with probability 50%. He will ask you, “Did I switch the ball?” This whole procedure is then repeated as often as necessary. By looking at their colours, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same colour and hence indistinguishable, there is no way you could guess correctly with probability higher than 50%. If you and your friend repeat this “proof” multiple times (e.g. 128), your friend should become convinced (“completeness”) that the balls are indeed differently coloured; otherwise, the probability that you would have randomly succeeded at identifying all the switch/non-switches is close to zero (“soundness”).
The above proof is zero-knowledge because the friend never learns which ball is green and which is red, this gains no knowledge about how to distinguish the balls.
Epicenter
I can also recommend this Epicenter podcast if you want to understand more about zero-knowledge proofs: