In this post, we explain in detail how zk-rollups and optimistic rollups work.

A Rollup is a layer 2 scaling solution that runs on the top of the Ethereum blockchain. But what is a layer 2 technology?

Basically, layer 2 is a secondary framework that built on top of the layer 1 (for example; Ethereum blockchain). These technologies depend on the existing blockchain for security purposes but in order to enhance the scalability level, they are being used by the current existing blockchains. Some layer 2 solutions such as Plasma, Rollups connect with Ethereum main chain, and to interact with off-chain activities, the smart contracts are being added on the main chain. By offloading the transaction from layer 1 to layer 2, we can make a large amount of transactions per second.  Right now, the Ethereum blockchain supports only ~15 transactions per second which is much smaller as compared to VISA (~65000 𝑡𝑝𝑠) and PayPal (~1000 𝑡𝑝𝑠).

The main advantage of layer 2 technology is the reduction in the amount of data storage on the main blockchain while managing the scalability and decentralization.

Figure 1 given below is taken from https://golucidity.com/layer-2-blockchain-technology/ shows the evolution of blockchain into multiple layers. The Lucidity protocol can be a lightning network that sits on the top of Ethereum blockchain.

Concerning scaling, there are two options. 

• We can directly increase the processing capacity on the base layer (main chain) called onchain scaling. Technical solutions are Sharding and DAG.
• Some part of the work is done off-chain and we can transfer it to the base layer once it is completed. Technical solutions are State Channel, Plasma, and Rollups.

Plasma

Plasma is a lightning network for Ethereum which is a system of smart contracts. It is a scalability method that place layer 2 on the top of the main chain in form of a side chain. It allows hundreds of transactions offline by creating the series of smart contract on side-chain and only the total balance of all the transactions given as a single hash of the side chain block is sent to the main blockchain. There is a well-known and indeed true meme on plasma:

“𝐶𝑟𝑒𝑎𝑡𝑒 𝑏𝑙𝑜𝑐𝑘𝑐ℎ𝑎𝑖𝑛 𝑖𝑛 𝑏𝑙𝑜𝑐𝑘𝑐ℎ𝑎𝑖𝑛, 𝑖𝑛 𝑏𝑙𝑜𝑐𝑘𝑐ℎ𝑎𝑖𝑛 𝑤𝑖𝑡ℎ 𝑟𝑜𝑜𝑡 𝑏𝑙𝑜𝑐𝑘 ”

No doubt, plasma is a good solution to enhance the scalability on blockchain but it has some drawbacks like:

• Centralization: since the off-chain computations are managed by some authorities therefore a central component is required to operate plasma.
• Withdrawal duration is approximately 7 to 14 days. 

Transactions in plasma are not instant, instead one has to wait for ~ 15 or 1 hours for each interval unless the operator (relayer/aggregator) generates the batch (block). Another problem with plasma is that it is a “full layer 2” technology which mean that both the data and computations are done off-chain therefore, it is impossible to implement it securely for all applications. The issue of data availability is solved by Rollups!

Rollups is a “hybrid layer 2” technology scheme in which the computation and state storage is done on side-chain while some data of each transaction is kept on the main chain.

Rollups

The concept of rollup dates back to 2014, it is an off-chain aggregation of transactions performed inside Ethereum smart contract. It not only reduces the transaction fee but also allows more than 1000 transactions per second. It guarantees the security and publish a highly compressed data onchain such that any user can reconstruct the state, for example account balance. In simple terms, every user must have a facility to reconstruct the full state of the system by scanning the history of the chain.

Rollups are based on the idea of Shadow Chain where the execution of the state is done off-chain while using the Ethereum blockchain for the data availability. There is a smart contract on the main chain (Ethereum blockchain) which maintains a state root. Now, what is this state root?

State root is a Merkle root (obtained from the Merkle tree) of the state of the rollup as shown in figure 3.

Merkle tree, given in the diagram above consists of the transactions received from several different users. It hashes to the universally acknowledge root “0x3217fe” which is a current state root. The Merkle tree is not stored directly inside the main chain rather only the state root is kept but the Merkle tree can be retrieved from the on-chain data.

Anyone can publish the rollup block called the batch. Each batch consists of the compressed transaction + previous state root + new state root (Merkle root after processing the transaction). Besides this the rollup contract checks if the previous state root given in the batch matches its current state root, if it holds then it updates the state root to the new state root. Here is how it looks like:

