Everything you need to know about ZK-Rollups (Part1)
Ethereum Scaling solutions are considered essential tools to manage network performance challenges. The previous article was dedicated to optimistic rollups (part1, part2), in this series of posts we will be addressing zero-knowledge rollups as one of the practical L2 existing solutions and learning how they effectively work.
Introduction
Rollups are layer 2 scaling solutions that enable blockchains to validate transactions faster and cheaper. It performs by combining many transactions to execute them off-chain at once and then submits them as one transaction on Ethereum’s blockchain.
There are two types of rollups: optimistic rollups and ZK rollups. The main difference between the two types of rollups is in how the state transition is verified on-chain. While optimistic rollups lean on fraud proofs, zk-rollups use zero-knowledge proofs to verify the state transition and to perform computation and storage off-chain, then sends a batch of transactions to Layer 1, where they are instantly validated or rejected.
Optimistic rollups represent a major problem of time. There must be enough time to send fraud proof and verify that there are no fraudulent transactions in the batch before the transaction can be verified on the mainnet. This process can take about 7 days which means users have to wait a long time to execute their transactions. Therefore, a new Rollup technique was developed and named ZK-Rollups.
In this article, we will mention the different improvements brought by this second type of rollup.
Zero-Knowledge Proof
In order to fully understand how it works, we have to start by learning the main concept behind ZK-Rollups which is ZKP (zero-knowledge proofs).
Introduction
ZKP stands for zero-knowledge proofs. It represents a way to prove that you know something without revealing what it is that you know.
There are two types of ZKPs:
- Interactive zero-knowledge proofs: require a prover and a verifier to interact together, there are rounds involving queries and answers between the prover and verifier to make sure that the prover actually has the knowledge.
- Non-Interactive zero-knowledge proof: direct communication between the prover and verifier is unnecessary. A prover generates proof that can be validated by any verifier with no further interaction.
Whatever the type of a ZKP is, it’s actually based on those properties:
- Completeness: if an honest prover convinces an honest verifier, then the statement is true.
- Soundness: If the prover is dishonest, he can’t trick the verifier.
- Zero-knowledge: The verifier will not know what data is behind the proof.
1. Computational integrity
Verifiable computation, also known as proof of computational integrity, is a cryptographic protocol allowing a user or a client to prove a calculation, or more generally, a program’s execution by computing a proof. The proof is then provided to a verifier who can ensure that the program has been executed correctly.
To do this, almost all verifiable computation schemes follow the same protocol. First, they transform the function that must be proven into bounded-degree polynomials. This step transforms the discrete steps of a program where an error is local and hard to detect into polynomials that will undergo many changes if a step is not correct or respected. The error is then much easier to detect. However, simply checking these polynomials by giving them to a verifier is not easier than redoing the computation of the program itself.
The hardest part is then cryptographically proving that the polynomials are indeed of low degree without revealing them. If the polynomials were not of low degree, the prover would have been able to choose the polynomials after the execution of the program and create fake proof, breaking the protocol.
Most verifiable computation schemes can be classified into one of two categories: SNARKs and STARKs.
2. ZK-SNARK
ZK-SNARK is a protocol for generating proofs to verify ownership of specific knowledge without exposing the underlying data.
ZK-SNARKS stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.”
- Succinct: The size of the proof in zk-SNARKs is smaller than the size of the statement being proved.
- Non-interactive: Don’t require rounds of interaction between the prover and verifier.
- ARgument: A weaker notion of a mathematical proof where we assume the prover has bounded computational resources. For obvious reasons, this makes ZK-SNARKs ideal for blockchains.
- Knowledge: The prover cannot construct a proof without knowing a particular witness for the statement, this would be the equivalent of knowing “what to look for”, or “what to decode”. For blockchains, this ZK-SNARK feature is incredibly important, since we want the information to remain secure and private.
A ZK-SNARK consists of three algorithms G, P, V defined as follows:
- G (Key Generator): takes a secret parameter lambda and a program C to generate two public keys, a proving key “pk” and a verification key “vk” that need to be generated once for a given program C
- P (the prover): takes as input the proving key “pk”, a public input “x” and a private witness “w”. The algorithm generates a “proof” that the prover knows a witness “w” and that the witness satisfies the program.
- V (the verifier): computes V(vk, x, proof) which returns true if the proof is correct, and false otherwise
To construct zero-knowledge proofs with ZK-SNARKs, a set of public parameters is needed, along with the creation of cryptographic keys which are ensured by a trusted setup.
2.1 Trusted Setup
A trusted setup is a procedure that involves more than one party. It aims to produce the standard parameters that a proof system or similar cryptographic protocols rely on. A trusted setup is generated in two phases:
- Setup phase: The setup phase is done only once, produces generic setup parameters, thereby enabling the main phase.
- Main phase: Once the main phase is activated, this enables all participating parties to interact with a single trusted party repeatedly. Individuals send inputs to the trusted party, which’s job is to run certain functions, after which the trusted party sends the corresponding output to the respective participating parties.
As the participants need to be trusted for the setup to fulfill its purpose, this process is called a trusted setup.
Based on the different dynamics that can take place at this time, a typical trusted setup should fit into one of the following categories:
- No setup: This is the simplest case, in which we don’t really use any trusted entity or any trusted setup.
- Pairwise setups: Here we assume there is some set of initial parties, and each two parties have a reliable communication channel between them.
- Broadcast setups: We assume a setup whose implementation requires no secrets.
- Partially public setups: Often called the Common Reference String (CRS) model.
- Fully private setups: Often called the offline phase in the context of secure multiparty computation (MPC) protocols.
The ZK-SNARK relies on trusted setup ceremonies to collaboratively generate their cryptographic parameters. In these ceremonies, SNARKs use a common reference string (CRS) to encode all necessary information for proving and verification without interaction. The CRS is created during a setup phase, and afterwards, both the Prover and the Verifier can access it.
This procedure must be run to generate the proving and verification keys. Generating SNARK public parameters is basically equivalent to generating a public/private keypair, keeping the public key, and destroying the private key referred to as “toxic waste” to ensure the protocol remains false Proof.
In order to reduce the risk of an attacker acquiring the toxic waste, we use Multi-Party Computation (MPC) protocol that runs the trusted setup in a decentralized way, this responsibility will be shared among all participants of the setup.
Each participant separately generates one shard of the public key, which requires them to temporarily use a corresponding private key shard. They all combine their public key shards to generate the final public parameters, and then each deletes their private key shard.
If at least one participant is honest and deletes their part of the toxic waste, then no fake proof can be created by anyone.
The entire event, from generating random values to creating a structured reference string (parameters), destroying them, etc. is known as a trusted setup ceremony.
2.2 Proof generation steps
In the following section, we will describe the ZK-SNARK proof generation process. It works in a few steps, from computation to arithmetic circuit to rank-one constraint system (R1CS), to quadratic arithmetic programs and finally to its homomorphic hiding in order to build a zero-knowledge proof.
- Arithmetic circuit: Turning the computation (transaction validity function) into a mathematical representation is to break down the logical steps into the smallest possible operations, creating an “arithmetic circuit”.
The computation can be represented by a polynomial, that can be flattened to a circuit where each gate takes two inputs. Each gate corresponds to one of the constraints.
- Rank 1 Constraint System (R1CS): This step consists of converting the flattened constraints into 3 sets U, V, W of n vectors of length m + 1, where n is the number of constraints (gates), and m corresponds to the number of variables.
The R1CS was translated into 3 sets U, V, W of m + 1 polynomials of degree n − 1:
U = [u0(x), u1(x), . . ., um(x)]
V = [v0(x), v1(x), . . ., vm(x)]
W = [w0(x), w1(x), . . ., wm(x)] - Quadratic Arithmetic Program (QAP): The process involves encoding the R1CS into polynomials, and particularly, the form of QAP (Quadratic Arithmetic Programs).
In order to enable checking all the constraints simultaneously, polynomials from each of the 3 groups will be combined into a single polynomial, resulting in 3 polynomials U(x), V(x), W(x).
Equation should hold: U(x) · V(x) = W(x)
Let us define new polynomial, a so-called target polynomial:
S(x)= U(x) · V(x) − W(x)
Meaning that S(x) = 0 for x ∈ {0, 1, . . ., 6}. That also means that there is a polynomial H(x), such that: S(x) = H(x) · Z(x) where
Z(x) = (x − 0) (x − 1) . . .(x − 6).
The single constraint that needs to be checked is now between polynomials rather than between numbers.
2.3 Homomorphic hiding and the zero-knowledge property
Up to this point, we have yet to encrypt our input to satisfy the “zero-knowledge” requirement. With ZK-SNARKs, sophisticated mathematical techniques such as homomorphic encryption and pairings of elliptic curves are used to evaluate polynomials “blindly” without knowing which point is being evaluated.
To hide the coefficients of the polynomial H(x), the proof will not consist of the vector of the coefficients of H(x). Instead, it will contain the evaluation of H(x) at some random point τ unknown to the Prover. If the prover knew in advance which point the verifier would choose to check, they might be able to craft polynomials that are invalid, but still satisfy the identity at that point.
The point τ will be unknown to all parties, but the homomorphic hidings E(τ), E (τ 2), E (τ 3). will be available to everyone. The public parameters described above are used to determine which point will be checked, but in encrypted form so that neither the prover nor the verifier know what it is. This enables the Prover to use the homomorphic hiding of the evaluation of the polynomials U(x), V(x), W(x) and H(x) at τ.
As a result, the polynomial that needs to be verified only contains an encrypted version of the original data. However, the Verifier can still check the equality, only operating on encrypted objects.
2.4 Proof verification
Now, we have gone so far as transforming the initial program into a secured polynomial that contains information about the original function.
To prove the validity of the polynomial equality
U(x) · V(x) − W(x) = H(x) · Z(x) (already encrypted through pairing) is true, SNARK Verifier does not directly plug in the solution in principle, the Verifier has to check that: E(U(τ)) · E(V(τ)) − E(W(τ)) E(Z(τ)) = E(H(τ)).
2.5 Proof generation techniques
The reality is that zkSNARKs can be reduced to four techniques:
- Encoding as a polynomial problem
The program that is to be checked is compiled into a quadratic equation of polynomials: t(x) h(x) = w(x) v(x), where the equality holds if and only if the program is computed correctly. The prover wants to convince the verifier that this equality holds. - Succinctness by random sampling
The verifier chooses a secret evaluation point s to reduce the problem from multiplying polynomials and verifying polynomial function equality to simple multiplication and equality check on numbers: t(s)h(s) = w(s)v(s)
This reduces both the proof size and the verification time tremendously. - Homomorphic encoding / encryption
An encoding/encryption function E is used that has some homomorphic properties. This allows the prover to compute E(t(s)), E(h(s)), E(w(s)), E(v(s)) without knowing s, she only knows E(s) and some other helpful encrypted values. - Zero Knowledge
The prover permutes the values E(t(s)), E(h(s)), E(w(s)), E(v(s)) by multiplying with a number so that the verifier can still check their correct structure without knowing the actual encoded values.
3. ZK-STARK
Due to their transparency and scalability, ZK-STARKs are thought to be an upgrade over ZK-SNARKs.
Since they can function without a Common Reference String’s (CRS) trusted setup, ZK-STARKs are considered transparent. To establish the criteria for creating and checking proofs, ZK-STARKs relies on publicly verifiable randomness.
Additionally, ZK-STARKs offer greater scalability because the time required to demonstrate and confirm the veracity of validity proofs rises quasi-linearly with the complexity of the underlying computation.
Regarding quantum computers, ZK-STARKs are also impervious. The downside of ZK-STARKs is that they produce larger proof sizes, which are more expensive to verify on Ethereum.
ZK-STARK is an acronym for Zero-Knowledge Scalable Transparent Argument of Knowledge. Just like ZK-SNARKs, ZK-STARKs show a statement is valid without revealing anything about the statement itself.
- ZK: Like in “ZK-SNARKs”, this also means “zero-knowledge.
- S: This means “scalable”, highlighting how these zero-knowledge proofs focus on enhancing blockchain scalability. ZK-STARKs enable developers to execute computation and store data off-chain, increasing scalability exponentially.
- T: Stands for “transparent”, and this quality marks one of the most significant differences between ZK-STARKs and ZK-SNARKs. They use publicly available randomness to generate parameters, eliminating the need for a trusted setup.
- ARK: “Argument of Knowledge” implies the same as in zk-SNARKs but uses a different computation approach. They use hash functions resistant to collisions, effectively eliminating the need for trusted setups.
ZK-STARK technology is more recent than ZK-SNARKs, and it was pioneered by Starkware with rollup solutions. Using ZK-STARKs, one can compute several thousands of transactions in batches off-chain and submit a sole ZK-STARK proof to confirm the transactions’ validity on-chain.
Proof generation steps
When it comes to steps to generate a proof zk-stark is different from zk-snark:
- Instead of R1CS, Zk-Stark uses AIR (Algebraic Intermediate Representation), to represent the mathematical problem that the proof is trying to verify.
- Since we need to transform the mathematical representation into some polynomial that can be evaluated ZK-Stark propose a Two steps approach Constraint system encodes the calculation -> Execution trace values.
- For the last part which is the encryption of the input to hide it zk-stark uses Shamir’s Secret Sharing Scheme.
4. SNARK vs STARK
Both zk-STARKS and zk-SNARKs are types of non-interactive ZKPs. However, they are different from various perspectives, as discussed in the table below:
5. Recursive proof
Recently, StarkWare announced the very first recursive proving being live on Ethereum Mainnet. In this part we will talk about the main idea and the key features behind this solution.
5.1 Non-recursive proving
Before we dive in, let’s take a side back to go over some of the terminologies.
Starkware employs SHARP machine which enables any computational program to be efficiently proven as STARK-based validity proofs
SHARP — a SHARed Prover /Stark prover — is a big machine shared among multiple applications who send their job requests (multiple statements), and then Sharp is computing one big proof for all of them together in one single STARK-proof and this proof is sent to an on-chain verifier smart contract.
As shown in the following figure, five statements are sent to SHARP (possibly from two different sources like StarkEx and DeFi) and these statements are proven individually.
On the one hand, we note that the proof computation starts obligatorily after the reception of the last statement, which implies that the total computation time is approximately equal to the sum of the proving times of each statement.
On the other hand, Available compute resources such as memory eventually limit proving extremely large statements. This was effectively the limiting scalability barrier of STARK proving before recursion.
Cairo programs proposed by Starkware allows expression of general computational statements that can be proven by STARK proofs and verified by the corresponding STARK verifiers.
This is where the opportunity to perform recursion kicks in: In the same way that we write a Cairo program that proves the correctness of thousands of transactions, we can also write a Cairo program that verifies multiple STARK proofs. We can generate a single proof attesting to the validity of multiple “up-stream” proofs. This is what we call Recursive Proving.
In the next section, we will review this mechanism and its essential features.
5.2 STARK recursive proving with simple program
let’s take a simple example to understand recursive Proving on STARK with a simple program as input to the SHARP.
The following steps resume the process of proving of the program A with some input X.
- Step 1: SHARP gets jobs that are a program A with the input X
- Step 2: SHARP takes the input program and generates a single STARK-proof (Proof A)
- Step 3: The verifier program verifies the generated proof (Proof A)
- Step 4: SHARP gets the verifier program with Proof A as input
- Step 5: SHARP now proves the verifier program and generates a single STARK-proof (Proof RA) –R for recursive)
- Step 6: in this time the verifier program verifies the generated proof and there’s another verifier call program is sent to SHARP and for another round of proving and we have a proof for the verification of the verification of the program and so on (step 7+8+9)
- Step 10: This results in one proof attesting to all proof statements. This proof can then be submitted on-chain, verified by a Solidity verifier smart contract on layer 1.
5.3 STARK Recursive proving with Statements example:
In this example, we will show how to prove two statements (1 and 2) recursively using SHARP machine and verifier program. SHARP can prove statements upon their arrival.
- Step 1: SHARP generates proof 1 for statement 1.
- Step 2: While the verifier program is verifying proof 1, statement 2 arrives at SHARP for proving.
- In a parallel way, SHARP generates Proof 2.
- Step 3: The verifier program verifies the proof 2
- Step 4: The pair verification of proofs (1 and 2) is sent to SHARP for proving. The resulting proof (proof 12) is sent to the on-chain layer 1 verifier
We note that in the case of the arrival of the two statements simultaneously, SHARED will generate one proof and send it to the layer 1 verifier.
Recursive improves the latency of proving, the total computation time is approximately equal to the proving time of the last statement plus the time it takes to prove a Recursive Verifier statement.
With recursion, the computational resources barrier (e.g., memory) that limited proofs size up until now, is eliminated, since each limited size statement can be proven separately. Hence, when using recursion, the effective size of the recursion is almost unlimited, and the cost per transaction can be reduced by orders of magnitude.
After you have finished reading about ZKP, you are now ready to learn all about zk-rollups in the second part of the article.