Posts tagged "bnb":

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).

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.

07 Jul 2024

This is a personal note for BNB chain-blog.

Run multiple EVM instances concurrently on different threads.
Execute transactions independently on each thread and later merge a finial state update.
Parallel EVM scheme

Optimistic parallelism: assigns transactions to various threads.
Software transaction memory (STM): detect conflicts when transactions try to modify the same shared state simultaneously.
Conflict resolution: when conflicts are detected, the offending transactions are discarded without affecting the blockchain state and are re-executed.

Dispatcher: combine both static and dynamic dispatch strategies.
Execution engine: streaming pipeline to enable smooth transaction processing.
Conflict detection: ensure data integrity while minimizing unnecessary re-execution.
Memory: shared memory pools and light copying techniques to reduce memory footprint.
The overall performance ranges from 20% to 50%.

leverages external hint providers to analyze transactions and generate predictions about potential state access conflicts.
Simple hints include read/write state sets; advanced hints incorporate weak/strong ordering for optimal parallelism.
Conflicting transactions are assigned to the same slot.
Transactions with no conflicts are distributed across different slots.
Conflict detector remains as a backup for handling unforeseen conflicts.

Solutions	TX dependency check	Conflict resolution	StateDB optimization
BlockSTM	tracks at execution	re-execution	N/A
Polygon	minimal metadata solution	reduced re-execution	N/A
Monad	static analysis	reduced re-execution	Monad DB
Sei	tracks at execution	re-execution	SeiDB
Neon EVM and Solana Sealevel	contract provided	reduced re-execution	depends on Solana
BNBChain	hint info	reduced or eliminated re-execution	Thread local DB

Opcode-level optimization: fine-tuning individual EVM instructions for maximum efficiency.
Compilation optimization: JIT/AOT compilation paradigms; instruction-level parallelism (SIMD).
Database sharding: distribute data across multiple databases.
Concurrent node execution.