Intro
In blockchain narrative, the term “zero knowledge” entered our vocabulary when rollups first emerged. In particular, we’ve heard it a lot in the context of zero knowledge rollups (ZK-rollups). But, zero knowledge technology has existed for years before. The first article on zero knowledge was published back in 1989.
In this blog, we’ll break it down to clarify what zero knowledge (ZK) is and what it ISN’T (the latter might actually be more interesting than the former). We’ll investigate if ZK-rollups have any ZK for real, and if not, why they get to use the term at all, and dive into the difference between ZK as a technology and ZK as a marketing term.
For those who need answers right away:
- ZK-rollup provides a succinct verification mechanism
- But ZK-rollup does NOT provide privacy
*by privacy we mean (i) user privacy (transaction sender and recipient), (ii) data privacy (payload of the transaction, e.g., the asset or value being transacted), and (iii) code privacy (the program logic).
Now let’s dive a bit deeper.
Zero Knowledge Property Outside of Rollups
If we want to discuss ZK in a rollup context, we first need to understand zero knowledge property on its own. As we mentioned above, the concept of ZK was introduced in 1989 (years before the first blockchain was baked) in a paper titled, “The knowledge complexity of interactive proof systems.” It wasn’t until around 2018 that the Ethereum community figured out ZK might be a good fit for a rollup universe.
We usually consider zero knowledge as a property of a proving system. In blockchain, we often say ZKP, meaning zero knowledge proof. But “proof” might mean proof of statement or proof of knowledge. So, in the next section of this article, we will differentiate between the two types of proofs.
Proof of Statement
Proof of statement proves that a statement is true without revealing anything about the statement itself.
Examples of statements:
- z is a square modular n: z = x^2 mod n
- The graphs G and H are non-isomorphic
- The number 638634389........3427 has 3 prime factors
Proof of Knowledge
Proof of knowledge proves that the person making an assertion has some knowledge about the statement.
So, if we look at the examples from the previous paragraph side-by-side:
One should note that every proof of knowledge is a proof of statement (but not the opposite). For instance, if one proves that they know a value x such that z = x^2 (mod n), this will be proof of knowledge, but it also automatically proves that z is a square modulo n (proof of statement).
Let’s explore one of these examples to see how proof of statement and proof of knowledge can be constructed!
Exploring Examples: the Graph-Isomorphism Problem
Let’s use the graph-isomorphism problem. To do this, we’ll say proof of graph non-isomorphism will be proof of statement, while a proof of graph isomorphism will be proof of knowledge.
What Is the Graph-Isomorphism Problem?
Basically graph isomorphism (denoted by ≅) is the following: two graphs with labeled nodes are isomorphic if they are "the same" up to a permutation of the labels. That is to say, there exists a permutation of the labels of one graph that results in the other graph.
More formally, we say that two graphs G and H are isomorphic if there is a bijective function f between the vertices’ labels of G and H such that there is an edge between the vertices u and v in G if and only if there is an edge between the vertices f(u) and f(v) in H.
An example of two isomorphic graphs:
If there exists no such permutation, we say that the two graphs are non-isomorphic. Now, assume we want to prove that two graphs are non-isomorphic. We only want to prove this single fact; nothing about the graphs themselves, no other knowledge except for the statement that they are non-isomorphic.
Example of A Proof of statement: the Graph-Non-Isomorphism Problem
Proof intuition:
- If there are two non-isomorphic graphs G and H, one randomly chooses a permutation π (re-orders elements in a deterministic way) as well as randomly chooses one of two graphs, and calculates K = π{G or H} that is K is a permutation of either G or H.
- If G and H were isomorphic, anyone else should NOT be able to tell from which of the two graphs K was computed, and could only guess.
- The probability of guessing would be ½. Repeating the protocol enough times makes the probability of guessing negligible.
One round of protocol:
Example of A Proof of Knowledge: Graph Isomorphism
Now, let’s think… What if we want to prove two graphs are isomorphic? In other words, the Prover wants to prove that they know the isomorphism σ such that H = σ(G).
Proof intuition:
- If σ is an isomorphism between two graphs, it means that H = σ(G) and G = σ^{-1}(H) where σ^{-1} is the reverse isomorphism.
- Let π be a permutation randomly chosen by the Prover. Using ρ = πσ^{-c} (where the Verifier randomly assigns 0 or 1 to c), they get either ρ = π or ρ = πσ^{-1}.
- By applying ρ = π to a graph, one will get its permutation. By applying ρ = πσ^{-1} to a graph, one will get its permuted reverse isomorphism:
One round of protocol:
Back to Zero Knowledge!
Now that we’ve explored examples of proof of statement and proof of knowledge, let’s discuss whether or not they have zero knowledge property.
Informally, zero knowledge means that a Verifier can’t retrieve any additional information from a Prover (except for the information clear from the proof itself).
In the example of graph isomorphism, proof of knowledge is zero knowledge (with honest Verifier). According to the protocol, the Prover doesn’t reveal any information on the isomorphism or permutation to the Verifier. Instead, they send the Verifier commitments and that’s it.
However, in the example of the proof of graph non-isomorphism, it’s not zero knowledge. Because, instead of setting K = π(G) or K = π(H), a malicious Verifier (i.e. a Verifier which deviates from the protocol) can set K = π{RANDOM GRAPH} and as a result of the protocol execution by the Prover, the Verifier will know if RANDOM_GRAPH is isomorphic to either G or H. So the Verifier is definitely able to retrieve additional information.
Can we convert our proof of graph non-isomorphism into zero knowledge? Yes, we can. The Verifier should also provide proof that (i) the graph it sends is isomorphic either to G or to H (meaning the graph they’re sending is not arbitrary), and (ii) they know the isomorphism.
One should note that most protocols in the space are only honest-verifier ZK (i.e. ZK property doesn’t hold with malicious verifier). However, this isn’t an issue because the protocols are made non-interactive with the Fiat-Shamir heuristic. Hence – there is no distinction for non-interactive protocols as the verifier cannot "misbehave.”
Now, when we differentiated between proof of statement and proof of knowledge and saw that both of them can have zero knowledge property or not have it, let’s take a look at ZK-rollup and figure out (i) does it use proof of statement or proof of knowledge, (ii) does it have zero knowledge property?
Finally, Back to ZK-Rollups!
In a ZK-rollups, the logic is pretty similar to the graph-non-isomorphism problem (where we prove the statement that two graphs are non-isomorphic). In ZK-rollup, we prove the statement that the state transition was done correctly.
A Glimpse into How ZK-Rollups Work
In this section, we’ll briefly cover how ZK-rollups work and how they utilize proofs. By “ZK-rollups,'' we mean regular (i.e. NON-privacy-preserving) ZK-rollups such as Scroll, Starknet, zksync, Taiko, and many more.
The main use of “vanilla” ZK-rollups is to enable scalability by posting a single proof of the validity of transactions.
ZK-rollups execute transactions off-chain and post proof on L1 (Ethereum) that whatever they did off-chain was done correctly. Their purpose is to prove that the new chain state is correct.
To generate a proof of correct state transition, one needs to prove that all transactions were executed correctly on given inputs.
For the sake of this, the Prover needs to know previous state and input values.
However, for the Verifier to verify the proof, they need to have the proof as well as to know new state, previous state, and input values:
Inputs
There are two types of inputs, public and private. In ZK-rollups, “private input” does NOT mean “secret” even though they are called “private.” Instead, it means that private inputs are consumed by Prover only while public inputs are consumed both by Prover and Verifier (sometimes private inputs are also called “witness” as a reference to the NP complexity class). Public inputs are expensive as they need to be submitted to L1 hence we want it to be as small (“succinct”) as possible. In terms of what these inputs consist of in the context of the proof:
Public inputs (consumed by Prover AND Verifier) – all data that needs to be submitted to L1 so that everyone can update their records of the current state. This will include new state root as well as might include signatures, sender, receiver, functions, contract addresses, function arguments, newly-deployed contract data, storage slots which have changed and their new values, events that were emitted. One should note that this reveals A LOT of information to a public observer. The specific list of public inputs will depend on the specific ZK-rollup design.
Private inputs (consumed by Prover ONLY) – all information that was needed by rollup circuits to prove correctness of the state transition. This will include Merkle membership proofs (hash paths) as well as the execution trace (might include transaction inputs such as newly-deployed contract data, storage slots which have changed and their new values, and events that were emitted).
As you can see from the logic above, private inputs have nothing to do with privacy. So if a ZK-rollup is generating a proof that Alice sent Bob 1ETH, both the Prover and the Verifier will be aware of this information (i.e. no privacy at all!).
To sum it up, in the case of a ZK-rollup, we want to prove the validity of transactions, it is a proof of statement and it does NOT have zero-knowledge property because all the information (i.e. state, functions, inputs) is public and everything that is not provided explicitly can be derived by a Verifier.
That is to say, there is no ZK in a vanilla ZK-rollup. Why is it called ZK-rollup then?
.png)
Maybe… For the sake of marketing =)
And Still, Can ZK Provide Privacy?
Short answer: yes, it can. While the main use of “vanilla” ZK-rollups is to enable scalability, the main use of Aztec is to enable scalability AND allow privacy. And, it utilizes ZK exactly for the privacy purpose.
Aztec provides privacy by means of client-side proof generation, i.e. whatever should be processed privately is processed on the user’s device and then a proof of its correct execution is supplied to the mempool.
Processed privately means that
- Transactions are processed privately (on user’s device)
- Their outputs shroud side effects (such as note hashes and nullifiers)
- And those get added to the global state without revealing any information to anyone except for (i) the client who executed transactions and emitted side effects, and (ii) the receiver of side effects (for example, in case of a transfer from Alice to Bob, Alice executes transactions client-side and emits side effects and Bob receives side effects).
Client-side proofs are then verified by the sequencer (who manages the mempool).
In this case, client-side proof is a zero knowledge proof of statement: the sequencer verifies the proof validity without any information about what was executed on the client-side, and is unable to retrieve any information about it.
After client-side proofs have been verified by the sequencer, everything is similar to a vanilla ZK-rollup mechanism as described in the previous section. That is to say, Aztec ZK-rollup first generates a number of client-side proofs (which are zero knowledge proofs) and then a block proof (which is not zero knowledge).
One Can’t Just Add ZK to Get Privacy
It’s not possible to add privacy ad-hoc to an already existing ZK-rollup. It should be designed to be private from the very beginning.
One first needs to give a precise definition of “privacy” as the statements proved, depending on the rollup design, may reveal unnecessary information and harm user privacy.
If builders want their dApps to interact with the external world; meaning that dApps aren’t monolithically private but instead allow some functions and variables to be private while some functions and variables stay public (e.g. necessary for AMMs, lending protocols, etc.), rollup state management becomes very non-trivial. Now it has to process public and private state updates separately. However, it’s exactly the latter approach that unlocks dozens of use cases we’ve been dreaming about for years! (Think programmable on-chain identity management and DeFi alternatives to conservative financial institutions).
As of today, Aztec is one of very few privacy-preserving L2s on Ethereum where privacy is provided by processing private information on the client-side. Check out this article to dive into client-side proof generation and this article to learn more about Aztec smart contracts anatomy allowing for hybrid private and public state management.
Ready to join Aztec’s building pioneers? Let us know by filling out this form.
{{blog_divider}}
Many thanks to Palla, Patrick, and Brecht for review.