In short, the main chain holds funds and a succinct cryptographic commitment, and the side-chain usually has a Merkle tree of accounts, balances, and their states being operated by users and operators. 

You might be confused with some strange terms like succinct cryptographic commitment or Merkle tree etc. Don’t worry! We will discuss it in section 4, it is just an introduction. 

Basically, there are two very wonderful types of rollups called “zk-Rollups” and “Optimistic Rollups”. Both of these have their own way of construction but at some points they are similar, both have their own benefits and drawbacks but yes! the most interesting thing about zk-rollups and optimistic rollup is that zk-rollups are based on cryptography and optimistic rollup gets the flavor of game theory. 

Therefore, before we dive into these layer 2 technologies, let us briefly introduce some important cryptographic primitives that are essential for these technologies. So! What are these primitives?

• Zero Knowledge proofs:

Zk-Rollups deploy zero-knowledge proofs for the generation of proof and its verification. To be more precise, it relies on zk-SNARKs proofs which is “zero-knowledge succinct non-interactive argument of knowledge” and this universal type of zero knowledge proof actually works behind the zk-rollups, this is what we mean by “succinct cryptographic commitment”. To know about zkSNARKs, please see the post by Vitalik Buterin at https://medium.com/@VitalikButerin/zksnarks–under–the–hood–b33151a013f6. 

• Merkle Tree:

Another concept is about the Merkle tree, which you have already seen in the diagrams above. The blockchains are typically made up of hundreds of thousands of blocks, and each block contains several thousand transactions, therefore memory space and computing power are the main issues that need to be solved. The idea is to use less amount of data while processing and verifying transactions. This is the point where the Merkle tree comes in. Merkle trees take a large number of transaction IDs and run them through a mathematical process that results in one 64-character single code, called a Merkle root (in our case state root). The Merkle root offers a quick way to verify if a specific transaction took place correctly on a certain block.

There are several benefits of using the Merkle tree ranges from proving the integrity and validity of data, simplified payment verification, etc. If anyone tries to change any leaf node, it will result in a completely different hash that reaches a completely different final hash (merkle root) so we can detect the changes. Now let’s see, how to construct the Merkle tree? Merkle tree is a tree structure where every leaf node is a hash of the data and every non-leaf node is the hash of its children nodes that results in a single hash called the Merkle root as can be seen in figure 5 given below.

Now the question is how we can check the validity and integrity of the data? Without going into depth, we will give a quick solution by considering an example where Bob received the Merkle root from Alice. Now Bob wants to check the validity of some particular transaction, let say he wants Alice to prove that the transaction 𝑇₅ has not tempered with. To prove this, Alice will send

𝑇₅ along with these hashes: 𝐻₆, 𝐻(𝐻₇, 𝐻₈) and 𝐻(𝐻₁, 𝐻₂, 𝐻₃, 𝐻₄) rather than sending all the transactions or hashes as shown in figure 6.

Bob will simply generate a hash of 𝑇₅ (using 𝑆𝐻𝐴 − 256 cryptographic hash function) and append all hashes of transactions together to compute the merkle root. If both of them are same then it means that Alice has not tempered with the data at any step. Exactly, it is that simple.

Alright! Now we have grabbed some knowledge about some cryptographic primitives, it is time to jump into zk-rollups first!!!   

ZK-Rollups

Zk-rollup proposed by Barry Whitehat (2018) is a layer 2 scaling solution in which all the funds are held by the smart contract on the main chain. The computation and the storage are done off chain, and the validity of the side chain is proved by using the zero knowledge proofs. Accounts and balances are represented by two separate Merkle trees to ensure the security of the data. The roots denoted by “state roots” of both accounts and balances based on the Merkle tree are kept in a smart contract on the Ethereum blockchain which can be updated by sending a valid proof. Hence, prove provides the succinct (very small in size that we can easily store it inside the blockchain) representation of off-chain computation and the rest of the data is kept off-chain.

The rollup smart contract verifies each state transition before finalizing it on the block, once it is verified then the security of all the transactions inside the particular block are the same as if you have done transaction directly on the main blockchain.

Zk-rollup contract will only accept the new state if and only if the previous state matches the most recent state saved in the rollup contract. Also, it will verify the zk-SNARKs proof, if the verifications hold it will save the new state. This is how the zk-rollups compress and stores the user state (for example account balance) on-chain while zk-SNARKs ensures the correctness of the off-chain transition. The transition cost is very high on the blockchain, however the amount to verify the zero knowledge proof on-chain is very low that is why we generate the proof off-chain and verify it on-chain.

