In-depth interpretation of parallel execution: potential, challenges and future

Ethereum introduced programmable smart contracts through the EVM.

Original title: "Parallel Power Unlocked"

Written by: ROBERT MCTAGUE, Investment Analyst, Amber Labs

Compiled by: Yvonne

Current challenges facing the blockchain industry

Currently, mainstream blockchains provide a range of applications, including DeFi, NFT, social media, and even games. However, the quality and capabilities of these applications are limited by a fundamental limitation: the difficulty of blockchains in processing multiple transactions simultaneously. Parallel execution is crucial in decentralized applications because it allows smart contract platforms to process multiple transactions simultaneously, increasing the overall throughput and responsiveness of the network. To address this critical hurdle, industry developments over the past five years have focused on improving blockchain performance through parallelization.

In previous reports, we've delved into various ways to enhance scalability, showcasing modular designs, innovative architectures like DAG, and case studies like Aptos and Sui. However, an often overlooked aspect in the blockchain space is how the network handles parallel execution and how these approaches compare.

This research report aims to shed light on upcoming layer-1 blockchains that will help solve the problems of current blockchains and establish a taxonomy framework for future parallel execution. We will focus on how these solutions enable parallel execution and compare their approaches to overcoming the limitations of existing blockchain networks. By examining the various strategies and techniques employed by these next-generation blockchains, we hope to provide valuable insights into the future of parallel execution and its role in driving blockchain innovation.

EVM

Most smart contract platforms today rely on the Ethereum Virtual Machine (EVM), but it suffers from a major drawback: it cannot execute transactions concurrently. This limitation has prompted the development of a new wave of L1 solutions emphasizing parallel execution as a means of increasing scalability and efficiency.

A smart contract blockchain has two main components: a consensus mechanism, which helps nodes agree on transaction ordering and inclusion, and a virtual machine, which runs application code and updates application state and account balances. Ethereum introduced programmable smart contracts through the EVM, a shared system where each node keeps a copy of all applications and their state. Despite its popularity, blockchains using the EVM are limited in terms of processing speed. For example, Ethereum can process about 10 transactions per second (tps), while the fastest EVM chain, BinanceChain, can only reach more than 200 tps. This inefficiency is due to the sequential processing model of the EVM, ie transactions are processed one after the other.

Monad, an L1 focused on scalability, does this analysis right in a recent post, "For reference: A simple card game with 10,000 users moving every 10 seconds requires 1000tps." Judging from the current situation, it is unlikely that EVM can support so many transactions in one chain.

To address this challenge, developers are exploring solutions that support parallel execution. This report aims to create a framework to classify how these blockchains achieve parallelization, focusing on the improvement of parallel execution. By implementing these strategies, smart contract ecosystems can overcome the limitations of sequential processing and pave the way for wider adoption of decentralized applications.

What is parallel execution?

In blockchains, parallel execution can be understood through a simple analogy. Imagine a grocery store that needs to charge customers for their purchases. If a store has only one checkout lane and cash register, the line will move slowly, frustrating customers and potentially prompting them to shop elsewhere. The store employed multiple checkout lanes and cash registers to speed up the process. This is parallel processing in action, enabling the store to handle the needs of multiple customers at the same time, rather than one at a time.

Applying this analogy to a blockchain, multiple checkout lanes represent different paths or lanes for processing transactions. In parallel execution, these channels exist within a single system, enabling it to process multiple transactions simultaneously. This setup allows a single blockchain system to process a larger volume of transactions more efficiently, improving overall performance.

Now that we have grasped the importance of parallel execution to blockchain efficiency and scalability, let’s delve a little deeper into its mechanics.

How does parallel execution work?

Parallel execution in blockchain means processing unrelated transactions at the same time. Treat unrelated transactions as independent events. For example, if two people trade tokens on different exchanges, their transactions can be processed simultaneously. However, if they are trading on the same platform, transactions may need to be executed in a specific order.

The main challenge in achieving parallel execution is determining which transactions are uncorrelated and which are independent. This includes understanding how each transaction affects the blockchain's data. With many interconnected applications, determining which transactions depend on each other can be tricky.

Different blockchain systems use different methods to identify unrelated transactions, usually by managing access to blockchain data. Each account or smart contract has its own specified range of data that can be changed. Independent transactions do not attempt to change the same data in the same block, while related transactions do.

