Parallel Ethereum Virtual Machine (EVM) promises to significantly enhance transaction processing and scalability. Since 2021, the core team at BNB Chain and NodeReal has been actively exploring and implementing parallel EVM solutions within the BNB Chain ecosystem, including the BNB Smart Chain (BSC) and opBNB. 

This blog delves into the core principles of parallel EVM’s algorithms, showcases the specific solutions implemented in BNB Chain, and unveils our exciting roadmap for further development. Join us as we explore the full potential of this revolutionary technology!

Introduction to EVM Execution

EVM is a virtual instruction interpreter similar to the Java Virtual Machine (JVM). It executes bytecode, which is a series of specialized instructions packaged within transactions. These transactions, submitted by users, ultimately modify the state of the network.

Here’s how the EVM works:

1. Transaction Selection:Transactions compete to be included in a block, akin to tasks lining up in a computer's queue. Once selected, they proceed into the EVM.
2. Opcode Execution: Each transaction contains a string of EVM opcodes, like "PUSH" (place a value on the stack) or "ADD" (combine two values). The EVM reads and executes these opcodes one by one, manipulating internal data structures like a stack.
3. State Database Access: As the EVM processes transactions, it needs to access and update the global state database, which holds information about all accounts and their balances.

Remember, interactions with the state database always occur through transactions and their embedded EVM opcodes, ensuring a secure and controlled environment.

Why Parallel EVM is not easy

In Web3 applications, the stateDB (state database) plays a crucial role in ensuring data integrity and accurate modification. To achieve this, the design prioritizes two key characteristics:

1. Observability: All accounts can access and read the current state of the database, fostering transparency and trust in the system.
2. Modifiable by Design: Authorized accounts can initiate transactions that update the stateDB. However, to guarantee the consistency and correctness of these changes, transactions are executed in a specific sequence.

Example:

Alice sends 2 BNB to Bob, while simultaneously Danil sends 3 BNB to Eric. With sequential execution, the stateDB updates occur in the following order:

1. Alice's transaction: Alice's account balance decreases by 2 BNB, and Bob's account balance increases by 2 BNB.
2. Danil's transaction: Danil's account balance decreases by 3 BNB, and Eric's account balance increases by 3 BNB.

Given that transactions TX1 and TX2 modify distinct accounts, their execution order becomes inconsequential in this scenario. This opens the door to parallel execution, potentially enhancing system performance.However, the key lies in identifying and managing dependencies. 

Dependencies arise when transactions share a common state, like Bob transferring to Danil before Danil transfers to Eric (TX3). In such cases, sequential execution is crucial. Executing TX3 before TX2 would fail due to insufficient funds in Danil's account, causing inconsistencies in the state.

The EVM faces challenges in executing transactions in parallel due to the difficulty of pre-determining dependencies between them before they are included in a block. This lack of visibility into potential conflicts necessitates sequential execution to ensure data integrity.

The sequential nature of transaction execution in EVM presents a fundamental hurdle to achieving high throughput and scalability, especially as blockchains experience surges in transaction volume. Notably, blockchains like BSC have recorded peak days exceeding 32M transactions/day, while opBNB reached an all-time high of 71M transactions/day. 

Parallel EVM Ideas

Parallel EVM seeks to unlock the scalability potential of the EVM by enabling parallel transaction execution. This approach leverages the fact that independent transactions can be processed simultaneously, boosting throughput.

The core concept involves running multiple EVM instances concurrently on different threads. These instances execute transactions independently, and their results are later merged and submitted as a final state update. This parallelization significantly increases processing capacity, especially for high transaction volumes. 

The diagram shows how a Parallel EVM executes transactions concurrently across four independent EVM instances, each on a separate thread.

Parallel EVM introduces exciting possibilities for improved scalability, but several questions need to be answered for its successful implementation:

1. Transaction Scheduling: How do we efficiently distribute transactions across multiple EVM instances? 
2. Dependency Management: What happens when transactions rely on each other's outcomes?
3. Dependency Detection: How can we accurately determine whether transactions have dependencies before executing them? 
4. State Merging: How do we seamlessly combine the results from multiple EVM instances into a single, consistent state update for the stateDB?.
5. Optimizing Parallelism: What strategies are required to push the boundaries of parallelization and maximize the simultaneous processing of independent transactions?

The following sections will delve deeper into these challenges and explore proposed solutions from various approaches to parallel EVM architecture. 

The Optimistic Parallel EVM Solutions 

The Block STM (Software Transactional Memory) algorithm, and its accompanying paper are crucial for parallel transaction execution. The Block STM algorithm introduces key concepts to enable parallelism in EVMs:

1. Optimistic Parallelism: This strategy enables concurrent transaction execution, enhancing throughput by overcoming sequential limitations. Block STM assigns transactions to various threads for parallel processing.
2. Software Transactional Memory (STM): This mechanism detects conflicts when transactions try to modify the same shared state simultaneously, potentially leading to inconsistencies. It flags these conflicts to maintain data integrity and prevent invalid state updates.
3. Conflict Resolution: When conflicts are detected, the offending transactions are discarded without affecting the blockchain’s state. These transactions are then re-executed and re-validated to ensure they conform to the current state and produce the correct results.

