<aside> đź’ˇ Project Website: https://nouhailafellahi.github.io/zk-proof-demo/
</aside>
<aside> đź’ˇ GitHub Repository: https://github.com/nouhailafellahi/zk-proof-demo
</aside>
Zero-knowledge proofs emerged from the need to convey characteristics of pieces of information without revealing said information.
For example, convincing a friend that you know their birthday without revealing the date to the friends around you.
A more realistic use for zero-knowledge proofs would be in B2B interactions: Retail company A wants to buy a large dataset of sample customer information from company B in order to better train their AI recommendation algorithm. Company A, however, wants to be certain that the data set meets certain quality standards before buying it.
This can’t be done by letting company A review the dataset to confirm its quality because then they would already have possession of the dataset and would have no incentive to buy/pay for it. A solution to this problem is the use of zero-knowledge proofs.
Through the encryption of the dataset and a back and forth between company A and B using said encrypted set , company A can be convinced of the quality of the product company B is selling to them without jeopardizing company B!
The specific type of proof used in our subject application is called Interactive Zero-Knowledge Proof. They involve multiple rounds of interactions between the prover and verifier. During each round, the verifier subjects the prover to multiple challenges that reinforce the validity of the prover’s claims if answered right, and invalidate their claims if not. This interchange can be repeated as many times as the verifier needs to feel convinced in the soundness of the prover’s claims.
(For reference, in the scenario introduced in the previous paragraph, company A would be the verifier and company B would be the prover. While suitable quality of the subject dataset would be the prover’s (company B) claim that would be assessed by the verifier (company A))
Remember how we said that interactive zero-knowledge proofs consist of rounds of challenges posed by the verifier and answered by the prover? Let’s see what a round of challenges and answers looks like in order to formulate a zero-knowledge proof for 3-colorable graphs.
Let $G$ **be a graph on $n$ number of vertices. Let the set of vertices be