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.
Let’s begin!
What is a “zero-knowledge proof”?
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.
- Proving to your color-blind friend, that you’re not color-blind (Wikipedia)
- Peggy proves that she knows the magic words to unlock a door within Ali Baba’s cave without sharing the secret words (Wikipedia)
- Solving a fake telecom company’s scaling issue by solving the graph-three coloring problem (Matthew Green)
- Proving that you know where Waldo is without giving up his location (0xSage)
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.
- Cut out: She cuts Waldo out of the image and hands Waldo to Bob. All done without sharing Waldo’s original location
- Overlay: She cuts a small hole in a sheet of paper, then overlays that on top of the image, only showing Waldo and nothing else. This still prevents Bob from seeing the exact location.
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).
- Soundness: everything that is provable is true. Assuming Alice doesn’t know Waldo’s locations and presents random pieces of the scene to her proof systems… then, her cardboard holes will display random images without Waldo. Put simply, Alice’s proof systems are truthful and do not let her cheat.
- Completeness: everything that is true has proof. As long as Alice finds Waldo, she’s able to consistently use her proofs to show Waldo, in each game. Put simply, Alice’s proof systems convince Bob that she found Waldo.
- Zero-Knowledge: only the statement being proven is revealed. As Alice proves to Bob that she has found Waldo, the only information revealed to Bob is that “Alice has found Waldo”. Waldo’s location is never revealed. Put simply, Alice’s proof systems prove her victory to Bob, without revealing her knowledge.
Why should I care?
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.
- Not Boring covers renting an apartment as an example, then briefly lists a series of more advanced examples such as establishing credit and enterprises that can use ZKPs while staying compliant.
- Maksym’s paper covers a series of theoretical examples on Pg. 1. Personally, I think the outsourcing computation example is pretty mind-blowing
“Outsource an expensive computation and validate that the result is correct without redoing the execution; it opens up a category of trustless computing”
- Amber Group wrote a piece covering the ZK roll-up ecosystem at a high level. The use of ZK roll-ups to scale Ethereum seems to be the most prominent in the crypto realm currently.
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.
What are the main elements of a ZKP?
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.
- SNARK: Succinct Non-interactive Argument of Knowledge (source: CoinCodeCap)
- Succinct: the proof is significantly smaller than the data it represents and can be verified quickly.
- Non-interactive: only one set of information is sent by the prover to the verifier, thus there’s no back-and-forth interaction.
- Argument of knowledge: the proof is considered computationally sound (a malicious prover isn’t likely to cheat the system without possessing the knowledge to support its statement). Same as STARKs.
- SNARK: Succinct Non-interactive Argument of Knowledge (source: CoinCodeCap)
- STARK: Scalable Transparent Argument of Knowledge
- Scalable – they are more scalable in terms of computational speed and size as proving time scales quasi-linearly; and, crucially, total verification + preprocessing time scales poly-logarithmically.
- Transparent – The “T” replaces the non-interactive property, which is what makes the biggest difference between SNARKs and STARKs. Meaning, STARKs, unlike SNARKs, don’t require a trusted setup.
- Note: Lots of jargon above, we’ll break it down in future posts. Also, note that SNARKs are faster in some aspects, but slower or more bloated in others, see tables below.
- STARK: Scalable Transparent Argument of Knowledge
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.
What “moon math” is needed to grok ZKPs?
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.
Resources
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!