Some transactions are more likely to be considered irrelevant than others. For example, a simple transfer of tokens between two people does not affect other people, so it is clear that these types of transactions are almost always independent. However, transactions involving the same smart contract or account can change its data and cannot be executed in parallel. An example is a token transaction involving multiple platforms, where all participating platforms must wait for the initial transaction to complete before processing other transactions.

In the following sections, we will delve into three different approaches to achieve parallel execution in blockchain systems: state access/optimistic, sharding, and computation-based parallel execution. It's worth noting that traditionally, only state access and optimistic models have been considered by others in the blockchain industry to be truly parallel execution methods, as they enable a single blockchain to process transactions concurrently. However, with the advent of sophisticated cross-chain communication protocols, the concept of what constitutes parallel execution has expanded significantly. For example, sharding, while not traditionally viewed as a means of parallel execution, does facilitate parallel processing of transactions across multiple shards, so it is worth considering. Finally, we'll explore the relatively new concept of computation-based parallel execution. This innovative model, while not widely known, represents a revolutionary approach to parallel transaction processing in blockchain systems, which we describe in detail later in this paper. As we explore these approaches, we will uncover how each one offers unique advantages and challenges for more efficient and scalable blockchain technology.

Parallel Execution: State Access and Optimistic Model

Currently, most blockchains with parallel execution rely on two popular approaches: the state-access approach and the Optimistic model. The state access approach is a strategic approach that pre-emptively identifies which transactions have access to which part of the blockchain state, allowing the blockchain to easily declare which ones are independent. Optimistic models, on the other hand, operate under the assumption that all trades are independent and simply verify this assumption retrospectively and make adjustments if necessary. Several blockchains exploit these approaches to facilitate parallelization, demonstrating each of these theoretical approaches in action. These are usually the models people are referring to when they discuss parallel blockchains. This section will explain these two approaches and their application in the blockchain field.

Solana: The Pioneer of Parallel Blockchains

Solana has become a pioneer in the blockchain space, pioneering a unique approach to managing transactions and extending scalability. Its breakthrough innovation is determining which parts of the blockchain state—the comprehensive record of all accounts or assets—can be accessed by specific actions.

Think of it like a giant filing system. Each transaction submits a request to access a specific file. Transactions can be processed independently if the file request is unique. But if they request the same files, those transactions become intertwined and require coordination. The real trick is determining which transaction requests which file.

As the first parallel blockchain, Solana introduces a solution. Each transaction must pre-declare which file it intends to access. This requirement is contained within Solana's "SeaLevel" execution model, where all functions operate within an account-based framework. Each account can only be accessed by the transactions associated with it, preventing potential conflicts.

Crucially, Solana also uses stateless procedures contained within these accounts. Stateless programs are pieces of code that don't remember any data between executions -- they start from scratch each time they run. When a function call is made, these programs are activated to perform their tasks without relying on any past data. This concept helps maintain transaction independence and contributes to Solana's innovative approach to improving blockchain scalability.

Sui: Objects concept

Sui recently debuted and caused quite a stir in the blockchain space. But what exactly does Sui bring to the table? To delve into the nuances of Sui's architecture, our team produced a comprehensive paper comparing it to Aptos, another blockchain we will explore further. However, at this juncture, our main concern is understanding Sui's unique approach to parallel transaction execution.

Sui's parallelization strategy is similar to Solana's, but with a unique twist: replacing accounts with a structure called "objects". Sui transactions do not reference accounts, instead, they change properties of objects, which can be assets or smart contracts. If a transaction is designated as independent (that is, if no other transactions interact with the target object), it will bypass the consensus mechanism entirely - a feature known as Byzantine consensus broadcasting.

To illustrate, suppose Alice owns a unique NFT, which is represented as an object in Sui's context and "Alice" is listed as its "owner". If Alice transfers this NFT to Bob, the transaction is treated as a separate object transaction, bypassing the consensus process. However, if Alice decides to perform a more complex operation, such as buying an NFT through the marketplace, the dynamics change. Because objects can be manipulated by other transactions, the transaction may be designated as a dependent transaction and may need to be sequenced before execution.

Fuel: Use UTXO to enhance execution

