Zero-Knowledge Proofs Simplified: Unveiling Secrets Without Revealing Them
Zero-knowledge proof (zk proof or ZKP) is, in simple terms, a proof that separates knowledge from verification.
Abstract: This article introduced a simplified method for achieving zero-knowledge proofs for general Boolean circuits. It highlights the versatility of zero-knowledge proofs, showcasing their ability to prove knowledge of various secrets without revealing them. While the method presented here is computationally expensive, it serves as a foundation for understanding how zero-knowledge proofs work in principle. Modern cryptographic systems leverage more efficient techniques to make this powerful tool practical for real-world applications.
There’s been a surge of interest in zero-knowledge proofs, particularly in blockchain technology. They underpin the privacy features of cryptocurrencies like Zcash and Monero. But what exactly are these cryptographic marvels?
While numerous articles explain zero-knowledge proofs, they often cater to a niche audience. Some are heavy on math, while others focus on specific, limited scenarios. This article cuts through the noise to answer a fundamental question: what can be proven with a zero-knowledge proof?
In short, almost anything. In cryptography, a zero-knowledge proof allows one party (the prover) to convince another (the verifier) that they possess a secret solution to a problem, without revealing the solution itself. Imagine proving you know the pre-image of a hash function, the private key to a public key, or the specific transactions that maintain blockchain integrity — all without divulging any details!
A Simple Example: The Impeccable Inspector
Let’s say Mary invents a method to detect arsenic impurities in steel. She wants to keep her method secret but get paid per test. On the other side, Tom is a steel factory manager who needs a reliable inspector. How can Mary convince Tom her method is foolproof without revealing its inner workings?
Mary proposes a solution. Tom flips a coin 128 times, creating samples with or without arsenic based on the results. He keeps track of which is which but hides this information from Mary. Mary’s task is to identify the composition of each sample. If she’s right every time, statistically, it’s highly improbable she’s just guessing. This demonstrates Mary’s secret method is indeed accurate, without revealing its details — a classic zero-knowledge proof.
Beyond Simple Examples: Proving Almost Anything
The power of zero-knowledge proofs lies in their versatility. You can prove knowledge of solutions to puzzles, ownership of private keys corresponding to public keys, and more — all without revealing the solutions or keys themselves.
This article explores this concept without diving into the complex math behind efficient zero-knowledge proofs used in real-world applications.
The Blind Date Protocol: A Secure Matchmaking Exercise
Imagine a blind date scenario where both Mary and Tom want to know if a second date is on the cards, but neither wants to reveal their preference unless it’s mutual. They need a way to determine if their desires align without learning the other’s choice unless it matches their own.
In essence, we’re looking to implement an AND gate. Here, 1 represents wanting a second date, and 0 represents not. The gate’s output, 1, signifies that both parties want a second date. However, neither party should be able to glean the other’s preference beyond what the gate’s output reveals.
Here’s a solution assuming honesty and good memory on both sides. We assign keys to each possible AND gate input (0 or 1). Mary and Tom each have keys for their respective preferences. Boxes are created, each requiring two keys (one from Tom, one from Mary) to open. These boxes contain either a 0 or a 1.
Mary and Tom can learn the outcome (whether they both want a second date) by attempting to open a box with their corresponding keys. The key pairings and box contents are designed to ensure neither party learns the other’s preference from the process.
From Blind Dates to Secure Voting: Expanding the Scope
Imagine Tom, Dick, and Harry deciding on a vacation destination via a majority vote (0 or 1 representing two choices). They want the result to reflect the majority preference, but without revealing who voted for the less popular option.
We can leverage the same key-and-box approach to achieve this. The key concept is using the outputs of AND gates (representing individual preferences) as inputs to OR gates (determining the majority). By strategically placing keys within boxes corresponding to gate outputs, we ensure the privacy of individual votes while accurately reflecting the collective decision.
This system, known as Yao’s garbled circuit, can be applied to any computation expressed as a Boolean circuit. Since most computations can be modeled using Boolean circuits, the possibilities become vast. In real-world implementations, these boxes and keys are replaced with cryptographic equivalents (encryptions and encryption keys).
Building a Zero-Knowledge Proof System
We’ve seen how to construct a garbled circuit. How can we use it to create a zero-knowledge proof system?
Let’s say a function f(x, n) takes a set of Boolean variables (x) and a value (n) as inputs, and outputs either 0 or 1. We can design such a function for various purposes. For instance, if the prover claims to know the factorization of a number n, the function would output 1 only if the input x represents two factors of n. We can build a Boolean circuit to achieve this logic. The prover can then create a garbled circuit of this function.
Here’s how the prover can convince the verifier they know the factorization without revealing it:
- The prover provides the garbled circuit to the verifier.
- The prover shares keys corresponding to their secret input (x) with the verifier, but in a way that hides whether the keys represent 0 or 1 (using the envelope trick).
- The verifier shares keys for their input (n) with the prover, but openly (since n isn’t a secret).
- The verifier runs the garbled circuit and checks the final output (revealing if the prover’s input validates the function).
This approach protects the prover’s secret (x) from the verifier. However, it doesn’t guarantee the prover hasn’t tampered with the garbled circuit. To ensure legitimacy, the verifier might want the prover to reveal everything — boxes and envelopes. But that would expose the secret (x).
The solution lies in creating multiple copies:
- The prover creates two copies of the garbled circuit, each with unique keys.
- Both copies are made public.
- The verifier randomly selects one copy for the prover to reveal (boxes and envelopes).
- The verifier checks if the remaining copy (with the unrevealed keys) produces the expected output using the keys provided by the prover.
Since each copy has a 50% chance of being chosen, attempting to deceive the verifier by tampering with one circuit carries a high risk (50%) of getting caught.
Fortifying the System: Catching Cheaters with High Probability
What if a near-certain guarantee of catching a dishonest prover is desired? We can increase the number of copies:
- The prover creates 256 copies of the garbled circuit, each with unique keys.
- All copies are made public.
- The verifier randomly selects 128 copies for the prover to reveal.
- The verifier checks the remaining copies using the prover’s keys, ensuring they all produce the correct output.
Here, even if a correct circuit exists among the unrevealed ones, the prover must create at least 128 incorrect copies to avoid detection. The probability of the verifier selecting only the incorrect copies for revelation is incredibly small (essentially zero), making it highly likely a dishonest prover will be caught.
This demonstrates a zero-knowledge proof system for proving knowledge of any secret that satisfies a given condition.
Beyond the Basics: Modern Zero-Knowledge Proofs
While the above technique offers a general approach, it can be communication and computation-intensive. Modern zero-knowledge proofs are significantly more efficient, generating much smaller proofs requiring minimal verification effort. These techniques delve into the world of finite fields, which are beyond the scope of this article. However, interested readers can explore this topic further.
