At a certain point in my career, I stumbled upon the magic world of “zero knowledge”. I encountered this cutting edge technology while working on cryptocurrencies, and was so fascinated by it and eager to discover how it worked that I decided to dive head first into the subject and learn all I could. It was definitely not an easy journey, I had one too many foggy days and brief bouts of good weather, every now and then. The sun shone every time I added a new piece to the puzzle and the overall picture became just a little bit clearer. In those moments, I felt the excitement of discovery and, at the same time, the urge to understand more.
I began taking notes when I embarked on this journey and I intend to keep taking them as I continue on my quest, since I feel like I’m nowhere near a final destination. This technology is at an early stage of development, and every month features a new research paper, an event, an advancement, a progression. I will post everything I learn here, in the hope that my small personal effort may spread the very same excitement I have about all this and, maybe, make the reader’s journey slightly easier than mine.
As I add posts, I will try to create an overall coherent “structure”, so they can be read sequentially and maybe, at some point, look like some sort of high level tutorial.
Just a disclaimer before we take off: I’m not a cryptographer; the language used and the content presented is simplified and may, at times, be imprecise. I welcome any corrections and suggestions, there is a contact form on the site. In any case, the purpose of this blog is only to supply a reader-friendly overview of the technology, leaving any formal approach to the academic world that so cleverly developed it.
Enjoy,
Maurizio
Zero-knowledge: a breathtaking journey
I first encountered zero-knowledge during the summer of 2018. I was about to join the Horizen tech team, and was preparing by taking a deep dive into the bits and bolts of cryptocurrencies. Zero-knowledge is used by some cryptos to provide users with strong privacy protection (e.g. Zcash and Horizen itself use it for this purpose), or to achieve better scalability (e.g. Coda), but it has many more possible applications; I personally have no doubt that its use will grow exponentially over the next few years. What exactly is “zero-knowledge” then? Essentially, it’s a cryptographic technology, and as such, it rests on some serious maths, the stuff that cannot be immediately grasped by those with no specific theoretical background. There is a way, though, to understand the base concepts and the key mathematical tools it uses, and that’s exactly what I set out to do: to learn and understand its main components and the way they work together. Unfortunately, I wasn’t able to find an on-line “tutorial” that was both complete and at the same time accessible to a non-expert. I had to search around here and there and it took me a quite a few months of bedtime and weekend readings to get a decent overview of the topic.
One day, zero-knowledge will become an off-the-shelf tool, and actually, the first standardization efforts are already taking place (see http://zkproof.org/). When that happens, there will be no need to share these kinds of notes, we will all just use it! In the meantime, I will try not only to keep adding material to this blog, but also to update the list of links to all good sources to make it easy for everyone to further explore.
I’ll start by posting my personal notes on one of the most used zero-knowledge protocols, “Pinocchio”; this should a good starting point from where we can then investigate other more recent protocols (Bulletproofs, Spartans, …)
Before you start navigating through the material in this blog, it’s probably useful to have an appropriate, high level introduction to the concept by way of an example. Let’s do that straight away!
“Zero-knowledge” proving system
A zero knowledge proving system is a cryptographic tool that allows a prover to demonstrate that:
- She knows a secret (a secret will be a value, or a few values)
- She used those secret values inside a defined and known computation
- She really performed that computation
AND let her prove all the above without revealing the original secret. The proof also needs to have some specific positive features (be short, quick to verify, etc).
I can almost see the expression on your face as you’re reading this and thinking “yeah, right… impossible!”. If you are thinking that, maybe it’s best to start off with an example to let you see that this can actually be achieved “in real life”, without the help of technology and cryptography. Actually, all the introductory presentations about zero-knowledge that are currently online start with an example similar to this one, usually based on a “protocol” that relies on random questions (e.g. Ali Baba's Cave , Sudoku, 3-Coloring, ...). So let’s do the same here, just so you get the feeling that zero-knowledge is actually possible:
Alice and her magic snooker balls
Alice has two snooker balls, a black one and a white one. She knows a secret: the black one is lighter than the white one. She can prove to Bob that, even blindfolded, she is able to tell which ball is white and which black, without revealing how she does it. To prove it, she stands in front of Bob, puts the two balls in a basket, puts both hands in the basket, picks up the balls randomly one in each hand, and asks him which colour he wants. If he says white, she holds up the heaviest; if he says black, the lightest. She repeats the process until Bob is convinced that she has a way of telling them apart without looking.
Okay, so now we can see how it is actually possible to prove that we know a secret without disclosing it: it’s doable! It’s not actual “solid” proof, but statistical proof, meaning we don’t have formal proof that Alice can actually tell the balls apart without looking, but it appears extremely likely that she can, since she would have to be extraordinarily lucky to guess right every single time. So, the more correct answers she gives Bob, the more it seems likely that Alice knows a way to distinguish the two balls without looking.
If we wanted to make the same example non-interactive, we could place Alice in front of a camera and repeat the same process without the presence of Bob. Bob’s role could be replaced by the toss of a coin. Alice could start shooting the video, toss a coin, show the result on camera, then put both hands in the basket, check the weight of the balls secretly and pull out the correct ball. After showing it to the camera, Alice could put the ball back in the basket and repeat the process for, say, 30 times. Assuming the entire process is recorded live and the viewer trusts that the video has not been edited, he will be convinced just by watching the clip that she can tell the two balls apart without looking… and he won’t know how she does it.
Now, considering our purpose, we want zero-knowledge proofs to be easily handled by computers; so a video won’t really do! We also want a solid and robust system: the video may have been edited, Alice could have cheated, maybe she had a way of looking inside the basket that was not captured by the camera. Oh, and one more thing: we need our proofs to be succinct, i.e. “short”.
To accomplish all this, we’ll use cryptography.
Let’s start exploring the cryptographic space by introducing three properties that need to be respected by our proof /proving system. These properties are: “Soundness”, “Completeness”, and “Zero-Knowledge”.
Soundness means that Alice cannot cheat. If Alice is not actually able to distinguish the two snooker balls, there is close to zero probability that she will be able to convince Bob (in our case, the probability decreases with the number of times she shows him that she can guess right).
Completeness means that each possibility has a way to be proven. So if we add a third green ball to our example, as heavy as the white one, Alice won’t be able to prove that she can blindly distinguish each of the three balls, and therefore we won’t have completeness. If, on the other hand, we limit the statement we want to prove to “I can blindly distinguish the black ball only”, then we’ll have completeness for that proof system.
Zero-Knowledge means that the only statement disclosed is the one being proven. In our example, the only statement disclosed is “Alice can tell which ball is which, without looking”, and she won’t need to show that the balls have a different weight to prove this: it’s zero-knowledge.
Ok, so now we understand there is a way to prove knowledge without revealing it. I’ve given you a hint that we’ll use cryptography to build proofs that are both reliable and practical, and we’ve taken a look at some key properties that zero-knowledge proof systems must comply with. Now you’re ready to surf through the Blog! In time, I may add new posts while trying to keep some sort of overall structure so that the whole Blog can be used as a basic tutorial on zero-knowledge technology that may be read sequentially. Otherwise, it may also be used as a high- level resource per subject/post.
One last disclaimer: it won’t always be easy reading, some posts may require time and have to be read a few times to be fully digested. But I believe it’s worth the effort.
Happy surfing!