Zero-Knowledge Proofs: A Beginner's Guide

Zero-Knowledge Proofs (ZKPs) are powerful cryptographic tools with a wide range of practical applications.

In this article, we’ll provide a simple introduction to the core principles of zero-knowledge proofs without diving too deep into complex mathematics.

We’ll discuss the foundational ideas behind ZKPs, focusing on the basic concepts that originated in computer science in the 1980s. (So we won’t cover modern protocols like ZK-SNARKs and Bulletproofs.)

Whether you've come across the term and want to understand it better or are curious about how zero-knowledge proofs might be relevant to your work, this guide is a good place to start.

What are zero-knowledge proofs?

Zero-knowledge proofs are a cryptographic technique that enables one party, known as a prover, to convince another party, a verifier, that a statement is true, without disclosing any additional information.

This means that the verifier learns nothing other than the fact that the statement is true.

A brief history of ZKPs

The concept of Zero-Knowledge Proofs was first introduced in a seminal paper published in 1985 by researchers Shafi Goldwasser, Silvio Micali, and Charles Rackoff.

To better understand their innovation, let’s consider the traditional notion of a proof:

Typically, a proof not only confirms the truth of a statement but also reveals additional information that shows how the truth was established.

Imagine you’ve solved a very hard mathematical problem. You could show your friend the solution to prove you solved it, but this would also give away the answer. Is there a way to prove you’ve solved it without revealing the solution itself?

This leads to a broader question:

Is it possible to prove the truth of a statement without revealing anything beyond the fact that the statement is true?

Goldwasser, Micali, and Rackoff gave a positive answer to that question, which led to the development of what we now know as zero-knowledge proofs.

Since then, ZKPs have evolved from a theoretical concept to finding numerous practical applications, especially in areas where privacy and security are critical.

Proofs vs. proofs of knowledge

Zero-knowledge proofs are sometimes also called “zero-knowledge proofs of knowledge.”

While these terms describe related but technically different concepts, they are often used interchangeably in recent literature.

Strictly speaking, zero-knowledge proofs of knowledge are a subset of zero-knowledge proofs. But for most practical purposes, when we talk about zero-knowledge proofs, we refer to proofs where the prover demonstrates their knowledge of a solution rather than simply confirming that a solution exists.

In this article, when we refer to zero-knowledge proofs (ZKPs), we specifically mean zero-knowledge proofs of knowledge.

Understanding ZKPs through examples

Let's illustrate ZKPs using two examples:

1. Finding Waldo

Imagine you're looking at a "Where's Waldo?" puzzle and find Waldo hidden in the picture. You want to prove to someone else that you know where Waldo is, but you don't want to show his exact location.

One way to do this is to take a large piece of cardboard and cut a small hole in it, just big enough to show Waldo and nothing else. You then place the cardboard over the puzzle in such a way that only Waldo is visible through the hole. By doing this, you convince the other person that you know where Waldo is without giving away his position.

