This article discusses the evolution ideas and design reasons of the Rollup expansion solution

Original Author: ORFEO

The L2 project is once again in the spotlight.

As a representative of the Rollup expansion route in L2, after the Arbitrum airdrop, the zkSync Era will be launched. Behind the endless new designs and roadmaps, what is the main line of Rollup and what is the evolutionary thinking? Let’s take a look today.

Main points of this article:

• The expansion idea of L1 written for the third grade
• Design a Rollup solution from scratch
• How to use zero-knowledge proof to make Rollup evolve again

Starting with an analogy

For Bitcoin and Ethereum, since their birth, there are two biggest criticisms from ordinary users:

• Slow: The lane is originally narrow, and if there are too many cars, it will be blocked.
• Expensive: Tolls on flat peaks are not cheap. If you want to pass quickly during the peak period, you need to use the "money ability" to add money and let miners fly helicopters to get you.

These two criticisms stem from two factors in the blockchain design:

• Block capacity: analogous to a lane, the larger the block capacity, the more cars it can accommodate, and the less likely it is to be blocked.
• Incentive mechanism: No matter how big the driveway is, there is a possibility of being blocked. In this case, who is allowed to pass first? It depends on who is in a hurry, but you can’t just listen to people’s words, it depends on the willingness to pay, such as calling an ambulance. It will be several hundred.

If the blockchain can really be like a driveway, then the fundamental solution is naturally to widen the driveway, and at the same time cooperate with price means to guide the time to go out, and don’t go out if you are not in a hurry.

However, although widening the lanes and increasing the block capacity is an attractive traffic efficiency solution, it is a last resort in blockchain design. Because the larger the block size, the higher the hardware requirements for miners, and the fewer miners who can meet the requirements; according to this idea, if you want to process thousands of transactions per second like Visa, you will only end up Making another centralized Visa runs counter to the core purpose of blockchain trustlessness.

Is there any other solution? Yes, in addition to time guidance, we can also optimize space, including but not limited to:

• Open up different lanes, one for large trucks, one for cars, and one for buses, without interfering with each other — Based on this idea, we can come to some main chains, side chains or Plasma with their own strengths.
• Optimize the route design, divert traffic appropriately, don’t go to the city to do anything, you have to take this main road, you have to go through the checkpoint here —— Based on this idea, we can sharding.
• Why do you have to go out? It is not too late to have a remote meeting and reach an agreement, and it is not too late to sign an agreement offline——Based on this idea, we can have a state channel (State Channel).
• You don’t necessarily have to drive by yourself when you go out, you can also carpool, or take public transportation —— Based on this idea, we have the protagonist of this article, Rollup.

As a bus on the blockchain, the key to Rollup is actually saving space and saving gasoline (Gas, pun intended):

• Save space, so it is not easy to get stuck, and the toll shared by each person is much less than driving by yourself;
• Gasoline is saved, so the ticket price is close to the people, and everyone can afford it.

In this way, the two slots of "slow" and "expensive" are solved by Rollup.

Let's go back to the blockchain and see the specific plan of Rollup.

Design a Rollup solution from scratch

Instead of peeking at the standard answer (not to mention there is no), it is better to have some suspense and imagine what you will do when you are tasked with designing Rollup for Ethereum.

We might as well start from the two perspectives of reducing computing costs (saving gasoline) and reducing storage costs (saving space), and first propose a more radical solution called Rollup 1.0.

Rollup 1.0

Rollup 1.0 consists of 3 main points:

• There is a service provider (Operator) that collects everyone's "carpooling" transactions (Transaction), and "send orders" when the carpool is full or not but the agreed time is up, taking into account price and timeliness;
• All calculations involved in the transactions submitted by everyone are performed off-chain by this service provider, because off-chain calculations are faster than on-chain, and calculations are often the bulk of on-chain costs, which can save a lot of money;
• After the calculation, get the updated status (such as the latest balance in your account), and store it on the chain, so that the storage cost is much lower.

To put it simply, it is to regularly and quantitatively collect everyone's transaction requests, and after off-chain calculations, only the calculation results are solidified on the chain.

