The core of parallelism is to improve execution efficiency by executing through multiple paths. To achieve multi-path execution, the chain needs to perform a series of actions such as conflict detection and rollback mechanisms to ensure that they can execute in parallel without affecting the final state consistency, and to improve the database to some extent.
Written by: Tia, Techub News
Blockchain sacrifices efficiency due to its decentralized design, so improving execution speed has always been one of the urgent problems to solve. The 'execution layer' of the blockchain is the key part that processes each transaction and adds it to the chain. To accelerate processing capacity, enhancements at the execution layer have become one of the core strategies, with parallel execution being an important breakthrough in this regard.
Traditional blockchains usually process transactions serially one by one, greatly limiting transaction speed, especially in transaction-intensive networks, which can lead to congestion. However, through parallel execution, multiple transactions can be processed simultaneously, significantly improving execution efficiency and alleviating on-chain pressure.
To better understand what parallelism is, we will first introduce execution starting with Ethereum under the PBS model after Merge, to explain what execution is while showing its position in the entire transaction lifecycle.
Specific steps of transaction execution
Transactions enter the memory pool and are filtered and sorted: This is the pre-processing stage after the transaction is submitted, including interactions between Mempool, Searcher, and Builder to complete the filtering and sorting of transactions.
Builder constructs the block (but does not execute): The Builder arranges profitable transactions into a block to complete the packaging and sorting of transactions.
Proposer verifies and submits the block: After the block is constructed, the Builder sends the block proposal to the Proposer. The Proposer verifies the structure and transaction content of the block and then officially submits the block to the network to start execution.
Execute transactions: After the block is submitted, nodes execute the transactions in the block one by one. This is the key phase for state updates, where each transaction triggers smart contract calls, account balance changes, or state changes.
Witnesses witness: Validators witness the execution results and state root of the block and confirm them as the final confirmation. This ensures the authenticity and validity of the block at the execution layer and prevents inconsistencies.
State synchronization: Each node synchronizes the execution results of the block (such as account balances, contract state updates, etc.) to its local state. After executing each transaction, the node calculates and stores a new state root to be used as the initial state in the next block.
Of course, this is just state synchronization at the block level. To maintain the latest on-chain state, nodes generally synchronize data block by block and continuously verify blocks and states. However, to achieve finality under the POS mechanism, the aggregator needs to aggregate the signatures of witnesses from each Slot into a complete signature and pass it to the proposer of the next Slot. Validators need to confirm the state of all blocks within that Epoch based on the number of votes after one Epoch has passed, forming a temporary consensus state checkpoint. Only when two consecutive Epochs receive testimony support from the majority of validators will the blocks and transactions achieve finality.
From the entire lifecycle of a transaction, execution occurs after the Proposer verifies the structure and transaction content of the block sent by the Builder. The actual execution process requires processing transactions one by one and updating the corresponding account or contract state. Once all transactions have been executed, the Proposer will calculate a new state root (Merkle root), summarizing the execution results of all transactions in the current block and the final global state. In simpler terms, the complete block execution process includes a series of computations needed to transform Ethereum from the previous state to the next state, from executing each transaction to calculating the Merkle root.
Sequential Execution
In contrast to parallel execution, sequential execution is the more common execution method in current blockchains. Generally, transactions are executed step by step in order. When a transaction completes execution, Ethereum updates the account state and related information (such as balance, contract storage data) in the account state tree, generating a new account state hash. After all account state trees have been updated, a root node hash known as the state Merkle root is formed. After completing the state Merkle root, transaction Merkle root, and receipt Merkle root, the block header undergoes a hash calculation to generate the block hash.
Among these, the execution order of transactions is crucial. Since the Merkle tree is a binary tree of hash values, the Merkle root values formed under different orders will differ.
Parallel Execution
In a parallel execution environment, nodes will attempt to process transactions in parallel within blocks. Transactions are not executed one by one in order but are allocated to different 'execution paths' so they can execute simultaneously. By executing in parallel, the system can process transactions in blocks more efficiently, improving throughput.
Once all transactions have been executed, the nodes will aggregate the execution results (i.e., the state updates affected by the transactions) to form a new block state. This state will be added to the blockchain, representing the latest global state on the chain.
State Conflict
Since parallel processing handles transactions simultaneously on different paths, one major challenge of parallelism is state conflict. This means that multiple transactions may read or write to the same portion of data (state) on the blockchain within the same time frame. If not handled properly, this situation can lead to uncertain execution results. Because the order of state updates differs, the final computation results will also vary. For example,
Assume there are two transactions, Transaction A and Transaction B, both attempting to update the balance of the same account:
Transaction A: Increase account balance by 10.
Transaction B: Increase account balance by 20.
Initial account balance is 100.
If we execute sequentially, the result of the execution order is deterministic:
1. Execute Transaction A first, then Transaction B:
Account balance first increases by 10, resulting in 110.
Then increases by 20, resulting in a final balance of 130.
2. Execute Transaction B first, then Transaction A:
Account balance first increases by 20, resulting in 120.
Then increases by 10, resulting in a final balance of 130.
In both of these sequences, the final balance is 130 because the system ensures the consistency of the execution order of transactions.
However, in a parallel execution environment, Transactions A and B may both read the initial balance of 100 and perform their respective calculations:
Transaction A reads a balance of 100, calculates, and updates the balance to 110.
Transaction B also reads a balance of 100, calculates, and updates the balance to 120.
In this case, since the transactions execute simultaneously, the final balance is only updated to 120 instead of 130, because the operations of Transactions A and B 'overwrote' each other's results, creating a state conflict.
Such state conflict issues are often referred to as 'data overwrites,' meaning that when transactions attempt to modify the same data simultaneously, they may overwrite each other's computation results, leading to incorrect final states. Another potential issue caused by state conflicts is the inability to guarantee execution order. Since multiple transactions complete operations at different times, different execution orders may result in different computation results, making the outcome uncertain.
To avoid this uncertainty, blockchain parallel execution systems typically introduce some conflict detection and rollback mechanisms or perform dependency analysis on transactions in advance to ensure they can execute in parallel without affecting final state consistency.
Optimistic Parallelism vs. Deterministic Parallelism
There are two approaches to address potential state conflict issues: deterministic parallelism and optimistic parallelism. These two modes trade off efficiency and design complexity.
Deterministic parallelism requires declaring state access in advance. Validators or sequencers will check the declared state accesses when sorting transactions. If multiple transactions attempt to write to the same state, these transactions will be marked as conflicts to avoid simultaneous execution. Different chains implement the form of declaring state access in various ways, but generally include the following methods:
Through contract specifications: developers directly specify the state access scope in smart contracts. For example, ERC-20 token transfers require access to the sender's and receiver's balance fields.
Through structured data declarations in transactions: adding dedicated fields in the transaction to label state access.
Through compiler analysis: high-level language compilers can statically analyze contract code to automatically generate a set of state accesses.
Through framework-enforced declarations: some frameworks require developers to explicitly specify the state that needs to be accessed when calling functions.
Optimistic parallelism will optimistically process transactions first, and when conflicts occur, it will reorder the affected transactions for sequential re-execution. To minimize conflicts, the core design of optimistic parallelism is to quickly predict and hypothesize states through historical data, static analysis, etc. That is, the system assumes that certain operations or state updates are valid without complete verification to avoid waiting for all verification processes, thereby improving performance and throughput.
Although optimistic parallelism can avoid conflicts as much as possible through quick predictions and assumptions about states, there are still some unavoidable challenges, especially involving contract execution or cross-chain transactions. If conflicts occur frequently, re-execution may significantly slow down system performance and increase computational resource consumption.
Deterministic parallelism avoids potential conflicts of optimistic parallelism by performing state dependency checks before transactions, but since it requires accurately declaring state dependencies before submitting transactions, it raises higher requirements for developers, thereby increasing implementation complexity.
EVM Parallelism Dilemma
Addressing state conflicts involves not only determinism and optimism but also requires consideration from the perspective of the chain's database architecture in the actual implementation of parallelism. The issue of state conflicts in parallelism is particularly challenging in the EVM under the Merkle tree architecture. The Merkle tree is a hierarchical hash structure, and each time a transaction modifies a piece of state data, the root hash of the Merkle tree also needs to be updated. This updating process is recursive, calculating upwards from leaf nodes to the root node. Since hashing is irreversible, the upper levels can only be calculated once the changes in the lower levels are complete, making it difficult to update in parallel.
If two transactions execute in parallel and access the same state (such as account balance), it can cause conflicts in the Merkle tree nodes. Resolving such conflicts typically requires additional transaction management mechanisms to ensure consistent root hash values across multiple branches. This is not easy for EVM because it must make trade-offs between parallelization and state consistency.
Non-EVM Parallel Solutions
Solana
Unlike Ethereum's global state tree, Solana adopts an account model. Each account is an independent storage space stored in the ledger, thus avoiding path conflict issues.
Solana is deterministic parallelism. In Solana, each transaction must explicitly declare the accounts to be accessed and the required access permissions (read-only or read-write) when submitted. This design allows blockchain nodes to analyze the resources needed by each transaction in advance before execution. Because the transactions have clearly stated all account dependencies before execution begins, the nodes can determine which transactions will access the same accounts and which can safely execute in parallel, thus enabling intelligent scheduling and avoiding conflicts, laying the foundation for parallel scheduling.
Since each transaction has declared the accounts and permissions it needs to access before execution, Solana can check for account dependencies between transactions (Sealevel model). If there are no shared read/write accounts between transactions, the system can allocate them to different processors for parallel execution.
Aptos
Aptos' parallel execution design is vastly different from Ethereum, making some key innovations in architecture and mechanism, mainly reflected in account models and state storage.
When executing transactions, Ethereum frequently updates the global state tree (MPT). The states of all accounts and contracts are stored in a shared state tree, and any transaction needs to access and update a portion of this state tree. Aptos, on the other hand, partitions accounts into independent state units, each object being an independent key-value pair. Objects can exist independently of each other without affecting each other, and only when a clear reference relationship exists will they be associated. There are no common tree paths between objects, preventing lock contention, allowing complete parallelism.
Aptos' underlying data structure is the Jellyfish Merkle Tree. The state of each object is ultimately stored in the JMT as independent key-value pairs. Unlike Ethereum's MPT, the Jellyfish Merkle Tree is structured as a complete binary tree, simplifying the storage and query paths for nodes, significantly reducing verification time. Additionally, each account has a fixed position in the tree, and the nodes in the tree are stored independently, allowing for parallel updates and lookups of multiple accounts.
Aptos is optimistic parallelism; it does not need to pre-declare the dependencies of all the accounts. For this, Aptos uses Block-STM, which estimates dependencies using a preset transaction order, thus reducing the number of aborts.
Parallel EVM
Compared to non-EVM parallelism, parallel EVM faces greater technical challenges in handling state dependencies, conflict detection, gas management, and rollback mechanisms. To better understand this, we can refer to how some parallel EVM projects (like Sui, Monad, Canto) solve these issues.
Sui
Like Aptos, Sui also uses an object model to handle state, treating each object (such as account, smart contract state) as an independent resource, distinguished by a unique identifier. When transactions involve different objects, these transactions can be processed in parallel because they operate on different states, avoiding direct conflicts.
Although Sui uses an object model to manage state, to be compatible with EVM, Sui's architecture bridges the object model and EVM's account model through an additional adaptation layer or abstraction mechanism.
In Sui, transaction scheduling uses an optimistic parallel strategy, assuming there are no conflicts between transactions. If conflicts occur, the system will use rollback mechanisms to restore the state.
Sui uses an object model and state isolation technology, effectively avoiding state dependency issues. Each object acts as an independent resource, allowing different transactions to execute in parallel, thus improving throughput and efficiency. However, the trade-off of this method is the complexity of the object model and the overhead of rollback mechanisms. If conflicts occur between transactions, some states need to be rolled back, which increases the burden on the system and may affect the efficiency of parallel processing. Compared to non-EVM parallel systems (like Solana), Sui requires more computational and storage resources to maintain efficient parallelism.
Monad
Like Sui, Monad also adopts optimistic parallelism. However, Monad's optimistic parallelism will predict some dependent transactions before executing the specific transactions, mainly through Monad's static code analyzer. Prediction requires access to the state, and the way Ethereum stores the state in its database makes state access very difficult. To make the parallelism in the state reading process more efficient, Monad has also restructured the database.
The Monad state tree is partitioned, with each partition maintaining its own state subtree. Updates only require modifying the relevant shards without needing to rebuild the entire state tree. A state index table quickly locates the state within the partition, reducing interactions between partitions.
Summary
The core of parallelism is to improve execution efficiency by executing through multiple paths. To achieve multi-path execution, the chain needs to perform a series of actions such as conflict detection and rollback mechanisms to ensure that they can execute in parallel without affecting the final state consistency, and to improve the database to some extent.
Of course, improving execution layer efficiency is not limited to just parallelism; optimization of execution processes can also be achieved by reducing read/write operations required by a single transaction on the database. The scope of improving chain speed is broader, including enhancements in consensus layer efficiency.
Every technology has its specific limitations. Parallelism is just one way to improve efficiency; whether to use this technology also needs to consider its friendliness to developers and whether it can be achieved without sacrificing decentralization, etc. The stacking of technologies is not necessarily better; at least for Ethereum, parallelism is not that attractive. From the perspective of improving efficiency alone, adding parallelism is not the optimal solution for Ethereum, whether from the standpoint of simplicity or considering Ethereum's current Rollup-centric roadmap.