“`html
\n<\/p>\n
Through this blog entry, the aim is to formally unveil a significant risk to the Ethereum network, which posed a clear and present threat up until the Berlin hardfork.<\/p>\n
<\/p>\n
<\/p>\n
Let’s start with some context on Ethereum and State.<\/p>\n
<\/p>\n
The Ethereum state is made up of a patricia-merkle trie, which is a type of prefix-tree. This post will not delve too deeply into this structure, but it is important to note that as the state expands, the branches of this tree become denser. Every additional account represents another leaf. Between the tree’s root and the actual leaf, there are several “intermediate” nodes.<\/p>\n
<\/p>\n
To locate a specific account, or “leaf” within this vast tree, approximately 6-9 hashes must be resolved, going from the root through the intermediate nodes to finally determine the last hash that leads to the desired data.<\/p>\n
<\/p>\n
In simple terms: when a trie lookup is executed to locate an account, around 8-9 resolve operations take place. Each resolving operation constitutes one database query, and each database query may involve various actual disk operations. Estimating the quantity of disk actions is challenging, but given that the trie keys are cryptographic hashes (collision-resistant), the keys appear “random”, resulting in the worst-case scenario for any database.<\/p>\n
<\/p>\n
As Ethereum has expanded, it has been necessary to increase the gas fees associated with operations accessing the trie. This adjustment was made in Tangerine Whistle<\/span> at block 2,463,000<\/span> in October 2016, which included EIP 150<\/a>. EIP 150 significantly raised certain gas costs and introduced a series of modifications to guard against DoS attacks, following the so-called “Shanghai attacks”.<\/p>\n <\/p>\n Another such increase occurred during the Istanbul<\/span> upgrade, at block 9,069,000<\/span> in December 2019. In this update, EIP 1884<\/a> was initiated.<\/p>\n <\/p>\n EIP-1884 introduced the following amendments:<\/p>\n <\/p>\n <\/p>\n <\/p>\n In March 2019, Martin Swende conducted some measurements<\/a> concerning EVM opcode efficiency. This investigation subsequently resulted in the formulation of EIP-1884. A few months prior to the activation of EIP-1884, the document Broken Metre<\/a> was published (September 2019).<\/p>\n <\/p>\n Two security researchers from Ethereum — Hubert Ritzdorf and Matthias Egli — collaborated with one of the authors of the paper; Daniel Perez, and ‘weaponized’ an exploit they submitted to the Ethereum bug bounty on October 4, 2019.<\/p>\n <\/p>\n We encourage you to read the submission<\/a> thoroughly, as it’s a well-crafted report.<\/p>\n <\/p>\n On a platform aimed at cross-client security, developers from Geth, Parity, and Aleth were notified about the submission on that same day.<\/p>\n <\/p>\n The core of the exploit is to induce random trie lookups. A very straightforward version could be:<\/p>\n <\/p>\n <\/p>\n In their report, the researchers executed this exploit against nodes synced to the mainnet, via eth_call<\/span>, and these were their findings when executed with 10M<\/span> gas:<\/p>\n <\/p>\n <\/p>\n It is evidently clear that the alterations made in EIP 1884 were significantly reducing the impact of the assault, yet they were still far from adequate.<\/p>\n <\/p>\n This transpired right before Devcon in Osaka. During During Devcon, awareness of the issue was disseminated among the primary client developers for the mainnet. We also convened with Hubert and Mathias, alongside Greg Markou (from Chainsafe — who were engaged with ETC). Developers of ETC had also received the findings.<\/p>\n As 2019 came to an end, we realized we faced bigger challenges than we had previously foreseen, where hostile transactions could result in block times extending into the minute range. To complicate matters further: the developer community was already dissatisfied with EIP-1884, which had disrupted specific contract flows, and both users and miners were eagerly advocating for increased block gas limits.<\/p>\n Additionally, merely two months later, in December 2019, Parity Ethereum announced<\/a> their exit from the ecosystem, allowing OpenEthereum to assume responsibility for the codebase’s maintenance.<\/p>\n A novel coordination channel for clients was established, wherein developers from Geth, Nethermind, OpenEthereum, and Besu collaborated further.<\/p>\n We understood that we would need to implement a dual approach to address these challenges. One strategy involved working on the Ethereum protocol, aiming to resolve this issue at the protocol level; ideally without disrupting contracts, and preferably without penalizing ‘positive’ actions, while still thwarting attacks.<\/p>\n The second strategy would involve software engineering, altering the data models and structures within the clients.<\/p>\n The initial attempt at addressing such types of attacks can be found here<\/a>. In February 2020, it was officially introduced as EIP 2583<\/a>. The concept entails simply imposing a penalty each time a trie lookup results in a miss.<\/p>\n However, Peter devised a workaround for this concept — the ‘shielded relay’ attack – imposing an upper limit (approximately ~800) on the magnitude of such a penalty can effectively be.<\/p>\n The challenge with penalties for misses<\/em> is that the lookup needs to occur first to establish that a penalty should be enforced. If there isn\u2019t sufficient gas available for the penalty, an unpaid execution has taken place. Even though that results in a throw, these state reads can be encapsulated within nested calls; allowing the outer caller to persist in executing the attack without serving the (full) penalty.<\/p>\n Due to this, the EIP was discontinued while we sought a superior alternative.<\/p>\n While iterating through these various concepts, Vitalik Buterin suggested merely increasing the gas costs, while maintaining access lists. In August 2020, Martin and Vitalik commenced iterations on what was to evolve into EIP-2929<\/a> and its partner EIP, EIP-2930<\/a>.<\/p>\n EIP-2929 effectively resolved a significant number of the previous issues.<\/p>\n On April 15th, 2021, both went live with the Berlin<\/span> upgrade.<\/p>\n Peter’s initiative to address this issue was dynamic state snapshots<\/a>, implemented in October 2019.<\/p>\n A snapshot serves as an additional data structure for storing the Ethereum state in a flat format, which can be fully constructed online during the active operation of a Geth node. The advantage of the snapshot is that it functions as an acceleration structure for state accesses:<\/p>\n The downside of the snapshot is that the raw account and storage data is essentially duplicated. In the context of the mainnet, this translates to an additional 25GB<\/span> of SSD storage used.<\/p>\n The concept of dynamic snapshots had already been initiated in mid-2019, primarily aiming to enable snap<\/span> sync. At that time, there were several “large projects” the Geth team was involved with.<\/p>\n “`sync<\/li>\n <\/p>\n Nevertheless, a decision was made to fully focus on snapshots, deferring other initiatives for the time being. These established the foundation for what would eventually become snap\/1<\/span> sync algorithm<\/a>. It was integrated in March 2020.<\/p>\n <\/p>\n With the “dynamic snapshot” feature released into the ecosystem, we gained some breathing space. Should the Ethereum network face an attack, it would be challenging, indeed, but communicating to users about enabling the snapshot would at least be feasible. The entire snapshot generation process would require considerable time, and synchronizing the snapshots was not yet possible, but the network could continue its operations nonetheless.<\/p>\n <\/p>\n <\/p>\n Between March-April 2021, the snap\/1<\/span> protocol was introduced in geth, allowing synchronization via the new snapshot-based algorithm. Although it wasn’t the standard synchronization method yet, it represented a significant (crucial) progression toward making snapshots not just beneficial as an attack deterrent, but also as a substantial enhancement for users.<\/p>\n <\/p>\n On the protocol front, the Berlin<\/span> upgrade was implemented in April 2021.<\/p>\n <\/p>\n Some benchmarking conducted in our AWS monitoring environment is outlined below:<\/p>\n <\/p>\n <\/p>\n The (approximate) data suggests that the Berlin<\/span> upgrade diminished the attack effectiveness by 5x<\/span>, while snapshots further mitigated it by 10x<\/span>, resulting in a total impact reduction of 50x<\/span>.<\/p>\n <\/p>\n We project that currently, on Mainnet (15M gas), it would be feasible to create blocks that would require 2.5-3s<\/span> to process on a geth<\/span> node without<\/em> snapshots. This figure is expected to continually decline (for non-snapshot nodes) as the state expands.<\/p>\n <\/p>\n If refunds are utilized to augment the effective gas usage within a block, this can be further intensified by a factor of (max) 2x<\/span>. With EIP 1559<\/a>, the block gas limit will possess greater elasticity, facilitating an additional 2x<\/span> (the ELASTICITY_MULTIPLIER<\/span>) during temporary surges.<\/p>\n <\/p>\n\n
The issue(s)<\/h2>\n
\tjumpdest <\/span>;<\/span> jump label, start of loop\n<\/span>\tgas <\/span>;<\/span> acquire a <\/span>'random'<\/span> value on the stack\n<\/span>\textcodesize <\/span>;<\/span> initiate trie lookup\n<\/span>\tpop <\/span>;<\/span> disregard the extcodesize outcome\n<\/span>\tpush1 0x00 <\/span>;<\/span> jump label dest\n<\/span>\tjump <\/span>;<\/span> revert to start\n<\/span><\/code><\/pre>\n<\/div>\n\n
\n
\n<\/li>\n
\n
\n<\/li>\n<\/ul>\n
\n“““html<\/p>\nThe solution(s)<\/h2>\n
Protocol work<\/h3>\n
\n
\n
Development work<\/h3>\n
\n
\n
Connecting the threads<\/h3>\n
\n