What Are Zero Knowledge Proofs? Mathematically Speaking
One of the biggest backbones of cryptocurrencies and blockchain technologies are zero knowledge proofs (ZK proofs).
I’m creating a series about core topics around cryptocurrencies from a technical and mathematical standpoint. Here, I want to start with a very beginner friendly explanation of ZK proofs. This topic is often mist-understood because of its complexity, so I will try my best to explain it with simplicity while at the same time helping you understand the mathematical mechanics behind it.
What are ZK proofs?
Essentially, a ZK proof is what validates transactions on most blockchains including Ethereum and Solana.
A ZK proof is essentially a protocol, which allows a prover to prove you, the verifier, a statement about a secret without actually giving away the secret.
Let me illustrate this with an example. I will show you an interactive proof showing that the prover can distinguish between a red and a green ball, whereas, the verifier cannot distinguish them.
The prover wants to show the verifier that they have different colours but does not want him to learn which is red and which is green.
Step 1: The verifier takes the balls, each one in each hand, holds them in front of the prover and then hides them behind his back. Then, with probability 1/2 either swaps them (at most once) or keeps them as they are. Finally, he brings them out in front.
Step 2: The prover has to say the verifier switched them or not.
Step 3: Since they have different colours, the prover can always say whether they were switched or not. But, if they were identical (the verifier is inclined to believe that), the prover would be wrong with probability 1/2.
Finally, to convince the verifier with very high probability, the prover could repeat Step 1 to Step 3 k times to reduce the probability of the prover being successful by chance to a extremely small amount.
So far we merely defined the notion of an interactive proof system, but we need to define what it means for a proof to be zero knowledge. Before we attempt a definition, let us consider an example. Going back to the notion of quadratic residuosity, suppose that x and m are public and Alice knows s such that x = s 2 (mod m). She wants to convince Bob that this is the case. However she prefers
not to reveal s. Can she convince Bob that such an s exist without revealing any information about it? Here is a way to do so:
Putting things into Context
We can apply this protocol for cryptocurrency validation. Lets say, I know a secret number such that if you take the word ‘dog’, add the number to the end, and SHA256 hash it a 100 million times, the output starts with 0x53d00358bb, the verifier can verify the proof far more quickly than it would take for them to run 100 million hashes themselves, and the proof would also not reveal what the secret number is
In the next article, I will show a practical implementation of this concept with more examples.