What are Zk Snarks ?

What are Zk Snarks ?
Zero Knowledge Proofs
Drawback
Solution → Zk Snarks
More Blog Posts
Subscribe to newsletter

What are Zk Snarks ?

First, we need to understand what zero-knowledge proofs are. Then, we will see what zk-SNARKs are.

Zero Knowledge Proofs

A zero knowledge proof is the ability to show that you can do something or you know something without even having to demonstrate or tell the thing you know.

Here is an example:

Let's say there are two people, Alice and Bob. Alice says that she knows a magical spell using which she can go right through the wall. Bob doesn't believe her.

Claim

Alice can pass right throught the wall using the magical spell

What are her choices?

Choices	Is Zero Knowledge
Demonstrate how she does it?	No
Somehow proof to bob that she can do it without actually doing it	Yes

Alice decided to conduct an experiment where she could go into a cave either via path A or B.

Bob will then stand at the center of the cave and call Alice to come out through a specific path. Alice has to come out only through that path.

Given that Bob doesn't know which paths Alice chose to go in, the probability that both might have chosen the same path is 50%.

Here is some math behind it:

If we assume that each person independently chooses a path without any prior knowledge or influence from each other, then the probability of both individuals choosing the same path depends on the number of available paths and the choices made by each person.

Let's say there are two paths, path A and path B. Each person has a 50% chance of choosing either path, assuming they have no preference or bias. In this case, the probability of both individuals choosing the same path would be:

Probability = (Probability of choosing path A) * (Probability of choosing path A) + (Probability of choosing path B) * (Probability of choosing path B)

Since each person has a 50% chance of choosing either path, we can substitute the probabilities:

Probability = (0.5) * (0.5) + (0.5) * (0.5)
Probability = 0.25 + 0.25
Probability = 0.5

Therefore, if both individuals choose their paths independently and without any influence, the probability of both choosing the same path is 0.5 or 50%.

So that means there is a 50% chance she knows the magic spell and a 50% chance she doesn't. Well, that's not so convincing. In other words, she had a 50-50 chance of successfully faking the magic spell.

But what if we repeat this experiment 100 times? Here is the math.

If both individuals are choosing the same path for each of the 100 times, we can calculate the probability by multiplying the probabilities of choosing the same path in each individual trial.

Let's assume that the probability of both individuals choosing the same path in a single trial is denoted by p. Since they are choosing the same path each time, the probability of this happening in each trial is p.

The probability of them choosing the same path for 100 times in a row is:

Probability = p * p * p * ... * p (repeated 100 times)

Mathematically, this can be expressed as:

Probability = p^100

Therefore, the probability of both individuals choosing the same path for 100 consecutive times depends on the value of p. If p is 0.5 (50% chance of choosing the same path in a single trial), the probability would be:

Probability = 0.5^100

Calculating this value gives us:

Probability ≈ 7.88860905221e-31

In other words, the probability is approximately 0.0000000000000000000000000000000788860905221.

Therefore, if both individuals are choosing the same path each time for 100 trials, the probability of that happening is extremely small.

After conducting this experiment 100 times, she has a 0.00000000000000000000000000000788860905221% chance that she will be able to successfully fake that she knows the magic spell every time without actually knowing it.

Which means after this experiment if conducted 100 times, Bob will know that Alice knows the magic spell with 99.99999999999999999999999999999211139094779% certainty.

In fact, we don't even need to do it 100 times to be sure. Conducting that experiment just 7 times will give more than 99% certainty that Alice knows the magic spell.

To determine the number of times you need to repeat the experiment to achieve a probability less than 0.01, we can follow a similar approach.

The complement of the probability you desire (0.01) is 1 - 0.01 = 0.99.

Let's find out the number of times we need to repeat the experiment to achieve a complement probability of 0.99.

The probability of two people choosing the same path each time is given by (1/2)^2 = 1/4 = 0.25.

Let's denote the number of times we need to repeat the experiment as N.

The probability of two people choosing the same path in all N repetitions is (1/2)^N.

So, we need to solve the following equation:

(1/2)^N < 0.99

Taking the logarithm base 2 of both sides:

log2((1/2)^N) < log2(0.99)

N * log2(1/2) < log2(0.99)

N * (-1) < log2(0.99)

N > -log2(0.99)

Using a calculator, we find:

N > 6.643856189774724

Since N represents the number of repetitions, it must be an integer. Therefore, we need to repeat the experiment at least 7 times to achieve a probability less than 0.01.

So to sum up, a zero-knowledge interaction proof will look like this:

Drawback

While that experiment was cool, it is not practical due to two main reasons:

Interactive: Both verifier and prover need to be present at the time of this ceremony.
Time-consuming: You have to repeat the experiment at least seven times to get more than 99% certainty of the proof.

Solution → Zk Snarks

Instead, what we verify and prove is that they can both agree on the same sequence of challenges and a hash function. Finally, the prover only needs to send the very last proof, and verifiers can iteratively check and verify that it's correct, making the whole interaction non-interactive and sufficient.