Fuel is a leader in the blockchain space, and it takes full advantage of the UTXO (Unspent Transaction Output) model. If you think of the UTXO model as a physical cash transaction, it's like buying something for $7 with a $10 bill and getting $3 in change. By using the UTXO model, Fuel can efficiently process transactions in parallel. This is because the UTXO model allows for easy identification of independent transactions - those that do not overlap in the objects or "bills" they interact with. This independence means that these transactions can be processed concurrently without conflict, significantly increasing transaction throughput.

Bitcoin also adopts the UTXO model, which Fuel uses to establish strict access lists. These lists act as regulators, controlling which parts of the blockchain state are accessible. The strategy relies on the idea of canonical transaction ordering, the way it arranges transactions within a block, simplifies the process of identifying dependencies between transactions.

Fuel has brought this concept to life by developing a new virtual machine, FuelVM, and an innovative programming language, Sway. FuelVM is designed as a lean but fully compatible replacement for the Ethereum Virtual Machine (EVM), which allows developers to more directly integrate into the Fuel ecosystem.

In addition, Fuel emphasizes a modular blockchain structure. This modular approach allows transactions executed within Fuel to be settled on the Ethereum mainnet network. As a result, Fuel has the capacity to handle a large number of transactions, all of which are consolidated and settled on Ethereum. This strategic move enables Fuel to efficiently manage heavy transaction loads.

Aptos: Execute in an optimistic way

In our exploration of blockchain parallelization, we first describe how blockchains establish dependencies at transaction initiation. We call this the state access approach, where a smart contract or developer defines which transactions can access which part of the state. Now we turn to another technique called optimistic execution. Optimistic execution is a strategy in which each transaction is processed as if it were not connected to any other transaction, allowing all transactions to be processed simultaneously. However, if it turns out that some transactions are linked, they are stopped, their results are cleared, and they are rerun. This can speed things up when transactions are mostly independent, but when many are connected, processing must be stopped and reset frequently, which can slow transactions down.

Aptos uses an approach called Block Software Transactional Memory (Block-STM) to apply optimistic execution. Aptos is built on top of Diem's Move language and MoveVM, which automatically discovers transaction links. It does not require transactions to say which part of the blockchain state (like a memory location) they touch.

• *

Source: Block-STM White Paper

(The diagram shows that if some transactions are connected, the verification will be suspended, the results will be deleted, and then run again.)

In block-stm, transactions are first set in a certain order within a block, and then split among different processing threads for simultaneous execution. As these transactions are processed, the system keeps track of which memory location each transaction changes. After each round of processing, the system checks all transaction results. If it finds that a transaction touched a memory location changed by an earlier transaction, it wipes its results and runs again. This process continues until every transaction in the block has been processed.

The success of Block-STM largely depends on the connections between transactions. According to the Aptos team, using 32 processing cores provides an 8x speedup when transactions are highly correlated, and a 16x speedup when transactions are less correlated. However, if every transaction in a block is concatenated, block-stm may result in a slight slowdown compared to doing it one by one.

Monad: The leader of the EVM chain

Monad pioneered a new approach in EVM-compatible blockchains and was the first blockchain to introduce a parallel architecture at the first layer of the EVM. Like Aptos, it takes an optimistic execution path, operating under the assumption that transactions are not interconnected, and resolving dependencies as they arise.

This novel approach is not without its challenges. Making major modifications to blockchain technology is a complex and long-term commitment. Nonetheless, Monads remain committed to innovation and have become a beacon for other blockchain networks aiming to enhance their own architecture.

Take Polygon and BinanceSmartChain as examples, two well-known blockchains are now trying to upgrade their systems, employing similar strategies. The importance of monads' pioneering work on optimistic implementation cannot be overstated, as it has influenced large platforms to re-evaluate and revise their own architectures.

For example, Polygon has fast throughput and millions of daily transactions. Its networking API already provides enough data to drive a parallelizable engine, and by exploring EVM-specific Block-STM, they have managed to avoid changes to the API. However, considering the huge transaction volume on the PolygonPoS chain, the assumption of zero dependencies between any blocks is unrealistic. Therefore, they adopted a minimal metadata approach, recording transaction dependencies as metadata in blocks, reducing redundancy and computational requirements.

