Interactive Zero-knowledge Proof
Zero-knowledge proofs have been widely studied in the blockchain world. Blockchain projects with zero-knowledge proofs focus on a succinct proof and non-interactive proofs, in which the proof can be verified quickly and the proof size is extremely small.
There is another type of zero-knowledge proofs, called inter-active zero-knowledge proofs. Interactive proofs are necessary as most current works integrate an interactive proof with Fiat-Shamir transformation to construct a succinct non-interactive zero-knowledge proof (SNARK). We will talk about the work-flow of designing a SNARK in future blogs.
In interactive zero-knowledge proofs, a prover first claims that it knows a witness that can satisfy a relation, then the prover and the verifier interact with each other for several rounds. At the end of interaction, the verifier outputs accept or reject. In addition, all messages sent by the prover reveal nothing about the witness. In this first blog, we will first give the formal definition of interactive proofs, then give an example to illustrate interactive proofs as shown in Figure 1 .
Informally, an interactive proof with two parties, a prover and a verifier, should satisfy the following properties:
- Completeness. Given a statement, the prover can convince the verifier with a correct witness with probability 1.
- Soundness. Given a statement, a malicious prover can convince the verifier with a false witness with negligible probability (i.e. with a very small probability).
- Zero-knowledge. The proof does not reveal anything except for the validity of the statement, more precisely, it leaks no information about the prover’s witness.
Suppose there are two parties, called Alice and Bob, where Alice acts as a prover and Bob acts as a verifier. Alice would like to show that she has the key to the gate and she does not want to show the key to Bob directly. They can do it as follows:
- First, Bob is at point A and Alice is at point B. Alice can randomly enter the cave from the left (Path A) or the right side (Path B), which means Alice can go to either point C (left) or point D (right).
- Second, Bob walks to point B and randomly lets Alice come out from the left or the right side.
- Finally, Alice responds to Bob and come out from the corresponding side.
In the above example, if Alice has the key to the gate, she can come out from any side, which satisfies completeness. Soundness shows that if Alice does not have the key to the gate, she can come out from corresponding side with probability 1/2. If they execute the following protocol for λ times and Alice has no key to the gate, Alice can pass all tests with probability 1/2λ, which is a negligible probability (close to 0). Finally, the ’zero-knowledge’ shows that Alice reveals nothing about her key to the gate to Bob in communication. The above example is an interactive zero-knowledge proof system, in which two parties need to communicate with information flowing in several rounds. Outside the zero-knowledge domain, interactive protocols are also commonly used in practice.
In next blog, we will present interactive proofs for circuits. Circuits are widely used in building a proving system as it can represent almost all computation tasks with various types of gates. Compiling a computation to a circuit and proving this circuit with zero-knowledge protocol is a general method to build a zero-knowledge proving system.
