PREDA: The Last Missing Puzzle of the Parallel Blockchain

TL:DR

• The current landscape of parallel blockchain and problem statements;
• Pros & Cons of 1. Deterministic(Solana), Optimistic(Monad) and (PREDA) Asynchronous Parallelization
• Data Dependency
• Solidity V.S. PREDA

Introduction

The Evolution of Parallelism in Computer Architecture

The history of parallel computing in computers can be broadly categorized into three levels: instruction-level parallelism, data-level parallelism, and task-level parallelism.

Instruction-Level Parallelism

The first level of parallelism is instruction-level parallelism (ILP). ILP was the primary means of improving performance in computer architectures during the last 20 years of the 20th century. Programmers particularly appreciate ILP because it can enhance performance while maintaining binary compatibility. There are two types of ILP: temporal parallelism, realized through instruction pipelining, and spatial parallelism, achieved through multiple issue or superscalar execution. Pipelining is analogous to an automobile assembly line, where multiple cars are produced simultaneously across different stages. Multiple issues allow for out-of-order execution, similar to multiple lanes on a highway. After the introduction of RISC architectures in the 1980s, ILP development reached a peak in the following two decades, but further improvements have been limited since 2010.

Data-Level Parallelism

The second level of parallelism is data-level parallelism (DLP), primarily referring to single instruction, multiple data (SIMD) vector architectures. Early DLP appeared in ENIAC, and vector machines like Cray-1 and Cray-2 were popular in the 1960s and 1970s. After Cray-4, SIMD went through a period of dormancy but has recently regained momentum, with increasing adoption. For example, AVX instructions in x86 can perform four 64-bit or eight 32-bit operations using a 256-bit datapath. SIMD has played a crucial role as a complement to ILP, especially in streaming media applications. While initially used in specialized processors, SIMD is now a standard feature in general-purpose processors.

Task-Level Parallelism

The third level, task-level parallelism, is prevalent in Internet applications. Task-level parallelism is represented by multi-core processors and multi-threaded processors, which are the primary methods for enhancing computer architecture performance. Task-level parallelism has a larger grain size, with a single thread containing hundreds or more instructions. From the perspective of the development of parallel computing, the current state of blockchain technology is in the process of transitioning from the first level to the second level. Mainstream blockchain systems typically employ either a single chain or a multi-chain architecture. Single-chain systems, such as Bitcoin and Ethereum, have a single chain with each node executing the same smart contract transactions, maintaining a consistent chain state. Each blockchain node typically executes smart contract transactions serially, resulting in low throughput. Recent high-performance blockchain systems, although employing a single-chain architecture, also support parallel execution of smart contract transactions. Thomas Dickerson and Maurice Herlihy from Brown University and Yale University, respectively, first proposed a parallel execution model based on Software Transactional Memory (STM) in their 2017 PODC paper. This model utilizes optimistic parallelism to execute multiple transactions in parallel, detecting and rolling back any conflicts that arise during execution. This approach has been applied to several high-performance blockchain projects, including Aptos, Sei, and Monad. In contrast, another parallel execution model is based on pessimistic concurrency, where transactions are executed in parallel only after detecting that they do not conflict with each other. This approach typically employs pre-computation, using program analysis tools to statically analyze smart contract code and build dependency graphs. When concurrent transactions are submitted to the system, the system determines whether transactions can be executed in parallel based on the dependencies between the states they access. Only transactions without dependencies can be executed in parallel. This approach has been applied to high-performance blockchain projects such as Zilliqa (CoSplit version) and Sui. Both models can significantly enhance system throughput. However, these works face two challenges: scalability and parallel semantic expression, which will be discussed in detail below.

1. Parallel Design

We will use the technical solutions of typical projects like Solana and Monad as examples to dissect their parallel architecture designs. This includes parallelization categorization, data dependencies, and other key metrics affecting parallelism and TPS.

1.1 Parallel Design — Solana

