Popular science | How to design Optimistic Rollup to achieve sustainable expansion and decentralization?

You must have heard of optimistic rollup while reading this article. It is a promising new capacity expansion solution that has sparked heated discussions at DevCon 2019. There have been many articles explaining how the technology works, but none has explained the reasons behind it . This has led to many teams trying to implement optimistic rollup in their own way. This kind of separate development model is usually not conducive to the security of the entire cryptocurrency economic system.

This article focuses on the issue that is overlooked by the public: explain why optimistic rollup can expand in a safe and sustainable manner, while maintaining the decentralized nature.

What is Optimistic Rollup?

I wrote the first minimum feasible specification of optimistic rollup in June 2019, which provided a specific parameterized high-level specification for my earlier paper, "Building a Scalable Decentralized Payment System", co-authored with Mikerah . The specification aims to realize the first trust-free and extensible trust-free side chain in the history of blockchain development.

• Research Report | The biggest hidden danger of blockchain security in 2020 is it
• Business Insider predicts that Libra will not be officially released in 2020, and China will release digital currency
• Instead of gaining weight, build a knowledge map of the blockchain in 7 days and 14 hours | Babbitt Industry Welcome Orientation

-I said "rollup" is not edible.-Optimistic rollup works as follows: anyone can submit a sidechain block without permission, and treat the entire block as pending verification (ie, Merkelization). ) The calldata (calldata) is posted to the chain and a deposit is paid. A new sidechain block can only be linked to the end of the sidechain and tracked by the on-chain contract (from the most simplified perspective, the contract is like a light client running a sidechain, storing the sidechain block header Hash value). After a long period of time (this is a system parameter, but it needs to be long enough, such as one to two weeks), the sidechain block will be determined, and then the deposit will be refunded. The operation of withdrawing money from the side chain and returning to the main chain is to be initiated on the side chain. It is only necessary to provide a non-interactive inclusion proof of a determined side chain block. If a sidechain block is invalid and has not been finalized, just submit it to me and explain: Why do you design Optimistic Rollup so?

Facts have shown that there are some slight differences between the optimistic rollup and the previous expansion plan, making the former the most promising short-to-medium-term expansion plan and making the latter history. This section explains the causes behind these important differences.

Merge consensus

One of the most prominent features of optimistic rollup is merged consensus . Merge consensus is a consensus protocol that can be verified on the chain (in addition to true block verification, it is done through implicit error proof). But what is a decentralized consensus protocol?

The decentralized consensus protocol includes the following independent functions:

• Fork selection rules (how to choose a chain between two chains that both follow the consensus rules)
• Block validity function (state transition function)
• Leader election algorithm (through this algorithm, a leader is elected to generate a new block, linked to the end of the blockchain, thereby increasing the height of the blockchain, or increasing its length)
• Anti-witch mechanism (proof of workload, proof of equity, etc.)

The above functions ensure the economic security of the blockchain: manipulating history comes at a price. (Note: For the sake of simplicity, I ignore some facts here, for example, some decentralized consensus protocols are leaderless ).

In the optimistic rollup scheme, the side chain will not fork, so no fork selection rule is needed. The validity of the block is calculated off-chain, and its incorrectness can be proven on the chain with a proof of error. The remaining issues of leader election and resistance to witch attacks need to be addressed.

The specification I proposed proposes a "first come, first served" mechanism, that is, at any height, the first transaction that extends the length of the side chain will be adopted. Leader election is implicit and will not be seen until afterwards, and anti-witch attacks are achieved through the main chain (i.e. transaction fees and block size / Gas ceiling). Why does such a simple leader election rule work? Because the Ethereum blockchain already provides security. A block on the sidechain can be turned into an orphan block only when the following three situations occur: 1) the block is invalid; 2) an ancestor block of the block is invalid; 3) The Ethereum blockchain has been reorganized. Therefore, a valid block also has the same degree of certainty and security as Ethereum! Therefore, we do not need complicated leader election algorithms or costly anti-witch attacks to ensure security. Sidechain can obtain security without paying extra cost, so we can greatly simplify the setting of system parameters.

