Dodging the Bullet: Ether State Issues

The purpose of this article is to formally disclose a serious threat to the Ether platform whose dangers were clear and unambiguous until the “Berlin” hard fork was lifted.

The purpose of this article is to officially disclose a serious threat to the Ether platform whose danger was clear and unambiguous until the “Berlin” hard fork was lifted.

The State
Let’s start with some background knowledge about Ether and “state”.

Ether state is a particia-merkle trie (a merkle tree with prefix tree rules). This article will not go into too much detail, just know that as the number of states grows, the branches of this tree structure will become denser and denser. For each additional account on the ethereum blockchain, there is one more leaf node in this tree. At the root and leaf nodes of the tree are many so-called “intermediate” nodes.

In order to find a certain account, or to find a certain “leaf” in this huge tree, it is necessary to parse 6 ~ 9 hashes, starting from the root node, through the intermediate nodes, and finally to a hash that can give us the data we need.

In big words: whenever we want to look up an account in this tree, we have to go through 8 ~ 9 parsing operations. Each parse operation is a database query, and each database query implies an indeterminate number of multiple hard disk operations. The number of hard disk operations is hard to estimate, but because the “keys” of the state tree are cryptographic hashes (collision-resistant), these keys are random, which is a worst-case scenario for all databases.

With the increase in Ether state, it becomes necessary to increase the Gas consumption of operations that access the state tree. We did this back in October 2016 with the “Tangerine Whistle” fork (incorporated into EIP 150, activated at block height 246 3000).EIP 150 drastically increased the Gas consumption and introduced a series of measures to protect the network from DoS attacks; this was introduced after the so-called “Shanghai attack”.

Another such Gas consumption boost was introduced at the time of the “Istanbul” fork, activated at block height 906 9000 (December 2019), with the introduction of EIP 1884.1884 The contents of

Gas consumption of the SLOAD opcode increased from 200 to 800 gas

BALANCE consumption increased from 400 to 700 gas (a cheaper SELFBALANCE opcode has also been added)

EXTCODEHASH consumption increased from 400 to 700 gas

Question(s)
In March 2019, Martin Swende measured the performance of the EVM opcode. This study later led to the creation of EIP-1884. The paper, titled “Broken Metre”, was published a few months before 1884’s activation (September 2019).

Two Ether security researchers — Hubert Ritzdorf and Matthias Egli — collaborated with Daniel Perez, one of the authors of this paper, and “weaponized” a vulnerability and submitted it to Ether’s bug bounty program. That was on October 4, 2019.

We recommend you read their submission in its entirety, it’s very well written.

In a channel dedicated to cross-client security, developers from the Geth client, Parity client, and Aleth client were informed about this report on the very same day.

The nature of the vulnerability is that it triggers a random tree lookup. A very simple variant of this is.

Dodging the Bullet: Ether State Issues

In their report, the researchers performed this load on nodes synchronized to the main network via the eth_call RPC endpoint, and here is how long it took them to consume 10 million gas.

Exhausting 10 million gas using EXTCOEHASH (nominal gas consumption is 400)

Parity: about 90 seconds

Geth: about 70 seconds

Use EXTCODESIZE (nominal gas consumption is 700) to consume 10 million gas

Parity: about 50 seconds

Geth: approx. 38 seconds

(Translator’s note: this means that if a block of 10 million gas is filled with these two opcodes, it will take this long for the node to finish processing the block)

Obviously, EIP-1884 did reduce the effectiveness of the attack, but it was not enough.

By that time, Devcon Osaka was very close. During Devcon, knowledge about this issue spread among client developers on the main network. We also met with Hubert and Mathias, as well as Greg Markou (who is from the Chainsafe team and has been working on ETC). developers of the ETC blockchain also received this report.

As 2019 draws to a close, we’re finding that this is an even trickier problem than we previously thought, with malicious transactions potentially causing block-out times to extend to minutes. To make matters even more difficult, the developer community is already unhappy with EIP-1884, which breaks a number of contracts, and the fact that users and miners alike want to raise the Gas Limit on blocks.

Furthermore, just two months later, in December 2019, Partiy Ethereum announced it was pulling out and the OpenEthereum project took over the maintenance of the code for the Parity client.

A new client collaboration channel was then created, and developers from Geth, Netheremind, OpenEthereum, and Besu continued to collaborate.

The Solution
We realized that only a two-pronged approach could solve the problem. On the one hand, we have to improve the ethereum protocol, that is, solve the problem at the protocol layer; preferably without breaking the contract and without penalizing “good faith” behavior, yet preventing attacks.

On the other hand, we can rely on software engineering to change the data model and structure within the client.

Protocol layer work
The first idea to deal with such attacks is this. In February 2020, its official version was released as EIP 2583. The idea behind the proposal was to add a penalty that would be triggered every time a tree lookup resulted in a miss (“not found”).

However, Peter found a way around it – a “shielded relay” attack – so that essentially the penalty has a cap (about 800).

