Beginners Guide to Zero Knowledge Proofs

In today era, secure communication and privacy are more important than ever. Keeping our communication secure is done with this thing called ‘Cryptography’. Basically some smart calculations with prime numbers that mean we can secure and verify things easily, but it’s hard for a bad actor to come and steal the information.

As bad actors become more and more complex, so does the underlying Cryptography that keeps us all safe. One important and recent discovery in Cryptograhy is that of a Zero Knowledge Proof.

Well what is that?

A Zero Knowledge Proof basically means that I can prove something (proof) without giving away any information about what that thing is (zero knowledge).

A zero-knowledge proof is where a prover (Alice) can prove that she knows information x to a verifier (Bob) without communicating any other information to Bob other than the fact that she knows x.

Now this might not sound very cool, but it is!

You’ve probably heard words like blockchain and cryptocurrency recently. Zero Knowledge Proofs can be used in these things to provide complete anonymous transactions.

What happens in a blockchain is that each transaction is recorded and added to the end of the chain. What ZKP’s allow us to do is to have this information be completely anonymous. It can still be looked at and verified by anyone, but we get Zero Knowledge about who is doing what.

The classic example of a ZKP is the cave example. Consider a circular cave with a door in the middle.

Cave Example

Now lets say I want the key to the cave. I want to be able to go all the way round this circle.

My friend Tash has knows the code to get through the door. She can go all the way round the cave.

I want to buy this code from her, but I can’t be sure that she knows it!

So we set up a Zero Knowledge Proof. I wait outside the cave, and Tash goes in. Importantly, I don’t see which way Tash goes inside the cave.

I then call out to her and ask her to come out on side A.

Now if Tash knows the code to get through the door, she can come out side A if she went in though side A or side B. But if she doesn’t know the code, she will have to come out from the side that she came.

So let’s say she doesn’t know the code but luckily picks the side of the cave that I chose. She has a 50% chance of picking the correct way just by guessing. This isn’t great odds for us because we need to be certain that Tash knows the code before we pay her for it.

To be more certain that Tash isn’t just lucky but does in fact know the code, we repeat the experiment. We keep going until I can be almost certain that Tash is telling the truth that she knows the code.

If we do the experiment again and she manages to pick the pick the correct side again. We can be more confident that she knows the code.

If Tash manages to pick the right way 10 times in a row then I know she is telling the true with probability. $1-0.5^{10} = 1 - 0.000977 = 99.90\%$

So after 10 correct guesses we can be pretty sure she is telling the truth. I can be sure she knows the key and I can then purchase it from her.

ZKP Principles

There are three main prinicples that underly a ZKP.

• Completenes
• Soundnes
• Zero-knowledgeness

If we use the example of Tash and the secret code above, we can illustrate these principles.

Completeness means that I can be sure that Tash knows the secret code.

Soundness means that Tash can only convice me she knows the code if she is telling the truth. She couldn’t convince me if she didn’t know the code.

And Zero-Knowledgeness which means that I gain Zero Knowledge about the code, only information that Tash knows the code.

Applications

Everything on a blockchain is public. Anyone can see what is on there.

For example if I buy a bitcoin, you can go onto the blockchain and see who I purchased my bitcoin from.

Not everything needs to be public though, some things are better in private.

ZKP’s allow things to be anonymous because now I can Prove what you did, while having Zero Knowledge of your identity.

Voting Systems

One cool use case of blockchains is in voting systems. Blockchains can keep unchanging, permanent, public records of who cast each vote and when.

What if we wanted to keep the information about who voted anonymous? This is where we would use a ZKP.

Votes can still be verified and are still unchanging, but using a ZKP we can verify that someone voted without giving away their identity.

Transactions

The main way blockchains are used at the moment is for crypto currency, and some currencies are designed for anonymity.

These currencies use ZKP’s to keep the identities of these people private.

What we can do with ZKP’s is prove that a transaction is valid without knowing any information about the parties involved.

One such example of this is a currency called ZCash which you can read about here - https://z.cash/.

Conclusion

ZKP’s will fundementally change the way blockchains work. Being able to keep things on a blockchain verifiable and yet private opens up many more use cases, and many that we are not aware of yet.

The blockchain and cryptography space is one that is very exciting and I am looking forward to how these technologies will change our world for the better.

Useful Sources

Zero-knowledge proof https://en.wikipedia.org/wiki/Zero-knowledge_proof

Zero Knowledge Proofs: An illustrated primer https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

What Are Zero-Knowledge Proofs? Complete Beginner’s Guide https://blockonomi.com/zero-knowledge-proofs/

Example of A Good Zero Knowledge Proof https://101blockchains.com/zero-knowledge-proof-example/

What are Zero Knowledge Proofs? https://decrypt.co/resources/zero-knowledge-proofs-explained-learn-guide

3 Real World Applications of Zero Knowledge Proofs https://www.coinbureau.com/adoption/applications-zero-knowledge-proofs/

Anonymity in blockchain part 2: zk-snarks https://medium.com/newtown-partners/anonymity-in-blockchain-part-2-zk-snarks-df0cf0a0337b

Privacy Coins and zk-SNARKs: How Do They Work? https://decrypt.co/resources/privacy-coins-and-zk-snarks-how-do-they-work