Dodging a bullet: Ethereum State Problems

The purpose of this blog post is to formally disclose a significant threat to the Ethereum platform that was clearly a current danger until the Berlin hard fork.

state

Let’s start with some background about Ethereum and nations.

The state of Ethereum consists of a Patricia Merkle trie, a prefix tree. I won’t go into too much detail in this post, but suffice it to say that as the state grows, the branches of this tree become denser. Each added account is a separate leaf. There are a number of “intermediate” nodes between the root of the tree and the leaves themselves.

To find a particular account, or a “leaf” of this huge tree, we need to resolve around 6-9 hashes from the root through intermediate nodes, and finally the last hash. The data we were looking for.

Simply put, every time a try lookup is performed to find an account, 8-9 resolution operations are performed. Each resolve operation is a database search, and each database search can perform any number of actual disk operations. The number of disk operations is difficult to estimate, but since the try key is a cryptographic hash (collision resistant), the key is “random”, which is exactly the worst case for the database.

As Ethereum grew, we needed to increase the gas price for operations that access tries.This was done in tangerine whistle in blocks 2,463,000 In October 2016, EIP150. EIP 150 aggressively increased certain gas costs and introduced a number of changes to protect against DoS attacks in response to the so-called “Shanghai attack.”

Another similar raise is istanbul Upgrade, blocking 9,069,000 In this upgrade, EIP1884 Activated.

EIP-1884 introduced the following changes:

  • Sload I went from 200 to 800 gas,
  • balance I went from 400 to 700 Gasoline (and cheaper) self balance) has been added,
  • EXTCODEHASH I went from 400 to 700 gas,

problem)

In March 2019, Martin Swende had a few things going on. measured value EVM opcode performance. This investigation later led to his creation of EIP-1884. Several months before EIP-1884 became operational, this paper broken meter has been published (September 2019).

Two Ethereum security researchers, Hubert Ritzdorf and Matthias Egli, teamed up with one of the paper’s authors. Daniel Perez “weaponized” an exploit he submitted to an Ethereum bug bounty. This was on October 4, 2019.

We recommend that you read. submission Overall, it’s a well written report.

On the same day, developers of Geth, Parity, and Aleth were notified of this application in a channel dedicated to cross-client security.

The essence of this exploit is to trigger a random try search. A very simple variation would look like this:

	jumpdest     ; jump label, start of loop
	gas          ; get a 'random' value on the stack
	extcodesize  ; trigger trie lookup
	pop          ; ignore the extcodesize result
	push1 0x00   ; jump label dest
	jump         ; jump back to start

In their report, researchers executed this payload against nodes synced to the mainnet. eth_callThese are the numbers when executed. 10M gas:

  • 10M gas exploitation using EXTCODEHASH (400 gas hours)

  • 10M gas exploitation using EXTCODESIZE (700 gas hours)

As is clear, while the changes in EIP 1884 did have an impact on reducing the impact of attacks, they were far from sufficient.

It was right before Devcon in Osaka. At Devcon, knowledge on this issue was shared among mainnet client developers. We also met Hubert and Mathias, and he also met Greg Markou (Chainsafe – who worked on ETC). ETC developers also received this report.

As 2019 draws to a close, we’re seeing a bigger problem than we previously anticipated: malicious transactions can cause minutes of block time. Adding to the problem, the development community was already dissatisfied with EIP-1884, which broke certain contract flows, and users and miners alike were clamoring for block gas limits to be increased. .

Furthermore, just two months later, in December 2019, Parity Ethereum announced They left the scene and OpenEthereum took over maintenance of the codebase.

A new client coordination channel was created where Geth, Nethermind, OpenEthereum, and Besu developers continued to coordinate.

solution

We found that addressing these issues requires a two-pronged approach. One approach is to work on the Ethereum protocol and somehow solve this problem at the protocol layer. Preferably without breaking the contract, preferably without punishing “good” behavior, and still manage to prevent the attack.

The second approach is through software engineering, changing the data model and structure within the client.

Protocol work

The first iteration of how to deal with this type of attack is as follows: here. The service officially started in February 2020. EIP2583. The idea behind it is to simply add a penalty every time a mistake occurs in the try search.

However, Peter discovered a workaround to this idea: a “shield relay” attack. This sets an upper bound (approximately 800) on how large such a penalty can actually be.

Problem of penalty for mistakes This means that to determine if a penalty should be applied, you must first do a search. However, if there is not enough gasoline left to cover the penalty, unpaid consumption has occurred. These state reads can be wrapped into nested calls, even though they result in slowness. This allows the outer caller to continue repeating the attack without paying (full) penalty.

