Article source: Techub News
Author: Tia, Techub News
Blockchains sacrifice efficiency due to their decentralized design, so improving execution speed has always been one of the urgent problems to solve. The 'execution layer' of a blockchain is the key part that processes each transaction and adds it to the chain. Therefore, enhancing the processing capability at the execution layer has become a core strategy, and parallel execution is a significant breakthrough in this regard.
Traditional blockchains usually process transactions one by one in a serial manner, which greatly limits transaction speed, especially in transaction-heavy networks where congestion can occur. However, through parallel execution, multiple transactions can be processed simultaneously, significantly improving execution efficiency and reducing on-chain pressure.
To better understand what parallelism is, we will first introduce execution and take Ethereum under the PBS model after Merge as an example to explain what execution is and show the position of execution in the entire transaction lifecycle.
Specific aspects of transaction execution
Transaction enters the memory pool and is filtered and sorted: This is the preprocessing stage after the transaction is submitted, which includes the interaction between Mempool, Searcher, and Builder to complete the filtering and sorting of the transaction.
Builder constructs the block (but does not execute): The Builder arranges profitable transactions into a block to complete the packaging and sorting of the 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 of the block and the content of the transactions, and then formally submits the block to the network to begin execution.
Executing transactions: After the block is submitted, nodes execute the transactions within the block one by one. This is a key stage for state updates, where each transaction triggers smart contract calls, account balance changes, or state changes.
Witnessing by validators: Validators witness the execution results and state root of the block and take it as 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 only state synchronization of transactions on a block basis. To maintain the latest on-chain state, nodes typically synchronize data block by block and continuously verify blocks and states. However, to achieve finality under the POS mechanism, an aggregator must aggregate the witness signatures 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, forming a temporary consensus state checkpoint. Only after two consecutive epochs receive witness support from a majority of validators will the blocks and transactions achieve finality.
From the entire lifecycle of transactions, execution occurs after the Proposer verifies the structure of the block and the content of the transactions sent by the Builder. The actual execution process requires processing each transaction one by one and updating the corresponding account or contract states. 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 block execution process includes the series of calculations necessary to transition 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 parallel execution, sequential execution is the currently more common execution method in blockchains. Typically, transactions are executed step by step in order. When a transaction completes execution, Ethereum updates the account state and related information (such as balances, contract storage data) in the account state tree, generating a new account state hash. After all account state trees have been updated, a root 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 of that block.
In this context, the execution order of transactions is crucial. Since the Merkle tree is a binary tree of hash values, the Merkle root formed under different orders will differ.
Parallel execution
In a parallel execution environment, nodes attempt to process transactions in the block in parallel. Instead of executing transactions one by one in sequence, they are distributed across different 'execution paths' so that they can execute simultaneously. Through parallel execution, the system can handle transactions in the block more efficiently and improve throughput.
After all transactions are executed, the node summarizes the execution results (i.e., state updates affected by the transactions) to form a new block state. This state is added to the blockchain, representing the latest global state on the chain.
State conflict
Since parallelism processes transactions simultaneously on different paths, a major challenge of parallelism is state conflicts. That is, multiple transactions may read or write to the same piece of data (state) on the blockchain within the same time frame. If not handled properly, this can lead to uncertain execution results. Due to different update orders of the states, the final computed results can also differ. For example,
Suppose 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 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.
Then increases by 20, ultimately becoming 130.
2. Execute transaction B first, then execute transaction A:
The account balance first increases by 20, becoming 120.
Then increases by 10, ultimately becoming 130.
In both orders, the final balance is 130 because the system ensures the consistency of transaction execution orders.
But in a parallel execution environment, transactions A and B may simultaneously read the initial balance of 100 and perform their 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, because the transactions execute simultaneously, the final balance is only updated to 120 instead of 130, as the operations of transaction A and transaction B 'override' each other's results, resulting in a state conflict.
Such state conflict issues are commonly referred to as 'data overwrites,' where transactions attempt to modify the same data simultaneously, potentially overriding each other's computation results, leading to an incorrect final state. Another type of state conflict that may occur is the inability to guarantee execution order. Since multiple transactions complete operations at different time intervals, different execution orders may lead to different computation results, thus making the results uncertain.
To avoid such uncertainty, blockchain parallel execution systems typically introduce some conflict detection and rollback mechanisms or conduct dependency analysis on transactions in advance to ensure they execute in parallel without affecting the final state consistency.
Optimistic parallelism vs. deterministic parallelism
There are two ways to deal with potential state conflict issues: deterministic parallelism and optimistic parallelism. These two models have different trade-offs in terms of efficiency and design complexity.
Deterministic parallelism requires prior declaration of state access. Validators or sequencers check the declared state access when sorting transactions. If multiple transactions attempt to write to the same state, these transactions will be marked as conflicts, preventing simultaneous execution. Different chains implement the prior declaration of state access in various forms, but generally include the following methods:
Through contract specifications: Developers directly specify the scope of state access in smart contracts. For example, ERC-20 token transfers need to access the balance fields of both the sender and the receiver.
Through structured data declarations in transactions: Adding special fields to transactions to label state accesses.
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 they need to access when calling functions
Optimistic parallelism processes transactions optimistically first and only re-executes the affected transactions in order when conflicts occur. To avoid conflicts as much as possible, the core of optimistic parallelism design is to make quick predictions and assumptions about the state through historical data, static analysis, etc. That is, the system assumes certain operations or state updates are valid without fully verifying them, thus 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 can significantly slow down system performance and increase resource consumption.
Deterministic parallelism avoids potential conflicts of optimistic parallelism by checking state dependencies before transactions, but this requires the developer to accurately declare state dependencies before transaction submission, thereby increasing the complexity of implementation.
EVM parallelism dilemma
Addressing state conflicts involves both deterministic and optimistic approaches, and in the specific implementation of parallelism, considerations from the perspective of the chain's database architecture are also necessary. The state conflict problem in EVM under the Merkle tree architecture is particularly challenging. The Merkle tree is a hierarchical hash structure, and after each 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 layer by layer from the leaf nodes up to the root. Since hashing is irreversible, the upper layers can only be computed once the lower layer's data changes 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 will 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 to achieve for the EVM, as it requires a trade-off between parallelization and state consistency.
Non-EVM parallel solutions
Solana
Unlike Ethereum's global state tree, Solana employs 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 which accounts will be accessed and the required access permissions (read-only or read-write) upon 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, nodes can determine which transactions will access the same accounts and which transactions can be safely executed in parallel, thereby achieving intelligent scheduling and avoiding conflicts, laying the foundation for parallel scheduling.
Since each transaction declares the accounts and permissions needed for access before execution, Solana can check whether there are 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 differs significantly from Ethereum's, making key innovations in architecture and mechanisms, mainly reflected in the account model and state storage.
Ethereum frequently updates its global state tree (MPT) during transaction execution. The states of all accounts and contracts are stored in a shared state tree, and any transaction needs to access and update a part of this state tree. In contrast, Aptos avoids the path conflict issue by dividing accounts into independent state units, with each object being an independent key-value pair that can exist independently of each other, only associating when there is an explicit reference relationship. There are no common tree paths between objects, allowing for 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 and greatly reducing verification time. Moreover, each account's position in the tree is fixed, and the nodes in the tree are independently stored, allowing for parallel updates and searches for multiple accounts.
Aptos is optimistic parallelism, which does not require prior declaration of all account dependencies. To this end, Aptos uses Block-STM, which uses a preset transaction order to estimate dependencies, thereby reducing the number of aborts.
Parallel EVM
Compared to non-EVM parallelism, parallel EVM faces greater technical challenges when dealing with state dependencies, conflict detection, gas management, and rollback mechanisms. To better understand this, we can refer to how some parallel EVM projects (such as Sui, Monad, Canto) address these issues.
Sui
Like Aptos, Sui also uses an object model to handle state, treating each object (such as accounts, smart contract states) as independent resources, which are distinguished by unique object identifiers. When transactions involve different objects, these transactions can be processed in parallel as they operate on different states without causing direct conflicts.
While Sui uses an object model to manage states, in order 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 no conflicts exist between transactions. If conflicts occur, the system uses rollback mechanisms to restore the state.
Sui employs an object model and state isolation technology to effectively avoid state dependency issues. Each object serves as an independent resource, allowing different transactions to execute in parallel, thereby increasing throughput and efficiency. However, the trade-off of this approach is the complexity of the object model and the overhead of rollback mechanisms. If conflicts occur between transactions, part of the state may need to be rolled back, increasing the system's burden and potentially 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 dependent transactions before the actual transaction execution, with predictions primarily carried out by Monad's static code analyzer. Predictions require access to the state, and the way the Ethereum database stores states makes accessing the state very difficult. To make the reading of states during parallelism more efficient, Monad has also restructured the database.
The Monad state tree is partitioned, with each partition maintaining its own state subtree. During updates, only the relevant shards need to be modified without rebuilding the entire state tree. A state index table is used to quickly locate states within partitions, reducing inter-partition interactions.
Summary
The core of parallelism is to improve execution efficiency at the execution layer through multi-path execution. To achieve multi-path execution, the chain needs to perform a series of tasks such as conflict detection and rollback mechanisms to ensure they execute in parallel without affecting the final state consistency, along with some improvements to the database.
Of course, improving the efficiency of the execution layer is not limited to parallelism; optimizations in the execution process can also be achieved by reducing the read and write operations a transaction requires on the database. The overall chain speed improvement involves a broader scope, including enhancements in the consensus layer's efficiency.
Every technology has its specific limitations. Parallelism is just one way to improve efficiency; the decision to use this technology also needs to consider whether it is developer-friendly and whether it can be completed without sacrificing decentralization, etc. The stack of technologies is not necessarily better the more it includes; at least for Ethereum, parallelism is not that attractive. If viewed solely from the perspective of improving efficiency, adding parallelism is not the optimal solution for Ethereum, considering simplicity and Ethereum's current Rollup-centered roadmap.
