From Sei blog
Special thanks to Yannis, Gurnoor, Pavel, Ren, Lefteris, and Evan for feedback and discussions.
Introduction
In this post, we'll clarify the concepts of sequential, concurrent, and parallel execution in blockchains, highlight the differences between dependent and independent transactions—both abstractly and specifically in Ethereum's EVM—and then briefly examine how other chains approach parallelization.
We'll analyze the average number of independent transactions per block to measure the potential performance boost from parallel execution.
We'll conclude by examining the Sei protocol's optimistic concurrency control (OCC) strategy, demonstrating how it can scale the EVM by providing significant throughput gains while preserving a straightforward and simple developer experience.
Dependent Transactions
Two or more transactions are dependent if they touch the same state:
- Interact with the same addresses
- Modify the same storage slots in a contract
- Have read/write conflicts (one transaction reads what another writes)
For a blockchain to be deterministic, transactions must be executed sequentially. The order of execution for these transactions impacts the resulting state, and one must wait for the other.
For example, consider a scenario where your balance is 0:
- tx1: Bob sends you 1 ETH
- tx2: You send me 1 ETH
These transactions must be executed sequentially. If they run in parallel and tx2 executes first, it won't be valid; your balance will still be 0 until tx1 completes.
The same is true of borrowing: we must process the collateral lockup before releasing the borrowed funds.
Sequential execution of dependent transactions on a single CPU core
The order in which dependent transactions are executed matters. Even with multiple CPU cores, we cannot utilize them to improve throughput.
However, not all transactions have such dependencies. When transactions don't interact with the same state, we can explore more efficient processing strategies. This brings us to the concept of independent transactions.
Independent Transactions
Two or more transactions are independent if they do not modify (write to) the same state and the result of one transaction does not affect the other.
Independent transactions can be executed concurrently or in parallel because their execution paths do not block or rely on each other.
For example:
- tx1: Bob sends Alice 1 ETH
- tx2: I send you 1 ETH
Neither transaction needs to wait for the other to finish, and the order of execution doesn't matter.
To be specific, concurrency does not necessarily mean parallelization. With only one CPU core, independent transactions can make progress over the same time period, but the CPU still processes one transaction (or part of it) at a time and must change context when switching between transactions.
You might ask why we should bother with concurrency at all.
Transactions that are I/O-heavy—meaning they are related to hard drive or network operations—can cause delays. Concurrency ensures that the CPU doesn't remain idle while waiting for other transactions to process.
In other words, while the CPU waits for a packet to travel over a slow internet cable, it can switch context to another transaction instead of doing nothing.
Concurrent transaction execution on a single CPU core with context switching
However, if most transactions are CPU-bound—meaning the main bottleneck is the CPU—then concurrent processing can actually be slower than sequential processing due to context switching overhead.
Old computers with only one CPU core would run concurrently by switching context between various tasks: controlling the mouse, writing to disk, reading from memory, and displaying graphics. This created the illusion of parallel execution, but it was actually concurrent execution, with different tasks making progress during the same time period.
Context switching happened so quickly that it usually went unnoticed—until you encountered a blue screen of death.
Parallel execution is a subset of concurrent execution and can occur only when two or more CPU cores are available. Most modern consumer-grade processors come with multiple cores.
Parallel transaction execution on multiple CPU cores
The EVM is currently sequential: it runs all transactions one after the other, even if some are independent.
Before examining the methodology and statistics, let's review different implementations of concurrency.
Approaches of Implementing Parallel Execution
State Access Parallelization
State Access Parallelization is an approach for parallel transaction execution that aims to identify and leverage independent transactions before processing them. The key characteristic of this method is its ability to determine transaction dependencies upfront by analyzing state access patterns. Solana (explicitly) and Sui (implicitly) are among the blockchains that employ this technique.
Key Features:
- Transactions are analyzed for their state access requirements before execution
- The scheduler identifies which transactions can be run in parallel by mapping out potential conflicts
- Focuses on granular dependency tracking at the state access level
Pros:
- Enables creation of localized fee markets
- Provides a clear scheduling mechanism for transaction execution
- Allows for more predictable parallel processing
Cons:
- Increases complexity for developers
- Requires sophisticated dependency tracking mechanisms
- May introduce additional overhead in transaction preprocessing
Localized fee markets
To prevent one contract from clogging the entire network (as observed with CryptoKitties in 2017, which peaked at 11% of all network transactions), Solana uses localized fee markets. This is achieved through per-block and per-account compute unit (CU) limits:
Per-block limit: ~48M CUs, which dynamically adjusts based on network conditions
Per-account, per-block limit: ~12M CUs, a soft cap that can be exceeded by paying higher fees
Compute unit cost is defined per program, based on transaction complexity. Simple transfers have low CU cost, while complex DeFi trades cost more.
If a contract hits its soft CU cap from a transaction hotspot, further transactions get throttled unless they pay extra fees to exceed the cap. This creates localized congestion, while unrelated transactions can still fit in unused block space without fee spikes.
Sui's approach to this issue is through Shared Object Congestion Control, a mechanism that limits the rate of transactions to a single shared object, preventing network overload from hotspots that take too long to execute.
By controlling the number of transactions touching a congested or hot shared object within each checkpoint, the system ensures consistent processing times, preventing delays. This mechanism also promotes transaction fairness by ensuring that transactions with higher gas fees are prioritized for checkpoint inclusion. Users expect more costly transactions to process more quickly.
Optimistic Concurrency Control
Optimistic Concurrency Control (OCC) is a parallel execution strategy that allows transactions to proceed under the assumption that conflicts are unlikely to occur frequently. Unlike strictly sequential processing, OCC permits transactions to run in parallel and then validates their compatibility after execution. Blockchains that employ this technique include Sei protocol, Aptos, and Monad.
The process works as follows: Transactions are initially executed in parallel. After execution, the system checks for any conflicts or state inconsistencies. If conflicts are detected, some transactions are rolled back and re-executed sequentially. Transactions without conflicts are committed to the blockchain state.
Characteristics:
- Assumes most transactions are independent
- Relies on post-execution validation
- Allows for potentially significant performance improvements
Pros:
- Can significantly boost transaction throughput as there is no upfront overhead to track dependencies
- Works well when most transactions are independent
- Reduces initial waiting time for transaction processing
Cons:
- Requires re-running transactions in case of conflicts, which leads to poor user experience. Sei protocol puts a limit on the total number of retries per transaction to mitigate this risk.
- Potential performance overhead from validation and potential re-execution
- Slightly slower due to the need to check and potentially rollback transactions (in the case of an ecosystem of highly dependent transactions)
Sharding-Based Parallelism
Sharding involves partitioning the blockchain's state and transaction set into multiple independent "shards" or "sub-chains." Each shard can process its own subset of transactions independently and in parallel with others.
Sharding divides the blockchain into multiple sub-chains (shards), each processing its own transactions independently
Characteristics:
- Divides network into smaller groups (shards)
- Each shard processes a subset of transactions
- Allows for parallel processing
Pros:
- Increased scalability
- Lower node hardware requirements
- Potential for better decentralization
- Allows for shard-specific optimizations
Cons:
- Increased system complexity
- Cross-shard transaction overhead
- Data availability challenges
- Possible reduction in network effects
- Difficult to implement on existing networks
- Risk of shard imbalance
Sharding is a promising but complex scaling solution. It's being explored by Ethereum 2.0 (not yet rolled out) but faces significant implementation challenges. NEAR has implemented Nightshade, its sharding mechanism, which differs from Ethereum's proposed implementation in two ways:
- It provides asynchronous (cross-shard) composability
- It shards within each block, resulting in 1-2 second finality for cross-shard transactions
Methodology to identify dependent transactions on Ethereum Virtual Machine
Software engineering is all about trade-offs. The higher the number of independent transactions per block, the greater the potential performance boost from parallel execution. However, if most transactions are dependent, parallel execution might be slower than sequential execution.
The key question is how many transactions per block are independent on average, so we can calculate the potential performance impact of parallel execution.
There are two types of addresses/accounts:
- EOAs (Externally Owned Accounts), parts that can be modified:Balance (modified by value transfers and gas payments to validators)Nonce (incremented with each transaction)
- Balance (modified by value transfers and gas payments to validators)
- Nonce (incremented with each transaction)
- Contracts:BalanceNonce (incremented when contract creates other contracts)Internal storage slots (organized as 256-bit key-value pairs)Mappings between addresses and internal storage slotsInternal variables used for calculationsCode (immutable after deployment)
- Balance
- Nonce (incremented when contract creates other contracts)
- Internal storage slots (organized as 256-bit key-value pairs)Mappings between addresses and internal storage slotsInternal variables used for calculations
- Mappings between addresses and internal storage slots
- Internal variables used for calculations
- Code (immutable after deployment)
Transactions are always initiated by EOAs. This increments the EOA's nonce and reduces its balance due to gas costs (paid to validators), so the EOA's state is always modified. EOAs can:
- Send ETH to another EOA (value transfer)Sender's EOA balance decreases, nonce increasesRecipient's EOA balance increases
- Sender's EOA balance decreases, nonce increases
- Recipient's EOA balance increases
- Call a contract (contract call)Sender's EOA balance decreases due to gas, nonce increasesContract code is executed which can:Read from its own storage or another contract's storageWrite/modify its own storage or another contract's stateSend ETH to EOAs or other contracts
- Sender's EOA balance decreases due to gas, nonce increases
- Contract code is executed which can:Read from its own storage or another contract's storageWrite/modify its own storage or another contract's stateSend ETH to EOAs or other contracts
- Read from its own storage or another contract's storage
- Write/modify its own storage or another contract's state
- Send ETH to EOAs or other contracts
- Create a new contractSender's EOA balance decreases, nonce increasesNew contract is deployed with its code and initial storage
- Sender's EOA balance decreases, nonce increases
- New contract is deployed with its code and initial storage
Contracts cannot initiate transactions; they can only respond when their functions are invoked by an EOA or another contract. When invoked, they can:
- Send ETH to an EOA
- Make another contract call
- Create other contracts
This process can continue recursively, with gas always being paid by the initiating EOA.
A user transaction from an externally owned account (EOA) calls a function in Contract A, which in turn makes an internal call to Contract B
To determine transaction dependencies, we analyze transaction traces to identify potential dependencies between transactions based on their modifications to blockchain state. We use the callTracer to obtain detailed execution traces of transactions, including internal calls.
For each transaction, we identify four types of modifications:
1. ERC20 token transfers (detected via function selector 0xa9059cbb)
2. ETH transfers to EOAs
3. Contract function calls
4. Direct ETH transfers
We consider transactions dependent if they have any of these conflicts:
1. Multiple transactions make ETH transfers from the same source address
2. Multiple transactions affect the same ERC20 token balance for the same address
3. Multiple transactions transfer value to the same EOA
4. Multiple transactions call the same function (identified by function selector) on the same contract
Ethereum Transaction Conflict Analysis
Overall Statistics
Total Blocks: 14,400
Total Transactions: 2,490,744
Dependent Transactions: 875,100
Per Block Averages
Transactions/Block: 172.9
Dependent Txs/Block: 60.77
Conflict Rates
Average Block Conflict Rate: 35.15%
Distribution of dependent vs. independent Ethereum transactions per block
Key Findings
Analysis of 2,490,744 transactions across 14,400 blocks reveals:
- 35.15% of all transactions have dependencies with other transactions in their block
- Each block averages 60.77 dependent transactions, indicating significant potential for parallel execution optimization
*conflict rate metrics are indicative. The analysis doesn't account for inter-chain dependencies. For example, a smart contract on Ethereum calls a smart contract from another blockchain via an oracle. This is a negligent edge case, at the time of writing.
Ethereum Speedup Boost with OCC
To estimate the performance improvement from parallel execution, we can leverage a well-known principle in parallel computing: Amdahl's Law. This law states that the maximum possible speedup from parallelization is determined by:
- P = Fraction of the task that can be parallelized
- N = Number of parallel execution units (e.g., CPU cores)
- (1-P) = 0.35
If we assume optimistic concurrency control on Ethereum and accept that 64.9% of transactions can be parallelized (i.e., 64.9% are independent), we have:
P=0.649
P=0.649 (fraction of transactions that can be parallelized)
N = number of parallel execution units (CPU cores)
(1−P) = 0.351
When we plug in N ∈ {4,8,16,32,64}:
- For N = 4, Speedup(4) = 1.95x
- For N = 8, Speedup(8) = 2.31x
- For N = 16, Speedup(16) = 2.55x
- For N = 32, Speedup(32) = 2.69x
- For N = 64, Speedup(64) = 2.77x
- For N = 128, Speedup(128) = 2.81x
With a consumer-grade number of cores, you could see roughly a 2x speedup. With more advanced hardware, it could approach a 3x speedup.
Sei Protocol Transaction Conflict Analysis
While Ethereum's analysis shows a direct conflict rate of 35.1%, Sei protocol uses an optimistic concurrency control (OCC) system where conflicts are measured through transaction retries. In Sei protocol, our best approximation comes from the scheduler_incarnations metric, which measures how many times a transaction needs to be re-executed due to conflicts. Over the past 24 hours, we observed:
- Average incarnation rate: 2.68 (suggesting that transactions typically need 2-3 retries when conflicts occur)
- Conflicts ≈ Attempts − 1 (initial) ≈ 1.68 per block
These metrics indicate that while conflicts do occur in Sei protocol, the OCC system handles them efficiently through retries.
The Lower The Conflict Rate, The Higher OCC’s Performance Boost
As the Sei Protocol continues to grow and more smart contracts are deployed and utilized, we expect to see an increase in transaction conflicts due to higher state interaction complexity. However, based on our analysis of Ethereum's state access patterns and Sei protocol's current metrics, we don't anticipate the conflict rate exceeding 50% even under heavy network utilization.
This reinforces that optimistic concurrency control (OCC) is a suitable architectural choice for Sei protocol, as it can provide substantial performance improvements even with moderate conflict rates. The key advantage of OCC over other parallel execution approaches is its developer-friendliness—developers can write smart contracts focusing purely on business logic without worrying about complex parallel execution patterns or state access specifications. When conflicts occur, the system handles retries automatically, typically requiring only 2-3 retries per conflicting transaction.
This makes Sei protocol a versatile platform suitable for all types of blockchain applications, from DeFi and gaming to NFTs and social platforms. Developer productivity and straightforward system behavior are crucial for ecosystem growth, and Sei maintains high throughput through efficient parallel execution.
To check the code and reproduce the results visit the github repository: https://github.com/vangelisandr/evm-conflict-rate
Bibliography
Sharding Technique in Blockchain, Vo Truong Trung Hieu, 2023-10-19
All Comments