The problem with the penalty miss method is that there must be a search process before a penalty can be applied. But if there is not enough gas left to apply the penalty, then (from the protocol’s point of view) an underpaid consumption process has been executed. Even if this leads to throwing errors, these state reads can be encapsulated in nested calls, allowing the external caller to repeat the attack without having to pay the (full) penalty.

Therefore, this EIP was also discarded and we had to find a better alternative.

Alexey Akhunov investigated the concept of Oil – a kind of secondary “Gas”, but completely different from Gas in that it is invisible to the execution layer and can lead to a transaction-global rollback ( transaction-global revert).

Martin has proposed a similar proposal, called “Karma”, in May 2020.

While these many proposals have progressed, Vitalik Buterin proposes to simply increase Gas consumption and maintain an “access list”. In August 2020, Martin and Vitalik began iterating on the idea that would become EIP-2929 and its companion, EIP-2930.

EIP-2929 fundamentally solves many of the problems mentioned above.

In contrast to EIP-1884; which unconditionally increased Gas consumption, 2929 only increased Gas consumption for accessing new objects. This results in a net cost increase of less than one percentage point.

Again, when combined with EIP-2930, it does not break any contracts.

It can be further adjusted by increasing the Gas consumption (also without breaking the contract)

On April 14, 2021, both EIPs are activated at the “Berlin” fork.

Development work
Peter tried to solve this problem with a dynamic snapshot of the state, in October 2019.

A snapshot is a secondary data structure used to store Ether state in a flat format. Snapshots can be created during the normal operation of a Geth node and do not require dedicated execution offline. The benefit of snapshots is that they can be used as an accelerated structure for state access.

Instead of performing O(log N) hard drive reads (also multiplied by the overhead of LevelDB) to access an account/storage entry, snapshots can provide straightforward, O(1) level access times (multiplied by the overhead of LevelDB).

Snapshots also support iterating over accounts and stored items with O(1) complexity per entry, which allows remote nodes to retrieve continuous state data very much cheaper than before.

The existence of snapshots also supports other, stranger uses, such as pruning state trees offline and migrating to another data format.

The downside is that snapshots amount to an exact copy of the unprocessed (raw) data of accounts and storage items. If used in a primary network environment, this means an additional 25 GB of SSD space is required.

The idea of dynamic snapshots has been around since mid-2019, when the main goal was to enable “snapshot synchronization”. At that time the Geth team was also working on a number of “big projects:”

Off-line state pruning

Homomorphic snapshots + snapshot synchronization

LES state dispersion through shared state

However, they later decided to focus on the snapshot feature and postponed other projects. This work laid the foundation for the snap/1 synchronization algorithm that followed. This algorithm was merged into the code base in March 2020.

With the “dynamic snapshot” feature, we can take a breath. If the ethereum network is attacked, it will be painful, but at least we will be able to inform users to turn on the snapshot feature. It takes some time to generate snapshots, and there is no way to synchronize them, but the network can at least continue to function.

Combining
In March/April 2021, the snap/1 protocol has been rolled out on the geth client, and nodes are now able to use the new, snapshot-based algorithm to synchronize the blockchain. While not yet the default mode of synchronization, this is one part of the process that enables snapshots not only as an attack protection measure, but also as a significant improvement to the user experience.

At the protocol level, the “Berlin” upgrade was activated in April 2021.

In our AWS monitoring environment, our benchmarking results are as follows.

Before “Berlin”, without snapshots, processing 25 million gas: 14.3 seconds

Before “Berlin”, with snapshot, processing 25 million gas: 1.5 seconds

After “Berlin”, without snapshot, processing 25 million gas: about 3.1 seconds

After “Berlin”, with snapshot, processing 25 million gas: approx. 0.3 seconds

This (crude) figure shows that the “Berlin” upgrade reduces the efficiency of the attack by a factor of 5, while the snapshot reduces it by a factor of 10, and ultimately reduces its impact by a factor of 50.

We estimate that on the current mainnet (15 million gas blocks), a geth node without snapshots may be able to execute a block in just 2.5 ~ 3 seconds. This number will continue to deteriorate as the state grows (for nodes that do not use snapshots).

If the gas return mechanism is used to cause a boost in actual gas usage for a single block, this worsens by a factor of (at most) 2. With the implementation of EIP-1559, the Gas Limit of a block will be more resilient and can explode to a maximum of 2x deterioration multiplier in a short period of time.

As for the feasibility of implementing such an attack, the cost for an attacker to buy out a block is probably on the order of a few ETH (15 million gas at 100 Gwei, multiplied out to 1.5 ETH).

Why go public at this time
This threat has been an “open secret” for a long time – it has been publicly disclosed at least once due to an oversight; and it has been mentioned several times in core developer meetings, though not in public detail.

Because we’ve activated the “Berlin” update, and because the geth client already uses the snapshot feature by default, we believe that the threat is low enough and that transparency is more important. So it’s time to make all the behind-the-scenes work public.

It’s important that the community gets a chance to understand and think about these changes that affect the user experience (these EIPs increase Gas consumption and also limit the effectiveness of the return mechanism).

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/dodging-the-bullet-ether-state-issues/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2021-05-20 10:56
Next 2021-05-20 11:13

Related articles