Turning the tables: Ethereum’s state of affairs

Source | Ethereum Blog

Source | Ethereum Blog

Author | Martin Holst Swende & Peter Szilagyi

The purpose of this blog post is to formally expose a serious and obvious problem with the Ethereum platform prior to the Berlin hard fork.

state

Let's start with the background of Ethereum and its "state".

The state of Ethereum consists of a patricia-merkle trie, a type of prefix tree. This article will not go into technical details. Simply put, as the state grows, the branches of the tree will become denser and denser. Each account that joins is a new leaf. Between the roots of the tree and between the leaves, there are a large number of "intermediate" nodes.

In order to find a specific account, or a "leaf" in this giant tree, from the root of the tree and through the intermediate nodes, 6-9 hashes need to be solved in order to finally hash the data we are looking for calculate.

In short, for every trie query that looks up accounts, 8-9 parse operations are performed. Each parse operation is a database query, and each database query could be any number of actual disk operations. The number of disk operations is hard to predict, but since the trie keys are cryptographically hashed (collision resistant), the keys are "random", which is worst case scenario for any database.

As Ethereum has grown, it has always been necessary to increase the gas cost of tree access operations. In October 2016, after experiencing the "Shanghai Attack" time, the Ethereum network underwent a Tangerine Whistle hard fork at block height 2,463,000, which included EIP 150, which greatly increased the gas cost of certain operations and introduced a large number of Change to defend against DoS attacks.

Another increase in gas fees was in the Istanbul upgrade in December 2019, which activated EIP 1884.

EIP-1884 introduces the following changes to gas fees:

➤SLOAD increased from 200 to 800 gas

➤EXTCODEHASH increased from 400 to 700 gas

problems

In March 2019, Martin Swende was doing some EVM opcode performance measurements. The subsequent EIP-1884 was based on this investigation. Broken Meter published this paper (2019/9) a few months before EIP-1884 was activated.

Two ethereum security researchers, Hubert Ritzdorf and Matthias Egli, and one of the paper's authors, Daniel Perez, "weaponized" a vulnerability and submitted it to ethereum's bug bounty program. This is on October 4, 2019.

It is recommended that everyone read the full document they submitted, which is very detailed.

On the same day, developers from Geth, Parity, and Aleth learned about the document in a channel dedicated to cross-client security.

The essence of this vulnerability is to trigger random trie queries. Here is a simple example:

In their report, the researchers used eth_call to execute this payload on the nodes that synchronized the main network. The following is the data during their execution, which cost 10 million gas:

• Parity: ~90s

• Geth: ~70s

➤ EXTCODEHASH (400 gas) that consumes 10 million gas

• Parity : ~50s

• Geth : ~38s

➤ EXTCODEHASH (700 gas) that consumes 10 million gas

Clearly, the changes in EIP-1884 did help in reducing the impact of this attack, but not enough.

It was approaching the developer conference in Osaka. At the developer conference, information on this issue was shared with client developers on the mainnet. We also met with Hubert, Mathias and Greg Markou (from Chainsafe, who was also doing some ETC work at the time). The developers of ETC also received this report.

As 2019 draws to a close, we know the problem is worse than previously anticipated, with malicious transactions potentially pushing block times into the minute range. To make matters worse, the developer community is dissatisfied with EIP-1884, because EIP-1884 broke some contract processes, and users and miners are very eager to increase the gas limit of the block.

secondary title

solution

solution

The second way is to solve it through software engineering, modifying the data model and structure in the client.

The work of the protocol layer

The first release on how to deal with these types of attacks is here. In February 2020, it was officially released as EIP 2583. The idea is to impose a penalty whenever a trie lookup results in a miss.

However, Peter found a countermeasure, a "shielded relay" attack, which effectively limits the upper limit of this penalty (around 800).

The problem with penalizing miss queries is that a lookup is first required to determine whether to impose a penalty. But if the remaining gas is not enough to pay the penalty, unpaid consumption has been performed. Even if it does cause an exception to be thrown, it's possible to wrap these state reads into nested calls, allowing external callers to continue the repeat attack without paying the (full) penalty.

