[CryptoTimes] Blockchain & Technology Enabling Parallel Execution

0. About This Report

This article is a translation of "ブロックチェーンの並列実行を実現する技術とプロダクト解説レポート," published on June 13, 2024, by the Japanese crypto media CryptoTimes on its research platform CT Analysis. While the CryptoTimes series is typically available exclusively to the stakers through the Access Protocol, this particular article has been released for public access at our request.

In this report, we explain the parallel execution of transactions aimed at improving blockchain scalability. Through parallel execution, the transaction processing speed, which has been a bottleneck for traditional blockchains, is enhanced, allowing nodes to handle transactions more efficiently.

1. Prerequisite: Transaction Lifecycle

To understand parallel processing, it's essential to know how transactions are processed on a blockchain.

Transactions are generally created and executed in the following sequence:

1. Transaction Creation: The user signs the transaction using a private key.
2. Broadcast: The signed transaction is broadcast to the network.
3. Transaction Verification: The transaction's validity is verified, including its signature, balance, and format.
4. Storage in Memory Pool: Valid transactions that pass verification are temporarily stored.
5. Block Creation: A block is created from selected transactions in the memory pool, and transactions within the block are executed.
6. Block Approval and Addition: The new block propagates through the network, where other nodes verify and approve the block.
7. State Update: Upon confirmation of the transaction execution, the chain's state is updated.

This sequence is performed on the blockchain nodes (computers). The software executed by the nodes is a VM (virtual machine), providing the execution environment for transaction processing and verification.

2. Transactions and Bottlenecks in EVM

In the EVM (Ethereum Virtual Machine) used by Ethereum, several bottlenecks exist in transaction execution, affecting scalability and performance.

The primary limitations in Ethereum's design that restrict performance are:

• Single-threaded transaction execution, allowing only one transaction to be processed at a time.
• Inefficient storage and access patterns.
• Execution and consensus are inseparable by rule.
• Increasing state and future state access costs.

The L1 networks introduced in this report aim to create more scalable chains by adopting different VM designs, introducing parallel execution, and improving storage access to eliminate these bottlenecks.

3. Concepts of Serial and Parallel Execution

3.1. Serial Execution

In a blockchain with serial execution, transactions 1, 2, 3, etc., are processed sequentially. Transaction 2, 3, and so forth must wait for the completion of transaction 1.

While this design maintains simplicity and data consistency, it has the disadvantage of slower processing speed since subsequent transactions must wait for the previous ones to complete.

3.2. Parallel Execution

Parallel execution, where transactions 1, 2, 3, etc., are processed simultaneously, is gaining attention as a solution to overcome processing speed bottlenecks. By processing transactions concurrently, the utilization of computer resources is optimized.

4. Main Approaches and Comparison Criteria for Parallel Execution

There are several methods to achieve parallel execution.

4.1. Transaction Dependencies

Dependencies indicate whether the result of transaction A affects transaction B.

For example, consider two transactions initiated by Alice.

In this case, transactions A and B depend on Alice's balance, causing conflicts if executed simultaneously.

Next, consider two transactions initiated by Alice and Carlos, respectively.

Here, transactions A and B are independent and can be executed concurrently without issues.

Parallel execution becomes significantly difficult if transactions are dependent.

Generally, dependency management is done using two methods.

4.2. Static Dependency Management

In static dependency management, transactions explicitly specify dependencies in advance. When a transaction is created, it specifies the data it will modify, preventing conflicts during parallel execution.

Blockchains like Solana, Sui, and Sei v2 adopt this method.

4.3. Dynamic Dependency Management

In dynamic dependency management, dependencies are detected dynamically at runtime. Independent transactions are executed in parallel, and conflicting transactions are re-executed sequentially.

Blockchains like Monad and Aptos (Block-STM) use this method.

5. Comparison of Execution Models

5.1. Parallel Execution

The parallel execution model improves speed and efficiency by processing similar tasks simultaneously. It increases throughput by executing multiple transactions concurrently. When two transactions are dependent, the conflicting transaction is re-executed in the next cycle.

5.2. Pipeline Execution

The pipeline execution model processes tasks in stages, with each stage operating independently in parallel. Each transaction is divided into multiple stages, and each stage is executed concurrently. This ensures consistent transaction processing and improves throughput.

