Through this blog post, our intention is to officially disclose the serious threat to the Ethereum platform, which was a clear and present risk until the Berlin hard fork.
situation
Let’s start with some background on Ethereum and States.
The Ethereum state consists of a prefix tree, the patricia-merkle trie. I won’t go into too much detail about this in this post. Suffice it to say that as the state grows, the branches of this tree become more dense. Each account added is another leaf. There are a number of “intermediate” nodes between the root of the tree and the leaves themselves.
To look up a specific account, or “leaf” in this huge tree, you need to check roughly 6-9 hashes, from the root through intermediate nodes, and finally the last hash leading up to the next. The data we were looking for.
Simply put, each time you perform a try lookup to find an account, 8-9 verifications are performed. Each resolve operation is one database query, and each database query can be multiple physical disk operations. It’s hard to estimate the number of disk operations, but since the tree key is a cryptographic hash (collision-proof), the key is “random”, which is exactly worst case for any database.
As Ethereum grew, it had to increase the gas price for operations accessing the tree. This work was done in: tangerine whistle in the block 2,463,000 Included in October 2016 EIP 150. EIP 150 aggressively increased certain gas costs and introduced global changes to protect against DoS attacks due to the so-called “Shanghai attack”.
Another impression was made. Istanbul Upgrade, from blocks 9,069,000 December 2019. In this upgrade EIP 1884 Activated.
EIP-1884 introduced the following changes:
- slowo went from 200 to 800 gas,
- balance went from 400 to 700 gas (and cheaper) self balance) has been added.
- Xcode Hash went from 400 to 700 gas,
problem
In March 2019, Martin Swende was onto something. measurement EVM opcode performance. That investigation later led to the creation of EIP-1884. A few months before EIP-1884 was released, this paper broken meter 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 submitted to an Ethereum bug bounty. This was on October 4, 2019.
Please read the following: submit Overall, this is a well-written report.
In a secure dedicated client-to-client channel, developers on Geth, Parity, and Aleth were informed of the submission on the same day.
The core of the exploit is to execute random try lookups. A very simple variation 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 the report, the researchers executed this payload against nodes synced to the mainnet via: eth_callHere are the numbers when run like this: 10M gas:
- 10M using gas exploitation Xcode Hash (based on 400 gas)
- 10M using gas exploitation Xcode size (at 700 gas)
As can be clearly seen, the changes in EIP 1884 certainly had an impact in reducing the impact of attacks, 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 Hubert and Mathias as well as Greg Markou from Chainsafe who was working on ETC. ETC developers also received the report.
As 2019 came to a close, we learned that there was a bigger problem than previously anticipated: malicious transactions could cause block times in minutes. The bigger problem is that the developer community is already unhappy with EIP-1884, which halts the flow of certain contracts, and both users and miners are very concerned about the block gas limit being raised.
Moreover, just two months later, in December 2019, Parity Ethereum was launched. presentation They left the scene and OpenEthereum took over maintenance of the codebase.
A new client coordination channel has been created where Geth, Nethermind, OpenEthereum, and Besu developers continue to collaborate.
solution
We realized that we had to take a two-pronged approach to solve these problems. One approach is to somehow solve this problem at the protocol layer using the Ethereum protocol. You can still prevent attacks, preferably without breaking the contract, and preferably without penalizing ‘good’ behavior.
The second approach is to change the data model and structure within the client through software engineering.
Protocol operation
The first iteration of how to deal with this type of attack is as follows: here. It was officially released in February 2020. EIP 2583. The idea behind it is to simply add a penalty every time a try lookup fails.
However, Peter found a workaround for this idea: a ‘shielded relay’ attack. This attack sets an upper limit (about 800) on how large these penalties can actually be.
the problem is punishment for mistakes The idea is that a lookup must first occur to determine if a penalty should be applied. However, if there is no gas left to cover the penalty, unpaid consumption has occurred. Even though this results in a throw, these state reads can be wrapped in nested calls. Allows the outside caller to continue repeating the attack without paying the (full) penalty.
This led to the EIP being scrapped while a better alternative was sought.
- Alexey Akhunov explored the following ideas: Oil — A secondary source of “gas,” but is essentially different from gas. gasThe problem is that it is invisible to the execution layer and can result in transaction-global reversal.
- Martin wrote a similar proposal. upMay 2020.
In iterations of these various plans, Vitalik Buterin proposed increasing gas costs and maintaining access lists. In August 2020, Martin and Vitalik began taking a continuous look at what might happen next. EIP-2929 And its companion eip, EIP-2930.
EIP-2929 effectively solved many previous problems.
- Unlike EIP-1884, which increases costs unconditionally, it only increases costs for things that have not yet been accessed. This leads to a simple result. Bottom percent increase Net cost.
- Additionally, no contract flow is broken with EIP-2930,
- And you can adjust it further by increasing (without damaging) your gas costs.
Both on April 15, 2021 Berlin upgrade.
development work
Peter’s attempt to solve this problem was as follows. Dynamic state snapshotOctober 2019.
Snapshots are auxiliary data structures for storing the state of Ethereum in a flat format that can be built completely online while Geth nodes operate in real time. The benefit of snapshots is that they act as an acceleration structure for state access.
- Instead of doing O(log N) Read disk (X LevelDB overhead) can be provided directly through snapshots to access accounts/storage slots. Oh(1) Connection time (X LevelDB overhead).
- Snapshots support account and storage iteration. Oh(1) The increased per-item complexity allows remote nodes to retrieve sequential state data much more cheaply than before.
- Snapshots also enable more exotic use cases, such as pruning the state tree offline or migrating it to a different data format.
The downside to snapshots is that the raw account and storage data are inherently redundant. For mainnet this means additional costs. 25GB Percentage of SSD space used.
The dynamic snapshot idea has already been launched in mid-2019, and primarily aims to enable: snap tuning. There were several “big projects” the geth team was working on at the time.
- Offline status cleanup
- Dynamic Snapshot + Snap Sync
- LES state distribution via sharded states
However, we decided to prioritize snapshots and postpone other projects for now. These laid the foundation for what would become later. snap/1 tuning calculation. Merged in March 2020.
The launch of the “dynamic snapshot” feature has given us some leeway. If the Ethereum network were to be attacked, it would be painful. However, it would at least be possible to notify users about enabling snapshots. Creating a full snapshot would take a lot of time and there was no way to synchronize the snapshots yet, but at least the network could still function.
tying the thread
From March to April 2021 snap/1 The protocol has been released to geth, enabling synchronization using a new snapshot-based algorithm. It’s still not the default sync mode, but it’s one (important) step toward making snapshots not only useful as attack protection, but also a major improvement for users.
On the protocol side Berlin The upgrade took place in April 2021.
Some benchmarks for AWS monitoring environments include:
- Before Berlin, no snapshots; 25M gas: 14.3 seconds
- Berlin relocation, with snapshots; 25M gas: 1.5 seconds
- After Berlin, no snapshots 25M gas: ~3.1 seconds
- Post Berlin, with snapshots; 25M gas: ~0.3 seconds
(Approximately) The numbers represent: Berlin Reduced attack efficiency. 5 timesSnapshots reduce this to: 10 timesThe sum is 50 times Reduced shock.
We estimate that it is currently possible to generate blocks on the mainnet (15M gas). 2.5-3 seconds Execute Guess word without Snapshot. As the state grows, this number continues to degrade (for non-snapshot nodes).
This can be (up to) times worse if rebates are used to increase effective gas usage within a block. Twice . with EIP 1559Block gas limits have higher elasticity and more Twice (that much Elasticity_MULTIPLIER) in transient bursts.
Regarding the feasibility of executing this attack: It would cost an attacker a few more ETH to purchase an entire block (15M fill up the gas tank 100Gwei is 1.5 ether).
Why are we revealing it now?
This threat has been an “open secret” for a long time. In fact, it has been accidentally released publicly at least once and referenced several times in ACD calls without explicit details.
Now that the Berlin upgrade is over, and geth nodes use snapshots by default, we assume the threat is low enough for transparency to take precedence, it’s time to fully disclose the workings behind the scenes.
It’s important to give the community an opportunity to understand why changes are being made that negatively impact the user experience, such as increasing gas costs or limiting refunds.
This post was written by Martin Holst Swende and Peter Szilagyi on 2021-04-23. It was shared with other Ethereum-based projects on April 26, 2021, and was made public on May 18, 2021.