This solution perfectly solves the two major pain points of "slow" and "expensive", but it seems to generate new problems:

• Incentive: Who will provide the "carpooling" service and what are the benefits.
• Review problem (Censorship): The service provider deliberately does not process my order (or hangs up or quits), what should I do;
• Fraud problem (Fraud): What should I do if the service provider cheats and tampers with the calculation results, causing me to transfer money to others, and the money is embezzled by him.

For these three new problems, we can iterate a version of the plan.

Rollup 2.0

The motivation problem is best solved, and the problems that can be solved with money are not problems. The service provider can share the cost of "carpooling" equally, and charge a little extra "tip". Even so, it is still a win-win situation with the "carpooling" person.

The review problem is a little more troublesome, but the solution is very common in the blockchain field, and that is decentralization. A group of people are service providers, which is better than only one service provider; anyone can be a service provider, which is better than a fixed group of people. In the latter way of playing, if all service providers are not good, you can also be a service provider yourself, or directly go to L1 to initiate arbitration.

Fraud is a little more difficult. It can be broken down into two questions—one is how to identify fraud, and the other is how to prevent it.

First, to identify fraud, we need to know everyone’s transaction (Transaction) data, the state before the transaction (State), so as to calculate the new state (State’) after the transaction, and use it to store it on the service provider chain Compared with the new state, if it is the same, it means that the service provider is honest, otherwise it means that he lied. However, we do not know the transaction data because they are not on-chain. As a result, we can only be skeptical and unable to judge whether the service provider is honest or not.

Next, to prevent fraud, the best way is to make fraud impossible, which is more difficult, unless the calculation of the service provider is checked every time on the chain, but in this way, there is no advantage of "carpooling" up. So we can only take a step back and make the cost of fraud very high, so that service providers have skin in the game, such as paying a deposit (Stake), which will be confiscated if fraud is found. (This method is called social consensus, which belongs to game-based security, and was also mentioned in "Weekly #3".)

Rollup 3.0

Rollup 2.0 is not bad, but the problem of identifying fraud is not solved.

According to the previous inference, to identify fraud, we must know the transaction data, so this part of the data must be on the same chain as the status data.

Who is going to find out they are fraudulent? Obviously, this is unlikely to be an ordinary user, because it is impossible for everyone to monitor every move of the service provider 7x24 hours, so it can only be a professional "bounty hunter" (Validator). If a "bounty hunter" reports fraud within 7 days after the service provider "sends the order" and verifies that it is true, the transaction will be rolled back and the service provider will be punished. Of course, in the same way, "bounty hunters" also need incentives. For example, after fraud is discovered, a part of the service provider's deposit will be given to the "bounty hunter" (only a part, to avoid collusion between the service provider and the bounty hunter).

Rollup 4.0

By the Rollup 3.0 stage, the entire solution has been able to run smoothly, but new costs have been introduced. Costs so far include:

• Fees to service providers (including costs and "tips");
• On-chain storage cost of transaction and state data;
• When the "Bounty Hunter" believes that the service provider is fraudulent, the computational cost of verifying what he said is true on the chain.

Let's take a look at what costs can be optimized.

transaction data

In a specific way, multiple transactions are aggregated together, and the space occupied can be smaller than the sum of the space occupied by each transaction.

Taking the simplest ETH transfer transaction as an example, we disassemble the content composition of each transaction, and we can see that the signature space accounts for the largest proportion. We can combine the signatures of all transactions into one (Key Aggregation), which saves a lot of storage overhead (similar to Schnorr in Bitcoin). In addition, we can also optimize other parts, such as getting rid of Nonce, and choosing "fat and thin" as much as possible when "carpooling", and a "carpooling person" that fits perfectly to maximize the use of the "car" space.

source:

Just three or two times, the size of each ETH transfer transaction has been reduced from 112 bytes to 12 bytes, which is close to one-tenth of the previous one; of course, there are other means to further compress the transaction data.

In actual operation, we can insert such a method in the contract deployed on the chain:

