Understanding zero-knowledge proofs

A zero-knowledge proof (ZKP) is a method in which you (the prover) have 3 tasks:

1. Prove someone (the verifier) that some statement or claim is true.
2. Do not expose any other information apart from that the statement is true.
3. Prove it only to the verifier, and nobody else.

As an example: Imagine a scenario where you want to prove to a verifier that you know the password of a large gate in a cave. You should not expose any information other than that you know the password. Therefore, you should not expose the password itself. The fact that you know the password should be proved to the verifier only and nobody else.

The mighty cave

The above figure is representing the mighty cave¹. A strange place that help us understand zero-knowledge proofs. There are 3 people shown in the figure.

The mysterious fact about this cave is that there is a large gate inside it, and nobody on earth knows the password of the gate. However, recently a guy called Thomas told his friend Muthu that he figured the password out, and he can now open the gate.

In this scenario, Thomas wants to prove to Muthu that he knows the password. There are multiple strategies in which Thomas can prove this, but not all of them are zero-knowledge.

Before analyzing the strategies Thomas can pick to prove his claim, let’s review the scenario.

• Claim: Thomas knows the password of the gate.
• Characters:
  • Thomas: The prover who wants to prove the claim.
  • Muthu: The verifier who wants to verify the proof provided by Thomas.
  • Emma: An unknown stranger who happens to be in the scene. In a zero-knowledge proof, Emma shouldn’t be able to verify the proof even with eavesdropping.

Now that we understand the problem, let’s analyze the strategies.

Strategy #1: Just tell Muthu the password.

The first option would be to just tell Muthu (the verifier) the password, so he can try it out. Let’s see if this strategy is zero-knowledge by reviewing our task list:

Task 1: ✅ Prove Muthu that the claim is true.

Assuming Thomas knows the password, this task is really checked. Muthu can test the password on the gate and see if it opens.

Task 2: ❌ Do not expose any other information.

Well, Thomas did not really do a good job for this task. Now Muthu knows the password too. Remember, the claim was that “Thomas knows the password”, not that “The password is ABC123”. Therefore, in addition to the claim, we have exposed the secret too.

Task 3: ❌ Prove it only to the verifier.

Welp! When Muthu wasn’t paying attention, Emma installed a tiny voice recorder on Muthu’s t-shirt. She was eavesdropping the whole thing. She knows the password too, in contrary to Thomas’s intent.

It looks like we should not expose the password if we want to remain zero-knowledge. So let’s do that in the next scenario.

Strategy #2: Thomas enters from one side of the cave and exits from the other side, while Muthu is watching him at the entrance.

In this scenario, Thomas won’t expose the password. He asks Muthu to verify that he can go around the cave. The only person who can go around the cave without backtracking is the person who knows the password of the gate.

Task 1: ✅ Prove Muthu that the claim is true.

Thomas really goes around the circle by entering one side and exiting from the other. Muthu can verify that Thomas knows the password.

Task 2: ✅ Do not expose any other information.

Thomas did not tell Muthu the password. Even though Emma installed a microphone on Muthu, she doesn’t know the password, as it was not mentioned in their friendly chat.

Task 3: ❌ Prove it only to the verifier.

What?! Emma did not only install a microphone on Muthu, but a camera too?! (Where is your mind wandering, Muthu?).

Emma have seen that Thomas went around the cave without any issues. Now, Emma also knows that Thomas figured the password out.

Can you see where the problem is? Going around the cave 100% proves that Thomas knows the password of the cave, therefore any third party who is illegally observing the scene can verify the claim alongside the actual verifier.

To fix the problem, let’s make our proof probabilistic.

Strategy #3: Muthu doesn’t see from which side Thomas enters the cave. Thomas picks the entrance path randomly, but Muthu decides which side Thomas should exit from.

In this scenario, Muthu stays outside the cave without observing what path Thomas chose to enter the cave. After Thomas picked a path and entered the cave, now it’s time for Muthu to shout an exit path and ask Thomas to come towards the entrance from that path.

Task 1: ✅ Prove Muthu that the claim is true.

In the first round, there is a 50% chance that Thomas picked the entrance path correctly and exited from the path Muthu asked him to exit from. However, this does not prove that he knows the password, he might have just been lucky that day.

Muthu asks Thomas to do this strategy again and again until the probability of Thomas knowing the password is high enough. Remember that Thomas did not prove that he 100% knows the password, however, after a couple rounds, Muthu is convinced that Thomas knows the password.

Task 2: ✅ Do not expose any other information.

Thomas did not tell Muthu the password. Even though we know that Emma installed a microphone on Muthu, she doesn’t know the password, as it was not mentioned in their friendly chat.

Task 3: ✅ Prove it only to the verifier.

Emma did not only install a microphone on Muthu, but also a camera. She watched the whole process through the camera, and heard everything via the microphone. Yet she can’t know if Thomas really knows the password.

