Zero-knowledge proof is a way to prove that you have some information or data without ever revealing it. Sounds magical right? Let’s take look at how zero-knowledge proofs work.
History
The history of ZKPs can be traced back to the 1980s, when computer scientists Shafi Goldwasser, Silvio Micali, and Charles Rackoff first proposed the concept in a paper titled "The Knowledge Complexity of Interactive Proof-Systems."
In the following years, several other researchers proposed different variations of zero-knowledge proofs, including "interactive" proofs, where the prover and verifier engage in a back-and-forth dialogue to establish the proof, and "non-interactive" proofs, where the prover sends a single message to the verifier that establishes the proof.
More recently, these concepts have been used to develop zk-SNARKs (zero-knowledge succinct non-interactive arguments of knowledge) and zk-STARKs (zero-knowledge succinct transparent argument of knowledge), which are useful to build applications in Web3.
Intuition
As mentioned before, the crux of ZKPs is that you should be able to prove that you have some information without revealing it.
For example, let’s say you want to work as an assistant to a magician (maybe David Blaine) and his business partner asks you to prove that you know how his trick works so that you can help. But you don’t know if the partner knows the secrets of the trick and you don’t want to reveal them. So what do you do?
You simply perform the trick in front of them which serves as proof that you know the trick, and you have achieved to do this without revealing the secret of the trick.
Technically, this is not entirely accurate because the verifier (partner) asks the questions repeatedly and each question is slightly different, but as intuition, I think this is a good way to see that you can prove some information without ever revealing it.
Deep Dive
Section A: From the white-paper
In this section, I break down the concept from the white paper.
Interactive Turing Machine (ITM)
An ITM consists of an input tape, a work tape, a random tape, one read-only communication tape and one write-only communication tape. Here are the functions of the tapes:
Random tape: Consists of an infinite sequence of bits that can be read from the left to right.
Input tape: Consists of the inputs to the Turing Machine
Work tape: Used for internal computations
Write-only communication tape: write results to other TMs
One read-only communication: read results written by other TMs
Interactive Protocol
Setup
An interactive protocol is an ordered pair of TMs A and B such that A and B have the same input tape, A’s write-only communication tape is B’s read-only communication tape and vice-versa as shown in the figure
Working
The machines take turns being active with the verifier being active first. B will use the input tape, work tape and read-only communication tape, and write the result to its write-only tape.
A will then read from the read-only tape (B’s write-only tape), and writes on its write-only tape.
This interaction can be terminated from either machine by not writing anything during the active stage.
Zero-knowledge protocol definition and example
Consider the diagram below:
It has an additional tape H’ which is a hidden tape that B (the verifier) has access to. You can think of this as additional information that B in addition to the information from the read-only tape.
Then a protocol (A, B) is said to be zero-knowledge on language L if it is impossible to determine in polynomial time about the members of L even with cheating. (i.e. with the additional H’ tape)
Let’s look at an example of this might work with the graph coloring problem:
The problem is formulated as this, given a set of nodes and edges connecting the nodes, we have to choose colors such that no edges connect nodes with the same color.
Now assume A claims that he knows such a configuration, and then the verifier B will repeatedly ask A to reveal an edge’s endpoints. Now if A is randomly guessing, the probability of him guessing incorrectly for a given edge is 1/E. If this process is repeated many times and A gives correct answers, then B can be sure that it is probabilistically very unlikely that A is cheating. And more crucially, A has not revealed the actual configuration of the graph to B.
Section B: Exploring perspectives
Witness, challenge and response
This blog on Ethereum.org, explains how a witness, a challenge and a response are the 3 components of ZKPs
The witness is the secret that is used to prove that the prover has some information. (Think private key)
The challenge is a random question asked by the verifier and asks the prover to answer it.
The response is the answer to the challenge and can be verified by the verifier.
By asking a different question many times, the verifier can be sure that the prover is not randomly guessing and has access to the witness.
The Ali Baba Cave
This is a very famous example given by Jean-Jacques Quisquater and others in their paper "How to Explain Zero-Knowledge Protocols to Your Children".
The basic idea is this:
There is a cave that has two exits E1 and E2. Person A goes into the cave and person B asks A to come out of either E1 or E2. Now, to pass through the cave you need a magic stone. A can either use the magic stone to pass the cave or guess where B might ask A to come out of and enter from the same end. Guessing correctly (and incorrectly) has a probability of 1/2. So if B asks A enough times, the probability that A can correctly guess the end B will choose reduces exponentially. (As it is (1/2)^n for n trials)
If A can come out of the required exit many times, B can be sure that A has the magic stone.
Here,
The Witness is the magic stone.
The Challenge is to come out of E1 or E2 successfully.
The Response is A using the stone and coming out of the required exit.
Properties of ZKPs
Some of the properties of ZKPs are:
Completeness: A ZKP is considered complete if the verifier will always accept a valid proof and reject an invalid proof.
Soundness: A ZKP is considered sound if the verifier will only accept a valid proof.
Zero-knowledge: A ZKP is considered zero-knowledge if the verifier learns nothing beyond the statement being proven
In addition to this, there also are a few more properties which depend on the design of the ZKP such as Verifiable computation, Transparency, Succinctness, Non-interactivity, etc.
Conclusions & Review
ZKPs are useful to prove to a verifier, a piece of information without revealing the information.
Their applications include financial systems, identity verification, voting, data privacy, etc.
Although it is a useful method for building web3 applications, it does have some drawbacks such as being computationally intensive, complex by design, not safe from quantum computing attacks, etc.
That’s it for this issue. I hope you found this article interesting. Until next time!
Resources: