Interactive proof systems were discovered in the 80s and are the foundation behind zero knowledge proofs. Although almost 40 years have passed, zero knowledge proofs only recently got more widely adopted with the advent of blockchains and non-interactive zero knowledge proofs. There exist many protocols implementing non-interactive zero knowledge proofs (or NIZK): zkSNARKs, zkSTARKs, zkSNARGs, etc. Here I will give a brief overview of what zkSNARKs are and where they can be found today.
(zk)SNARKs, an intuition
Informally speaking, in zero knowledge proof systems the Verifier learns nothing from the interaction with the Prover, except the information to conclude that the claim is true. In this context, the Prover is able to convince the Verifier that she knows a witness (a secret) without sharing that information. The zero knowledge proof systems introduced in my last post required multiple interactions between actors to properly function, but zkSNARKs don’t have that requirement.
Intuitively, a SNARK is a succinct and fast to verify proof that a claim is true. If zero knowledge is added to the definition, we get a zkSNARK. To illustrate it, consider that Alan is claiming the following to Brandon:
"I know a witness w such that SHA256(w) = 0"
Alan wants to prove Brandon that he knows a witness w such that the SHA256 hash of w is equal to 0, or SHA256(w) = 0. Alan is playing the role of the Prover and Brandon the role of the Verifier. The SHA256 primitive is a popular hashing algorithm that Brandon is also capable of running. The simplest way to prove the claim is for Alan to share w directly, but if w is too large (e.g, 1TB in size) it would be costly and slow to send it to Brandon, who would also need to take a significant amount of time to rehash the data to verify that SHA256(w) = 0, this is a waste of time and resources. The problem gets more convoluted if Alan can’t share his secret witness w openly with Brandon.
Thankfully, SNARKs can help them! Alan can use a SNARK system to create a succinct (small) proof. It will be cheaper and faster to send this much smaller proof to Brandon, who would be able to quickly verify and be convinced of Alan’s claim. Furthermore, Alan could use a zkSNARK protocol if he also needs to protect his secret from Brandon. The zkSNARK approach will ensure Alan that the proof reveals nothing about w to anyone.
Validity vs ZK proofs
Even though it is common to see the terms “validity proofs” and “ZK proofs” being used equivalently, they are two different things. Validity proofs are generated by SNARK systems, by applications that don’t need to hide their computation or its outcomes. On the other hand, ZK proofs actually use zkSNARKs and are employed by applications that need the zero knowledge property.
Why now?
In recent years there’s been a lot of commercial interest around (zk)SNARKs. The area has expanded dramatically, with new business models being created and new avenues for opportunities flourishing. But, why only now, if the core idea is almost 40 years old? Why did it take us so long to get to where we are? The main reason lies in blockchains! To explain this, let’s think about the key characteristics of SNARK systems:
- The Prover is a powerful computer, idealized to have unlimited computational power.
- The Verifier is a limited computer, very slow and expensive.
- The actors don’t need to trust each other when they use SNARKs.
As described by Moore’s Law, our computing power has increased exponentially in the last 40 years. For this reason, there was no clear use case for SNARKs because we could make the Verifier more powerful and cheaper in a matter of months. This changed when blockchains came up.
The picture above shows the daily average USD price users had to pay to send transactions on Ethereum in the last 3 years. In peaks of high on chain activity, it is common to see users having to pay hundreds of dollars just to get a single transaction prioritized first in a block, this is crazy! As you can see, L1 blockchains such as Ethereum can be considered a limited, slow, and very expensive computer. They fit the Verifier role in SNARKs systems very well.
Another reason for why (zk)SNARK proofs fit so well in blockchains is that they don’t require interactivity. Blockchains are distributed systems. They are P2P networks consisting of many nodes that often have to replay transactions from other peers to validate blocks. If the protocol required interactivity it would not suit blockchains well, as the Prover would have to interactively prove to every node on chain that the proof is valid.
Now that you learned what (zk)SNARKs are and why they suit blockchains like a glove, let’s explore some of their coolest applications. Even though scaling was the main reason for the initial wide adoption of SNARKs in blockchains, today there are many other promising cool approaches also available!
zkRollups
A zkRollup is used to scale L1 blockchains. It is the technology responsible for making SNARKs so popular! In a zkRollup, we move the hard computation work off-chain, normally to much faster L2 chains, while the L1 stays in charge of simply verifying the work done by the L2. Here is a general overview of the solution:
- The L2 chain processes transactions and creates blocks quickly.
- A Sequencer takes a large chunk of those transactions (maybe different blocks) and creates a batch of transactions. These transactions might also carry computation from smart contract executions.
- The Sequencer then uses SNARK system to create a proof for the correctness of the batch. This validity proof proves that the state transition happened correctly within the batch in the L2.
- The Sequencer (or another actor) sends the validity proof and the new rollup state to smart contracts sitting on the L1. The contracts are capable of verifying the proof and updating the state on the L1.
- Once the L1 contract verifies the SNARK, it can decide to accept or reject the new rollup state. The L2 state is normally handled by a different contract (aka rollup state) on the L1.
As you can see, a zkRollup is also a data compression mechanism as it reduces the amount of data L1s need to track due to the short size of SNARKs. Due to the fact that validity proofs are also quick to verify, smart contracts can check them cheaply. One last thing about zkRollup is that we don’t actually use zero knowledge in it, only validity proofs. Nevertheless, that’s the name that stuck with the community and it is what most people use today.
Today you can find many projects implementing zkRollups for different L1s: zkSync, Polygon, Scroll, Zeko (Mina), Aztec, and many others! Optimism, also known for implementing optimistic rollups, has recently shown interest in zkRollups as well.
zkBridges
zkBridges use SNARKs to enable interoperability in between blockchains with the goal of “bridging” their assets.
Here is a general overview on the application of zkBridges:
- A user wants to send an asset from a blockchain to another. To better illustrate this case, let’s assume that the user is sending Ether from Ethereum to Mina.
- The user interacts with a contract on Ethereum that locks his Ether.
- After the Ethereum consensus algorithm confirms the Ether has been locked, a SNARK that proves the Ethereum state of consensus is created.
- Another smart contract on Mina (aka a zkApp) verifies that the validity proof is valid and materializes the Ether (mEther sounds like a cool name) in the Mina ecosystem. The verification of the SNARK is crucial for Mina to be convinced that Ethereum really locked up the Ether before releasing mEther on its own chain.
In this solution, Mina (or the target chain) can quickly verify the short proof that the assets were locked up in Ethereum (or the source chain) instead of re-running the whole Ethereum consensus algorithm all over again. The SNARK in a zkBridge is a validity proof of the source chain consensus. Similarly to zkRollups, zkBridges conceptually also don’t need zero knowledge, the name stuck and it’s what most people use today.
Some projects implementing zkBridges are Telepathy, Mina, Mystiko, Electron zkBridge, zkIBC, zkBridge, and Zendoo.
zkOracles
Smart contracts from any blockchain depend on Oracles to access data that’s off-chain. An entire industry has developed around this fact, with Chainlink being one of the most notable projects in this domain. Unfortunately, smart contracts must trust that the Oracles consistently provide accurate information.
Most of the current projects use a consensus algorithm to handle the data their Oracles provide. For instance, in a price feed, if 10 Oracles provide different values for the price of Ether in USD a consensus must be reached before sharing the price of Ether. Slight variations in the Oracles’ reports are expected, as the Ether price change constantly and Oracles may not always access the price API simultaneously. Once there’s consensus among the Oracles around the price, an average of the values is taken, and the final answer is sent to the smart contracts.
There are sophisticated hacking tactics that can manipulate Oracles into giving token prices much lower than their real value, causing smart contracts to undersell. There are already mechanisms in place today to ensure that Oracles don’t deceive, but a robust network of Oracles with strong tokenomics, a well-tuned consensus algorithm, and multiple layers of security is essential for everything to run smoothly. Additionally, every time a new web2 API is added to Oracles blockchains, more Oracles and incentives are needed to ensure the process remains trustworthy. The following image gives an overview of the Oracles dynamics.
zkOracles have the potential to transform the Oracle industry using ZK proofs that mesh API responses with the execution of smart contract logic. For instance, Mina’s smart contracts (or zkApps) operate off-chain, and only the SNARK proof is uploaded to the blockchain. In this scenario, we could use zkOracles to fetch the Tesla stock price from a public API, perform complex off-chain Defi calculations, and then send the proof to the zkApp contract sitting on chain. The zkSNARK validates that the API response and zkApp execution are authentic and unchanged.
As of now, Oracles haven’t yet been capable of accessing Web2’s private user data. But with zkOracles, private data can be accessed securely! Using zkOracles, users could, for instance, access their bank accounts and prove they have over X dollars without publicly revealing any private details (like their balance, loans, credit score, etc). Unlike the other two applications mentioned earlier, zkOracles need zero-knowledge to maintain user privacy, so they employ ZK proofs. Without this zero-knowledge feature, zkOracles wouldn’t be able to handle private info appropriately.
zkOracles could revolutionize the entire financial sector, seamlessly bridging web2 and web3. They can pave the way for a new wave of innovative Defi applications. Regrettably, no project has yet to implement and deploy zkOracles successfully, although protocols like Deco are already setting the stage. Some projects currently exploring zkOracles include Mina, Chainlink, and Hyper Oracle.
zkGames
Everything that gets committed to a blockchain becomes public information. For this reason, only complete information games are suited for blockchains. In complete information games, the entire game state is available to all participants, examples are: chess, tic-tac-toe, and checkers.
There’s another class of games where players only have the knowledge of part of the game state. These are games of incomplete information, examples are: Poker, Battleship, Blackjack, most MMOs, etc. zkSNARKs can be used to bring incomplete information games to blockchains. The ZK proof hides the game state from other players while allowing the blockchain to quickly verify that the game state changes executed off-chain are valid.
In the image above you can see a snapshot of Dark Forest. Other examples of games using zkSNARKs on blockchains are: Zordle and zkSNARK Sudoku. The zkGames industry is still taking its first steps. As blockchain and SNARKs systems become more performant I expect zkGames to become one of the main narratives for web3 massive adoption.
Identity
New applications using ZK proofs are being built to prove the identity of users without revealing their private information on chain. Many interesting use cases can spawn from this idea, one that was recently released (currently on Polygon) is Worldcoin.
Worldcoin aims to establish universal access to the global economy regardless of country or background. It is designed to become the world’s largest human identity and financial network, giving ownership to everyone. All with the intention of welcoming every person on the planet and establishing a place for all of us to benefit in the age of AI.
Worldcoin uses zkSNARKs to prove that users are humans verified by their orb. Here’s how it works:
After the orb verifies you are a unique human, your identity commitment is added to a public list of verified humans. Everytime you want to prove you are a unique person, your World app generates a ZKP that proves you know the secret to an identity commitment, without revealing which one.
Other examples of applications using zkSNARKs for user’s identity are: Sismo, Humanode, iden3, Polygon ID, Sealance, and Clique.
Privacy
ZK proofs are also used to bring privacy to blockchains. Benefited by zkSNARKs, the computation may happen on a zkVM (or off-chain) and when committed to the blockchain its transaction won’t reveal any data. A ZK proof is used to prove that private the transaction (or computation) are actually valid (i.e., the smart contract executed correctly, there was no double spending, the transaction was properly signed, no money was lost, etc). The following projects are exploring this space: Semaphore, Manta, Tornado Cash, Penumbra, Aztec, ZCash, Anoma, and Ironfish.
zkML
Machine learning (ML) applications require significant computational power and sometimes also have to handle sensitive data. These needs are not currently supported by blockchains. Additionally, ML models need to be trained and tested before they are ready to provide predictions (or outcomes) during the inference step. To receive predictions, users provide input and run the inference step on a trained model. While tremendous value could be extracted from zero-knowledge proofs of the training step, this is by far the most resource-intensive and costly step in ML and doesn’t align with the performance of the most modern SNARKs systems available. Currently, zkML is only used to refer to proofs created for the inference step of ML models.
Most zkML applications utilize validity proofs, although some projects are starting to explore ZK proofs as well. Here are two use cases:
- Transparency in ML as a Service (MLaaS) through validity proofs: MLaaS providers are becoming increasingly popular with Google, Azure, and AWS as a few examples. However, much like other service/platform solutions, MLaaS are opaque black boxes to end-users. Users send inputs to a model through APIs that capture and execute the inference on the model, but behind closed doors. How can users trust they are getting predictions from the models they genuinely paid for? MLaaS providers can ensure this transparency by attaching validity proofs to their API responses. In this way, users can quickly verify that the results they receive genuinely come from the inputs they provided to the ML models they paid for.
- ZK proofs for privacy-preserving ML: zkSNARKs can be utilized to enhance privacy for critical ML applications, like in healthcare. Alongside the diagnosis, the ML model would also create a ZK proof that the patient’s private inputs (CT scans, blood tests, X-rays, etc.) correlate with the diagnosis without revealing the patient’s sensitive information given as input. These proofs could be verified by third parties, such as insurance companies, without needing to share any private data. Consider the case for disease detection:
A hospital takes a patient’s CT scan or X-ray, and sends the scanned image to the AI doctor. Then the AI doctor diagnoses the disease based on the image and returns the diagnosis result to the hospital and the patient. The integrity check of the AI results is required since incorrect results may endanger the life of the patient. The most straightforward approach to verify the result is to re-execute the same AI program. However, it is impossible in most cases since the AI weight parameters are important IPs and are not available publicly. In addition, the privacy of input data is another issue to consider. In our scenario, we allow the AI doctor to know the user’s input for diagnosis, but it may be desirable to hide the user’s private information when the diagnosis result is transferred to the third party such as an insurance company. In this situation, (with zkSNARKs) it should be possible for the insurance company to verify that the diagnosis result is correct without the private information of input data as well as AI weights.
What is next?
Blockchain interest and industry investments propelled the development of SNARKs systems in many ways. These systems were not so performant 10 years ago as they are today, they used to take a very long time just to generate proofs, even for very small statements. The key breakthrough in newer SNARK systems is happening in the development of much faster Provers. Newer systems are capable of generating proofs in linear (or quasilinear) time, mostly possible thanks to many interesting clever ideas coming from algebra. In the next post I will start covering these cool ideas as I introduce the design of modern SNARK systems.
I hope you enjoyed learning more about the history of SNARKs and all the different interesting applications they are enabling. Hopefully they inspired you to keep learning more! Até breve!