How to build a trusted decentralised system without sharing Information?
How to build a trusted decentralised system without sharing Information?
Zero Knowledge Proofs and zkSnarks
In this post we will discuss one of the various ways to build “trustless” applications of massive scale.
Let’s learn about Zero Knowledge proofs in this post and in the next one we will learn about zk-SNARKs.
Zero-knowledge proofs involve two parties: a prover and a verifier. The prover makes an assertion that his or her proof is valid, which the verifier must approve, without the prover leaking any “knowledge” other than the assertion itself.
The “prover” want to prove the knowledge of a solution to a specific problem(or truth of a statement), without leaking any knowledge of the solution itself to the “verifier”, who wants to be reassured that the prover actually does know the solution(or that the statement is true).
Three properties of Zero-knowledge proofs -
Completeness: If statement is true, the verifier would be convinced of the truth of statement by the prover.
Soundness: The prover can only convince the verifier of the truth of the statement if that statement itself is actually true, except with some very small probability.
Zero-Knowledge: The verifier does not know any knowledge(zero knowledge) of the prover’s statement or solution that, other than the truth of the statement.
One of the first such valid general zero-knowledge proof systems was proposed by Goldreich, Micali, and Widgerson, specifically to verify that a prover knew the 3-coloring of a graph.
The 3-Coloring graph problem is an NP-Complete problem stated as follows:
“Given a graph G, can you color the nodes with <3 colors such that for every edge {u, v} we have f(u) =/= f(v)?”
In this zero-knowledge proof system, the prover wants to prove to the verifier that he or she knows the 3-coloring of a given graph to a verifier, without revealing to the verifier the actual 3-coloring solution.
Thus, the z-k proof system works in the following way:
The provers covers each vertex of a 3-coloring solution of the graph such that it is not observable to the verifier.
The verifier randomly chooses an edge of the graph and the prover reveals the two vertices of the chosen edge. The prover shows that the two vertices are of a different color. If the two vertices are of the same color, we know that the prover is dishonest and does not have the solution. If the two vertices are of different color, the verifier has some(but not full) confidence that the prover is telling the truth. We note that the prover has (E-1)/E probability of cheating, where E is the number of edges in the graph. Then we continue to the next step.
The prover now covers all vertices of the graph again, and randomly switches the ordering of the three colors in the prover’s solution. Again, the verifier then chooses a random edge to check that the edge is valid(the two vertices are of different colors). Although the prover could be cheating again, we see that now the probability that the prover successfully cheated in both the rounds is ((𝐸 − 1)/𝐸) ∗ ((𝐸 − 1)/𝐸) = ((𝐸 − 1)/𝐸)^2, which is lower than the previous round.
After repeating this process for multiple n rounds, we can lower the probability that the prover can cheat the verifier, to a negligible value.
Probability of Prover Cheating: ((E-1)/E)^n .
Reference - An Exploration of Zero-Knowledge Proofs and zk-SNARKs
Please feel free to reach out to me if you need help with building large scale distributed systems or data engineering solutions at your organisation, I would be more than happy to help.
If you are liking my articles and want me to write more then feel free to buy me a coffee! 😁
I hope that you enjoyed this read, if so then please share this article with your friends, let’s build a solid community. I will be back next week with another well thought/researched article delivered straight in your inbox. See you!
You can connect with me on Twitter.