Zero-Knowledge Proofs: Proving Secrets Using Mathematics

This article provides a comprehensive overview of zero-knowledge proofs (ZKPs), a cryptographic method that enables one party to prove to another that they know a specific piece of information without revealing the information itself. You will learn the core rules that govern these proofs, the three-step interaction required to execute them, and the exact mathematical principles—specifically modular arithmetic and blinding factors—that secure the secret while proving its existence.

What is a Zero-Knowledge Proof?

A zero-knowledge proof involves two parties: the Prover (who possesses a secret) and the Verifier (who wants to confirm the Prover has the secret). To be considered a valid zero-knowledge proof, the protocol must satisfy three strict criteria:

  1. Completeness: If the statement is true and both parties follow the rules, the Verifier will be convinced.
  2. Soundness: If the statement is false, a dishonest Prover cannot convince the Verifier that it is true, except with an infinitesimally small probability.
  3. Zero-Knowledge: The Verifier learns nothing about the secret itself, other than the fact that the Prover knows it.

The Three-Step Protocol

Zero-knowledge proofs rely on a mathematical structure called a "Sigma Protocol," which consists of three steps:

  • Commitment: The Prover locks in a random mathematical value related to the secret and sends it to the Verifier.
  • Challenge: The Verifier picks a random question (a number) and sends it to the Prover.
  • Response: The Prover uses both their secret and the random value from the Commitment step to answer the Challenge. The Verifier checks the math to confirm validity.

The Mathematics Behind the Proof

ZKPs rely on one-way functions—mathematical operations that are easy to calculate in one direction but practically impossible to reverse. A common tool for this is modular arithmetic (often called "clock math," where numbers wrap around after reaching a certain value, known as the modulus) combined with the Discrete Logarithm Problem.

Here is a simplified breakdown of the Schnorr Protocol, a classic mathematical ZKP.

1. The Setup

Everyone agrees on two public numbers: a prime number \(p\) (the modulus) and a base number \(g\) (the generator).

The Prover has a secret number, \(x\). The Prover calculates a public value, \(y\), using the following formula:

\[y = g^x \pmod p\]

Because of the properties of modular arithmetic, if \(p\) is hundreds of digits long, anyone with \(g\), \(x\), and \(p\) can easily calculate \(y\). However, if someone only has \(y\), \(g\), and \(p\), it is mathematically impossible for modern computers to reverse the equation to find the secret \(x\). The Prover shares \(y\) with the world.

2. The Commitment (Hiding the Secret)

To prove they know \(x\) without revealing it, the Prover cannot just use \(x\) in an equation, or the Verifier might solve for it. The Prover must mask \(x\) with randomness.

The Prover generates a random secret number, \(r\), and calculates a commitment value, \(C\):

\[C = g^r \pmod p\]

The Prover sends \(C\) to the Verifier. Because of the one-way function, the Verifier cannot extract \(r\) from \(C\).

3. The Challenge

The Verifier generates a random number, \(e\), and sends it to the Prover. This prevents the Prover from pre-calculating fake answers.

4. The Response

The Prover now combines their secret (\(x\)), the random mask (\(r\)), and the Verifier's challenge (\(e\)) into a single response, \(s\):

\[s = r + (x \cdot e)\]

The Prover sends \(s\) to the Verifier.

Notice why the secret \(x\) is safe here. The Verifier knows \(s\) and \(e\), looking at the equation \(s = r + (x \cdot e)\). Because the Verifier does not know the random mask \(r\), they are left with one equation and two unknowns (\(r\) and \(x\)). It is algebraically impossible to solve for \(x\).

5. Verification

Even though the Verifier cannot extract \(x\), they can still verify the math holds true using exponent rules. The Verifier calculates \(g^s \pmod p\) and checks if it equals \(C \cdot y^e \pmod p\).

Why does this prove the Prover knows \(x\)? Because of standard laws of exponents:

\[g^s = g^{r + x \cdot e}\] \[g^{r + x \cdot e} = g^r \cdot g^{x \cdot e}\] \[g^r \cdot (g^x)^e = C \cdot y^e \pmod p\]

If the two sides of the equation match, the Prover must know \(x\). If the Prover did not know \(x\), they would not have been able to construct \(s\) in a way that satisfies this equation after receiving the random challenge \(e\).

Scaling Up: Polynomials

For more complex secrets—such as proving a private cryptocurrency transaction is valid or proving a password is correct—mathematicians translate the secret into a massive polynomial (an equation like \(ax^3 + bx^2 + cx + d = 0\)).

Two different polynomials of a high degree will share very few intersections. Therefore, if a Prover wants to prove they know a massive polynomial without revealing it, the Verifier simply asks them to evaluate the polynomial at a single, random point. If the Prover returns the correct result (masked using the same modular arithmetic tricks described above), the Verifier can be nearly 100% certain the Prover knows the entire underlying equation, without ever seeing the equation itself.