Beyond The Meme of Parallelization & Solving For State Growth

Parallelism is not an alien concept to crypto or the rest of the world. It has existed as a design pattern in nature and technology. The neural networks in our brain do not process information sequentially like the EVM :p but absorb and process information from multiple sense organs at once. IBM’s supercomputer, Summit, also performs operations related to data and memory in parallel across multiple processing units. But as we can imagine, parallelism alone does not sustain or scale a system. Summit supports several other optimizations, such as asynchronous I/O, that allow Summit to concurrently perform read/write operations concurrently without waiting for other CPU-bound activities to complete. It also uses an insane amount of storage and memory with over 250 petabytes of storage capacity and over 27K Nvidia Tesla GPUs.

Another aspect of parallelizing VMs I’d like to bring into focus is the reliance of transactions on different pieces of state. Only transactions that do not update the same state can be executed in parallel. As for transactions that depend on the same state, they need to be executed sequentially to avoid any conflicting “write” operations that try and change the same piece of state at the same time. What does this imply? If out of 100% of transactions, 50% of them relate to the same piece of state, the speed up resulting from parallel execution will only affect the 50% of the transactions that are independent and do not access the same piece of state.

Source: https://en.wikipedia.org/wiki/Amdahl%27s_law

Amdahl’s law states that the theoretical speedup you can achieve with parallel execution is limited by the fraction of the workload that is inherently sequential (cannot be parallelized). Based on Paradigm’s historical analysis of Ethereum data, 80% of storage slots are accessed independently. This could theoretically result in a 5x improvement in execution.
Parallel Execution is no holy grail, as most marketing teams portray it. Parallelizing the EVM alone will not result in breakthrough scalability. Optimizations across state growth and state access need to be made. Otherwise, just maximizing transaction execution will lead to uncontrolled state growth, higher fees, and greater centralization due to heavy hardware requirements.

Before we discuss parallelization and its consequences further, let’s examine the current state of EVM execution.

Ethereum’s Sequential Execution

To run Ethereum validators, minimum hardware requirements are currently at 8GB RAM and a CPU with 4 cores, clocked at 2.8 Ghz. While the hardware requirements are multi-core, the EVM executes transactions sequentially using single cores. This is clearly not the most hardware-optimized VM out there.

But why can’t the EVM execute transactions in parallel using multiple cores? One primary reason is that the EVM has no way of identifying which transactions have the same state dependencies.

Another reason lies in how EVM’s data base system is structured. Ethereum uses RockDB and Merkle Particia Trees to store state data such as accounts, contracts, balances etc. Before we dive in deeper, let’s understand what it means to read and write to a Merkle tree.

Write operations add new data to the MPT. New data is added as leaf nodes at the bottom of the Merkle tree. The hash of the new data is computed and stored in the corresponding leaf node.

The hash values are then pushed upwards by computing the hash of the child hashes at each level until reaching the root node.

Read operations to verify existing data. To verify whether a particular piece of data is part of the Merkle tree, a Merkle proof or path is used. The Merkle path consists of t