There are two main actors involved in zk-rollups: 

• User (transactors)
• Aggregator (operator/relayer/prover)

Users have their accounts on the Ethereum blockchain, they sign their corresponding transactions using the secret key and send it to the operator. On the other hand, the operator collects and verify each transaction then aggregates all the transaction and put them inside the batch, and generate a succinct zero knowledge proof called SNARKS for every single state transition. Finally, the operator submits the zk-SNARKs proof, compressed transaction and state root of the new user state to the smart contract on the main chain which is then verified by the rollup contract on the main chain. Therefore the aggregator cannot steal the user’s funds in any way. 

The SNARKs prove that there exists a series of transactions that update the account balance correctly starting from the previous merkle tree to the new merkle tree and is correctly signed by the user.

Unlike plasma, the data availability feature of zk-rollup allows users to withdraw their funds anytime and also they do not need to monitor the network all the time to check if everything is working correctly because of the validity of the proof.

Now let’s see it step by step:

State Transition Function (STF): 

On receiving the transaction, the operator will execute it which will change the status of the corresponding account. The state transition function is use for this purpose. Assume that the initial state is denoted by 𝑆₀, once an action 𝑇₁ is applied on the current state, it updates the state to 𝑆₁ written as:

𝑆₁ = 𝑆𝑇𝐹(𝑆₀, 𝑇₁)

Suppose there are 𝑁 actions 𝑇₁, 𝑇₂, … , 𝑇_𝑁 on the state so it will keep updating. Generally, we can write the state update process as:

𝑆_𝑁 = 𝑆𝑇𝐹(𝑆₀, 𝑇₁, 𝑇₂, … , 𝑇_𝑁)

If we talk in term of previous state and post state then, the above equation can be written as:

𝑃𝑜𝑠𝑡 𝑆𝑡𝑎𝑡𝑒 = 𝑆𝑇𝐹(𝑃𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑆𝑡𝑎𝑡𝑒, 𝑇₁, 𝑇₂, … , 𝑇_𝑁)

State of Accounts:

The state of all the accounts is managed by the Merkle tree. The leaf nodes of the Merkle tree represent the users’ account status and the root of the tree is used for the state root. In practice, there are two Merkle trees in zk-rollups, one for the address book and the other one is for the balance.

A simple Ethereum transaction takes ~110 𝑏𝑦𝑡𝑒𝑠 whereas an ether transfer using zk-rollups takes only ~12 𝑏𝑦𝑡𝑒𝑠. A rough estimation of the compressed transaction is given by Vitalik in his article:

Parameters	Ethereum	Rollups
To	~ 21 𝑏𝑦𝑡𝑒	~ 4 𝑏𝑦𝑡𝑒𝑠
From	~ 0 𝑏𝑦𝑡𝑒	~ 4 𝑏𝑦𝑡𝑒𝑠
Nonce	~ 3 𝑏𝑦𝑡𝑒	~ 0 𝑏𝑦𝑡𝑒𝑠
Gas	~ 3 𝑏𝑦𝑡𝑒	~ 0 − 0.5 𝑏𝑦𝑡𝑒𝑠
Signature	~ 68 𝑏𝑦𝑡𝑒	~ 0.5 𝑏𝑦𝑡𝑒𝑠
Value	~ 9 𝑏𝑦𝑡𝑒	~ 3 𝑏𝑦𝑡𝑒𝑠

Proof:

When the user initiates the transaction, the current state will be changed. But there are some rules to follow while changing the state root.

1. Check if the user has a sufficient balance to pay for the transfer fee and the handling fee.
2. The nonce of the transferred account should be valid.
3. Check if the signature is correct (one used to sign the transaction).

If everything is correct, then the operator process the transfer and modify the account in the merkle tree and calculates the root of the new merkle tree (this gives us the post state root). Using this method, the operator will process the multiple transactions in sequential order and submit the final state root obtained from the final calculated merkle tree to the smart contract.

But there is a problem with the steps above. How do we get to know that the post-state root in the batch is correctly computed by the operator? Remember that the correction of post-state root in the batch means that all our transactions are correct and have been updated honestly. Here comes the role of zero knowledge proofs. Once a series of transactions are collected by the operator, he will generate a zk-SNARKs proof (change in the state is hashed and used as an input of the SNARKs that gives proof for each transaction in the rollup block) based on zero knowledge proof as:

1. For the given transactions 𝑇₁, 𝑇₂, … , 𝑇_𝑁, check the correctness of value, fee and signature (zk-rollups use Edwards-curve Digital Signature Algorithm (EdDSA)).
2. Check if: 

𝑃𝑜𝑠𝑡 𝑆𝑡𝑎𝑡𝑒 = 𝑆𝑇𝐹(𝑃𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑆𝑡𝑎𝑡𝑒, 𝑇₁, 𝑇₂, … , 𝑇_𝑁)

If both steps are satisfied, then the operator submits:

1. zk-SNARKs proof.
2. 𝑃𝑜𝑠𝑡 𝑆𝑡𝑎𝑡𝑒 (new State root)
3. Compressed transactions: 𝑡₁, 𝑡₂, … , 𝑡_𝑁 (without nonce and signature)

Verification:

Once the proof is submitted to the main chain, the smart contract verifies if the proof is valid. If the proof is correct and the current state root in the contract is the same as the previous state then previous state root will be replaced by the post-state root.

Because of zk-SNARKs proof, the operator cannot steal the users’ transactions and since only  𝑡₁, 𝑡₂, … , 𝑡_𝑁 transactions are saved without signature and nonce on the main chain therefore the size of the data gets smaller. Since data is available on-chain, therefore users can withdraw their funds from the chain if any operator refuses to serve.    

Optimistic Rollups (ORUs)

Optimistic rollup (ORUs) is an alternative to zk-rollups which does not rely on zero knowledge proof for the verification. Instead of checking the validity of every single transaction, optimistic rollup assume that all transactions and computations are correct by default until someone submits a “fraud proof” stating that the transaction is incorrect. 

Like zk-rollups, optimistic rollups also have an operator called “aggregator” who accumulates a large number of transactions and publishes them to a smart contract on-chain. Anyone can become an aggregator by placing deposits (bond) in the smart contract.

The term “optimistic” is used because the aggregator (operator) publish only a very small amount of information without the proof, assuming that the aggregator runs the rollup without any fraud and the proof is required only in case of fraudulent activity. While the term “rollup” states the commitment of transactions to the main chain in form of bundles. Finally, the transactions on ORUs are stored in a smart contract on Ethereum blockchain. Any new rollup can be challenged if the aggregator submits an invalid transaction. Hence, optimistic rollups rely heavily on game theory and trust in the sense that an aggregator will act honestly otherwise he will lose his deposits.

To give an overview of ORUs, Let’s try to understand the procedure of optimistic rollups using the figure 10 given below:

Here we have an Ethereum main chain and we have some smart contracts on Ethereum main chain representing our optimistic rollup. What happens here exactly? Users send their transactions to someone in the system. “Someone” means an aggregator that can be anyone depending on the number of assets he has on the blockchain. The aggregator will take this transaction and possibly many other transactions too and produce a state update. When the aggregator gets many sufficient state updates, he put it in a block and registers the block on the rollup contract.

Anyone can commit to the block on the rollup contract by including the three elements as a commitment transaction to the smart contract on-chain:

1. Block transaction data.
2. Security deposit (bond).
3. Block header consisting of the hash of the previous block header, state root using merkle tree, and transaction root that increase the efficiency.

The aggregators add the bond so if they will try to post an invalid transaction in the block, they will lose their bond. The aggregator creates a merkle tree of the rollup block to submit as a block on the Ethereum mainchain, and the validity of the transactions can be proved easily due to the commitment to transactions and their intermediate state roots. 

How ORUs work in steps?

1. User sends the transaction to the aggregator using off-chain.
2. Aggregator locally deploy the transaction and
   1. Computes a new state root (Merkle root).
   2. Creates Ethereum transaction consisting of the state root.
   3. Creates a new smart contract.
3. Since the ORUs does not compute the proof against the transaction therefore we need some method to check if all the transactions are correct and no one cheat. For this purpose, we rely on “fraud proof”. As blocks are added to the rollup chain, the summaries of the transactions that exist inside these blocks are added to the main chain so all users can keep an eye on the summaries. Any user that monitors the aggregator and detects fraud (can be an invalid state root created by an invalid transaction) can challenge an invalid update by posting the fraud proof consisting of the valid state proof and the Merkle proof. Therefore, the waiting time of the transaction being confirmed on the main chain is longer (~7 𝑑𝑎𝑦𝑠) as compared to the zk-rollups since it can be challenged.
4. Science of Fraud Proof: 