function storeTxData(bytes calldata data) external {// Nothing to do}

Then every time the "carpooling" is successful, the merged and compressed transaction data is passed into this method as calldata. Calldata does not need to be stored permanently, and after the Social Consensus Publicity Challenge Period (Challenge Period), it will not matter if it is pruned (Prune); the price itself is very low, and it will be cheaper with the implementation of EIPs such as Danksharding and Data Blob , this form of applying L1 to data storage distribution (Data Availability) will also be more formal.

status data

Now that the transaction data has been uploaded to the chain, anyone can calculate the updated state through the transaction data, and the state data is not so necessary. We can only keep the Merkel Root of the state data, which is used to allow ordinary users ("carpoolers") to apply for withdrawals directly to L1 when the service provider does not cooperate, and rely on Merkel Proof to prove that they have money in their accounts.

FRAUD ARBITRATION COSTS

When the "bounty hunter" reports a fraud to the service provider, the on-chain contract calculation (Replay) is performed once and the status results are compared. This is theoretically feasible. However, the cost of doing so is not low (although it is already good), and the second is that the sum of the Gas of the transactions included in the Rollup "carpooling list" may exceed the gas limit of Ethereum, making it impossible to verify.

Therefore, arbitration needs to reduce the burden, and the way to reduce the burden is naturally to put unnecessary calculation operations off-chain. One of the solutions is called Interactive Proving. The general process is as follows:

• "Bounty Hunter" pays a deposit, then reports, and splits the entire calculation process into n segments in order, pointing out that the service provider has fraud in segment k (1≤k≤n);
• The service provider drilled down and disassembled segment k into segment k, and pointed out which segment of the "bounty hunter" was incorrect;
• Going back and forth like this, knowing that computing operations can no longer be drilled down and dismantled, for example, when dismantled, the "bounty hunter" thinks 1+1=2, and the service provider thinks 1+1=3;
• At this time, the contract on the chain intervenes, calculates 1+1, and obtains 2, thus determining that the service provider is fraudulent, confiscating its deposit, and rewarding a part of it to the "bounty hunter".

(During the whole process, if one party fails to reply within a timeout, the party fails.)

In this way, the arbitration cost on the entire chain is very, very low.

Having said that, we have completely constructed a Rollup solution. Because this scheme assumes that the service provider is honest by default, unless there is a "bounty hunter" report, this faction is called the rollup of the optimist, the so-called Optimistic Rollup.

So, is our Rollup 4.0 the best solution?

Rollup re-evolution

After our multiple iterations, Rollup 4.0 still has some imperfections:

• Fraud needs to be discovered by "bounty hunters", but if there is no fraud for a long time, "bounty hunters" may go out of business because they are unprofitable, so there will be a gap (although unlikely, because of the Rollup chain Stakeholders such as application vendors will most likely act as "bounty hunters");
• To be sure that there is no fraud, based on social consensus, you need to wait for several days, which will affect operations such as withdrawals;
• There is a lot of data on the chain, and the cost is still there;
• Currently relying on a layer of Rollup expansion, the throughput may be increased by 10 times. Is it possible to be higher?

Is there a solution that can make fraud impossible at all, make finality (Finality) faster, make less data need to be uploaded to the chain, and make expansion an order of magnitude more? I don’t want too much, but there is a kind of solution that can satisfy almost all imaginations — Zero Knowledge Rollup (ZK-Rollup for short).

ZK-Rollup is a Rollup idea using zero-knowledge proof (ZKP). The so-called ZKP refers to the technology that convinces the other party that you know this information without revealing any sensitive information. To explain ZKP, there are two of my favorite examples:

*Imagine in a medieval European town and I have a treasure map with a treasure marked on it. In order to prove to you that I have a treasure map, but without letting you know the exact location of the treasure, I put a blindfold on you, drag you into a carriage, and drive you around town for half an hour to make sure you lose your sense of direction, Finally arrive at the destination, get out of the car and show you the treasure, and then take you back around. This is a naive form of ZKP.

• Another analogy is more common. Suppose there is a Sudoku puzzle, I know the answer but you don't, but you don't believe that I know; I want to prove to you that I know, but I don't want you to know the answer. what to do? I can put Sudoku on the table with cards, and then put the open numbers up and the numbers that need to be filled in down, and let you choose to check my answer by row or column. If it is by row, I will group the numbers in each row together, break them up, and show you that each row is 1 to 9. It's okay to repeat it several times, so you can believe that I really know the answer with a high probability. This is one of the interactive proof methods of ZKP (because it is difficult to achieve real-time on-chain interaction in the blockchain, non-interactive proof is generally used, and random challenges are generated by the Hash function).

In less rigorous terms, the core idea of ZKP is that the prover (Prover) first hides the secret knowledge, "commits" (Commit), and then the verifier (Verifier) initiates a random challenge (Challenge). Only if he can successfully pass the challenge, then there is a high probability that he has the corresponding secret knowledge.

ZKP must meet 3 requirements:

• If the prover is lying, there is a high probability of failing the challenge (Soundness);
• If the prover has knowledge, he will be able to pass the challenge (Completeness);
• During the interaction between the two parties, the prover will not disclose any useful information (Zero-knowledgeness).

In order to meet these three requirements, ZKP uses a variety of NP problems, including the simplest prime number decomposition, and discrete logarithms (such as Schnorr is) and so on.

ZKP is not a technology born for the blockchain, but it can be used for L2 expansion, mainly because a good ZKP has the following useful characteristics:

• The prover (service provider) can quickly give a proof, so as to ensure that the calculation efficiency under the chain is very high and will not become a bottleneck;
• The size of the proof is small, or at least proportional to the amount of calculation to be proved, and the impact of the amount of data is as small as possible, so that the storage cost on the chain is low;
• The verifier (L1 contract) can quickly verify whether the proof is valid, so the calculation cost on the chain is low.

Using these features, our Rollup solution can:

• There is no need for a "bounty hunter", the L1 contract can detect fraud on the spot by itself;
• As long as the ZKP verification is valid, withdrawals can be made immediately, and the finality is shortened from days to minutes;
• Only the diff between states is required on the chain, the space is very small, and the storage cost is very low (an additional bonus — privacy is also improved);
• Through the customized software and hardware optimization of the proof and verification process, the expansion capacity can be increased by another order of magnitude.

Of course, any security mechanism will have potential prerequisites, and ZKP is not a panacea for the blockchain. ZKP still has many limitations at present, which need to be overcome step by step, such as:

• Take the most commonly used zk-SNARK on the blockchain as an example. Many schemes need to introduce as many prestigious people or companies as possible at the beginning, and do a Trusted Setup to generate a true random number and guarantee The generation process is verifiable but not fully public (like in the Power of Tau ceremony, as long as one party can be trusted, but it still counts as a flaw). Of course, some new zk-SNARK schemes and later improved zk-STARKs can solve this problem, but sometimes new problems are introduced.
• Many problems are difficult to summarize as ZKP problems, which has led to the fact that programmability has not been well resolved for a long time. It is difficult to realize ZKP that is fully compatible with EVM on Ethereum, or even if it can be achieved, But other aspects (such as verification efficiency) will be affected.

source:

This is why, in ZK-Rollup, a future-oriented expansion field, every progress is commendable and gratifying.

source:

write at the end

As far as the future of capacity expansion is concerned, the author believes that compared with the native capacity expansion of L1, the layered design including Rollup is a more reliable idea. Modularization, each layer solves the concerns of each layer, which is less risky than continuous stacking on the already "monolithic" L1; moreover, the decentralization of the underlying L1 due to capacity expansion is theoretically unlikely to be The upper layer finds it and makes it up. Moreover, this layered design idea has seemingly successful applications in fields other than the blockchain. The point of view is not necessarily correct, but this is the author's current cognition.

This article attempts to sort out the thinking and design reasons of the Rollup expansion solution in a project-agnostic tone. Due to the limited level, some places are still a bit blunt, which may not only not explain it in place, but also increase the difficulty of understanding; as a vertical field that is changing with each passing day, the author may not be aware of and take into account many new developments in time. Sincerely welcome friends to correct and communicate.