Understanding Zero-Knowledge Proofs: A Simple and Practical Approach

Author: benlaw.eth

Have you ever read some articles on zero-knowledge proofs but still felt confused? These articles might:

• Use only stories and fairy tales as examples to discuss ZKP, failing to delve into its essence.
• Contain a lot of cryptographic terminology, mathematical formulas, academic papers, etc., making it overly complex for beginners.

This article provides a concise overview of ZKP and further elaborates on its core elements from the perspectives of mathematics, cryptography, and programming.

Proving Color to the Colorblind

How can you prove to a colorblind person that two balls are indeed different colors? It’s actually not complicated:

Have them hold two balls in their hands, turn them behind their back, then randomly choose to swap or not swap the positions of the two balls before showing them to you. You tell them whether the positions of the two balls have changed.

To them, it might seem like you could just guess to complete the proof. However, if this process is repeated thousands of times: if you can always state the correct answer, then the probability of maintaining correctness purely by guessing is negligible. Therefore, this method can be used to prove to the colorblind that the colors of the two balls are indeed different, and that we also have the ability to perceive and distinguish them.

Color Proof

The proof process described above is a typical zero-knowledge proof:

• The verifier cannot gain any knowledge about the colors during the proof process, as they still lack the ability to distinguish colors afterward.
• The verification process is probabilistic rather than deterministic.
• The process is interactive and requires multiple rounds of interaction. However, there are many protocols in zero-knowledge proofs that use advanced techniques to transform the proof process into a non-interactive one.

Proof of Knowledge

We have shared an example of a zero-knowledge proof in the real world, and now let’s look at how to implement zero-knowledge proofs in the binary world.

Arthur is a friend of Elon and knows his phone number. Betty does not know Elon’s number. If Arthur wants to prove to Betty that he knows it without revealing the number, how should he do it?

Proof of Knowledge

An immature solution would be for Elon to publish a hash of his phone number, and Arthur would input the pre-image of the hash into a program, which would compute and check the result. This method has some fatal flaws:

• Based on the hash, Betty could potentially obtain the pre-image through brute force, and the probability of being able to crack it is non-negligible, with the result being almost deterministic.
• Arthur must input the pre-image into the program. If the program runs on Arthur's computer, Betty might question: how do I know you haven't cheated? Your computer might always claim your proof is correct.
• If the program runs on Betty's computer, Arthur would also worry that the information he inputs might be stolen, even if there are no commands in the visible code of the program to steal information.
• Since the program cannot be run in separate environments, this trust issue is difficult to resolve.

Conventional methods have hit a wall here, and it’s time for zero-knowledge proofs to take the stage!

Cryptographic Implementation of Zero-Knowledge Proofs

Here, I will use the Sigma Protocol in zero-knowledge proofs to solve the problem, as it is relatively simple. Additionally, for the sake of brevity and ease of understanding, I will not use strict definitions, terminology, or derivations from cryptography and mathematics.

Core Process

To prove that a person has specific knowledge using zero-knowledge proofs, we take the following approach:

Sigma Protocol

1. Define a finite group of order P and its generator g. We can temporarily ignore what these strange terms mean.
2. According to the above definition, a third party who possesses or has access to the knowledge will encrypt the knowledge (denoted as w) using h = g^w (mod P) and publish h.
3. The prover initiates the zero-knowledge proof process. They generate a random number r, compute a = g^r, and send a to the verifier.
4. The verifier generates a random number e and sends it to the prover.
5. The prover computes z = r + ew and sends it to the verifier.
6. The verifier checks g^z == a·h^e (mod P). If true, then the verifier indeed possesses the knowledge they claim.

Alright, the proof protocol ends here! It’s very brief, but you might still be confused by some of the mathematical operations above. That’s okay; let’s first get a general impression before diving deeper.

Mathematical Principles

The core mathematical principle behind this process is the discrete logarithm problem: when P is a large prime number, it is difficult to find w that satisfies h = g^w (mod P) for a given h. This principle applies to all similar expressions above.

