With this blog post, the intention is to officially reveal a serious threat against the Ethereum platform, which was a clear and present danger until the Berlin hard fork.
Express
Let’s start with some background on Ethereum and State.
The Ethereum state consists of a patricia-merkle trie, a tree of prefixes. This post will not go into too much detail, suffice it to say that as the state grows, the branches of this tree become more dense. Each added bead is another sheet. Between the root of the tree and the leaf itself, there are a series of “intermediate” nodes.
To search for a given account, or “leaf” in this huge tree, somewhere on the order of 6-9 hashes must be resolved, from the root, through intermediate nodes, to finally resolve the last hash leading to the data. what we were looking for
In simple terms: every time a test search is performed to find an account, 8-9 resolve operations are performed. Each resolve operation is a database lookup, and each database lookup can be any number of actual disk operations. The number of disk operations is hard to estimate, but since the trie keys are cryptographic hashes (collision resistant), the keys are “random”, hitting exactly the worst case for any given database.
As Ethereum has grown, it has been necessary to increase gas prices for operations that access the trie. This was done in tangerine whistle in the block 2,463,000 in October 2016, which included FOOT 150. EIP 150 aggressively increased certain gasoline costs and introduced a host of changes to protect against DoS attacks, in the wake of the so-called “Shanghai attacks.”
Another such increase was made in the Istanbul update, bulk 9,069,000 in December 2019. In this update, EIP 1884 was activated.
EIP-1884 introduced the following change:
- LOAD It was of 200 a 800 gas,
- BALANCE It was of 400 a 700 gas (and cheaper SELF-BALANCING) was added,
- EXTCODEHASH It was of 400 a 700 gas,
Problems)
In March 2019, Martin Swende was doing some measurements the performance of the EVM opcode. That research later led to the creation of EIP-1884. A few months before EIP-1884 went live, the document broken meter was published (September 2019).
Two Ethereum security researchers, Hubert Ritzdorf and Matthias Egli, partnered with one of the authors behind the paper; Daniel Perez, and ‘weaponized’ an exploit that they submitted to the Ethereum bug bounty. This was on October 4, 2019.
We recommend you read the Shipping As a whole, it is a well-written report.
On a channel dedicated to client-to-client security, the developers of Geth, Parity, and Aleth were informed about the presentation earlier that day.
The essence of the exploit is to trigger random test searches. A very simple variant would be:
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, the researchers ran this payload on nodes in sync with the mainnet, via eth_calland these were their numbers when run with 10M gas:
- 10M gas exploitation using EXTCODEHASH (at 400 gasoline)
- 10M gas exploitation using EXTCODESIZE (at 700 gasoline)
As is clearly obvious, the changes in EIP 1884 definitely had an impact in reducing the effects of the attack, but they were not enough.
This was right before Devcon in Osaka. During Devcon, knowledge of the issue was shared among mainnet client developers. We also met with Hubert and Mathias, as well as Greg Markou (from Chainsafe, who were working at ETC). The ETC developers had also received the report.
As 2019 came to a close, we knew we had bigger problems than we had previously anticipated, where malicious transactions could lead to block times in the range of minutes. Adding to the issues further: the developer community was no longer happy with EIP-1884, which had caused certain contract streams to break, and users and miners alike were eager to increase block gas limits.
Furthermore, just two months later, in December 2019, Parity Ethereum Announced his exit from the scene and OpenEthereum took over maintenance of the codebase.
A new customer coordination channel was created, where Geth, Nethermind, OpenEthereum and Besu developers continued to coordinate.
The solutions)
We realized that we would have to take a two-pronged approach to handle these issues. One approach would be to work on the Ethereum protocol and somehow solve this problem at the protocol layer; preferably without breaking contracts, and preferably without penalizing ‘good’ behaviour, and still manage to prevent attacks.
The second approach would be through software engineering, changing the models and data structures within the clients.
protocol work
The first iteration of how to handle these types of attacks is here. In February 2020, it was officially launched as EIP 2583. The idea behind this is to simply add a penalty every time a test quest causes a failure.
However, Peter found a solution to this idea, the “protected relay” attack, which sets an upper limit (around ~800) on how large such a penalty can effectively be.
the problem with penalties for failures is that the search must be performed first, to determine that a penalty must be applied. But if there is not enough gasoline left for the penalty, an unpaid consumption has been made. Although that results in a release, these status reads can be wrapped in nested calls; allowing the external caller to continue repeating the attack without paying the (full) penalty.
Therefore, the EIP was abandoned, while we searched for a better alternative.
- Alexey Akhunov explored the idea of Petroleum — a secondary source of “gas”, but which was intrinsically different from gasin the sense that it would be invisible to the execution layer and could cause global transaction rollbacks.
- Martin drafted a similar proposal, on Karmain May 2020.
While iterating on these various schemes, Vitalik Buterin proposed simply increasing gas costs and maintaining access lists. In August 2020, Martin and Vitalik began iterating on what would become EIP-2929 and his partner-eip, EIP-2930.
EIP-2929 effectively resolved many of the above issues.
- Unlike EIP-1884, which increased costs unconditionally, it instead increased costs only for things that hadn’t been accessed yet. This leads to a mere sub-percentage increase in net costs.
- Also, together with EIP-2930, it does not break any contract flow,
- And it can be further tuned with high gas costs (without breaking things).
On April 15, 2021, both were released with the Sedan empower.
development work
Peter’s attempt to resolve this issue was dynamic state snapshotsin October 2019.
A snapshot is a secondary data structure for storing the state of Ethereum in a flat format, which can be built entirely online, during the live operation of a Geth node. The benefit of the snapshot is that it acts as a throttling structure for state accesses:
- instead of doing OR (register N) disk reads (X LevelDB overhead) to access an account/storage slot, the snapshot can provide OR(1) access time (X LevelDB overload).
- Snapshot supports iteration of accounts and storage in OR(1) complexity per input, allowing remote nodes to retrieve sequential state data much cheaper than before.
- The presence of the snapshot also allows for more exotic use cases, such as offline pruning of proof of health or migration to other data formats.
The downside of the snapshot is that the raw account and storage data is essentially duplicated. In the case of mainnet, this means an extra 25GB of used SSD space.
The idea of the dynamic snapshot had already started in mid-2019, with the main goal of being an enabler for snap sync At the time, there were a number of “big projects” the geth team was working on.
- Offline state pruning
- Dynamic Snapshots + Instant Sync
- LES state distribution via fragmented state
However, it was decided to completely prioritize snapshots, putting other projects on hold for now. These laid the foundation for what would later become snap/1 sync up algorithm. Merged in March 2020.
With the “dynamic snapshot” functionality released into the wild, we had a bit of breathing room. In case the Ethereum network is affected by an attack, it would be painful, yes, but at least it would be possible to inform users how to enable the snapshot. The whole snapshot generation would take a long time and there was no way to sync the snapshots yet, but the network could at least keep running.
tying the strings
In March-April 2021, the snap/1 The protocol was implemented in geth, which makes synchronization possible using the new snapshot-based algorithm. While it’s not the default sync mode yet, it’s a (important) step to make snapshots useful not only as protection against attacks, but also as a major enhancement for users.
On the protocol side, the Sedan the update occurred in April 2021.
Some benchmarks performed in our AWS monitoring environment are below:
- Pre-Berlin, no snapshots, 25M gas: 14.3s
- Pre-Berlin, with snapshots, 25M gas: 1.5s
- Post-Berlin, no snapshots, 25M gas: ~3.1s
- Post-Berlin, with snapshots, 25M gas: ~0.3s
The numbers (approximate) indicate that Sedan reduced the effectiveness of the attack by 5xand the snapshot reduces it by 10xtotaling a 50x impact reduction.
We estimate that currently, on Mainnet (15M gas), it would be possible to create blocks that would take 2.5-3s to run in a geth node without snapshots This number will continue to deteriorate (for non-snapshot nodes), as the state grows.
If rebates are used to increase effective gas usage within a block, this may be further compounded by a factor of (max) 2x . With EIP 1559the gas limit of the block will have a greater elasticity and will allow a greater 2x (the ELASTICITY_MULTIPLER) in temporary bursts.
Regarding the feasibility of executing this attack; the cost for an attacker to buy an entire block would be on the order of a few ether (15 M gas in 100Gwei is 1.5 ether).
why reveal now
This threat has been an “open secret” for a long time; in fact, it has been publicly disclosed in error at least once, and has been referenced in ACD calls multiple times without explicit details.
Since the Berlin update is long behind us, and since geth nodes use snapshots by default, we estimate that the threat is low enough for transparency to win, and it’s time to make a full disclosure about the works behind it. scene.
It’s important that the community have an opportunity to understand the reasoning behind changes that negatively affect the user experience, such as increasing gas costs and 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 publicly revealed on May 18, 2021.