Monad supports pipeline execution, as illustrated in the diagram above.

It divides each task into multiple stages (Wash, Dry, Organize, Store), where 2nd ‘wash’ task begins after the 1st ‘wash’ is done.

6. Project Comparisons

Here are some L1 networks employing parallel execution:

Parallel execution networks commonly use languages like Move and Rust, which center around resource ownership.

While Solana, Aptos, and Sui focus on scaling with non-EVM VMs, Monad and Sei aim at parallel execution within the EVM.

The approaches can be divided into two patterns: pre-detection of transaction dependencies from data structures (Sui, Solana) and post-detection of conflicts during parallel execution (Aptos, Monad, Sei v2).

7. Aptos

Aptos, derived from Meta's Diem (formerly Libra) project, is an L1 blockchain adopting the Move programming language and Move VM.

Related report: Aptos — Beyond Technical Excellence to a New Era of Ecosystem Expansion

It uses a parallel execution engine called Block-STM, improving scalability by executing transactions in multi-threaded parallel fashion, achieving up to 170,000 TPS.

7.1. Block-STM (Software Transactional Memory)

Block-STM is one of the key techniques for achieving high TPS in Aptos, a highly efficient, multi-threaded in-memory parallel execution engine.

Multithreading means that multiple threads can be executed simultaneously within a single process. By executing multiple processes within a transaction concurrently, the overall time required for processing can be compressed.

7.2. Transaction Execution in Block-STM

1. Pre-order Determination Transactions are executed in a pre-determined order within the block. Based on this order, dependencies are dynamically detected to avoid conflicts.
2. Optimistic Execution and Verification Transactions are executed optimistically and verified after execution. If a conflict is detected during verification, the transaction is aborted and re-executed.
3. Coordinated Scheduling By efficiently scheduling execution and verification tasks, the priority of transaction execution and verification is efficiently managed. Transactions are indexed and executed (re-executed) in ascending order.

7.3. Benefits of STM

In Software Transactional Memory (STM), there is no need for transactions to explicitly declare dependencies. While users previously had to declare dependencies when creating transactions, Aptos's parallel engine removes this requirement, simplifying the representation of transactions.

8. Sui

Sui, like Aptos, is an L1 blockchain that adopts the Move language and Move VM (virtual machine). However, Sui Move is utilized, and parallelization is realized in a different manner from Aptos.

To achieve parallelization, Sui adopts a data structure similar to Solana to optimize execution.

8.1. Data Structure and Consensus in Sui

In Sui, instead of optimistic execution, a resource-centric data model is adopted to understand transaction dependencies in advance, preventing conflicts and enabling parallel execution.

There are two types of object types defined: single-owner objects and shared objects.

Single-owner objects are basically modifiable only by the owner, and transactions defined in this way have deterministic execution results, essentially free from conflicts.

For this type of transaction, the result is not invalid and does not require re-execution, allowing consensus to be bypassed. This significantly improves performance through consensus.

Shared objects are expected to be used by multiple users, such as NFT mint contracts and DeFi contracts.

Even in these cases, since the dependencies of transactions are defined as data structures, it is possible to execute transactions that do not have dependencies in parallel at runtime.

9. Monad

Monad is an L1 network that enables pipeline execution and parallel execution of Ethereum transactions.

It has complete compatibility with EVM bytecode and Ethereum RPC, significantly improving performance while offering application portability for EVM developers.

Monad focuses on performance, building clients from scratch in C++ and Rust to speed up processing.

Monad features the following four points:

• Monad BFT - A high-performance consensus mechanism to agree on the order of transactions.
• Deferred Execution - Pipeline the consensus and transaction execution. Nodes agree on the order of transactions first and then execute them. The execution results are not required for consensus.
• Parallel Execution - Perform transaction execution in parallel and sequentially integrate the updated state.
• Monad DB - A high-performance DB to maintain the state.

9.1. Optimistic Execution

Monad realizes parallel execution of transactions through Optimistic Execution.

As the name suggests, transaction B is executed optimistically before transaction A is completed, allowing B to be executed without waiting for A's completion.

However, since this is optimistic parallel execution, scenarios where B becomes invalid due to A's state update are also expected.