This paper delves deeper into the technical intricacies of Block STM, offering detailed explanations of its implementation and addressing specific challenges encountered in parallel transaction execution.

Originally developed for the Aptos blockchain, the Block STM algorithm inspired projects like Polygon PoS, Monad Labs, and Sei V2 in the EVM community to adopt its parallel execution approach for enhanced transaction processing.

BNB Chain’s Parallel EVM Solutions and Plan

Since late 2021, the BNB Chain community has embarked on a journey to explore the realm of parallel EVM execution. Through two iterative development cycles, we've been actively investigating ways to unlock the performance potential of the BNB Chain. Recognizing the critical role of scalability, parallel EVM remains a central theme in our ongoing investment and innovation roadmap.

This blog serves as a retrospective, reflecting on our achievements and unveiling our future plans for the exciting frontiers of parallel EVM.

Parallel EVM v1.0 - Infrastructure

In early 2022, the BNB Chain community advanced towards parallel EVM execution with NodeReal's proposal of BEP-130. This proposal detailed the infrastructure for a parallel EVM solution, supported by a reference implementation in their BSC repository, moving beyond just theoretical concepts.

The Parallel EVM V1.0 solution tackled key challenges to enable efficient parallel transaction processing:

• Dispatcher: Responsible for distributing transactions across various threads for concurrent execution, optimizing throughput..
• Parallel Execution Engine: Leverages parallel processing to execute transactions independently on dedicated threads, greatly reducing processing time..
• Local StateDB: Each thread maintains its own dedicated "thread-local" stateDB to efficiently record state access information during execution.
• Conflict Detection & Re-execution: Ensuring data integrity by detecting and managing transaction dependencies, with conflicts leading to re-execution for accurate outcomes..
• State Commit Mechanism: Once finalized, the results are seamlessly committed to the global stateDB, updating the blockchain's overall state.

The Parallel EVM 1.0 solution offers a complete framework for executing transactions in parallel on the BNB Chain. NodeReal contributed a full implementation, thorough documentation, and detailed analysis of real-world on-chain activities, laying a strong foundation for further enhancements and the development of Parallel EVM 2.0.

(Please refer to the Parallel Transaction Execution (BEP-130) for more detail.)

Parallel EVM v2.0 - Performance

Parallel EVM 2.0 is more about performance enhancement.

Building upon the foundation of Parallel EVM 1.0, the 2.0 iteration introduces a series of performance-enhancing innovations:

• Streaming Pipeline: This approach enhances execution efficiency, enabling smooth transaction processing in the parallel engine..
• Universal Unconfirmed State Access: This feature significantly boosts performance by optimizing state information access for parallel execution.
• Conflict Detector 2.0: The enhanced conflict detection mechanism boasts improved performance and accuracy, ensuring data integrity while minimizing unnecessary re-executions.
• Dispatcher Enhancements: The dispatcher now leverages both static and dynamic dispatch strategies, leading to more efficient workload distribution and better resource utilization.
• Memory Optimizations: Shared memory pools and light copying techniques contribute to significant memory footprint reduction, further boosting system performance.

Beyond these highlights, numerous other optimizations contribute to the enhanced performance of Parallel EVM 2.0. For a detailed exploration, refer to the official repository.

Parallel EVM 2.0 delivers tangible performance improvements, as documented in their repository. Their findings reveal a significant reduction in total block processing cost, ranging from approximately 20% to 50%, with variability depending on specific block patterns.

Parallel EVM v3.0 - Production

Following the performance advancements achieved in Parallel EVM 2.0, the BNB Chain community is now actively developing Parallel EVM 3.0 with two ambitious goals:

Reduce or eliminate re-execution

The parallel solution till v2.0 can be summarized as following:

A dispatcher assigns TXs (from pool or re-execution) to slots, and slots execute the transactions in parallel and state access is recorded in slotDB, then the conflict detector decides which transactions need re-run and which can submit the result to stateDB. 

However, with the entire solution implemented, one problem remains:

The cost of re-execution wastes the resources and causes performance degradation. 

Is there a way to reduce, or ideally, eliminate it?

Re-execution in Parallel EVM, while necessary for ensuring data integrity, significantly impacts performance and resource utilization. Analysis suggests the primary reason is the conflict detector's inability to predict state access conflicts before dispatching transactions.

In other words, the dispatcher currently lacks knowledge of whether newly dispatched transactions conflict with those already assigned to other instances. This leads to situations where conflicting transactions land in different slots, necessitating re-execution even if they ultimately access the same state concurrently. So the problem goes to: 

How can the dispatcher be made aware of transaction conflict information before execution?

Our proposed solution introduces a hint-based dispatcher that leverages external hint providers. These providers analyze transactions and generate predictions about potential state access conflicts. By incorporating these hints into the scheduling process, the dispatcher can:

• Co-locate conflicting transactions: Transactions predicted to access the same state are assigned to the same slot, ensuring conflicts are detected and resolved within that slot.
• Distribute independent transactions: Transactions with no predicted conflicts are distributed across different slots for efficient parallel processing.

