Dodging a bullet: Ethereum State Problems
With this blog post, the intention is to officially disclose a severe threat against the Ethereum platform, which was a clear and present danger up until the Berlin hardfork.
The Ethereum state consists of a patricia-merkle trie, a prefix-tree. This post won’t go into it in too much detail, suffice to say that as the state grows, the branches in this tree become more dense. Each added account is another leaf. Between the root of the tree, and the leaf itself, there are a number of “intermediate” nodes.
In order to look up a given account, or “leaf” in this huge tree, somewhere on the order of 6-9 hashes need to be resolved, from the root, via intermediate nodes, to finally resolve the last hash which leads to the data that we were looking for.
In plain terms: whenever a trie lookup is performed to find an account, 8-9 resolve operations are performed. Each resolve operation is one database lookup, and each database lookup may be any number of actual disk operations. The number of disk operations are difficult to estimate, but since the trie keys are cryptographic hashes (collision resistant), the keys are “random”, hitting the exact worst case for any database.
