ZK Rollup & Optimistic Rollup

0
156

ZK Rollup & Optimistic Rollup (En)

ZK Rollup is not a new idea. It was proposed by Barry Whitehat about a year ago. At the same time, Vitalik has a relatively complete article in the EF Research forum. The implementation is being developed by Matter Lab and Iden3. After deep diving into zk-SNARKs, I haven’t had time to look at ZK Rollup until recently. In addition to the ZK Rollup, let’s take a look at the Optimistic Rollup that was firstly introduced by John Adler.

When ZK Rollup was proposed, it was defined as a layer 2 solution. At the beginning of this year, it was published under the name Plasma Ignis. That’s because Plasma was very hot, and there have been a lot of progress last year, and it was also defined as the layer 2 solution. For these reasons, developers have named the Plasma. But this technology was completely different from the spirit of Plasma. After being protested by the community, it was later restored to the name Rollup (the developer’s statement), so searching for ‘Plasma Ignis’ would not find anything. Recently, Rollup was renamed semi-layer 2 solution, which is a little layer 2 but not so layer 2… XD

A brief explanation of ZK Rollup is the layer 2 solution where the data is placed on-chain. Before you understand ZK Rollup, let me explain what is problem of the original layer 2. Take Plasma as an example, Plasma only puts the hash of the Plasma block on the Ethereum main chain. Which means transacting hundreds or thousands of transactions off-chain, and only a few dozen bytes on-chain. This is the idea of Plasma, but it is also the most difficult part in the design — data availability.

If someone wants to leave Plasma chain, they need a mechanism to withdraw the money. In Plasma, it is called the exit game (there is no data on the main chain so the side chain participants need to provide evidence), which means everyone has to save amount of data to challenge. Compared to the experience with the main chain, only need a wallet, download block data is not necessary. The user experience in Plasma is not good enough. Another problem of challenge period is that users need to stay online all the time to challenge someone, or they may lose money if they miss the challenge period (because using fraud proof, instead of validity proof). In short, because of the availability of data, it has the following problems:

1. Users need to be online frequently
2. Need to download some data

It causes an awful user experience.

How to put data on-chain without occupying large space?

First, let’s explain the overall architecture. Like Plasma, there is a smart contract to deposit. There are relayers to help send the transaction to the smart contract (called the operator in Plasma). In addition to sending the transactions, the relayers need to generate the SNARK proof, and send the proof together for verification.

The smart contract part can be imagined as ERC20, the balance of each participant is recorded in the contract. The difference is that an ECR20 transaction is a standard transaction which means only one ‘transfer’ is allowed in every single transaction. In Rollup, hundreds ‘transfer’ would be packaged into one transaction. The contract can disassemble these ‘transfer’ and verify.

In the smart contract, two merkle trees are used for the record. One is to record addresses, so only an index can represent an address (the value of unregistered index is zero), In the design, using 3 bytes length index, the amount of an address is reduced from the original 20 bytes to 3 bytes. The other tree records balance and nonce.

Merkle Tree of Addresses

Here is the data format(This is the initial proposal, it’s smaller in current implementation),

Because the index is used as the representative of the address, only 3 bytes (2²⁴ addresses) are needed, and the base unit of Value 10^-6 ETH, so that only 15 bytes represents a transaction. It only costs 892 gas (although the Value is 6 bytes, but the assumption in the article that most transactions will only use 4 bytes, so the algorithm is 13 bytes * 68 + 2 bytes * 4 = 892), and the ETH transfer costs 21K gas, so the transaction speed can be improved.

https://vitalik.ca/general/2019/08/28/hybrid_layer_2.html
Why can the transaction speed increase? Also to understand the calculation of transaction speed

Today, the gas limit of a block is about 8M, so if everyone simply does ETH transfer on Ethereum, the speed is about

8M / 21K / 15 ~= 25 tps

So, the current bottleneck is gas limit. If you lower the transaction fee or increase the gas limit of a block, you can get a better transaction speed (but it also causes other problems). ZK Rollup, by reducing the amount of transaction data, can increase the transaction speed. Let’s see how fast the transaction can be after using ZK Rollup.

(8M — 600K (zk-SNARK proof) — 50K(overhead)) / 892 / 15 ~= 550 tps

This number is the header of the Vitalik article “On-chain scaling to potentially ~500 tx/sec”. But in fact it is not so ideal. In the author Barry’s implementation, it is only about 268 tps. Because once an account balance is updated, the smart contract throws an event and it is extra gas cost. However, such a design is also more friendly for applications.

The data is on-chain, and verified by zk-SNARK, which means the on-chain data is verified. So there are such problems had in layer 2 as mentioned, need to challenge, need to download data and so on. This also implies that there is no need to trust relayers, because they couldn’t do anything bad. In the worst case, they just stop sending your transaction .

The reality is what we expect…

zk-SNARK is like a panacea, it seems to solve everything, but it is not so perfect. In addition to the trusted setup, the biggest problem is that it requires a lot of computing power. In the data provided by Barry, if the relayer’s computer is an 7G memory plus a 20G hard disk swap, it probably only produces 20 tx/sec. It’s far less than the expected 500 tps. So the biggest problem with this solution is how to solve the calculation problem.

Parallel Compution!

Matter Lab proposed a multi-operator model and parallel computation. Multi-operator model, like small blockchains, uses DPOS (Delegated Proof of Stake), and randomly pick block producers. The selected block producers can collect transactions, generate a proof and submit. This approach also avoids centralization. If the relayer is maliciously attacked, the entire network can still operate. On the other hand, it also paves the way for parallel computing. The generation of zero-knowledge proof is very time-consuming. Therefore, based on the multi-relay model, Matter Lab proposed a two-stage “commit-verify” approach. Blocks are first committed on chain, their verification with SNARK proof follows (as shown below). With some data optimization , the result can reach 1600 tps.

https://medium.com/matter-labs/introducing-matter-testnet-502fab5a6f17

Latency…

It sounds wonderful, but because your transaction is split in two stages, it takes several blocks from the time of delivery to the verification. The latency will be longer than the current situation. Of course, how long latency is acceptable to the user is not known at the moment. It is a trade-off, saving the transaction fee, increasing the transaction speed, but also increasing the commitment latency. All this is still known until the solution is online.

Earlier this year in Taipei, Vitalik talked an advanced version of ZK Rollup — ZK ZK Rollup. Refer this article for more details.

Plasma & Optimistic Rollup

The idea of Optimistic Rollup came from John’s post in EF research forum. Here, I only introduce some simple differences.

The concept is also to put the data on chain, but not using zk-SNARK for verification to achieve general purpose applications. From is changed to the user’s signature (65 bytes) because we need to know who sign the transaction without SNARK. The amount of data becomes larger, it can be imagined that it need to cost more gas. Which means transaction speed will be less than ZK Rollup. The other part is that because you do not use zk-SNARK for verification, you need a validation game to ensure data validation. I won’t go into detail here. If my time is available, I’ll write more detailed about Plasma/Optimistic Rollup.

In estimation, the transaction speed is about 100 tps. If the signature method is changed to BLS, it can be increased to 450 tps. With EIP2028, the gas will drop and the estimated transaction speed will reach 400/2000 tps.

Thanks for John Adler’s correctness.

references:
On-chain scaling to potentially ~500 tx/sec through mass tx validation
Introducing Matter Testnet
Optimistic Rollup
Minimal Viable Merged Consensus


ZK Rollup & Optimistic Rollup was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.