Zero Knowledge Proofs

In my past post I tried to explain what a mixing service is, I also put an example where Kim made a terrible mistake that got him into jail for sure. These articles will be part of a series of articles, trying to talk about the privacy on blockchain, which most of the time is taken for granted. Terrible assumption, just terrible.

In this one I’ll try to explain, with a basic example, what is Zero Knowledge Proof and where it is also used to obfuscate a transaction. The idea of Zero Knowledge Proof is just genius, this is one of the examples of when math can be so interesting for some people. A simple idea, that can be quite useful. Let’s dig on it then.

The problem

Let’s describe an example, for me it is way easier to explain and understand new concepts or ideas through examples with pictures. So we have two people, one called Gulolio and the other one called Tyushka. Now Gulolio likes to share with Tyushka his genius ideas, just for the fun of making Tyushka think. They have the following dialog:

[Gulolio]: Tyushka I have a question and I want you to think about it, and tell me if this is possible or not. Ok?

[Tyushka]: Ufff here we go again, so surprise me what is this new question?

[Gulolio]: I see you are extremely interested. Don’t hurry, the question is like this:

Demonstrate your ability to open this locked door without revealing how you do it or whether you have the keys.

[Gulolio]: Ok, I’ll give you some help. Let’s imagine you are in a cave with the shape of a ring.

[Tyushka]: What? A cave? You want me to be in a cave?

[Gulolio]: Xaxaxaxaxa(this is hahaha in Russian), нет, нет, нет. Just imagine it, ok? This cave is divided by a door, in the middle. In a way that the cave has a path A and a path B.

I’ll draw you some pictures, so you will get a better understanding. Смотри(Look!!):

[Gulolio]: Now imagine that you are inside of the cave, and I didn’t see you on which path you are. Ok? And I’m in the entrance of the cave, as in this amazing drawing made by an adult person. Now, back to the original question, how do you show me that you have the keys for opening the door, without showing me that you have the keys? And given that I’m outside of the cave and didn’t see you on which path you are. How can you** prove to me** that you have the keys?

[Tyushka]: I have no idea 😐, how am I supposed to do that? If at least you knew on which path I’ll be, you could ask me to get out of the cave from the contrary path. I mean if I’m in A and I can get outside of the cave but from path B, then obviously I have the keys. But that is not the case. Show me the idea, I have the suspicious this is related to math 😑. I hate it!!!

[Gulolio]: And you are right, there’s a way that doesn’t constitute a “proof” but a “probabilistic proof”. I’ll try to explain to you, but I need your help and cooperation, ok?

If we are in the same scenario, and I’m outside of the cave, right? And I call you and tell you: Tyushka, get out of the cave taking the path B.

What is the probability that you can accomplish that? That you can actually get out of the cave from that path.

[Tyushka]: Mmm for that I would say that a ½ probability, to take the path you specify me.

[Gulolio]: Good, now if we repeat this experiment, let’s say 40 times, what is the probability that on each experiment you can come back from the path I specify. Either A or B.

[Tyushka]: Well in that case, 🥲 there is almost no chance at all, to be honest. If I don’t have the keys, then my chances are

2^(-40) = 1/1099511627776 = 0.0000000000009094

That’s just impossible, there’s no way I’m gonna be able to get back from the right path each time.

[Gulolio]: Exactly, that’s how you prove to me you have the keys. Given that if we repeat this experiment 40 times, the chance that you can take the right path each time is so small. If you manage to do so, then I can assume, without any issues, that you actually have the key. If you noticed, in this way, you don’t have to show me that you can open the door, nor that you have the keys. That’s why math is awesome!

The use case

Like everything in math you just started wondering, yeah this is a cool idea, but how is this useful for me, man? And how is this related to blockchain? This idea has more applications in math itself, but I’ll let you Do Your Own Research. Related to blockchain, well there’s one particular project that I’m aware of, maybe there are a few more. The project aims to solve the issue we discussed in our previous article. Basically to be able to make transactions, in a blockchain, and to keep the anonymity. The project is called Zcash. The idea is that we can still make the transactions in the blockchain, keeping the benefits from that, and add encryption to it. In a way that still with encryption, nodes in the network can verify that this is a valid transaction. Applying a similar principle to what we described before, a lot more sophisticated of course.

In case you are curious about the tech, I recommend you to read this article about zk-SNARKS from the official doc. We can have several motives to use a more private blockchain for certain transactions, is up to you. In my opinion, using a blockchain solution, completely decentralized, is way better than a mixing service. As always, I recommend you to Do Your Own Research, at the end is your money.

In my case, what is more interesting for me is this genius idea, the Zero Knowledge Proof, is just amazing.