From a higher-level perspective, Solana’s design philosophy is that blockchain innovation should evolve with hardware advancements. As hardware continues to improve following Moore’s Law, Solana aims to benefit from higher performance and scalability. Solana co-founder Anatoly Yakovenko initially designed

Solana’s parallel architecture over five years ago, and now, parallelism as a blockchain design principle is rapidly spreading. Solana employs Deterministic Parallelization, derived from Anatoly’s past experience with embedded systems, where developers typically pre-declare all states. This allows the CPU to understand all dependencies, enabling prefetching of necessary memory parts. The result is optimized system execution, but it also requires developers to do additional work upfront. On Solana, all memory dependencies of a program are essential and are specified in the constructed transaction (i.e., access list), enabling the runtime to efficiently schedule and execute multiple transactions in parallel.Another major component of Solana’s architecture is the Sealevel VM, which supports parallel processing of multiple contracts and transactions based on the number of cores validators possess. Validators in a blockchain are network participants responsible for verifying and confirming transactions, proposing new blocks, and maintaining the integrity and security of the blockchain. Since transactions pre-declare which accounts need read/write locks, the Solana scheduler can determine which transactions can be executed concurrently. As a result, during validation, the “block producer” or leader can sort through thousands of pending transactions and schedule non-overlapping transactions in parallel.

1.2 Parallel Design — Monad

Monad is building a Turing-complete parallel EVM Layer 1. Monad’s uniqueness lies not only in its parallelization engine but also in the optimization engine they are building in the background. Monad adopts a unique approach to its overall design, integrating several key features, including pipelines, asynchronous I/O, separate consensus and execution, and MonadDB. Similar to Sei, the Monad blockchain uses “Optimistic Concurrency Control (OCC)” to execute transactions. When multiple transactions exist in the system simultaneously, concurrent transaction processing occurs. This transaction method has two phases: execution and validation.During execution, transactions are optimistically processed, and all reads/writes are temporarily stored in transaction-specific storage. Subsequently, each transaction enters the validation phase, where information in the temporary storage operations is checked against any state changes made by previous transactions. If transactions are independent, they run concurrently. If one transaction reads data modified by another transaction, a conflict arises. A key innovation in Monad’s design is a slightly offset pipeline. This offset allows for parallelizing more processes by running multiple instances simultaneously. Thus, pipelines are used to optimize many functions, such as state access pipelines, transaction execution pipelines, pipelines within consensus and execution, and pipelines in the consensus mechanism itself, corresponding to washing, drying, folding, and putting clothes in the closet in the diagram below.

In Monad, transactions are linearly ordered within a block, but the goal is to reach the final state faster through parallel execution. Monad uses an Optimistic Parallelization algorithm to design its execution engine. Monad’s engine processes transactions simultaneously and then analyzes to ensure that if transactions are executed successively, the results will be the same. If conflicts arise, a re-execution is required. The parallel execution here is a relatively simple algorithm, but combining it with Monad’s other key innovations makes this approach novel. It is worth noting that even if a re-execution occurs, it is usually inexpensive because the input required for invalid transactions is almost always cached, making it a simple cache lookup. Re-execution is guaranteed to succeed since you have already executed previous transactions in the block.In addition to delayed execution, Monad also enhances performance by separating execution and consensus, similar to Solana and Sei. The idea here is that by relaxing the condition of completing execution when consensus is reached, both can run in parallel, providing extra time for both. Of course, Monad uses deterministic algorithms to handle this scenario, ensuring that one does not run too far ahead and fall behind.

Disadvantages:

Whether adopting optimistic or pessimistic parallel execution, the above systems use shared-memory as the underlying data model abstraction, meaning that no matter how many parallel units there are, each unit can access all data (referring to all on-chain data in the blockchain). State data can be directly accessed by different parallel execution units (i.e., all on-chain data can be directly read and written by parallel units). Blockchain systems using shared-memory as the underlying data model typically have concurrency limited to a single physical node (Solana), and the concurrency capability of each physical node is limited by the node’s computing power, i.e., the number of physical threads (assuming each thread supports a virtual machine).This node-level parallel approach only requires modifications to the smart contract execution layer’s architecture, without the need to modify the system’s consensus layer logic, making it very suitable for increasing the throughput of single-chain systems. Therefore, as there is no sharding of data storage,

every node in the blockchain network still needs to execute all transactions and store all states. Additionally, compared to shared-nothing architectures more suitable for distributed scaling, these systems using shared memory as the underlying data model abstraction cannot achieve horizontal scalability, i.e., expanding system state storage and execution capabilities by increasing the number of physical machines, thus fundamentally failing to address the scalability issues of blockchain.Are there existing solutions to these challenges?

3. PREDA — Parallel Programming Model

Before introducing PREDA, we would like to pose a natural question: Why use parallel programming? In the 1970s, 80s, and even parts of the 90s, we were quite content with single-threaded programming (or serial programming). You could write a program to accomplish a task. Once it finished execution, it would give you a result. Task completed, everyone was happy! However, if you were working on a particle simulation requiring millions or even billions of calculations per second, or processing images with thousands of pixels, you would want the program to run faster, which meant needing a faster CPU. Before 2004, CPU manufacturers like IBM, Intel, and AMD could provide faster processors, with processor clock speeds increasing from 16 MHz, 20 MHz, 66 MHz, 100 MHz to 200 MHz, 333 MHz, 466 MHz, and so on. It seemed like they could continuously boost CPU speed, thereby enhancing CPU performance. However, by 2004, due to technological constraints, the trend of continuously increasing CPU speed was no longer sustainable. This necessitated other technologies to continue delivering higher performance. The solution from CPU manufacturers was to place two CPUs within one CPU, even if the individual speeds of these two CPUs were lower than a single CPU. For instance, compared to a single-core CPU operating at 300 MHz, two CPUs working at 200 MHz each (referred to as cores by manufacturers) combined could perform more calculations per second (i.e., intuitively 2×200 > 300). The seemingly dreamlike story of “single CPU, multiple cores” became a reality, requiring programmers to learn parallel programming techniques to leverage these two cores. If a CPU can execute two programs simultaneously, programmers must write these two programs. However, can this translate to double the program’s running speed? If not, then our idea of 2×200 > 300 is flawed. What happens if one core doesn’t have enough work? In other words, if one core is truly busy while the other is idle? In such a scenario, it might be better to use a single 300 MHz core. The introduction of multiple cores highlighted many similar issues, emphasizing the need for efficient utilization of these cores through programming.

To help you develop a better understanding of the importance of a parallel programming language like PREDA, a informal analogy has been given as the chart appears below:

1. 🚚Driving to Mine
2. ⛏️Mining
3. 🚚Loading the Mine
4. 🔮Storge and Polish

The entire mining process consists of four independent but sequential tasks, with each task taking 15 minutes. When Bob and Alice work simultaneously, they can complete twice the amount of mining work in one hour because they each have their own vehicle and can share the road. They can also share grinding tools.However, if one day Bob’s mining truck breaks down, he leaves it at the repair shop and forgets his mining pickaxe inside the truck.

By the time they return to the processing plant, it’s too late, but they still have work to do. Using only Alice’s mining truck and the one pickaxe inside, can they still mine two units of ore per minute?In the analogy above, the four mining steps represent threads, the mining truck represents cores, the ore represents data units that smart contracts need to execute, and the pickaxe represents execution units.

The program consists of two interdependent threads: you cannot execute thread 2 before thread 1 finishes. The amount of harvested ore signifies program performance. The higher the performance, the greater the profits from mining for Bob and Alice. The mining field can be seen as memory, where you can obtain a data unit (gold ore), similar to fetching a piece of ore in thread 1 being akin to reading a data unit from memory.Now, let’s consider what happens if Bob’s mining truck breaks down. Bob and Alice need to share a vehicle, which initially isn’t a problem, but as mining equipment upgrades while ensuring mining efficiency, things change.

