Intern Breakdown #4: Zero-Knowledge Proofs
Intern Breakdown #4: Zero-Knowledge Proofs
ZK proofs explained at 3 levels of depth (👶, 🐸, 🧠)
Zero-knowledge (ZK) proofs are like Su Zhu and Kyle Davies. They were born in the 1980s, but have only recently become a hot topic.
Now, you might be thinking:
- I’ve heard a lot about them, but what are ZK proofs really all about?
Or maybe you understand the basics, but want to know:
- What are the most promising projects using ZK proofs?
And I’m sure many people are thinking:
- Remind me again how SNARKs leverage polynomial commitments and the Fiat-Shamir heuristic to enable non-interactivity?
Let’s answer both the simple and the complex questions by breaking down ZK proofs for Normies (overview), Degens (use cases and projects), and Gigabrains (underlying tech).
Level 1: Normie
What are ZK proofs?
ZK proofs use cryptography to allow someone (a prover) to irrefutably demonstrate to someone else (a verifier) that a fact is true, without revealing any extra information besides the truth of the specific statement.
Here’s another good definition from Not Boring:
ZKPs essentially let someone prove that they know or have something without giving up any information about what they know or have.
Examples help to clarify what this really means:
I can use a ZK proof to certify the fact that I own a Little Rock NFT, without revealing which one I own, when I bought it, or how much I spent on it.
Someone could use a ZK proof to prove the validity of an Ethereum transaction that sends tokens from account A to account B, without revealing the token balance of either account or the amount being sent.
You could use a ZK proof to prove to the world that you owned tokens from not one, not two, but three Elon-Musk-themed meme coin rug pulls: Baby Musk Coin (January 2022), Baby Elon Coin (June 2022), and Saxon James Musk Coin (August 2022). Congrats on the trifecta.
ZK proofs were introduced to the world in a 1985 MIT research paper. One of the authors, Silvio Micali, would go on to found the Algorand blockchain. Like many technologies, ZK proofs first attracted mostly theoretical attention before ultimately finding practical uses after they’d been further developed and refined.
The earliest ZK proofs were interactive. To prove something, you had to play a game with the verifier. They were like a lie detector test — a ritual in which one party asks questions and the other answers until the truth has been established.
More recent (and more advanced) implementations are non-interactive. You can now generate a thing, a piece of data, that acts as your ZK proof, and you can submit it to a verifier without needing rounds of communication. These new ZK proofs are less like games/rituals/protocols, and more like unforgeable items that can be generated by a prover and submitted to verifiers.
What are ZK proofs used for?
There are two main ZK use cases:
1. Privacy: minimize the amount of data that’s made public as you conduct activities on the blockchain. Zcash is a prime example:
Like Bitcoin, Zcash transaction data is posted to a public blockchain; but unlike Bitcoin, Zcash gives you the option of confidential transactions and financial privacy through shielded addresses. Zero-knowledge proofs allow transactions to be verified without revealing the sender, receiver or transaction amount.
[Source: Zcash]
Other projects leveraging ZK proofs for privacy include IronFish, Worldcoin, and TornadoCash (famously “used” by big names like Brian Armstrong, Jimmy Fallon, and Dave Chappelle).
2. Scalability: allow intensive computations to be performed off-chain where it’s cheaper to do so, then create a concise proof that shows the computation was performed honestly. The proof can be published on-chain.
I like to think of this as technological division of labor. On-chain and off-chain systems get to specialize, focusing on what they do best. We can use centralized, high-performance, off-chain systems to process a whole bunch of transactions quickly and efficiently, then use a decentralized, immutable, trustless blockchain as the ultimate source of truth for recording who owns what.
Funnily enough, the usefulness of ZK proofs for scalability has nothing to do with their zero-knowledge properties. The ZK-rollup technologies we’ll discuss in more detail below often don’t care about hiding certain information from the verifier. They only care that the ZK proof is very small, and very quick to verify, relative to all of the off-chain transactions whose validity it’s proving. ZK proofs can do this thanks to an almost magical property: once they create a proof saying “yes, these billions of calculations were all solved 100% correctly,” verifiers can confirm the proof is correct without having the run the billions of calculations themselves.
There are plenty of ZK rollup projects focused on scalability (more on those in the next section), and there are also a handful of projects looking to simultaneously provide privacy and scalability, including Aztec and Espresso Systems.
The Hype
ZK proofs are a general-purpose technology. The past couple of blockchain bull markets have certainly helped drive investment into ZK R&D, but the first real-world applications of ZK proofs arose before Satoshi released the Bitcoin whitepaper. There are plenty of exciting ZK applications in the off-chain world — things like identity management, minimum age verification, anonymous credentials, ratings and risk assessments for financial investments, and digital voting.
All the ZK hype — for both on-chain and off-chain applications — is a good thing if it drives new use cases and pushes the technology forward. But we should expect this excitement to be cyclical. It will boom and bust as people’s short attention spans drive them to get bulled up on ZK while it’s hot, before sentiment inevitably turns ice-cold when they realize the tech isn’t 100% perfect yet.
Normie Additional Resources:
Level 2: Degen
ZK Rollups: The User Perspective
I’ve already mentioned how ZK-rollups work at a high level:
Instead of running computations on Ethereum which is slow and expensive, you do this work off-chain (i.e. on a layer 2 (L2) blockchain) ➡️ create a proof saying that you ran all the transactions honestly ➡️ publish the proof on Ethereum.
What does this actually look like for a user?
First, you find a ZK rollup project you’re interested in. Each will have its own separate ecosystems of apps and projects, so find one with some cool DeFi or NFT protocols you like.
Let’s assume the L2 uses Ethereum at its L1 settlement layer. It’ll have one or a few smart contracts on Ethereum which do a couple of important jobs:
Store all of the relevant data about what’s happening on the L2 chain (account balances, etc.). This contract might not have a perfectly live view of L2 blocks, but it should be close because L2 transactions aren’t considered official until they’ve been included in a rollup that’s stored on Ethereum.
Host the code that checks proofs to make sure they’re legit. When a rollup is submitted to Ethereum, the verifier smart contract makes sure the rollup’s proof is valid before making it official on the L1.
Need some analogies? The verifier is like the bouncer that makes sure rollups coming from the L2 are valid before it lets them onto Ethereum. Or, the blocks produced on the L2 are like sketchy independent science papers that make some claims, and getting checked by the verifier and added to Ethereum is like being peer-reviewed and published in a respected journal.
This might sound like we’re getting deep in the weeds, but understanding the basics of ZK rollup architecture is key to understanding why you have to do certain things to interact with ZK rollup projects. The basic user flow might look like this:
1️⃣ Send some ETH to the rollup project’s smart contracts on Ethereum, which stores/locks your funds up.
2️⃣ After a short delay, the L2 chain will hear that you’ve locked those funds, and it will unlock equivalent coins for you to use on the L2. This is a pretty typical bridging experience.
3️⃣ You play around on the L2 as much as you'd like using your tokens. You can swap 'em, invest 'em, use 'em to buy NFTs. Periodically (usually on the order of minutes), rollups are sent to Ethereum to finalize all the recent activities that have occurred on the L2.
4️⃣ Now you decide you want to withdraw your funds back to Ethereum. You’ve had fun playing on the L2 casino, but now you’d like to cash out your chips (L2 coins and tokens) for real money (ETH and L1 tokens). To do so, you send your L2 tokens to a burn address on the L2 chain, and wait for the rollup that proves you did so to get published on Ethereum. Once that’s happened, your funds that were locked in the Ethereum smart contract become unlocked, and you can reclaim them. Sounds complicated, but apps should make this entire withdrawal process as seamless as possible by abstracting away all the details.
Versus Optimistic Rollups
I won’t get into the details of optimistic rollups versus ZK rollups because there are so many articles out there that compare the two, but here’s a one sentence summary. Optimistic rollups take an “innocent until proven guilty” approach to transactions posted to the L1 (all transactions are considered valid by default, but anyone who observes a faulty rollup can call it out and earn a reward) whereas ZK rollups, as we’ve seen, require all off-chain computation to verify itself using validity proofs “at the door” before entering the L1.
There are pros and cons to each approach, but one major benefit of ZK rollups is that users can withdraw their funds onto the L1 much faster. After you initiate a withdrawal from an optimistic rollup, you must wait for a challenge period to expire (around 7 days) before your funds are unlocked.
Vitalik, for one, is long-term bullish on the ZK route:
In general, my own view is that in the short term, optimistic rollups are likely to win out for general-purpose EVM computation and ZK rollups are likely to win out for simple payments, exchange and other application-specific use cases, but in the medium to long term ZK rollups will win out in all use cases as ZK-SNARK technology improves.
— Vitalik (Jan. 2021)
Rollups vs. Validiums vs. Volitions
When a ZK rollup is published onto an L1, it includes both a proof that all the activity on the L2 was legit as well as a complete summary of all the changes to account balances on the L2 since the last rollup. This is crucial because when you want to withdraw your funds from the L2, you need to use that summary to say “this is what I did on the L2, which means I deserve to be able to withdraw X number of coins and tokens.”
There’s also something called a validium, which is basically a budget rollup. Validiums work almost the same as traditional ZK rollups, and they have the added benefit of being even cheaper and more scalable. What’s the catch? Security.
Validiums posted on an L1 don’t include all the data you need to prove you own funds on the L2 — that is, the data you need to withdraw your funds onto Ethereum. Instead, the data is stored off-chain. That’s not a problem if you trust the person/network/company who’s storing that data on your behalf, but you’d better be absolutely certain they’re reliable. Because if you have $1M stored on an L2 and whoever’s storing the data gets hacked and loses it, or gets told by the government to freeze it, or gets pissed at you because of something stupid you said on Twitter, then you might go to withdraw your money…
Or, more accurately, it’s locked up. Held hostage.
There’s an opportunity for a pithy “not your keys, not your coins” type of mantra here to spread awareness about the potential risks of validiums, but the best I can come up with is “data not available, your coins are assailable.” And no way that’s gonna catch on. So we’d better hope the validium projects that spring up keep good track of their rollup data.
Understanding the difference between rollups and validiums is even more crucial now that some projects are using volitions. These are marketed as a compromise between the two options — projects tout them as a way to “have your cake and eat it, too” or the “best of all worlds.” When L2s using volitions submit proofs to the L1 chain, they allow users to choose whether the data required for withdrawals is also published on the L1 or whether it’s stored somewhere else.
tl;dr: Validiums are cheaper than ZK-rollups, but they come with a risk of having your funds frozen on the L2. Projects using volitions let you choose whether you want to use validiums or ZK-rollups.
ZK Projects
There are waaaay too many projects leveraging ZK tech to list, but here are a few major categories and projects you’ll want to know about.
The zkEVMs
In the past month, a few different projects all made headlines by launching what’s called a zkEVM. The competition between these protocols has been called “The zkEVM Wars” and “The ZK Rollup Race,” and people were quick to call out the fact that each claimed to have beaten the others to the punch:
The three main players are Scroll, Matter Labs (creators of zkSync) and Polygon.
zkEVMs are a big deal because they allow ZK rollups to support many more applications than they can at the present. The first wave of ZK rollups allowed you to perform basic operations on super scalable and cheap L2s — things like sending ETH and transferring tokens. But with zkEVMs, developers can write any arbitrarily complex smart contract code and deploy it to ZK-powered L2s. Best of all, they can do so using the same Solidity code they’re used to using on Ethereum itself. Which means ZK-rollup L2s can now blossom into the crazy, convoluted, composable Wild West chains we all know and love.
Polygon
Polygon’s building a truly outrageous number of scaling solutions. It’s honestly hard to keep track of them all. They’ve been described as the “Swiss Army Knife of Scaling,” presumably based on this model:
This is their current line of products right now, four of which mention ZK proofs (including the zkEVM I just mentioned):
More info on each project can be found on their website — Polygon’s docs are pretty good, so I won’t bother reiterating the details here.
StarkWare
StarkWare is a company building ZK scaling tech that was founded by Eli Ben-Sasson, a true ZK gigachad. Eli co-invented STARKs (an advanced type of ZK proof) and is the founding scientist of Zcash. They have two main products:
StarkEx: allows applications to each build their own individual, permissioned ZK system. For example, dYdX and Immutable have used StarkEx to set up their own application-specific ZK projects for perpetual trading and NFTs, respectively. But these applications are siloed — there’s no composability across projects, so one StarkEx project can’t directly “talk to” another.
StarkNet: a more recent product that acts like a general-purpose blockchain. Any developer can create a smart contract and deploy it on StarkNet — it’s not permissioned, like StarkEx. Projects are fully composable with one another, and all transactions are rolled up and settled on Ethereum. I suspect you’ll be hearing a lot about StarkNet soon because its token is scheduled to launch in September 👀.
More info on StarkNet and Eli here:
The Big 🐕s (BTC & ETH)
Zcash, which I’ve already mentioned a few times, is a major chain in the privacy coin space. Given its similarities to Bitcoin, might we see BTC itself adopt ZK proofs to enable privacy? And what about Ethereum — could it take a page from the playbooks of L2s to use ZK proofs for scalability? In short: no for BTC, yes for ETH.
The early cypherpunks that created Bitcoin were big into privacy. Zooko, a co-founder of Zcash, thinks that BTC has lost its way when it comes to privacy given that most advanced users now accept that on-chain forensics allow transactions to be traced back to real-life identities. The Bitcoin community isn’t known for being receptive to new features so there likely won’t be major privacy upgrades any time soon, and Zooko predicts BTC will eventually fail (!!!) for this reason.
Interestingly, after doing some sleuthing in the sacred texts known as the BitcoinTalk forum, I found one of the discussions in which none other than Satoshi himself mentioned ZK proofs.
Unfortunately, ZK proofs were not advanced enough to support Zcash-level features at the time of this discussion, which is why Satoshi wrote them off:
This is a very interesting topic. If a solution was found, a much better, easier, more convenient implementation of Bitcoin would be possible.
…
It's hard to think of how to apply zero-knowledge-proofs in this case.
(August 11, 2010)
When it comes to Bitcoin and ZK proofs, the timing was just never right. The cryptography was too primitive to implement back when Bitcoin was young enough to adopt major features, and now BTC development has too much inertia working against complicated upgrades to justify its addition. C'est la vie.
Ethereum, however, is a bit more progressive when it comes to implementing new tech. In a recent post on zkEVMs, Vitalik mentioned that ZK proofs could “make it much easier to verify the Ethereum chain itself” and shouted out Ethereum’s Privacy and Scaling Explorations team who’s working on just that. After all, there’s no reason why L2s should have a monopoly on ZK tech. But let’s not get ahead of ourselves — Ethereum moves preeeetty slow relative to smaller, nimbler projects.
Degen Additional Resources:
Level 3: Gigabrain
Quick disclaimer before diving into the specifics behind ZK solutions: I’m no certified gigabrain myself, so for super in-depth breakdowns of the math behind ZK proofs you should check out the resources section below. Shockingly, undergrad CS and math courses aren’t sufficient to fully grok the inner-workings of this stuff (after all, it was considered “moon math” until just recently by experts in the field), but I know how to throw around acronyms and that’s half the battle when it comes to sounding smart.
Fortunately for me, anyone who claims to truly understand ZK proofs is probably a liar, and is definitely way too smart to be reading a meme-packed Substack post.
SNARKs — A Succinct Breakthrough
SNARKs are a type of ZK proof that first came on the scene in 2011 and helped enable many real-world applications. Most ZK projects out there right now leverage SNARKs, making it an important concept to grasp if you want to understand the ZK landscape from a technical perspective
It’s a nice piece of trivia to know that SNARK stands for “Succinct Non-Interactive Argument of Knowledge,” but it’s more useful to understand what they do:
💨 “Succinct” means the proofs are much smaller than the total sum of all the computations they represent. You can take a whole bunch of transactions that would normally need to be individually recorded on the Ethereum blockchain, for example, and create a SNARK that proves their validity in only a few hundred bytes.
📄 “Non-interactive,” as explained earlier, means you can use one computer to generate a proof that acts as an unforgeable certification of something (e.g. your account balance on an L2 blockchain) which you can submit to another computer/smart contract that will verify it.
🤫 ZK: Like all ZK proofs, they let you prove something while sharing the least amount of information possible.
💨 Speed: Since these proofs are so small, they can be verified very quickly.
🗝 Security: One major downside of SNARKs is that the computers that do the proving and the computers that do the verifying have to agree on a set of parameters called the Common Reference String (CRS). To cook up the CRS you need to use a source of randomness (entropy), and these random numbers are extremely powerful. If a bad actor found out about them, they could create any arbitrary proof and fool the verifier into thinking it’s valid. That’s why any legitimate project using SNARKs makes sure to destroy these random numbers as soon as they’ve been used.
Zcash, for example, designed a complicated ceremony that had several people participate in the creation of the CRS. As long as one of the participants was honest and destroyed their contribution to the entropy, the system was secure. In theory, if the random numbers had been leaked, an attacker could have found them and turned on Zcash god mode — counterfeiting coins, double spending, and wreaking havoc. The Zcash team took every precaution to avoid this, and if that sounds cool to you, I highly recommend their <5 minute video explainer or this Radiolab podcast.
STARKs vs. SNARKs
STARKs are the younger sibling to SNARKs — they’re newer and have different tradeoffs. Vitalik has a whole series on STARKs that cover them in depth, so I’ll settle for mentioning the main differences between these two flavors of ZK proofs:
Proof size: STARKs are larger than SNARKs, which also means they cost more to verify on Ethereum since bigger proof = more computation = higher gas fees.
Scalability: STARKs are generally considered more efficient than SNARKs, depending on the implementation. The scale of complexity for proving and verifying STARKs grows quasilinearly with respect to the complexity of the computation being proved, while the complexity grows linearly for SNARKs. This means STARKs have an even greater edge over SNARKs when proving larger computations.
Ecosystems and Projects: Many more projects are using SNARKs than STARKs since SNARKs have been around for longer.
Recursion: SNARKs support recursion — you can create a parent SNARK that proves multiple child SNARKs — which is a major feature used by many scaling solutions. STARKs do not support recursion.
Quantum Security: SNARKs use Elliptic Curve Cryptography (ECC), which is not quantum safe. Advancements in quantum computing could leave SNARK-based systems open to attack. More likely, they’ll just need to be updated at some point in the near future. STARKs are not vulnerable since they rely on hash functions for their encryption schemes.
Trusted Setup: As mentioned earlier, SNARKs require a trusted setup during the creation of a CRS. STARKs avoid this inconvenient problem by leveraging publicly verifiable randomness to produce the parameters shared by provers and verifiers.
It’s important to note that these characteristics are constantly evolving. New SNARK-based schemes have emerged recently to address the weaknesses of traditional SNARKs — more info on some of those here:
ZK EVM Tradeoffs
For anyone — devs in particular — who cares about the nitty gritty aspects of the zkEVM products mentioned in the previous section, it’s worth highlighting that not all zkEVMs are created equal.
The main tradeoff these projects have to make is between compatibility with Ethereum and performance. So-called “EVM-equivalent” zkEVMs are able to verify programs that run in an environment that’s exactly like normal Ethereum. Scroll, for example, isn’t just compatible with the EVM at some high level of abstraction like the Solidity programming language, it’s compatible with the EVM at the byte-code level. This is important because it makes the developer experience on Scroll virtually indistinguishable from developing on Ethereum itself, right down to the use of complicated debugger tools that examine individual opcodes. It also allows for the re-use of familiar and battle-tested Ethereum clients like geth, and it means that the zkEVM can draft on upgrades to Ethereum itself with minimal extra work needed from the project.
Compare this to “EVM-compatible” zkEVMs which are not quite as rigorous when it comes to harmonizing with the EVM. These zkEVMs take smart contract code written in, say, Solidity and compile it into a format that’s been optimized for ZK proofs. Taking this approach allows for code to run more efficiently, but it throws out a lot of Ethereum’s existing infrastructure. The geth client, for example, is known to have certain limitations, which is why teams like zkSync have replaced it with other software written in Rust.
One member of the zkSync team described the two types of zkEVMs like this: if you’ve got Photoshop software running on a Windows computer and you want to now run it on a Mac, you could either (a.) re-compile the Photoshop code so that it’s optimized for Macs, or (b.) run a Windows emulator on your Mac, and have that emulator run the Windows version of Photoshop. It’s obvious that (a.) would be more efficient.
This view is admittedly biased and ignores some of the benefits offered by greater compatibility, but it’s a pretty good analogy. At this point, it’s too early to tell which approach will ultimately prove the better strategy, so we should just be glad that there’s a diversity of experiments happening in parallel. If this topic is interesting to you, this Immutable X article is a great deep dive and offers this helpful graphic:
Gigabrain Additional Resources:
🎦 An Evolution of Models for Zero-Knowledge Proofs with Sarah Meiklejohn | a16z crypto research talks
📚 ZK Proofs Overview: SNARKs vs. STARKS vs. Recursive SNARKs (Alchemy)
The buzz around ZK proofs, along with other promising cryptographic technologies whose details I won’t get into here (homomorphic encryption, decentralized identifiers, verifiable credentials), lead me to believe we might be on the cusp of a “crypto, not blockchain” movement similar to the “blockchain, not Bitcoin” narrative of years past. Even some Bitcoin maxis and Web3/blockchain skeptics point to the continued development of innovative ZK proof techniques as one redeeming quality of (what they consider) otherwise worthless alt chains.
All that to say — ZK proofs are exciting for a number of reasons, and we’ll be hearing a lot about them in the next few years.
Ooooor maybe it’ll turn out that all this moon math is totally made up and we’ve been conned by an industry-wide conspiracy. After all, a lot of these cryptographic explanations of ZK proofs sort of sound like…
Fantastic read!
STARKs support recursion! https://medium.com/starkware/recursive-starks-78f8dd401025