Similarly, BinanceSmartChain is also exploring opportunities for parallel execution within its EVM chain via optimistic execution, reflecting the impact of Monad's innovative approach on the industry as a whole.

Monad's innovative spirit and its commitment to pushing the boundaries of blockchain technology has created a new trend in the EVM field. Its approach of adopting a parallel architecture in EVM layer 1 not only improves the efficiency of its own system, but also influences and inspires other important players in the field to follow suit, marking a major shift in the future of the blockchain industry.

Parallel execution based on sharding

So far, we have discussed how various blockchains break sequential ordering and achieve parallelization through concepts such as accounts, objects, UTXOs, and optimistic models. However, the next generation of blockchains we are about to study takes a unique approach to parallelization. These platforms resemble a sharding model, rather than having a single blockchain capable of processing transactions in parallel. The blockchain is divided into multiple parts, each responsible for processing its own transactions.

Shardeum: Sharding method of EVM

Shardeum brings a breakthrough approach to blockchain scalability through dynamic sharding, enabling linear scalability. Shards are subsections of the network, and each shard handles a portion of network transactions, improving resource efficiency and throughput. Consider a user conducting a transaction on a decentralized application (dapp) hosted on Shardeum, which is assigned to a specific shard based on its associated data. A shard processes transactions concurrently with other shards under its jurisdiction, like a mini-blockchain. Users benefit from faster processing, optimizing the user experience.

A key feature of Shardeum is its compatibility with the Ethereum Virtual Machine (EVM). Developers can easily migrate their Ethereum-based dapps to Shardeum, combining Shardeum's dynamic sharding and parallel processing with the extensive Ethereum ecosystem.

Dynamic sharding ensures the adaptability of the network to fluctuating demands, and promotes the scalability and high efficiency of the system. Shardeum automates cross-shard transactions, allowing seamless execution of complex applications that require input from multiple users, enhancing scalability.

What makes Shardeum unique is its ability to scale linearly. The network scales linearly as nodes are added, which means transaction throughput increases proportionally to the number of nodes. This linear scaling, combined with node flexibility and auto-scaling capabilities, enables Shardeum to optimally handle varying workloads and network growth. Shardeum provides a practical solution to real-world transactional needs by enhancing the scalability of complex applications and providing a practical solution to real-world transactional needs.

Linera: A revolutionary multi-chain protocol

Linera's innovative solution to blockchain scalability stands out through its dynamic multi-chain protocol, which includes user chains, public chains and ephemeral chains.

The diagram above shows three different types of chains in the Linera system: user chains, public chains, and temporary chains. Each chain type has a unique role that contributes to the overall functionality and scalability of the protocol.

Unlike Shardeum, where Linera pioneered the concept of user-controlled chains, Shardeum divides its network into many shard chains, each responsible for a subset of transactions. This granular approach gives users more control and autonomy while optimizing resource allocation across the network.

Userchains, which are solely owned and controlled by users, form the backbone of Linera's architecture. These chains process transactions for specific end users independently, allowing parallel execution and significantly increasing throughput while reducing latency.

The public chain is another important part of Linera's design. These chains are home to decentralized applications such as Automated Market Makers (amm). The public chain is open to all network participants, providing a common platform for applications requiring open and unrestricted interactions.

Linera also introduces the concept of temporary chains, which are specially designed to handle complex operations such as atomic swaps. This feature provides a significant advantage over protocols that need to record transactions on the main chain, which can create a bottleneck. In Linera, a temporary chain is created during an atomic swap, which is processed independently of and in parallel with other transactions. Once the swap is over, the temporary chain disappears and the updated state is reflected in the associated user chain.

The structure of the protocol supports horizontal scaling, which is an essential property for maintaining system performance under varying loads. As traffic increases, validators can add more worker machines to manage the increased activity and maintain high throughput under high load.

Unlike other protocols like Cosmos, where each blockchain or "zone" is operated by a different set of validators, Linera unifies all chains in one set of validators. This unified approach enhances the efficiency and security of the Linera protocol, simplifying cross-chain interactions by removing the complexity of validating with separate validator sets, which can lead to increased latency or discrepancies. As a result, transactions are processed more efficiently throughout the ecosystem, significantly reducing the risk of conflicts.

QuaiNetwork: Enhancing Parallelism and Interoperability with Proof-of-Work

