ZKP

In this entry, I focus on explaining What is Zero-Knowledge Proof (ZKP) in the simplest way. Besides, I give many specific examples for you to understand the practicality of ZKP for technology products.

ZKP in a nutshell

ZKP does not mean not revealing information, but revealing as little information as possible about the thing to be proven. With that information, the verifier does not have much knowledge about the thing, they only get a little information (considered zero) about its characteristics.
Through that, the Verifier knows that the statement the Prover is saying is correct.

ZKP properties

• Completeness: The witness given should be so complete and convincing that we do not need further information to verify.

  For example, you enter a private bar, which is only open for a secret group of people who already know one (or more) secret keywords. And you need to know all keywords to prove you are in that group.

• Soundness: The witness must be accurate so that no one but you can fool the verifier.

  This is important information so if you are not in the group, you will not be able to know what the keyword to enter the bar is.

• Zero-Knowledge: This is probably the best part, the verifier won’t know any more information about the secret other than proof that you know the secret.

  To ensure confidentiality, you (Prover) will not say the keyword directly to the guardian(Verifier - who also doesn’t know what the keyword is), instead, the guardian will ask you some questions based on an available checklist around keywords (Proving system), and you must describe it (Witness). Of course, the guardian will only let you in if your answers are correct.

Explaining in other ways

A common example when it comes to the fundamental idea of ​​ZKP is Ali Baba story ¹ by Jean-Jacques Quisquater.
I will try to give even simpler examples so that you can explain ZKP to everyone.

Explaining for infants children

The simplest way to explain this to infants children is the Finding number game (a game I loved to play as a child).

Image by krisetya

Imagine you and your child are playing a game, each person will write natural numbers (not duplicated) in any blank space on the paper until the whole page is covered with numbers. Both will compete to find the numbers in order from smallest to largest. Whoever finds more will be the winner.

At some point, both will struggle because of can’t see where the next number is. Suddenly, you smile and say “Hey, I found out where the number 152 you wrote”. Your child of course won’t believe it. So how can you prove to your child that you actually found that number 152 without pointing out its exact location on the paper?

Very simple, you can describe it. “In the number 152 written, does the number 1 have an underline”, your child doesn’t believe it right away and you continue to take the second evidence: “And the number 5 is the number you corrected from the number 3”. Surely at this point, your child will completely believe that you have found that number 152. You can tease him with a triumphant face later.

Explaining for your friends

Your friend just boasted that he bought one of the NFTs (a type of digital asset) released by iktp in the recent bid. You excitedly said you also bought an NFT from that collection. How can you prove to your friends that you also own it without revealing your wallet address or transaction ID? (Avoid being traced to all assets you own).

Image by Phenomenon Studio

Fortunately, those who own NFTs have the privilege of becoming VIP members to read new articles on iktp. Now you just need to mention the content of those new articles as convincing evidence.

Explaining for colleagues

Let’s say everyone on the team needs to vote for one of the features to sort out which feature to deploy first. Voting is anonymous. You and a colleague really want to know if each other voted for the same feature but don’t want to reveal the selection. Is there any way to know?

Image by Daniel Beere

Yes. Both can specify an ID for each option, for example, F1st, F2nd, F3rd… Each person will bring the ID they have chosen as input to the MD5 hash generator ² and compare the outputs if they match both have chosen the same option. If it is different, it means that you and your colleague have not chosen the same feature but still ensures that no one knows what choice the other person has chosen.

This is also how products know if their users have logged in with the correct password without saving their raw password.

Conclusion

Interactive proofs go beyond the model of classical proofs. If classical proof is a sequential of logical arguments leading to the result to be proven, interactive proof is a process of persuasion through question and answer so that the opposite person is completely convinced that a statement is true.

Zero-Knowledge Proof means giving witness to convince that the statement is true but the person being persuaded still doesn’t know anything about how to prove it!

That was extremely interesting, it makes me think of a big question in life:

“How do we prove that we love someone without saying we love them?”