14 Jul 2024

Parallel EVM: BEP-130

This is a personal note for BEP-130. BEP-130 is a proposal that introduces a parallel transaction execution mechanism on the BNB Smart Chain (BSC).

1. Blockchain fundamentals

Built-in contracts to perform system level operations, e,g., gas fee reward, cross chain communication.
Cannot be executed concurrently since they depend on the execution results of other transactions, e.g., a number of transaction made by an account at some timestamp.

Block mining phase: received from the P2P transaction pool, could contain invalid transactions.
Block sync phase: the block is confirmed.

Is the slot idle or occupied?
Is there a same address contract running or pending in this slot?
Has the slot’s pending transactions size reached the max transactions queue size limitation?
Is there a big transaction index gap between the slot’s head transaction and the dispatched transaction?
Is the transaction contract likely to have high gas cost or a conflict rate?

Execute the transaction \(Tx_i\)based on a specific worldstate, e.g., the state when the execution starts.
Wait for the finalization of the previous transaction \(Tx_{i-1}\).
Detect if there is any conflict between the state read by \(Tx_i\) and the state change after the execution of \(Tx_i\) starts.
If a conflict is detected, re-execute \(Tx_{i}\) again based on the latest finalized worldstate.
Finalize the state changed by \(Tx_i\) to the latest worldstate.
The state changes are kept within each slot, and are merged to the main StateDB once the execution is done.
The first transaction in a block can be immediately finalized.
If \(Tx_i\) and \(Tx_{i-1}\) are in the same slot, \(Tx_i\) can immediately start conflict detection.
Re-executed transaction can be immediately finalized as it reads the latest worldstate.

Detection items: storage key/value pair; account balance; contract content and status.
Overlap reads without write, or hardcode writes without read are not conflicts.