For this reason, this EIP was abandoned and we are looking for better alternatives.

➤ Alexey Akhunov proposed the concept of Oil, the second source of gas, but it is not the same as gas in essence because it is invisible to the execution layer and may cause the transaction to be rolled back globally.

➤ Martin also authored a similar proposal in May 2020 (Gas And Karma)

While iterating on these different mechanisms, Vitalik Buterin proposed to directly increase the gas cost and keep the access list. In August 2020, Martin and Vitalik began refining EIP-2929 and its companion EIP-2930.

EIP-2929 effectively solves many of the previous problems.

➤ Compared with EIP-1884, which unconditionally increases the gas cost, EIP-2929 only increases the gas cost of the unvisited part. This resulted in a net cost increase of less than a percentage point.

➤ With the addition of EIP-2930, there will be no disruption to any contract process

On April 15, 2021, both EIPs were activated in the Berlin upgrade.

Development work

The solution Peter proposed in October 2019 is "dynamic state snapshots".

Snapshots are auxiliary data structures used to store Ethereum state in a flat format, which can be constructed entirely online during live operation of a Geth node. The benefit of snapshots is that they act as accelerated structures for state access:

➤ Instead of O(log N) disk reads (x LevelDB overhead) to access an account or storage slot, snapshots can provide direct O(1) access time (x LevelDB overhead).

➤ Snapshots support iteration over accounts and storage with O(1) complexity per entry, which enables remote nodes to retrieve sequential state data much cheaper than before.

➤ Snapshots also enable more exotic use cases, such as pruning state Tries offline or migrating to other data formats.

The downside of snapshots is that the original account and storage data are effectively duplicated. For mainnet this means an additional 25GB of SSD space.

The concept of dynamic snapshots has been started since mid-2019, and the original purpose was mainly to promote the realization of snapshot synchronization. At the time the Geth team was busy with many "big projects".

➤ Trim offline

➤ Dynamic snapshot + snapshot synchronization

➤ Realize LES (Light Ethereum Subprotocol) state distribution through sharding state

secondary title

Summarize

In March-April 2021, the snap/1 protocol was implemented in the geth client, enabling synchronization via a new snapshot-based algorithm. While still not the default sync mode, this is an important step in making snapshots not only useful as an attack defense, but also an important optimization for users.

In terms of agreement, the upgrade of Berlin will be completed in April 2021.

Here are some benchmarks developed in our AWS monitoring environment:

➤ Before Berlin upgrade, no snapshot, 25M gas: 14.3s

➤ Before the Berlin upgrade, there was a snapshot, 25M gas: 1.5s

➤ After Berlin upgrade, no snapshot, 25M gas: ~3.1s

➤ After Berlin upgrade, with snapshot, 25M gas: ~0.3s

Rough figures show that the Perlin upgrade was able to reduce the effectiveness of the attack by a factor of 5, and the snapshot by a factor of 10, for a total reduction of impact by a factor of 50.

We estimate that currently on the mainnet (15M gas), for a geth node that does not use snapshots, it is possible to create a block with an execution time of 2.5-3 seconds. For non-snapshot nodes, this number keeps getting worse as the state grows.

As for the feasibility of carrying out this attack, the cost for the attacker to purchase a whole block is about a few ETH (15M gas is 1.5 ETH for 100 Gwei).

Why publish it now?

In fact, this risk has always been an "open secret", which has been accidentally disclosed publicly more than once, and has been mentioned many times in core developer meetings, but has not involved details.

Now that the berlin upgrade has been implemented and geth's nodes are also using snapshot sync by default, we estimate that the threat is now very low and it's time for a full disclosure of what's going on behind the scenes.

This article was written by Martin Holst Swende and Peter Szilagyi on 2021-04-23. It will be shared with Ethereum-based projects on 2021-04-26 and publicly released on 2021-05-18.

Original link:https://blog.ethereum.org/2021/05/18/eth_state_problems/