Let’s break it down step by step:

The encrypted knowledge h = g^w (mod P) is hard to brute-force. Due to the nature of the modulo operation, even if it were cracked, it would not yield a unique deterministic solution. This means that for the prover, cheating by brute-forcing to deceive the verifier is not feasible.

Now let’s look at steps 3, 4, and 5 as a whole to understand why they exchange these random numbers:

I. The prover does not want to expose their secret, so they must wrap it in a random number to hide it. The verifier also needs to add some randomness to ensure that the knowledge can be verified by themselves while preventing the prover from cheating, without prying into the prover's secret.

II. If the verifier sends the random number e first (i.e., swapping steps 3 and 4), it is clear that the prover could fabricate a = g^(z)·h^(-e) to deceive the verifier in the final check, even without knowledge. Therefore, the prover must first send a commitment (a = g^r), but not r itself, to avoid scenarios where cheating is possible, while also preventing the verifier from extracting the secret through w = (z - r)/e.

III. After receiving the commitment, the verifier sends the random number e to the prover. Since neither this number nor its derivatives can leak any information from either party, it does not need to be encrypted. The prover then computes z = r + ew and sends z to the verifier. The verifier ultimately determines whether the prover possesses the knowledge by checking g^z = g^(r + ew) = g^r·(g^w)^e = a·h^e.

Through this back-and-forth structure, we gain three properties:

Completeness: The verification passes if and only if the prover inputs the correct knowledge.

Soundness: The verification fails if and only if the prover inputs incorrect knowledge.

Zero-knowledge: The verifier cannot gain any knowledge during the verification process.

These three points are the core characteristics of zero-knowledge proofs. Through mathematics and cryptography, we have constructed a bizarre proof system. Congratulations on making it this far; you should now be able to say that you have officially stepped into the magnificent and mysterious temple of ZKP.

Have fun!

Further Understanding

Simulators and Zero-Knowledge

Now let’s consider some magical scenarios. If a prover has the superpower to predict or tamper with the random numbers generated by the verifier, we call them a simulator.

Simulator vs Verifier

Imagine that the simulator tampered with the verifier's random number e before it was generated, ensuring that it is the value they preset after generation. According to the above II, this ability allows the simulator to fabricate the commitment a to deceive the verifier. Regardless of the simulator's input, the verifier will always conclude that the simulator possesses knowledge, even though they do not.

Clearly, through this thought experiment, we can conclude that the verifier cannot gain any knowledge in this zero-knowledge proof protocol, thus its zero-knowledge property holds:

Zero-knowledge \<== ∀ simulator S, such that S(x) is indistinguishable from the real protocol execution, where S(x): chooses random z and e, letting a = g^z·h^(-e), and the distribution of (a, e, z) is consistent with the real random number environment and satisfies g^z = a·h^e.

Extractors and Soundness

Now let’s imagine another type of superpower—an extractor, who has the ability to reverse time. However, this time the extractor acts as the verifier, facing a normal prover.

At the end of the protocol, the extractor initiates a time rewind, returning to the start of the protocol while holding the previous round's (z, e, a). Now, the protocol is executed again. Since the prover does not have superpowers and cannot time travel, they can only perform deterministic actions on a fixed timeline, generating an identical random number r and commitment a = g^r, while the extractor can generate a new random number e' for the prover.

Prover vs Extractor

Now, the extractor obtains: g^z = a·h^e, g^z' = a·h^e => g^(z-z') = h(e-e') => the encrypted knowledge h = g^((z-z')/(e-e')) => knowledge w = (z-z')/(e-e').

Clearly, as long as the prover truly possesses the knowledge, the extractor can always extract it, thus completeness holds: Completeness \<== ∀ extractor E, for any given h, when possessing (a, e, z), (a, e', z') with e ≠ e', can output w such that (h, w) ∈ R.

Completeness

Completeness does not require any special role to prove, because: g^z = g^(r + ew) = g^r·(g^w)^e = a·h^e.