The capacity of the mining vehicle to hold ore becomes the bottleneck for overall efficiency because regardless of how efficient the mining machines are, the amount of ore that can be sent for grinding and processing is constrained by the “maximum ore capacity of the mining truck.”This is the essence of Solana’s parallel VM — 1. Core Sharing:

The ultimate design element of Solana is “pipelining.” When data needs to be processed through a series of steps with different hardware responsible for each step, pipeline operations occur. The key idea here is to acquire data that needs to be processed sequentially and parallelize it using pipelines. These pipelines can run in parallel, with each pipeline stage handling different batches of transactions. The higher the processing speed of the hardware (mining truck loading capacity), the higher the parallelized throughput. Today, the hardware node requirements of Solana have made it such that node validators have left one and only one choice — data centers, which brings efficiency but deviates from the original intent of blockchain.

2.2 Data Dependency（Core Resources Sharing）：

After upgrading the mining truck, the mining capacity couldn’t keep up, resulting in many instances where the truck wasn’t filled to capacity. Consequently, Bob spent a hefty sum to purchase a mining machine, increasing mining efficiency (upgrading execution units). Now, they can produce 10 units of ore within the same 15-minute timeframe. However, since the ore grinding work is still manually done as before, the increased production of ore per unit of time cannot be converted into more gold, leading to more ore being stockpiled in the warehouse. This example illustrates what happens when memory access becomes the limiting factor in program execution speed. The speed at which data is processed (i.e., core operating speed) becomes irrelevant. We are constrained by data retrieval speed. Slower I/O speeds can pose significant challenges because I/O is the slowest part of a computer, making asynchronous data retrieval crucial. Even though Bob’s mining machine can mine 10 units of ore in 15 minutes, if there is contention for memory access, they are still limited to mining 2 units of ore every 15 minutes. Existing parallel blockchain solutions propose two approaches to this problem — pessimistic execution and optimistic execution. The former requires clear definition of data state dependencies before data is written or read, necessitating developers to make upfront static control dependency assumptions. In the realm of smart contract programming, these assumptions often deviate from reality. The latter imposes no assumptions or restrictions on data writes and rolls back in case of conflicts. Taking MONAD’s optimistic execution approach as an example: in reality, most of the workload is transaction execution, and the scenarios where parallelism occurs are not as frequent as imagined. The graph below shows the gas fee consumption sources from Ethereum on a given day. While the distribution may not heavily favor popular smart contracts, there are variations in the distribution of different transaction types. Optimistic execution logic was feasible in the web2 era because a significant portion of web2 application requests were for access rather than modification. However, in the web3 domain, the majority of smart contract requests involve state modification — updating ledgers, which unexpectedly leads to more rollbacks, rendering the chain unusable.

DUNE Data: Gas fee consumption from Ethereum on 2024–01–01

Therefore, the conclusion is that Monad can indeed achieve parallelism, but: 1. Concurrency has a theoretical limit, falling within the range of 2–3 times, not the advertised 100K; 2. This limit cannot be expanded by increasing virtual machines, meaning multiple cores do not equate to increased processing power; 3. Lastly, the perennial issue remains — without data sharding, Monad fails to address the demands on nodes resulting from blockchain state expansion. The requirements for nodes have already exceeded what a home computer can handle, and with its mainnet launch, without data sharding, we may inevitably see Monad following the path of Solana. 4. Lastly, and most importantly, optimistic execution is not suitable for parallelism in the blockchain domain.

Hardware requirements of MONAD nodes

After mining for a while, Bob asked himself a question: “Why do I have to wait for Alice to return before grinding? While I grind, I can load the truck because the time required for loading and grinding is exactly the same. We definitely won’t encounter a state where we need to wait for grinding to be available. Before Alice finishes mining, I can drive to continue mining, so both of us can be 100% busy.” This ingenious idea brought them back to double efficiency, without the need for an extra mining truck. Importantly, Bob redesigned the program, specifically the order of thread execution, ensuring that all threads never get stuck waiting for shared resources within the core (such as the mining truck, pickaxe).