All Emma would see is Muthu shouting a path and Thomas exiting from that path. This doesn’t prove the claim to Emma, because Thomas and Muthu might have been faking the process, and Thomas might have told Muthu to pick paths from a pre-defined list they have agreed on beforehand.

To Muthu, Thomas knows the password, but to Emma, she can’t know if this process was fake or real.

Use cases

Proving that you know a passwords or secret is only one use case of the zero-knowledge proofs (called Zero-knowledge password proof). There are other use-cases like:

• Proving that you solved a Sudoku puzzle correctly without exposing your solution² (using property-testing of Sudoku rules).
• Verifying the authenticity of nuclear weapons without sharing any secret design information³.
• Tell your crush you like them with zero-knowledge ⁴.
• Protect the privacy and security of auctioneers in online auction systems. The auction system generates one proof for each losing bid. This proof demonstrate that the difference between the losing value and winning value is positive⁵.

Zero-knowledge proofs also helps you to protect your privacy. You can prove that if a claim about you or your personal data is true without exposing them.

Non-interactive zero-knowledge proof

The cave example we've seen in the previous section is an interactive zero-knowledge proof, meaning that the interaction between the prover and the verifier are required (in other words: both prover and verifier should be "online"). If Thomas wants to prove to someone else that he knows the password, he has to repeat the whole process with the new verifier.

In a non-interactive ZKP however, the interaction between a prover and a verifier can be simulated by the prover.

Remember how Muthu challenged Thomas to exit from one of the two paths? One of the easiest ways to transform interactive proofs to non-interactive proofs is to generate such random and unpredictable challenges for the prover using hash functions. This way the prover can not cheat because the output of hash function is beyond their control. There are a couple of famous zero-knowledge proof systems like zk-SNARKs, zk-STARKs, and Bulletproofs which are mostly being used in blockchain technologies.

Writing a zero-knowledge proof

In this scenario, Thomas wants to prove to Muthu that he knows a real solution to this 3rd degree polynomial without exposing his solution:

At first, Thomas needs to write a function (or in ZKP terms: an Arithmetic Circuit) that checks the properties of the proof:

// The arithmetic circuit
// This circuit checks if an equation in form of (a + bx + cx^2 + ...) is equal to 0
const checkPolynomialSolution = (factors: number[], x: number): boolean => {

  // Result calculates a + bx + cx^2 + dx^3 + ...
  const result = factors.reduce((result, currentFactor, index) => {
    const power = factors.length - index;
    return result + (currentFactor * Math.pow(x, power))
  }, 0)

  return result === 0;
}

For this circuit, the parameter factors is a public input which Muthu knows about (in this case, it is [3, -12, -60, -21]), and the input x is the solution of the equation and only Thomas knows about (hence it's a secret and Thomas should not expose it).

The goal for Thomas is to prove that he knows a value for input x where the function call checkPolynomialSolution([3, -12, -60, -21], x) return true.

We are going to use the zk-SNARKs ZKP system to help Thomas prove this claim to Muthu.

There are a couple of special functions in zk-SNARKs that helps Thomas to achieve his goal. The first one is called the generator function.

const generator = (program: Function, lambda: number): [provingKey: Key, verificationKey: Key] => {
  // ...
}

// ...

As we can see in the above code snippet, this function accepts two parameters. The circuit (our function) and a $\lambda$ parameter. For every unique circuit, we need to generate these two keys: provingKey and the verificationKey. $\lambda$ is a secret random input required for generating the keys.

The next special function is the prover function.

// ...

const prover = (provingKey: Key, publicInput: any, privateInput: any): Proof => {
  // ...
}

// ...

This function receives the key we've recently generated, and a public and private input. In our case, the factors of the polynomial is the public input which Muthu knows about, and the private input is the solution to the problem.

const factors = [3, -12, -60, -21]; // Public
const solution = 7; // Secret

const lambda = getRandomLambda(); // Secret

const [provingKey, verificationKey] = generate(checkPolynomialSolution, lambda)

const thomasProof = prover(provingKey, factors, solution)

Now it's time for the last zkSNARKs special function. The verifier function.

// ...

const verifier = (verificationKey: Key, publicInput: any, proof: Proof): boolean => {
  // ...
}

Muthu already knows the value of the publicInput. All he needs to do is to call the verifier function using the verificationKey and the thomasProof inputs he just received from Thomas. If the function returns true Muthu can be sure that Thomas indeed knows the solution to the problem.

if(verifier(verificationKey, [3, -12- -60, -21], thomasProof)) {
  console.log("Thomas knows the solution.")
}
else {
  console.log("Thomas doesn't know the solution.")
}

Conclusion

Zero-knowledge proofs help us prove our claims without exposing the knowledge behind that claim. We've seen an example of an interactive zero-knowledge proof (The mighty cave), and a non-interactive zero-knowledge proof using zkSNARKs approach. ZKPs have a wide variety of use cases, and one of the most important one of them is to protect your privacy and security. Many of the use cases of the zero-knowledge proofs are currently being used in the cryptocurrency industry, however, there are a lot of use cases for them in other areas as well.

Footnotes