Zero-knowledge proofs or ZKP for short. This is a topic I’ve known about for years, but my understanding of it was vague (to say the least). If I had to explain it to a five-year-old, my explanation would be…
“It’s a way to prove something, without sharing knowledge about that thing with another person”
Which is something, but nowhere near my preferred understanding. That’s why we’re here, it’s time I understand more about zero-knowledge cryptography, its applications, and most importantly security weaknesses.
The journey will be long and complex, so I plan to set a sustainable pace and scope for each topic. Think of each update I provide as a bite-size zero-knowledge snack for our brains to digest.
A ZKP is cryptographic to prove you know something without the need of sharing that information with the other person. During this interaction, there are two pirates, a “prover” that is doing the proving and a “verifier” who the prover is trying to convince.
There are tons of examples on the interwebs that explain how a ZKP works, below are a few I stumbled across.
I’ll provide a brief recap of the Where’s Waldo example, but for the in-depth breakdown, I recommend checking out 0xSage’s blog post above.
Alice knows where Waldo is, but Bob does not. Alice wants to show Bob that she knows without sharing the exact location, so she can take one of two paths.
Path 1 (source)
Path 2 (source)
In both of the examples above Alice is able to prove to Bob that she knows Waldo’s location without sharing it. Alice can repeat this multiple times on different Waldo maps (if that’s what they’re called) to improve Bob’s confidence that Alice is telling the truth.
This basic example provides the three ingredients that make up a zero-knowledge proof (quoted from 0xSage’s blog).
Great questions! It’s the same question I ask myself at the beginning of any learning journey and I recommend you do the same. If we understand the benefits and applications, it’ll likely sustain our excitement along the journey of grokking more difficult topics.
Initially, I was surprised by how many use cases ZKP could be applied to, but after gaining more intuition around the topic it began to resonate. If a stranger is able to prove the existence of knowledge or the possession of something to another stranger without having to share this information, a world of use cases opens up.
Here are a few resources that cover theoretical and practical applications.
“Outsource an expensive computation and validate that the result is correct without redoing the execution; it opens up a category of trustless computing”
An important note here is that applications for ZKP are not restricted to crypto, which can be easily assumed by those that lack a deeper understanding of the topic. Vitalik’s informal prediction during this panel sums it up well.
“I think that over the next 10 years it will become recognized that zk-SNARKS are at least as important a technology as blockchains are”
There are many more applications, but we’ll leave that for another day.
There are many different elements that makeup ZKPs, so I’ll cover the most discussed I found throughout my initial reading.
Interactivity: The Where’s Waldo example above is considered an “interactive” proof due to Alice and Bob needing to interact, so Bob is convinced Alice knows Waldo’s location. Within the realm of crypto, there’s a strong preference toward “non-interactive” proofs due to the scalability it provides. In a non-interactive proof, there’s no need for the prover and verifier to be online at the same time. In this case, the prover must demonstrate the validity of the transaction, by solving the hash of a random number. After, proof of the answer is returned to the verifier, without revealing its value (Wikipedia).
The non-interactive proof concept gets complicated fast, so we’ll dedicate a separate video/post to this topic. For the time being, I found Porter’s presentation and Maksym’s paper (Pg. 8) to be the most approachable on this topic.
Different Protocols: By simply taking a look at the table below from Wikipedia you’ll realize there are three main ZKP protocols, but many different implementations of each. Within the realm of crypto, you’ll hear more conversation around zk-SNARKs than anything else, with zk-STARKs coming in second. That’s not to say zk-SNARKs are better than zk-STARKs, it just highlights the fact that zk-SNARKs have been around longer, which comes with more tooling, understanding, and existing applications. The detailed difference between the two is yet again a separate topic for another day, so I’ll give a brief overview below, but if you want more I recommend Yan Zhang/Yi Sun post and Amber Groups post.
One caveat, the gap difference between SNARKs and STARKs is closing quickly due to newer implementations of SNARKs. For now, we’ll generalize.
Below are two tables by Matter Labs and Beanstalk presentation (slides 18 – 19) comparing the main protocols used within crypto.
Beanstalk (slide 18)
Beanstalk (slide 19)
As you can see above, the proving time, verification time, and proof size are critical to scaling different blockchains like Ethereum.
This section will be short and we’ll revisit this topic in the future. If you want to jump in right away, I recommend starting with Maksym’s paper.
The most intimidating part of ZKPs is definitely the “moon math” it’s built on top of. Fortunately, to build applications within the existing ZKP ecosystem there’s very minimal math needed. Over time this needed understanding will decrease eventually getting to ~0 like every other form of development.
From my current understanding (which will change over time) the minimal amount of math needed to gain an intuitive understanding of ZKPs would be Modular arithmetic and Polynomials. There’s a good prerequisites page here for the 0xparc course on ZKPs.
Well, it’s been fun, but we’ll leave it there for now. In the future, I will cover a series of topics relating to ZKPs, one of which will be the security issues due to that being a large interest of mine.
Also, we’ll narrow the scope to avoid the overwhelming topic that is ZKPs.
I’m a big fan of resource sharing, so here’s my gift to you.
I’ve created a master list of resources on ZKPs that I plan on adding to throughout this journey, which you can find here.
If you’re interested in receiving weekly email updates on things crypto security, crypto education, and weird things I stumble across throughout the week feel free to subscribe here or below!