Parallel EVM (Ethereum Virtual Machine) is an advanced approach to optimizing blockchain performance by allowing multiple transactions to be processed simultaneously. In traditional EVM, transactions are executed sequentially, which can lead to performance bottlenecks, especially under heavy network load. 

Parallel EVM addresses this limitation by identifying independent transactions that do not conflict with each other and executing them in parallel. This parallel execution significantly enhances transaction throughput, reduces latency, and improves the overall scalability of blockchain networks, making them more efficient and capable of handling a higher volume of transactions.

Performance Bottleneck of Parallel EVM

Traditional parallel processors often attempt to execute transactions optimistically in parallel, assuming no conflicts will arise. However, when conflicts between transactions are detected, the system must roll back and re-execute those transactions to ensure accurate results. 

This rollback process consumes considerable computing resources, leading to inefficiencies. In some cases, the overhead from detecting and resolving conflicts can cause the system to perform worse than if the transactions were processed sequentially, negating the benefits of parallel execution.

For example, in one block, the dependencies of transactions may look like this:

When parallel instances execute transactions, the following result will happen, and there will be lots of transaction execution rerun and computing resource waste. 

Dependency Hint Introduction

To maximize block execution performance, transactions must run in parallel, fully utilizing computing and I/O resources. Knowing transaction dependencies enables a clear parallel execution path.

Dependency Graph TxDAG

Dependency Graph TxDAG (Transaction Directed Acyclic Graph) is an interesting approach designed to enhance blockchain performance by structuring transaction processing based on dependencies. 

Unlike traditional methods that process transactions sequentially or optimistically in parallel, TxDAG builds a dependency graph to determine which transactions can be executed simultaneously without conflicts. 

Mapping dependencies in advance allows non-conflicting transactions to run parallelly, avoiding costly re-execution. This boosts throughput, optimizes resource use, and enhances scalability for blockchain networks like BSC.

How is TxDAG Generated 

Proposer Builder Separation(PBS) and Block Production

BSC has introduced the PBS and the builder can generate the TxDAG through read-write sets after the builder pre-execute transactions. After the TxDAG is generated, it can be included in the unsealed block bid and forward to proposers(validators) to validate. Below is a simplified diagram to explain the process. 

First, pre-execution by builders, and currently, the TxDAG is generated in the mining process by builders. 

TxDAG compression

There is also a potential TxDAG "compression algorithm" to further optimize the size. For the DAG describing the dependencies, some are redundant because it only needs to ensure that the final execution path is consistent.

How TxDAG is forwarded

To pass TxDAG data from builders to proposers for validation and block sealing, three methods are possible:

1. Reuse the Extra field in the block header to store TxDAG data. This is simple but constrained by the header’s size limit.
2. Add a new field in the block body, with the TxDAG hash in the header for verification. While more robust, it requires a hardfork to update consensus logic and an incentive-slashing mechanism for builders.
3. Embed TxDAG data in a transaction using system or gasless transactions. This avoids changes to consensus logic but lacks incentives for builders to generate the TxDAG.

Each method has trade-offs between complexity, scalability, and builder incentives.

TxDAG speed up the validation process

The simplest way to accelerate block validation with TxDAG is by integrating parallel processors. Typically, parallel processors execute transactions optimistically, but with TxDAG, they can follow the optimal parallel path for the entire block while quickly identifying invalid DAGs.

Additionally, TxDAG can enhance state prefetcher scenarios (introduced in BSC performance optimization) by preloading states through parallel prefetchers, significantly improving the processor's cache hit rate.

Performance Testing in lab

Introducing TxDAG resulted in an 88% performance improvement under fully conflict-free transactions. As transaction conflicts were gradually introduced, even with over 95% of transactions having conflicts, there was still a 7% performance gain. With simulated mainnet data showing 30%-70% transaction conflicts, the actual performance improvement averaged around 30%. Below are the detailed performance test results.

Testing data summary

Call for Community Discussion

BNB Chain is among the pioneering blockchains to introduce TxDAG, enhancing Parallel EVM performance based on valuable community feedback.

TxDAG Forward Mechanism

As noted, deciding how to forward TxDAG from builder to proposer is crucial, along with introducing incentive mechanisms to ensure honest TxDAG generation. The table below summarizes the differences among the three proposed methods. 

TxDAG Incentive Mechanism 

TxDAG is optional for decentralized builders, but it carries the risk of malicious DAGs, which fall into two categories: Wrong DAG and Bad DAG.

• Wrong DAG includes incorrect TxIndex, violations of preset orders, or circular dependencies. These issues can be quickly detected during verification, and the block will be rejected.
• Bad DAG is more subtle, providing incorrect dependencies that reduce parallelism or create conflicts.

To mitigate these risks, a builder punishment mechanism is essential to ensure compliance and maintain system integrity.

For details, please refer to BEP-396.

Future Work

The current TxDAG based PEVM implementation is just the first step of PEVM for BNB Chain, and the following advanced optimizations are in BNB Chain roadmap:

Advanced transaction scheduler

The current TxDAG-based scheduler is simple and efficient for layer-level parallel execution. However, further optimization opportunities exist, such as reducing the scheduling granularity from layers to individual transactions to enhance parallelism.

For example, in a layer-based scheduler, Tx3 and Tx4 must wait until both Tx1 and Tx2 in Layer 1 are completed before executing in Layer 2. This delay is unnecessary since Tx3 has no dependencies on Tx2, limiting scalability.

With transaction-based scheduling, the scheduler can execute Tx3 and Tx4 as soon as Tx1 is complete, without waiting for the entire Layer 1 to finish.  

Parallel stateDB 

Currently, BNB Chain has implemented an unordered stateDB, allowing the state change of Tx5 to be updated before Tx3, as both transactions are in the same layer. This optimization demonstrates significant improvement over in-order merging.

However, the unordered state update still operates sequentially. To further enhance performance, transitioning from unordered to parallel state updates would enable transaction execution and state updates to occur simultaneously, unlocking even greater efficiency and scalability.

Prediction based TxDAG for block builder

The current TxDAG+PEVM implementation relies on a block synchronization node, with the TxDAG generated during block creation by the block builder. As a result, the block builder cannot access the TxDAG beforehand, limiting the PEVM's effectiveness for this type of node.

To overcome this limitation, we are exploring the generation of a pre-TxDAG for the block builder. While this pre-generated TxDAG might not be entirely accurate, it must adhere to specific rules:

• No false negatives: If the TxDAG shows no dependencies, there must genuinely be none.
• Possible false positives: The TxDAG may indicate dependencies that don’t actually exist.

This approach allows the block builder to utilize parallel execution, improving performance. The builder can then refine the TxDAG, optimizing it for use by block synchronization nodes.

References:

1. Performance testing based on TxDAG of op-geth 
2. TxDAG implementation on op-geth 

Follow us to stay updated on everything BNB Chain

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