What is Zero-Knowledge Proof

Advanced

8m March 30, 2023

In cryptography, zero-knowledge proof is a method by which one party (the prover) proves to another party (the verifier) that a statement is true without revealing any information in addition to the fact that the statement is true.

Proofs in everyday life are not zero-knowledge. For example, when buyers have to prove that they are over 21 to purchase alcohol, they show a government ID with a birth date. However, this method is flawed because other irrelevant but sensitive information, such as name and address, is disclosed at the same time.

Zero-knowledge proofs are superior as they do not require the prover to reveal details about a statement or how s/he discovers the truth. Suppose Alice is color-bind and cannot distinguish between a blue ball and a red ball. Alice believes that the two balls are the same, but Bob wants to prove to Alice that the two balls are different in a zero-knowledge way. Bob can rely on the following mechanism.

Bob asks Alice to hold the two balls and put her hands behind her back, with the blue ball in her left hand and the red ball in her right hand. Alice can decide whether to switch the balls between her hands or not. Afterwards, Alice shows the balls to Bob again and Bob tells Alice what she did.

Alice: Have I switched the balls?
Bob: Yes.

Alice: Have I switched the balls?
Bob: No, not from last time.

Alice and Bob repeat this process until Alice is convinced that the two balls are indeed different, because otherwise Bob would not be able to tell consistently what Alice did behind her back. In this process, Bob does not need to tell Alice which ball is blue or how he learns about that.

The above example is interactive. While it is easy to understand, it is challenging to implement as a practical solution because it requires two parties to communicate with each other many times before the proof is established.

Researchers have invented non-interactive zero-knowledge proofs to solve the issues. Non-interactive proofs require only one round of communication between the prover and the verifier. The prover inputs the secret information to a special algorithm to compute a zero-knowledge proof. The verifier can then check the proof to ensure the validity of the secret information. Another benefit of non-interactive proofs is that, once a proof is generated, it is available for anyone to verify.

In the blockchain space, zero-knowledge proofs are mostly applied in a rollup scenario, enabling computation to be outsourced while maintaining verifiable results. Off-chain computers execute transactions and then submit results along with proofs that the transactions were executed correctly. This reduces on-chain network congestion and improves transaction speeds.

Zero-knowledge proofs allow the main blockchain to validate off-chain transactions without re-executing them. While zero-knowledge proofs are technically superior, research around the subject is still early. At least a few years are still expected before zero-knowledge proof technology can see practical adoption.