This analogy captures the essence of a zero-knowledge proof: You show that you know something (Waldo's location) without revealing the knowledge itself (the specific position of Waldo in the puzzle).

2. Graph coloring

Graph coloring is a classic problem in mathematics.

Imagine a graph consisting of nodes (points) and edges (lines connecting the points): Graph-3-coloring The goal is to color each node in such a way that no two connected nodes share the same color, using only three colors: Graph-3-coloring-solution Imagine you've found a valid coloring for the graph and want to prove this to a verifier without revealing the actual colors.

To do so, you could hide each node’s color from view by placing it in a small envelope. The verifier can now choose any edge they like. Whatever they choose, you open the envelopes for the two nodes connected by that edge to demonstrate that they’re colored differently. While the verifier can see that adjacent nodes have different colors, they don’t learn the overall coloring of the graph.

However, the verifier would likely remain skeptical after just one or two attempts. To further convince the verifier, you would repeat the process multiple times, repainting the graph differently each time before revealing the colors again. This repeated demonstration convinces the verifier that you know the solution without ever disclosing the actual colors (even partially, since the graph is repainted every time).

You can experience this process yourself—as a verifier—with this interactive demo.

Next, let’s look at how ZKPs work in practice by examining their key properties.

The (three-move) protocol structure

We’ll discuss a specific class of zero-knowledge proof systems known as Σ-protocols (Sigma-protocols).

These protocols are especially efficient and follow a distinct three-move structure: commitment, challenge, and response. The interaction occurs between two computer programs: the prover and the verifier.

Commitment (first message):
- The prover generates a random value and uses it to create a commitment. The commitment depends on both the random value and the secret information (witness).
- The prover sends this commitment to the verifier.
Challenge (second message):
- The verifier generates and sends a random challenge to the prover, asking the prover to open some parts of the commitment.
Response (third message):
- The prover computes a response using the witness, the random value from the commitment step, and the challenge provided by the verifier in the challenge step.
- The prover sends the response back to the verifier, who verifies it against the original commitment and challenge to ensure its correctness.

You may have realized that the graph coloring example from before fits the three steps perfectly:

The prover commits to a valid coloring of the graph.
The verifier sends a challenge asking for the colors of the nodes associated with a specific edge.
The prover responds with the required information.

What is a commitment?

Remember the envelopes we used to hide the colors?

A commitment (or commitment scheme) is a mathematical equivalent of those. A commitment binds the prover to a specific value but keeps it hidden from the verifier until the commitment is opened.

Important concepts for Σ-protocols

Interactivity

Zero-knowledge proofs typically rely on an interactive exchange of messages between the prover and the verifier.* This interactive nature of the protocol allows convincing the verifier of the prover’s knowledge incrementally. The protocol should run multiple times until there is only a negligible probability that the prover doesn’t actually know the secret.

Randomness

Another important element is the role of chance. The verifier asks a series of questions, choosing the questions by an electronic equivalent of flipping a coin.

This adds randomness to every challenge, which prevents the prover from simply "faking" the proof and ensuring that each round of the protocol offers a fresh opportunity to test the prover's knowledge.

The properties of a zero-knowledge protocol

For a proof system to be formally recognized as zero-knowledge, it must meet three criteria:

Completeness: If a statement is true, a prover who knows the proof can convince a verifier of its truth.
Soundness: If a statement is false, no prover can convince a verifier that it is true (except with negligible probability).
Zero-knowledgeness: If a statement is true, the verifier learns nothing beyond the fact that the statement is true. The proof reveals no additional information about the statement.

While the first two properties are relatively straightforward, finding a way to formally define zero-knowledgeness is a real challenge. The problem is that it is not clear how to formalize the notion that “the verifier learns nothing” from the proof.

The simulator algorithm

The solution came from Goldwasser, Micali, and Rackoff, and it’s very interesting.

They argued that a protocol can be considered zero-knowledge if, for every possible verifier, there exists an algorithm that can act as a simulator for the zero-knowledge proof. The simulator can generate a transcript of the proof interaction that looks indistinguishable from a real proof, but without actually knowing the secret.

Note: The simulator is a hypothetical construct used in a thought experiment. It doesn’t actually participate in a normal run of the protocol. Its existence is only used to demonstrate that the protocol transcript reveals nothing about the secret.

How is this possible?

The simulator uses a technique called rewinding, which allows it to "revisit" earlier stages of the interaction with the verifier. For simplicity, think of rewinding as similar to going back to an earlier commit in a version control system like Git.

To demonstrate the rewinding technique, let’s look at how a simulator would operate in the graph coloring scenario:

Initial commitment (to random values)
If the simulator knows the edge to be queried ahead of time, it can commit to random different colors only on the two nodes of that edge—and to dummy values elsewhere. This will be indistinguishable for the verifier due to the hiding property of the commitment scheme. So the simulator will simply repeatedly guess the edge to be queried ahead of time in the hope that the verifier will query that edge.
Challenge and response
The verifier issues a random challenge. If the verifier selects the expected edge, the simulator opens the envelopes for the two connected nodes, and the simulation of this iteration is complete. If not, rewinding is applied.
Rewind and retry
If the verifier’s challenge doesn’t match the simulator’s prediction, the simulator rewinds the verifier to the beginning of the iteration and tries again, choosing a new random edge. This repeats until the simulator succeeds in aligning its response with the verifier’s challenge as many times as required.

For the verifier, the simulation is identical to a real protocol execution. In both cases, the verifier sees a set of “envelopes” and two different random colors being opened. The only difference is that no rewinding takes place in a real proof, in contrast to the simulation. However, this is not evident to the verifier, and the protocol transcripts look the same.

For a more detailed and technical explanation—including how it is possible to technically “rewind” the verifier, the relationship between soundness and zero-knowledgeness, and what is required to achieve negligible probability—we recommend the Tutorial on the Simulation Proof Technique.

Why does this matter?

The idea here is that creating a convincing fake protocol transcript that looks exactly like the real one—without knowing the secret—shows that the real protocol transcript doesn’t give away any information about the secret.

The verifier cannot distinguish between a real proof and a simulated one, which means they learn nothing about the secret itself and the protocol is indeed “zero-knowledge.”

*Non-interactive zero-knowledge proofs

Originally, zero-knowledge proof systems required a prover and a verifier to exchange multiple messages. Yet in some scenarios, such interactivity is undesirable or impractical.

This led to the development of non-interactive zero-knowledge proofs (NIZKs), Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs), and Zero-Knowledge Succinct Transparent Arguments of Knowledge (zk-STARKs).