But if we want a solution that knows leaders in advance, how can we transform it? One suggestion is that you can run PoS + RANDAO on the chain for leader election. In this case, there is no need to include another token, otherwise it will have a negative impact. As stated in the Bitcoin white paper :

If a greedy attacker has more CPU power than the sum of all honest nodes, he can choose to launch a double spend attack or generate new tokens. He deserves to find that obeying the rules is in his best interest, because obeying the rules allows him to get more block rewards than other miners add up compared to destroying the entire system and faking personal assets.

As Satoshi Nakamoto said, the whole point of native tokens is to incentivize the "honest majority" to protect the entire system. There is no so-called "honest majority" in optimistic rollup, and there is no security concept independent of the main chain, so it is not necessary to include a native token at all, otherwise it will not be of any help, compared to using only ether. More inconvenient.

It should be noted that as long as it is a leader election mechanism that runs completely on the chain, it can be used, not limited to those I recommend in this article. For example, Proof-of-Burn is one of them.

Although optimistic rollup has many similarities with proposals such as delayed state execution and shadow chain , a key difference is the concept of merge consensus. The optimistic rollup consensus protocol runs completely within the smart contract on the chain; therefore, it does not affect the consensus rules of the main chain and does not require its support. In contrast, delayed state execution and shadow chain implementation are automatic state transitions on the chain, which need to be explicitly supported by the main chain consensus agreement and the reward and punishment mechanism within the agreement.

Sustainable expansion

Now that we understand how optimistic rollup achieves license-freeness by merging consensus and the reasons behind it, how does it achieve sustainable expansion?

At the time of writing , the size of the uncompressed Ethereum state (user balance and contract storage) is around 45GB. Unlike historical data (such as transactions and blocks), state cannot be deleted-it must be completely preserved by a full node in order to verify (ie, execute) new transactions in a new block. To make matters worse, in order to verify a transaction, many random accesses to the state are required, so the state needs to be stored in RAM-which is not met by most consumer hardware-or a fast NVMe solid state drive. State growth is the biggest expansion bottleneck encountered by Ethereum.