Therefore, EIP was abandoned while searching for a better alternative.

  • Alexei Akunov explored the following ideas: oil — A secondary source of “gas,” but different in nature. gasIn that it is invisible to the execution layer and can cause cancellation of the entire transaction.
  • Martin wrote a similar proposal. karmaMay 2020.

Reiterating these various plans, Vitalik Buterin proposed increasing gas prices and maintaining an access list. In August 2020, Martin and Vitalik began considering what the future holds. EIP-2929 and its companion eip, EIP-2930.

EIP-2929 effectively resolved many of the previous issues.

  • In contrast to EIP-1884, which raised costs unconditionally, we increased costs only for things that had not yet been accessed.This is just sub percent increase At net cost.
  • Additionally, when used in conjunction with EIP-2930, contract flow is uninterrupted.
  • And you can adjust it further by increasing the gas cost (without breaking things).

On April 15, 2021, both parties began live streaming. Berlin Upgrade.

Development work

Peter’s attempt to solve this problem was Dynamic state snapshotOctober 2019.

Snapshots are secondary data structures for storing Ethereum state in a flat format, and can be constructed completely online during the live operation of a Geth node. The advantage of snapshots is that they serve as an acceleration structure for state access.

  • instead of doing O(log N) Disk read (X (LevelDB Overhead) To access the account/storage slot, the snapshot directly ○(1) Access time (X LevelDB overhead).
  • Snapshots support account and storage iteration. ○(1) The complexity per entry is reduced, allowing remote nodes to retrieve continuous state data much more cheaply than before.
  • The existence of snapshots also enables more specialized use cases, such as offline pruning of state tries and migration to other data formats.

The disadvantage of snapshots is that the raw account and storage data is essentially duplicated. For mainnet, this means adding more. 25GB SSD space used.

The idea of ​​Dynamic Snapshots was already started in mid-2019 and primarily aims to: snap Sync. At the time, the geth team was working on several “big projects”.

  • Offline pruning
  • Dynamic snapshot + snap sync
  • Distribution of LES state by shard state

However, it has been decided to give full priority to snapshots and postpone other projects for now.These laid the foundation for what would come later Snap/1 Synchronize algorithm. Merged in March 2020.

Now that the “Dynamic Snapshots” feature is generally available, we have some leeway. If the Ethereum network were to be attacked, it would certainly be a huge blow, but at least users could be notified about enabling snapshots. The whole snapshot generation took quite a while, and there was still no way to synchronize the snapshots, but at least the network could continue to work.

tie a thread

From March to April 2021, Snap/1 The protocol has been expanded with geth to allow synchronization using a new snapshot-based algorithm. Although it is not yet the default sync mode, it is one (important) step towards making snapshots useful not only as an attack defense, but also as a major improvement for users.

On the protocol side, Berlin The upgrade took place in April 2021.

Here are some benchmarks created in the AWS monitoring environment:

  • Before Berlin, no snapshot, 25M gas: 14.3 seconds
  • Before Berlin, with snapshots, 25M gas: 1.5 seconds
  • There are no snapshots after Berlin, 25M gas: ~3.1 seconds
  • Snapshot after Berlin, 25M gas: ~0.3 seconds

The (rough) numbers show that Berlin The efficiency of the attack decreased due to 5 timesthe snapshot is reduced to: 10 timesin total 50 times Shock reduction.

Currently on mainnet (15M gas) it is estimated that the following blocks can be created: 2.5-3 seconds run with Guess node without it snap shot. This number keeps getting worse as the state grows (for non-snapshot nodes).

This can be even worse (up to) times if rebates are used to increase effective gas usage within the block. 2 times .and EIP1559the block gas limit has higher elasticity and furthermore 2 times ( ELASTICITY_MULTIPLIER) in temporary bursts.

Regarding the feasibility of this attack, the cost for an attacker to purchase an entire block is on the order of a few ethers (15M with gas 100 gwei teeth 1.5 ether).

Why disclose now?

This threat has long been an “open secret”. In fact, it has been erroneously published at least once and has been mentioned several times in the ACD call without providing clear details.

Since the Berlin upgrade has already been completed and geth nodes are using snapshots by default, the threat is presumed to be well below transparency, and it’s time to be fully open about what’s going on behind the scenes. It is thought that

It’s important to give your community the opportunity to understand the reasoning behind changes that negatively impact the user experience, such as increasing gas prices or limiting refunds.


This post was written by Martin Holst Swende and Peter Szilagyi on April 23, 2021. It was shared with other Ethereum-based projects on April 26, 2021, and published on May 18, 2021.

Related Article

0 Comments

Leave a Comment