These protocols eliminate the need for the prover and verifier to be online simultaneously, making them more efficient in certain scenarios. (But this efficiency comes with certain trade-offs).

Practical applications

Applications of zero-knowledge proofs extend far beyond graph coloring.

They can be adapted to any combinatorial problem where the challenge is to prove knowledge without revealing it.

More importantly, ZKPs are successfully used in complex real-world scenarios across several domains:

Cryptocurrencies and blockchain: ZKPs are widely used in cryptocurrencies to ensure transaction privacy. For instance, privacy-focused cryptocurrencies like Zcash implement ZK-SNARKs to provide anonymity in transactions.
Authentication systems: Consider server authentication. To enable secure communication, a server shares its public key while keeping its secret key private. Before interacting with the server, a client may need to make sure that it is connecting to the legitimate server, not an imposter. To do this, the client asks the server to perform a zero-knowledge proof that it knows the secret key.
Digital signatures: the Schnorr protocol is a foundational zero-knowledge proof technique that underpins many modern signature schemes. For instance, EdDSA signature family is based on Schnorr and is a key component in technologies such as OpenSSH, GnuPG, and various secure communication protocols.
Secure identification: In digital identity systems, ZKPs can be employed to protect users' privacy. Traditional digital identification methods often require individuals to share more information than needed, exposing unnecessary identity attributes and cryptographic details. With ZKPs, individuals can prove only the specific information the verifier needs and minimize data exposure. BBS/BBS+ signatures and Camenisch-Lysyanskaya signatures are examples of ZKP-based solutions that enable privacy-preserving identification.

ZKPs and privacy

By their very nature, zero-knowledge proofs are an ideal tool for proving computational integrity without revealing inputs. In other words, they can ensure that a computation was performed correctly and honestly. This makes ZKPs particularly valuable in cryptocurrencies, where they’re widely used.

On their own, ZKPs do not grant complete privacy to digital interactions. Determined and well-resourced actors might still find ways to re-identify and track users. But combined with other privacy-preserving mechanisms, ZKPs make it much harder for malicious actors to access personal or sensitive information. That’s why ZKPs should be used as part of a broader security strategy that accounts for the full range of potential threats.

Add-ons

Resources

Author