Zero Knowledge Proofs

In this post we’ll explore the very basics of Interactive Zero Knowledge Proof, which you might’ve heard about before, if you’re around the crypto world.

Zero Knowledge Proof is a cryptographic method by which one party, called “the prover”, can prove to another party, called “the verifier”, that certain statements are true without revealing any other information.

Let’s suppose I know a secret that I don’t want to tell anyone, but yet, I want to let them know that it’s true without revealing the details. Does it sounds familiar?

Let’s see a practical use:

I like the voting use case to explain the practicality of Zero Knowledge Proofs. Let’s suppose that I have to vote on a ballot, so I vote. But now, I want to prove to a verifier that I voted without revealing the vote I made. That’s where Zero Knowledge Proofs come in!

The protocol of Interactive Zero Knowledge Proofs has 3 requirements

1. Completeness:

The prover and the verifier are honest and will follow the protocol.

2. Soundness:

If we assume that the prover isn’t honest and doesn’t know a secret and want to convince the verifier that she or he knows the secret, it won’t be possible because the chances of successfully fooling the verifier are too low.

3. Zero-Knowledge

This means that we know that there’s a prover “A” and a verifier “B” and that the prover “A” will prove to the verifier “B” that “A” knows the secret. So “A” can prove to “B” and only “B” that he or she knows a secret. There’s no way for outsiders to be sure about the certainty of the proof.

Strange cave of Ali Baba example:

This is the most common and intuitive example to show Interactive Zero Knowledge Proofs:
Let’s say we have a cave that has a door on the other end and this door only opens when someone knows the secret to open this door. So “Bob” knows the secret to open the door in the cave, and wants to prove to “Alice” that he knows this secret without revealing it to her.

**1) So the first step on the protocol is to put “Bob” inside the cave and he can choose whichever path he wants, in this particular case “A” or “B”. **

Bob chooses a random path and Alice wait outside the cave.**

2) After Bob choosed “A”, Alice enters the cave and ask Bob to come outside appearing from the “B” path.

Now Alice shouts “B” to Bob.

3) Because Bob knows the secret to open the door, he came out for the “B” path and Alice can verify that he actually knows the secret.

Alice sees Bob come out from B path, she is convinced…or not?

4) The problem is that Bob might have luck the first time, he might have chosen the path that Alice asked and so he didn’t need to open the door. So at this point it’s very easy to fool Alice, because there’s a 50% chance that Bob knows the secret. In order to reduce the chance of Alice being fooled by Bob, they repeat the procedure several times. Each time they repeat this process the chances of Bob cheating reduces. For example, if they do it 20 times in a row, Bob chance of successfully anticipating all of Alice’s requests would become vanishingly small (about one in a million).

A side note about the Zero Knowledge requirement of this process is that, Bob proved to Alice and only Alice that he knows the secret. For example, let’s say that an Alice friend “Sarah” was with her at the exit of the cave. Sarah shouldn’t be convinced that Bob knows the secret because they might well agree beforehand on the sequence of A’s and B’s paths that Alice will ask.

Now that we understand the basic concepts behind Interactive Zero Knowledge Proofs, we can see how they are applied to Blockchain.

Non-Interactive Zero Knowledge Proofs

This protocol is also for “secret proving” but with the particularity that it doesn’t require interaction for the prover and the verifier. This protocol is the basics on which the zkSNARKS (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) are build. zKSNARKS are the backbone of the ZCash protocol (a blockchain project based on Zero Knowledge Proof) and a great feature of the next Ethereum release Metropolis.

A more practical approach of use is in a Blockchain like Ethereum:

Let’s suppose I have a company and I put 10 ETH in a smart contract that has a logic that makes an interactor of the contract to do certain confidential tasks, and when they are completed successfully, the smart contract releases the 10 ETH to the interactor.
I don’t want these tasks to be known by everyone as it may be harmful for my company. ZkSNARKS will provide the necessary proofs that those tasks have been completed successfully without revealing what they are. This means that I can prove my “honesty” as a company if I claim that certain tasks were completed, or not, without revealing them.

ZKSnarks will provide a layer of privacy to the operations inside Ethereum blockchain, we have to wait and see how this develops, but no doubt that this will be a great addition to the Ethereum blockchain.