Consider the same figure that we use for zk-rollups:

A fraud proof claims that an invalid block (batch) can contain the data in red, that is:

• The batch can be check against the hash stored on-chain (previous state root).
• Parts of the Merkle tree required to prove those specific accounts which are modified by the aggregator to create the batch.

This is how the merkle tree works! so the given data is sufficient to execute the batch and to compute the post-state root, if:

𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝑑 𝑝𝑜𝑠𝑡 − 𝑠𝑡𝑎𝑡𝑒 𝑟𝑜𝑜𝑡 ≠ 𝑝𝑟𝑜𝑣𝑖𝑑𝑒𝑑 𝑝𝑜𝑠𝑡 − 𝑠𝑡𝑎𝑡𝑒 𝑟𝑜𝑜𝑡

Then the block is invalid.

“In simple terms, the technique is the same as in zk-rollups. The contract create the state root of the transaction and verify the resultant root against the transaction root sent by the aggregator as a commitment transaction in block header”

5. Once the fraud proof is finalized and an invalid block is confirmed, the smart contract verifies that proof and revert that block (batch) and all the blocks after that, and resume from the last non-fraudulent block. But what will happen with the aggregator?

The aggregator will be punished for submitting an invalid block. Not only the block will be reverted back to the point where the fraudulent block was posted but the bonded stake (security deposits) provided by the aggregator while posting the invalid block along with all the following blocks after the fraudulent block will also be grabbed. Half of the security deposits will be burned and half of it will be paid as a reward to the prover to submit the fraud proof.

A valid side chain block provides the same guarantee as the main chain since the optimistic rollup cannot be reverted once finalized.

Data availability: ORU uses the classic rollup method to guarantee the data availability of the current state. For this purpose, aggregators pass all the blocks consisting of transactions and state roots through “calldata” on-chain. The calldata is merkalized and finally, a state root of 32 𝑏𝑦𝑡𝑒𝑠 is stored. 

Scalability: ORU process ~100 transactions per second using the Elliptic curve digital signature scheme (ECDSA) but it can go to ~500 transactions per second if Boneh–Lynn–Shacham digital signatures (BLS) are used.

Comparison between zk-rollups and optimistic rollups

Optimistic Rollups	Zk-Rollups
Long waiting time on the mainchain for the finalization of the transaction due to the fraud challenges (7 days).	Instant withdrawals based on data availability.
Someone needs to be online to check the validity of batch and publish the fraud proof in case of invalid block.	No need to monitor the network all the time because of the validity of the proof.
All transactions are recorded on-chain therefore, any user can recompute the full state.
Validity mechanism: Fraud proof.	zk-SNARKs Proof (Succinct proof generation time: ~20 𝑚𝑖𝑛𝑢𝑡𝑒𝑠).
Increase in scalability: ~200 − 2000 𝑡𝑝𝑠	~1000 transactions per second.
Good for general purpose EVM computation.	Good for simple payments and exchanges but in future it will win out with the increase in the efficiency of zk-SNARKs
Fixed cost per batch (~40,000) so a batch can be posted more frequently.	Cost per batch: ~500,000
The complexity of technology is lower.	The complexity of technology is higher due to zk-SNARKs
On-chain gas cost is higher per transaction.	Gas cost is lower (on-chain transaction).
Cost of off-chain computation is low.	Off-chain computation cost is high (zkSNARKs).
Rely on trust and game theory	Based on cryptography.
Security is based on 1-out-of-N participants (who execute all ORUs transactions and publish a fraud proof if any state transition is invalid.) and strong censorship-resistance of layer 1 network.	The state transition is verified by the rollup contract before it becomes effective.
Zk-rollups have more scalability gain as compare to optimistic rollups. The reason behind that is we have less data on-chain in zk-rollups because we only need enough data on-chain to update the state tree whereas, in ORUs we need to have enough data on-chain to verify the full computation which is a slightly large amount of data.

References

[1] https://vitalik.ca/general/2021/01/05/rollup.html  

[2] https://medium.com/interdax/ethereum-l2-optimistic-and-zk-rollups-dffa58870c93  

[3] https://medium.com/plasma-group/ethereum-smart-contracts-in-l2-optimistic-rollup2c1cef2ec537

[4] https://medium.com/matter-labs/optimistic-vs-zk-rollup-deep-dive-ea141e71e075