Introduction to zero knowledge proofs

In most of the situtations where you (Prover) make a statement and have to prove its authenticity to someone (Verifier), you'll actually have to disclose the actual value of the statement's argument.
Examples

Situation Statement Argument What is disclosed as a practical proof
Voting, Driving, Buying alcohol... I am over 18 yo Age ID card: actual age, birthdate, name
Execute a bank transfer or card transaction I have enough funds on my account Account balance Actual account value
Mathematical problem I know the solution Mathematical solution How to solve the problem
Private Key I am the owner of the private key Private key Actual private key value

Having to disclose the value of my account to anyone I want to buy something from, as a proof that I can actually pay him, is very problematic with regards to privacy and security.

Zero Knowledge Proofs

Zero knowledge proofs are precisely a mechanism to assert knowledge without divulging it.
It is a probabilistic-based verification (verification of the equality 2 polynomial products by randomly selecting several checkpoints). The verifier asks the prover based on certain randomness. If the correct answer is given, the prover has a high probability of possessing what he claims to be “knowledge.”

Example: How to explain zk Proofs to your children - The Strange Alibaba Cave

As illustrated by the Binance Academy, imagine a ring-shaped cave with a single entry and a magic doorway that separates the two side paths apart. In order to go through the magic doorway, one needs to whisper the correct secret words. So consider that Alice (yellow) wants to prove to Bob (blue) that she knows what the secret words are - while still keeping them in secret.

  1. Bob waits outside. Alice enters the cave and walks until the end of one of the two possible paths. Alibaba Cave
  2. Bob walks by the entrance and shout which side he wants Alice to appear from. Open magic doorway
  3. If Alice truly knows the secret, she will reliably show up from the path Bob names. Alive shows up

Bob could think that Alice doesn't really know the secret words and was just lucky. (50% chance to choose the right side of the cave). To convince him they could repeat the operation. After n repetitions, the probability for Alice to luckily choose the right side has decreased to (1/2)^n. The bigger n, the more reliable the proof.
Hence the description of zero knowledge proofs as a probabilistic-based verification mechanism. zk Proofs aren't proofs in the mathematical sense because there is always a small probability (converging to 0) that a cheating prover may convince a verifier that a false statement is true.

Another famous example is the 3-colarability puzzle.

Properties

The combination of the 3 following properties defines more formally a zero-knowledge proof:

Soundness: cheaters get caught

A dishonest prover can't convince a verifier that a false statement is true.

Completeness: true statements get accepted

Following the protocol, an honest prover will naturally convince the verifier that a true statement is true.

Zero knowledgeness: true statements don't teach the verifier anything else except it being true

Applications

zk-SNARK

zk-SNARKs are a particular type of zk Proof

Zero Knowledge

Succinct

Proofs are smaller in size and quick to perform.

Non interactive

The basic of Zero-Knowledge Proof protocol is interactive. It requires the verifier to constantly ask a series of questions about the “knowledge” the prover possess. zk-SNARKs are non interactive in the sense that there is little to no interaction required between the Prover and the Verifier. The Prover can publish their proof in advance, and a verifier can ensure its correctness.

ARgument of Knowledge

= considered computationally sound (see soundness property).

Limitations

zk-SNARKs have limitations though. They are dependent on a trusted setup between the prover and the verifier. A set of public parameters is required to construct zero-knowledge proofs. This creates a potential centralization issue because the parameters are often formulated by a very small group. The initial setup phase is critical in preventing counterfeit spending because if someone had access to the randomness that generated the parameters, they could create false proofs that seemed valid to the verifier.

zk-STARKs were invented as an alternative zk proof mechanism to zk-SNARKs. One that doesn't require such an inital trusted setup.

zk-STARK: succinct-Transparent- ARgument of Knowlege

Transparent

zk-STARK proofs present a simpler structure in terms of cryptographic assumptions. However, this novel technology comes with the disadvantage of generating bigger proofs compared to zk-SNARKs.


You'll only receive email when Gauthier Riou publishes a new post

More from Gauthier Riou