Zero Knowledge Proof: Next step to Privacy

If you are in blockchain space, you must have heard about Zero-knowledge proof, if not don’t worry. I have tried to cover the basic ground of ZKPs with unadorned examples. No codes, No complex mathematical equations, just a simple story. Sit back and enjoy it!

Contents

• What is ZKP
• Examples
• Interactive and Non-interactive Proofs
• Use cases
• Further Readings

What is Zero-knowledge Proof

The Zero Knowledge Proof ( ZKP) has been around for a while. It has gained huge popularity after its implementation in blockchain space.

“ZKP is a method by which a prover can prove to a verifier that a statement is true without revealing any information other than the validity of the statement”.

The Zero Knowledge Proof consists of 2 words:

• Zero-knowledge: The verifier must have zero knowledge about the statement.
• Proof: The prover can prove to the verifier that statement is correct with very high probability.

The zero-knowledge proof must satisfy 3 properties:

1. Completeness: If the statement is true, the verifier will be convinced by the prover.
2. Soundness: If the statement is false, no prover can convince the verifier that it is true, except with some small probability.
3. Zero-knowledge: If the statement is true, the verifier does not learn anything other than the validity of the statement

Hard to get? This is where we ask the help of almighty "Examples"

Time for Examples

The simplest example of ZKP is where Alice wants to prove to Bob that she possesses a key to a certain room without letting Bob know anything about the key. The 2 most common methods she can do it is

1. Alice can hand over the key to Bob and he uses the key to unlock the room, proving that Alice holds the correct key. You might be wondering, but didn’t Bob get access to the key? Yes, this is proof but not zero-knowledge.
2. Alice can unlock the room fetch an item that Bob knows can only exist in that room. Now Alice has proved to Bob that she knows the key without revealing any other information to Bob. Hence Bob has zero knowledge about the key or the unlock mechanism.

Let's take another very common example to explain Zero-knowledge Proof. Alice and Bob are still with us ;)

Assume Bob is colour blind. Alice has 2 balls; one is red and the other is green but they are completely identical to Bob. Now Alice wants to prove to Bob that these balls are different without letting him know any other details about the balls.

She gives balls to Bob and asks him to hold one ball in each hand behind his back and then he may or may not switch balls. Now Alice has to tell if Bob switched Balls. Alice knows the colours and can clearly tell if Bob has switched hands. Even if 2 balls are identical, Alice has a 50% chance of guessing it right. It might just be a lucky guess.

So Bob asks her to repeat the steps and again Alice gets its right and they do it 100 times in a row. There are very very fewer chances that Alice could have guessed correct 100 times in a row. This convinces Bob that the balls are different.

Now let us verify if this was really a zero-knowledge proof:

Statement: The 2 balls are of a different colour.

Completeness: Since the statement was correct. Alice was able to prove to Bob that balls had different colour

Soundness: If the balls were not identical, there was no way Alice could have guessed it correct 100 times.

Zero-Knowledge: Bob still doesn’t know anything about the actual colour of the balls.

The 2 very important points to be noted here is

• Zero-knowledge proof never gives 100% confirmation. It's about minimising the probability that another party is cheating.
• The example involves multiple interactions between prover and verifier to reduce the chances of cheating. This is called interactive proof.

Non-interactive proofs

The examples above were interactive Zero-knowledge proofs, where prover and verifier have to interact multiple times for decreasing probability of error. More importantly, if Alice has to prove the same to another friend Charlie ( who is also colour blind), Alice has to go all over again. Ahh, we see a problem here! Another big issue with the interactive proof is when all or some interactions are written in a block, the transactions become bulky and grows exponentially. And so we have non-interactive proofs

Non-interactive proofs, the proof consists of a single message sent from prover to verifier. This generally involves a setup phase that generates a common reference string shared between prover and verifier.

Some Non-Interactive Proofs in Blockchain space

The 2 major privacy coins implementing Zero-knowledge proofs are 1. Monero and 2. ZCash. Both use a different mechanism for protecting the privacy of transactions which has evolved over a period of time.

Confidential Transactions (CTs): Monero used CTs (before bulletproofs) which obfuscated the amount transferred in transactions using Pedersen Commitments to the amount. Since amounts were not visible to verifiers, it required the use of range proofs to ensure if transaction inputs are greater than the sum of transaction outputs, and that all transaction values are positive (as transferring negative values would allow the sender to create value out of thin air).

Range Proofs: The range proofs basically is a form of validation that allows anyone to verify that value lies in a given specific range without actually revealing the value. Another example of a real-world application of Range Proofs is Banking system, where you can check for a loan you can get offered by a bank without actually letting the bank know your exact income.

Bulletproofs: The proof size in CTs was linear (1 output = 5KiB then 2 output= 10KiB). This was a big problem as the CTs were consuming lots of space and we already how hard it is to sync blockchains. So in October 2018, Monero hard forked its protocol and reconstructed CTs into a Bulletproofs

Bulletproofs are a new zero-knowledge argument of the knowledge system, to prove that a secret committed value lies in a given interval.”. They are short, non-interactive (using Fiat-Shamir heuristic )proofs that do not require a trusted setup. The proof size is logarithmic. Monero has gained significant decrease in transaction size faster implementing bulletproofs. They also allow the prover to aggregate multiple range proofs for transactions with multiple outputs into a single, short proof. Hence are both time and space-saving.

zk-SNARKs: stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. The Zcash uses a different version of Zero-Knowledge Proof for its Privacy. Implementation of zk-SNARKs requires a trusted setup.

To get the detailed implementation of zk-SNARKs, we would need to have a Masters level understanding of highly complex mathematics, polynomial equations. I shall try to portrait some layman explanation.

It works by breaking the problem into a polynomial of degree n, generally quadratic like

t(x) h(x) = w(x) v(x)

The solution holds true for any value of x. The verifier chooses a secret evaluation point s, and solvers polynomial for s, and checks if equality holds.t(s)h(s) = w(s) v(s)

t(s)h(s) = w(s) v(s)

As we know a polynomial with degree n can have n solutions. It is required that prover does not know the point(s) at which verifier will evaluate the polynomial, else he can create a false proof that is only valid for those points and not at all possible at every point. See, I said you’ll require good Maths here.

Use Cases

Zero-knowledge proofs can have a huge number of real-world use cases related to privacy and scalability

• Anonymous transactions to blockchain like ZCash, Monero provided an increase in user privacy.
• Scaling blockchain applications like Ethereum, where verifier nodes just have to verify the validity of transactions with zero knowledge about sender and receiver, which will lead to scalability in terms of time and space.

Conclusion

Undoubtedly, a zero-knowledge proof is awesome where we need privacy. It has some limitations though, but name a thing without any limitations?

These proofs at the time are complex than normal verification processes but It is soon enough when we shall witness more applications incorporating zero-knowledge proofs that are less complex and can run on low powered devices as well.

Further Readings

• Homegraphic Encryption
• Pairings

Do share your thoughts!