Author: Tia, Techub News
Blockchain sacrifices efficiency due to its decentralized design, so improving execution speed has always been one of the urgent issues to resolve. The 'execution layer' of the blockchain is the key part that processes each transaction and adds it to the chain. Enhancing processing capability in the execution layer has become one of the core strategies, and parallel execution is a significant breakthrough in this regard.
Traditional blockchains typically process transactions serially one by one, which greatly limits transaction speed, especially in transaction-intensive networks where congestion may occur. However, through parallel execution, multiple transactions can be processed simultaneously, significantly improving execution efficiency and reducing pressure on the chain.
To better understand what parallelism is, we will first introduce execution, using Ethereum under the PBS model after the Merge as an example to explain what execution is, while showing where execution fits into the entire transaction lifecycle.
Specific steps of transaction execution
Transactions enter the memory pool and are filtered and sorted: This is the preprocessing stage after a transaction is submitted, involving the interaction of Mempool, Searcher, and Builder to complete the filtering and sorting of transactions.
Builder constructs blocks (but does not execute): 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, then formally submits the block to the network to begin execution.
Execute transactions: After the block is submitted, nodes execute the transactions in the block one by one. This is the critical phase of state updates, where each transaction triggers smart contract calls, changes in account balances, or state changes.
Witnessing by validators: Validators witness the execution results and state roots of blocks and confirm them as final. This ensures the authenticity and validity of blocks 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 only state synchronization for transactions at the block level. To maintain the latest on-chain state, nodes typically sync data block by block and continuously validate blocks and states. However, to achieve finality under the POS mechanism, aggregators need to collect the witness signatures from each slot into a complete signature and pass it to the proposer of the next slot, and validators need to confirm the state of all blocks in that epoch based on the number of votes after one epoch, forming a temporary consensus state checkpoint. Only after two consecutive epochs receive majority support from validators can blocks and transactions achieve finality.
From the entire lifecycle of transactions, 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. After all transactions are executed, the Proposer calculates a new state root (Merkle root), summarizing the execution results of all transactions in the current block and the final global state. In simple terms, the complete execution process of a block includes a series of calculations needed to transform Ethereum from the previous state to the next state, from the execution of each transaction to the calculation of the Merkle root.
Sequential execution
In contrast to parallelism is sequential execution, which is the more commonly used execution method in blockchain today. Typically, transactions are executed step by step in sequence. Once a transaction is completed, 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. Once all account state trees are updated, they form a hash of the root node of the state tree known as the state Merkle root. After completing the state Merkle root, transaction Merkle root, and receipt Merkle root, the block header undergoes hashing to generate the block hash.
In this context, the order of transaction execution 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 attempt to process transactions in the block in parallel. Transactions are not executed one by one in order but are assigned to different 'execution paths' to allow simultaneous execution. Through parallel execution, the system can handle transactions in the block more efficiently, increasing throughput.
Once all transactions are completed, nodes summarize the execution results (i.e., state updates impacted by 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
Because parallelism processes transactions on different paths simultaneously, one of the major challenges of parallelism is state conflicts. This means that multiple transactions may simultaneously attempt to read or write to the same part of data (state) on the blockchain. If not handled properly, this can lead to uncertain execution results. Because the update order of states differs, the final computational results may also differ. For example,
Assuming there are two transactions, transaction A and transaction B, both trying to update the balance of the same account:
Transaction A: Increase account balance by 10.
Transaction B: Increase account balance by 20.
The initial balance of the account is 100.
If we execute serially, the result of the execution order is deterministic:
1. Execute transaction A first, then execute transaction B:
The account balance first increases by 10, becoming 110.
Increase by another 20, finally becoming 130.
2. Execute transaction B first, then execute transaction A:
The account balance first increases by 20, becoming 120.
Increase by 10, eventually becoming 130.
In both orders, the final balance is 130 because the system ensures the consistency of transaction execution order.
But in a parallel execution environment, transactions A and B may read the initial balance of 100 at the same time and perform their respective calculations:
Transaction A reads a balance of 100 and updates it to 110 after calculation.
Transaction B also reads a balance of 100 and updates it to 120 after calculation.
In this case, due to transactions executing simultaneously, the final balance only updates to 120, rather than 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 override', meaning that when transactions attempt to simultaneously modify the same data, they may overwrite each other's computational results, leading to incorrect final states. Another potential issue caused by state conflicts is the inability to guarantee execution order. Because multiple transactions complete operations at different times, they can result in different execution orders. Different orders may lead to different computational results, making the results uncertain.
To avoid this uncertainty, blockchain parallel execution systems often introduce some conflict detection and rollback mechanisms, or perform dependency analysis on transactions in advance to ensure they can be executed in parallel without affecting final state consistency.
Optimistic parallel vs. deterministic parallel
There are two approaches to dealing with potential state conflict issues: deterministic parallelism and optimistic parallelism. Both modes have trade-offs in terms of efficiency and design complexity.
Deterministic parallelism requires declaring state access in advance, and validators or sequencers will check the declared state access when sorting transactions. If multiple transactions attempt to write to the same state, those transactions will be marked as conflicts and prevented from executing simultaneously. Different chains implement the pre-declaration of state access in various ways, but generally include the following forms:
Through contract specification constraints: Developers directly specify the state access scope in smart contracts. For example, an ERC-20 token transfer requires access to the balance fields of both the sender and receiver.
By declaring structured data through transactions: Adding specific fields in the transaction to mark state access.
Through compiler analysis: Compilers for high-level languages can statically analyze contract code and automatically generate a set of state accesses.
Through framework-enforced declarations: Some frameworks require developers to explicitly specify the state to be accessed when calling functions.
Optimistic parallelism will optimistically process transactions first, and when conflicts occur, affected transactions will be re-executed in order. To avoid conflicts as much as possible, the core of the optimistic parallel design is to quickly predict and assume state through historical data, static analysis, and other means. That is, the system assumes that certain operations or state updates are valid without complete verification, aiming to avoid waiting for all validation processes to improve performance and throughput.
Although optimistic parallelism can avoid conflicts as much as possible through rapid prediction and assumptions about state, there are still unavoidable challenges, especially involving contract execution or cross-chain transactions. If conflicts frequently occur, re-execution may significantly slow down system performance and increase computational resource consumption.
Deterministic parallelism avoids potential conflicts of optimistic parallelism by checking state dependencies before transactions, but this requires developers to accurately declare state dependencies before submission, thus increasing implementation complexity and raising the bar for developers.
EVM parallelism dilemma
Addressing state conflicts involves both deterministic and optimistic approaches. In the specific process of implementing parallelism, it is also necessary to consider the architecture of the chain database. The issue of state conflicts in parallelism is particularly difficult under the Merkle tree architecture of the EVM. The Merkle tree is a hierarchical hash structure, and every 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 from the leaf nodes up to the root node. Since hashing is non-reversible, it can only compute the upper layers after the changes in the lower layers are completed. This feature makes it difficult to update in parallel.
If two transactions execute in parallel and access the same state (like account balance), it will cause conflicts in the Merkle tree nodes. Resolving such conflicts usually requires additional transaction management mechanisms to ensure that a consistent root hash value can be obtained across multiple branches. This is not easy to achieve for the EVM, as it requires making 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 and the required access permissions (read-only or read/write) at the time of submission. This design allows blockchain nodes to analyze the resources each transaction needs to access before execution. Because all account dependencies are explicitly declared before execution begins, nodes can determine which transactions will access the same accounts and which can safely execute in parallel, thus achieving intelligent scheduling and avoiding conflicts, laying the foundation for parallel scheduling.
Because each transaction declares the accounts and permissions that need to be accessed 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 assign them to different processors for parallel execution.
Aptos
Aptos's design for parallel execution is quite different from Ethereum's. It makes some key innovations in architecture and mechanisms, mainly reflected in its account model and state storage.
Ethereum frequently needs to update the global state tree (MPT) when executing transactions. The states of all accounts and contracts are stored in a shared state tree, and any transaction must access and update a part of this state tree. In contrast, Aptos divides accounts into independent state units, where each object is an independent key-value pair, allowing objects to exist independently of each other, only relating when there is an explicit reference. There are no common tree paths between objects, avoiding lock contention, enabling complete parallelism.
Aptos's 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, the position of each account in the tree is fixed, and the nodes in the tree are independently stored, allowing for parallel updates and queries of multiple accounts.
Aptos is optimistically parallel; it does not require all declared account dependencies to be provided beforehand. For this, Aptos uses Block-STM, which estimates dependencies based on a predefined transaction order to reduce aborts.
Parallel EVM
Compared to non-EVM parallelism, parallel EVM faces greater technical challenges when 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 (e.g., account, smart contract state) as an independent resource. These objects are distinguished by object unique identifiers. When transactions involve different objects, these transactions can be processed in parallel because they operate on different states and do not produce direct conflicts.
Although Sui uses an object model to manage state, in order to be compatible with the EVM, Sui's architecture bridges the object model and the EVM's account model through additional adaptation layers or abstraction mechanisms.
In Sui, transaction scheduling uses an optimistic parallel strategy, assuming there are no conflicts between transactions. If a conflict occurs, the system uses a rollback mechanism to restore the state.
Sui uses an object model and state isolation technology to effectively avoid state dependency issues. Each object acts as an independent resource, allowing different transactions to execute in parallel, thereby 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, it may require rolling back part of the state, increasing the burden on the system and possibly affecting 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 still predict some transactions with dependencies before the actual execution of transactions, mainly using Monad's static code analyzer for prediction. Predictions require accessing states, and the way Ethereum's database stores states makes state access very difficult. To make parallelism more efficient during the state reading process, Monad has also restructured the database.
Monad's state tree is partitioned, with each partition maintaining its own state subtree. During updates, only the relevant shards need to be modified, without the need to rebuild the entire state tree. A state index table is used to quickly locate states within the partition, reducing interaction between partitions.
Summary
The core of parallelism is to improve the execution efficiency of the execution layer through multi-path execution. To achieve multi-path execution, the chain needs to implement a series of measures like conflict detection and rollback mechanisms to ensure that they can be executed in parallel without affecting final state consistency, and to make certain improvements to the database.
Of course, improving execution layer efficiency is not limited to parallelism; optimizations in the execution phase can also be achieved by reducing the read and write operations required for a transaction on the database. Moreover, the overall speed enhancement of the chain involves a broader scope, including improvements in the consensus layer efficiency.
Every technology has specific limitations behind it. Parallelism is just one way to enhance efficiency; ultimately, whether to use this technology needs to consider its developer-friendliness and whether it can be achieved without sacrificing decentralization, among other factors. The stacking of technologies is not necessarily better; at least for Ethereum, parallelism is not as attractive. From the perspective of enhancing efficiency alone, introducing parallelism is not the optimal solution for Ethereum, whether considering simplicity or Ethereum's current roadmap centered on Rollup.