This approach aims to significantly reduce re-execution by enabling conflict-aware scheduling, ultimately boosting Parallel EVM performance without compromising data integrity.

Key Components of the Hint-Based Parallel EVM:

1. Hints:

• The core information describing each transaction's state access patterns.
• Simple implementations include read/write sets, while more advanced options can incorporate weak/strong ordering information for optimal parallelism.

2. Hints Generator:

• Analyzes candidate transactions and generates hints.
• Designed as a modular component within the Parallel EVM for flexible targeting of different use cases.
• Potential approaches include:
  • Developer-provided hints: Hints supplied externally by developers.
  • Trail run generated hints: Hints generated by simulating transaction execution.
  • Static analysis hints: Hints derived through static analysis of transaction code.

3. Modified Dispatcher:

• Schedules transactions based on received hints.
• Aims to co-locate conflicting transactions and distribute independent ones for efficient execution.

4. Conflict Detector:

• Remains as a backup for handling unforeseen conflicts or false positives in hints.
• Can even leverage conflict information to generate hints for optimal re-execution scheduling.

The introduction of a hint-based system would offer several benefits:

• Reduced re-execution: The hint-based dispatcher, by proactively identifying conflicts, significantly reduces the need for re-executions, thereby leading to performance improvements.
• Flexibility: The modular design allows for customizing hint generation based on specific needs and use cases.
• Improved scalability: Efficient conflict resolution and reduced re-executions contribute to enhanced scalability of the Parallel EVM system.

Production Ready

Our ambitious goal extends beyond conflict elimination; we aim to seamlessly integrate Parallel EVM into the BNB Chain ecosystem, potentially within both BSC and opBNB. To achieve this, we are implementing several key strategies:

• Modularization: Breaking down the code into well-defined, independent modules improves maintainability and facilitates adaptation to different environments.
• Codebase rebasing: Aligning the Parallel EVM code with the latest BSC/opBNB codebase ensures compatibility and simplifies integration.
• Code restructuring: Optimizing the code structure promotes clarity, efficiency, and long-term maintainability.
• Thorough testing and validation: Extensive testing across various scenarios and workloads will guarantee the solution's stability and robustness for production deployment.

This comprehensive approach aims to transform Parallel EVM into a production-ready solution poised to significantly enhance the performance and scalability of the BNB Chain ecosystem.

Comparison With Other Solutions

Several exciting projects have recently emerged, exploring innovative solutions for parallel EVM:

• Polygon Parallel EVM: Introduces the "minimal metadata approach" to address conflicts and re-execution, and hence improving efficiency.
• Monad: Utilizes static analysis to identify transaction dependencies and prevent conflicts upfront.
• Sei V2: Streamlines developer experience by eliminating the need to provide state access information, while achieving full parallel EVM implementation.
• Neon EVM: Leverages Solana's Sealevel solution to achieve parallelization within the Solana ecosystem, deploying a custom EVM implementation.

Additionally, several projects are developing optimized or customized database solutions to further enhance parallel EVM performance.

In summary, while Parallel EVM solutions are unified in their core principle of executing transactions in parallel and managing the inherent conflict risks from dependencies, they differ in their approaches to conflict reduction and state access optimization, each presenting unique strengths and trade-offs.

For example, Polygon employs a "minimal metadata approach" to identify conflicts during block building, which accelerates the validation process, whereas Sei V2 enhances the developer experience by removing the necessity for manual state access specification.

These varying methodologies underscore the continuous innovation in this field, with each solution offering distinct advantages depending on the particular use cases and priorities.

Moving forward, the evolution of parallel EVM technology is likely to be influenced by further developments in conflict detection, state management, and cross-chain interoperability.

Looking Forward

This blog delves into the exciting world of parallel EVM technology. We explore leading solutions and projects, along with BNB Chain's own dynamic efforts in this space.

Our unwavering commitment to innovation will ensure BNB Chain remains at the forefront of blockchain infrastructure, delivering the most robust parallel EVM solution.

Moreover, the parallel EVM is just one piece of our comprehensive strategy to optimize EVM performance. We're actively exploring and developing additional innovative solutions that attack performance bottlenecks at the execution engine level:

• Opcode-level optimizations: Fine-tuning individual EVM instructions for maximum efficiency.
  • Opcode fusion
  • Stack operation reduction
  • Strength reduction
  • Gas precalculation
• Compilation technology optimizations: Leveraging advanced compilation techniques for performance gains.
  • JIT/AOT compilation paradigms
  • Instruction-level parallelism (SIMD): 

Beyond EVM-centric approaches, we're also actively researching and tracking alternative parallel transaction execution methods, such as:

• Database sharding: Distributing data across multiple databases for increased concurrency.
• Concurrent node execution: Enabling parallel execution of transactions on multiple nodes.

This comprehensive outlook ensures we're constantly evaluating and exploring the most promising solutions to cater to diverse user needs and deliver the best possible blockchain experience.

Follow us to stay updated on everything BNB Chain

Website | Twitter | Telegram | Facebook | dApp Store | YouTube | Discord | LinkedIn | Build N' Build Forum