This is the correct version of parallelism — by splitting the state of smart contracts, accessing shared resources does not lead to any thread queuing or limit the final atomicity due to data I/O pipeline restrictions.

The PREDA model exposes the structure of contract state access during contract code execution to the execution layer, allowing the execution layer to easily and reasonably schedule, completely avoiding rollbacks of execution results. This parallel mode is also known as 2.3 Asynchronous Parallelization.

Asynchronous Parallelization of PREDA

Because parallelization is inherently asynchronous, increasing threads will lead to linear improvements. Unlike the previous example, where upgrading the mining truck’s capacity was hindered by outdated mining equipment, resulting in the truck being idle, PREDA’s parallel execution environment differs fundamentally from MONAD and SOLANA, much like the distinction between multi-core CPUs and GPUs. The shared core processing efficiency will not be the bottleneck for parallelism, nor will there be issues with data dependencies during I/O read-write operations. More importantly, PREDA’s parallel model’s parallelism will increase with the addition of threads, similar to the relationship between GPUs. In the context of blockchain logic, increasing threads (VM) will reduce the hardware requirements of full nodes, thereby achieving performance enhancements while maintaining decentralization.

The ultimate goal of achieving parallel blockchain is still lacking in the industry, aside from architectural design, which is the 2.4 Lack of parallel programming language semantics. Just as Nvidia requires CUDA, parallel blockchain also needs a new programming language — PREDA. Currently, smart contract developers lack the ability to express parallel semantics, making it impossible to effectively utilize the underlying multi-chain architecture’s support (data sharding or execution sharding or both) for general smart contracts, which are independent of blockchain parallelization architectures and consensus algorithms. The lack of a parallel programming model and language for smart contracts will lead to the inability to reconstruct applications and algorithms from serial to parallel, resulting in applications and algorithms being unable to adapt to blockchain systems with parallel execution capabilities, thereby preventing improvements in application execution efficiency and overall throughput.PREDA proposes a distributed programming model that divides contract states into fine-grained scopes through programmable contract scopes and executes transactions using functional relay semantics, distributing the execution flow across multiple parallel execution engines. This model also defines the partitioning scheme for contract states through programmable scopes, allowing developers to optimize based on application access patterns. Through asynchronous functional relays, transactions can be moved to execution engines that need to access states, achieving process movement rather than data movement. This model achieves distributed partitioning of contract states and transaction traffic without requiring developers to worry about the underlying multi-chain system’s details. Experimental results show that the PREDA model can achieve a maximum 18-fold increase in throughput on 256 execution engines, approaching the theoretical parallel limit. By using partition counters and swappable instructions, parallelism is further enhanced.

Conclusion

Traditional blockchain systems use a single sequential execution engine (e.g., EVM) to handle all transactions, limiting scalability. Multi-chain systems run parallel execution engines, but each engine processes all smart contract transactions, unable to achieve scalability at the contract level. This article discusses the essence of deterministic parallelism, represented by Solana—core sharing; and the limitations of optimistic parallelism, represented by Monad, which cannot stably run in real-world blockchain scenarios and faces high-frequency rollback possibilities. It also introduces PREDA’s parallel execution engine. The PREDA team proposes a novel programming model that expands a single smart contract by dividing its state and distributing transaction traffic across execution engines. It introduces programmable contract scopes to define the partitioning scheme for contract states. Each scope runs on a dedicated execution engine. An asynchronous functional relay is used to decompose transaction execution flows and move them across execution engines when needed.

This decouples transaction logic from contract states, allowing inherent parallelism without data movement overhead. Its parallel model not only partitions states at the smart contract level, decoupling dependencies at the data publication level, but also provides a Multi-Threaded execution engine cluster architecture similar to Move; more importantly, it innovatively introduces the new programming model PREDA, which may be the last piece of the puzzle for achieving parallel blockchain.