Of course, we can set a hard upper limit for the size of the state , so that you do not have to worry about the problem of state growth. The real solution is to implement a state lease mechanism and continue to charge users of the state. However, deploying this mechanism on Ethereum is more difficult than expected and has been postponed indefinitely (Editor's Note: For the Chinese translation, see the hyperlink "On State Rent and Stateless Ethereum" at the end of the article).

There is a very practical solution to this problem by slowing down the state growth rate. What zk rollup promotes is to publish sidechain transaction data as calling data to the main chain, and then use validity proof or error proof to ensure the correctness of the data. It turns out that the cost of storing historical data is much lower (several orders of magnitude lower) than storing state. Later, the main chain can be used to ensure data availability, track the block header of the rollup chain, process deposits and withdrawals, and verify the validity proof / error proof, all of which do not require a large amount of usage status. By slowing state growth, capacity expansion can achieve long-term sustainability. Vitalik has written a good article before, summarizing how to apply on-chain data availability to zk rollup and optimistic rollup.

It should be noted that although it has been pointed out that shadow chains are completely equivalent to optimistic rollups, this is obviously wrong.

Now, my idea is to create a complete "shadow chain" that takes the calculation off-chain, but will submit a commitment to state transition to the main chain after generating 100 blocks. The oracle can add new blocks to the end of the chain, where each block contains a list of transactions and a state transition triggered by these transactions [[k1, v1], [k2, v2 ] …] list. After a block is generated, there will be a challenge period of up to 100 blocks. If there is no challenge during this period, the state transition will be automatically applied to the main chain.

In addition to being not clearly defined, the shadow chain will automatically perform state transitions on the chain, and will not promote state growth. Optimistic rollup does not perform any state transitions unless a user pays for it (that is, a withdrawal).

Non-interactive FTW

For optimistic rollups, non-interactive error proofs are very important. why?

The reason why non-interactive error proofs are so important is to avoid one of the shortcomings of Plasma Cash , that is, the interactive exit challenge mechanism for invalid history. This interactive multi-step challenge mechanism results in Plasma Cash 's low resistance to chain congestion attacks . The so-called chain congestion attack means that the attacker sends a large number of "exit" transactions to the main chain in order to steal all the funds in the Plasma contract (however, Plasma Cash is more resistant to these attacks than Plasma M (ore) VP ). Only a non-interactive error proof can be used to turn any number of invalid optimistic rollup blocks (on a single side chain) into orphan blocks, making the system more resistant to chain congestion attacks. Note: Because optimistic rollup uses erroneous proofs, if the main chain does not have censorship resistance , there is still a risk of funds being stolen.

In optimistic rollup, withdrawals are also processed in a non-interactive manner: first, a withdrawal is initiated on the side chain, and then a non-interactive proof of inclusion is generated for a block that has been finalized on the main chain, and then this proof is used To complete the withdrawal. However, this requires that the sidechain is license-free, so what is needed is a merger consensus, not an operator similar to Plasma.

Compared with interactive verification games , non-interactive error proofs have more advantages. Interactive verification games take longer. In view of the fact that optimistic rollup does not produce a fork, an attacker can generate an invalid block and use the verification game to cause the side chain to stop, thereby launching a DoS attack on the system. With non-interactive erroneous proofs, fraud can be confirmed immediately (however, it is important to note that the scope of proofs for erroneous proofs is narrower than for interactive verification games-as to whether this limitation really affects blocks The application of the chain has a great impact, which is yet to be discussed).

Transaction delay

Optimistic rollup does not reduce transaction latency. Each sidechain block needs to be submitted to the main chain, so the block generation time will not be lower than the main chain. There is no other secure and trust-free way to reduce this delay , other than using a fully pledged state channel .

However, you don't have to wait until the sidechain block is finalized before accepting its transactions. Since optimistic rollup does not produce a fork, valid blocks that are successfully listed on the chain must be finally confirmed, and all data of the block can be obtained (because all valid blocks are published on the chain), and users can execute the client Verify and immediately accept transactions within the block.

At first glance, delays in withdrawal seem to be a problem, but this is not the case. Generally, users do not need to wait for their withdrawal to be finalized. In fact, the longer challenge period is mainly to ensure the economic security of the cryptocurrency, which is generally not used. An easy way to withdraw money immediately is to perform an atomic swap with a liquidity provider (or other users who want to deposit on this rollup chain) on the main chain or another chain [see "Fast withdrawals" in the link : Liquidity Provider "section].

-Optimistic rollup allows you to make instant transactions without paying gas fees! –

Data availability challenges

My initial paper suggested three approaches to data availability issues:

1. Always publish all data to the chain
2. Leverage data availability challenges and publish data to the chain only when necessary
3. Leverage data availability proof

The data availability challenge seems to be a relatively simple and reliable solution. Unfortunately, if the attacker is responsible for the challenge costs, they will suffer losses; if the attacker is responsible for the challenge costs, the entire system will publish all data on the chain at all times. Therefore, at the time of designing the specification, the choice of optimistic rollup is to always release all data on the chain and implement it in an efficient and low-cost way. But later, it became feasible to use data availability proofs on optimistic rollups .

Further improvement

I have written a performance improvement proposal based on the initial version of the minimum specification and summarized it below. Please note that the focus is around UTXO-based payments, not general smart contract execution.

Multithreaded data availability on Ethereum 1.0 -data validation (i.e., hashing) and other preprocessing steps are pure functions because they do not involve any state at all. Therefore, these steps can be performed in parallel. Using Ethereum in this way will greatly reduce the use and growth of state. If a quad-core computer is used, the data availability throughput can be quadrupled. My plan is to achieve this through several EIPs, the first being EIP-2242 : Trading Postdata.

UTXO chain compact error proofs that do not need to serialize intermediate states-universal error proofs for Ethereum smart contracts are costly. Within the UTXO data model, each UTXO can be created and consumed at most once, and each transaction fully describes the state transition. Block producers can add metadata to each input, stating that this input was generated by a specific output. If such a statement is wrong, the error can be proved in a non-interactive manner. I reanalyzed the erroneous proof mechanism mentioned in BIP-141 in another article.

Stateless query parallel transaction verification using Merkel accumulators (stateless query client)-State queries are very expensive. Stateless clients reduce costs by eliminating the use of state. But we can make it a bit simpler: just dispense with status queries. "Witness data" does not expire immediately, and its validity will last for several blocks. These "witness data" must be compared based on the state transitions of the most recent blocks, which can be calculated statelessly in the UTXO data model.

Proof of availability of non-interactive data on the chain-if the data is chained from beginning to end, it will bring huge costs, and it will also cause optimistic rollup to only achieve linear expansion (such as Plasma's completely off-chain technology will There is this problem, and Plasma Cash 's checkpoint mechanism is also linear). We can express the ability of the consensus node to perform the availability check through an FFI function (for example, through pre-compilation), and we can obtain the quadratic scalability without sharding. This is to achieve the trust-free two-way bridge side chain by stopping. The two-way bridge side chain using wrong proof must always be online, which may be inconvenient for users. Although the watchtower is not suitable for Plasma Cash , it can be applied to optimistic rollup. However, we can do better: we can completely stop the sidechain after running for a period of time, and then provide users with a longer window period (up to several months) so that users can submit false proofs to determine valid zones Piece. The window period during which the user must be online is known and limited. Withdrawal is not allowed until the window period is over. If users want to withdraw money earlier, they can perform atomic swaps with liquidity providers.

Team Building Optimistic Rollup

Since the first version of the Optimistic Rollup Minimization Specification was written a few months ago, I'm glad to find that many development teams have begun building Optimistic Rollup implementations, which have experienced many twists and turns. Below is an incomplete list of the development teams we are currently seeing building Optimistic Rollups (in no particular order).

Fuel -UTXO data model focusing on stablecoin payments. It can be used for any ERC-20 token or ETH transfer, or for atomic exchange. It can also be used for "assert" script writing in the future. The model will be launched on a long-term public testnet (Editor's Note: Fuel is now open to public testnet).

Plasma Group -a universal EVM smart contract in the OVM (Optimistic Virtue Machine) environment, has announced a cooperation with Uniswap on Devcon 5.

Arbitrum -A general-purpose smart contract that uses interactive verification game mechanics. Otherwise, the new Arbitrum rollup design is roughly the same as the optimistic rollup.

Interstate Network -A universal EVM-type smart contract using false proof.

SKALE -Optimistic rollup using BLS signature aggregation.

NutBerry -A universal EVM-like smart contract that uses interactive verification game mechanisms.

IDEX -Constructed an "Optimistic Optimal Rollup" for the IDEX exchange.

in conclusion

With the launch of various optimistic rollup implementation projects, Ethereum will undergo a huge change in the next year, its throughput will be greatly improved, and sustainable capacity expansion will be achieved in terms of data availability.

I did not compare optimistic rollup with zk rollup (this concept was originally called roll_up , proposed by Barry Whitehat, and then improved by Vitalik to zk rollup ) in this article. If you are interested, you can take a look at this article by Alex Gluchowski (Editor's Note: For the Chinese translation, see the hyperlink "Optimistic Rollup vs. ZK Rollup: Check it out" at the end of the article).

Thanks to Mikerah Quintyne-Collins , James Prestwich , Robert Drost, and Joseph Chow for reviewing .

(Finish)

Original link: https://medium.com/@adlerjohn/the-why-s-of-optimistic-rollup-7c6a22cbb61a Author: John Adler Translation & proofreading: Min Min & A sword

Source: Ethereum enthusiasts, the original title "Science | Optimistic Rollup Why Design?" 》

We will continue to update Blocking; if you have any questions or suggestions, please contact us!