QuaiNetwork has carved its own path in the blockchain industry with its unique approach to scalability. By implementing a dynamic and interoperable multi-chain architecture, Quai provides a unique proof-of-work-based solution to the scalability problem, enabling transaction parallelization through infinitely executing shards. This approach differentiates Quai from protocols like Linera, which utilizes user-controlled chains, while sharing some similarities with Shardeum's dynamic sharding.

The version of sharding that Quai uses is similar to traditional methods used to enhance database performance in centralized systems. However, Quai differs from typical sharding schemes in that it has a dynamic, adaptable, deeply intertwined multi-chain architecture. This is somewhat similar to Shardeum's dynamic sharding, where the network is divided into chains of shards that process transactions independently. However, Quai coordinates these different shards using a merged mining hierarchy, creating a unique interconnect that allows operations to be performed in parallel across the network. Unlike all existing sharding implementations, which introduce some new trust mechanisms to facilitate interoperability (cross-shard transactions), the Quai network uses merge mining to interconnect shards, ensuring that the only The mechanism is mining. QuaiNetwork's unique approach to interoperability through merged mining significantly increases throughput and provides the ability to accommodate large numbers of concurrent transactions without sacrificing decentralization or performance.

In order to be able to coordinate an unlimited number of execution shards, the Quai network introduces a new consensus mechanism called PoEM. PoEM is based on Proof-of-Work (PoW) consensus, but unlike other consensus mechanisms, it is the first to eliminate consensus-based forks. When running PoEM, all nodes will always have the same preference for the next block in sequence immediately, given the same set of information. PoEM allows all nodes to immediately and fairly compare any proposed block, removing all uncertainty from consensus. By ensuring that consensus is always instant, PoEM provides the necessary prerequisite for infinite sharding. If it takes any time to establish consensus, there is a severe limit to the number of executing shards that can be coordinated. As the first "zero-time" method of reaching consensus, PoEM is the first and only consensus algorithm suitable for coordinating infinitely growing chain sets.

A prominent feature of Quai's architecture is the introduction of Parallel Threads of Execution (PETs), called "regions" in Quai. Each "region" or parallel thread of execution processes transactions independently and asynchronously. The ability of each Quai execution thread to process transactions independently supports the network's parallel processing capabilities, which is one of the core concepts behind Quai's scalability.

The number of chains in QuaiNetwork is dynamic and adaptable, just like Shardeum's dynamic sharding. However, QuaiNetwork's use of the PoEM consensus mechanism is unique in that it allows this dynamic sharding pattern to be performed infinitely without performance degradation. QuaiNetwork adds execution shards via dynamic sharding with an obvious trade-off: as more execution shards are added to the network, the time it takes for cross-chain transactions to be referenced by their target shards will increase. This relationship is sub-linear — for example, scaling Quai from 9 shards to 16 shards would increase the average time for a cross-chain transaction to reach its destination from 3300 seconds to 4400 seconds. Scaling further to 25 shards increases the average time to about 5,500 seconds. Theoretically, if Quai expands to 100 shards, the average time to global cross-chain settlement is about 11,000 seconds. QuaiNetwork's dynamic sharding algorithm monitors the network's gas limit and uncle block rate to understand when additional throughput is needed, and automatically weaves additional execution shards into consensus to accommodate increased throughput demands.

In addition, Quai's woven structure supports composable multi-chain smart contracts and allows efficient cross-chain contract interaction. Each Quai thread of execution has an EVM, and new opcodes are introduced to communicate with the EVM located on the alternate shard. This capability enables developers to deploy contracts across multiple or all Quai chains, ensuring the operability of decentralized applications (dapps) across the network.

QuaiNetwork's innovative application of sharding, coupled with its merge-mined interoperability and parallel execution threads, represents a major advance in blockchain scalability under a work-based consensus mechanism. Robust handling of cross-chain transactions and advanced smart contract capabilities make Quai a noteworthy contributor in the growing field of scalable blockchain protocols.

Computation-based parallel execution

An emerging paradigm in parallel execution of blockchains is the computation-based model. This term was coined by our research team at AmberGroup to describe a method of processing computing tasks concurrently in a shared environment. Unlike state-access and optimistic models, computation-based models do not strictly rely on sequential memory-based computations. Instead, it operates on the principle of a highly parallel virtual machine. This design promotes robust and efficient parallel execution. The following sections explore the principles of computation-based parallel execution, its potential applications, and the unique challenges it poses to the broader blockchain technology field.