To prevent this in Monad's Optimistic Execution, the results of executed transactions are incrementally merged into the state. In scenarios where B becomes invalid (conflicts), a mechanism can detect and reference the inputs and outputs of A that were executed beforehand.

If a conflict is detected, B is re-executed using accurate data.

10. Solana

Solana, founded by Anatoly Yakovenko in 2017, is an L1 network that supports up to 50,000 TPS through powerful GPUs and parallel processing.

Related reports:
Solana — Overviewing the fast-growing Ecosystem of Solana
Solana — From FTX Bankruptcy to Solana Summer 2.0

While parallel processing contributes to scalability, it is noteworthy that Solana implements its unique techniques from scratch.

10.1. Sealevel

One of the main components of Solana's VM (Solana Virtual Machine, SVM) is an engine called Sealevel. Solana supports parallel execution of smart contracts through Sealevel.

In Solana, when executing a smart contract, the data (state) that the transaction will read and write must be explicitly specified at runtime.

This design allows the detection of transaction conflicts in advance, enabling non-conflicting transactions to be executed simultaneously in multi-threaded fashion.

Executing transactions simultaneously increases the absolute number of transactions that can be processed per second, contributing to Solana's high performance.

10.2. Cloudbreak (Database)

Solana's unique database structure called Cloudbreak records information related to accounts and their balances, contributing to efficient parallel execution.

A key feature related to parallel execution is the superior indexing of account information. Account information is sharded and managed in segments, allowing parallel processing of multiple shards.

Furthermore, transaction execution (account changes) can be optimized by detecting dependencies in advance through indexing.

11. Sei v2

Sei v2 is an L1 network that supports parallel execution using optimistic parallel control similar to Aptos Block-STM and resolves dependencies using DAG. Sei v2, which includes parallel execution, was recently launched.

From v2, EVM is supported, enabling seamless interoperability between Ethereum and CosmWasm smart contracts.

The following techniques are used to improve performance through parallelization:

11.1. Optimistic Execution

Sei v2 adopts an optimistic execution technique similar to the parallel control used in Aptos Block-STM.

One of the changes in v2 is that it is no longer necessary to explicitly specify dependencies before creating a transaction. Transactions are optimistically assumed to be non-conflicting and executed in parallel.

In Sei v2, the network checks for storage conflicts operated by transactions at the chain level and re-executes them until the conflicts are resolved.

This execution applies to Sei's native transactions, CosmWasm transactions, and EVM transactions.

12. Conclusion and Considerations

This report discussed techniques for parallel execution in blockchains and how L1 networks employ these in their products.

Below constitutes of opinion from the author regarding the product & paradigm of parallel execution chains.

12.1. Solidity vs Move/Rust

The blockchains introduced in this report adopt two approaches: improving performance by introducing new L1s, VMs, and consensus mechanisms, and scaling the EVM. In the case of Solidity (EVM), as previously mentioned, design aspects such as storage access limit performance, but optimistic parallelization aims to improve scalability. For EVM scaling, solutions like Layer 2 are dominant, but adopting unique consensus mechanisms offers the advantage of achieving sub-second finality that Layer 2 solutions cannot provide. On the other hand, while EVM can be used as is, the drawback is the need to build economic security from scratch, which is weaker compared to Ethereum's economic security.

Aptos, Sui, and Solana, by building from scratch with resource-centric languages and VMs like Move and Rust, achieve higher efficiency in transaction processing compared to EVM. Given the inherently superior processing efficiency and scalability, it is plausible that Move VM and SVM will be chosen over EVM in scenarios requiring higher TPS in the future. However, like Monad and Sei, there are some challenges such as weaker economic security and increasing the number of developers, which are hurdles in growing the user base, making it difficult to determine which approach is correct.

12.2. Expected Use Cases

A significant expected use case for parallel execution is the on-chain order book (OB) in DEXs (Perp DEX). Attempts to design on-chain OBs in the EVM paradigm have been abandoned several times in the past due to long finality times and transaction costs. Therefore, the current approach mainly involves creating OBs through separate off-chain networks and maintaining economic security at the Layer 1 level as Layer 2. In the parallel execution paradigm, multiple non-conflicting orders can be processed in a short period, enabling products that do not rely on external off-chain networks.