Kindelia: The Powerhouse of Computation-Based Parallel Execution

Kindelia has emerged as a promising solution in computation-based parallel execution models in blockchains. Developed by HigherOrder Corporation, it is based on a unique runtime called the Higher-Order Virtual Machine (HVM), which enables efficient parallel computing.

Kindelia's innovation is based on a new model of computing called an "interaction network," a concept that differs from the Turing machine model that underpins most modern computers. Interaction networks are based on a graph of interaction nodes, each node possessing a rewritten set of rules that dictate how it interacts with other nodes in the network. Computation is achieved by reducing the interacting network and systematically removing nodes from the network according to its rewriting rules until a final state is reached. This model allows computation to be done in parallel without the need for a central clock to dictate the process, as nodes interact locally without any global coordination.

• *

*Victor Taelin's (CEO of HigherOrderCompany) drawing shows us how to reduce the interaction network. *

The advantages of this model are numerous. Due to its inherent parallelism, it facilitates faster and more efficient computations, greatly outperforming traditional sequential computing models. Furthermore, it opens up a field of application in various fields of computer science. Kindelia stands out as the first truly parallel virtual machine in the blockchain context, achieving many of the goals altL1 aspires to. However, due to their reliance on Turing machine-based architectures, these competitors may never achieve the same level of parallelization.

Kindelia's design requires fewer computational steps to perform functions, maximizes utilization of processing cores, and ensures operations are performed in the correct order—all with minimal additional effort from developers. This simplified execution process, coupled with a higher level of security, makes Kindelia a cutting-edge example of computation-based parallel execution in blockchain technology.

Although the theoretical basis of Kindelia and HVM is somewhat advanced, the practical significance is easy to understand: to improve the speed, efficiency and security of blockchain computing. With Kindelia, we are witnessing a revolutionary leap forward in blockchain technology, marking an important milestone in the ongoing development of this transformative field.

Concerns about parallel execution

As we explore the potential of parallel blockchains, it is important to acknowledge that while they offer considerable scalability and speed advantages, it also presents unique challenges and potential drawbacks. The two main issues that are often mentioned are the potential for increased centralization and high transaction conflict rates.

Parallel blockchains distribute transaction processing among numerous nodes, thereby increasing transaction processing throughput. However, this distribution can also lead to the concentration of power within a few nodes, thus bringing a certain degree of centralization. This centralization can undermine the trustworthiness and security of the blockchain, making it more vulnerable to attack. Additionally, parallel blockchains increase the risk of network downtime. For example, the Solana network experienced an outage in September 2021 due to excessive transaction requests. The incident highlights the potential risks associated with scaling blockchain networks and the need for solutions that can handle high transaction volumes without compromising stability.

The transaction conflict rate is another important issue. This ratio refers to the percentage of transactions that cannot be executed simultaneously due to conflicts. A high conflict rate can lead to a large number of transaction reworks in parallel blockchains. According to the Flashbots report, the conflict rate of Ethereum transactions in 2017 was about 35%. With major applications like OpenSea and Uniswap dominating the Ethereum network, the conflict rate will likely be even higher.

In the case of optimistic execution, the amount of transaction redo can severely disrupt the pipeline if the conflict rate exceeds 30%. Each redo slows down transaction processing and reduces the benefits of parallelization. Therefore, managing the transaction conflict rate is crucial to ensure the efficiency of parallel blockchains.

in conclusion

Significant changes are underway in the blockchain space as it attempts to address scalability and efficiency issues inherent in its design. We've explored various approaches to achieving parallel execution, each with its own unique advantages and challenges. A state-based access model marks the first step in overcoming the sequential nature of blockchains. Optimistic execution, while promising, also introduces the risk of conflicts and requires effective conflict resolution strategies. Sharding takes us a step further by dividing the network into smaller, manageable parts, each capable of processing transactions independently. Finally, compute-based parallel execution uses cutting-edge computer science to maximize node performance and application security. Despite the challenges and potential issues, these models show the potential to significantly improve the performance of blockchain technologies. As these technologies continue to develop and mature, we are on the cusp of a new era of blockchain technology.