Allen

IIRC, the Rust VM will be included in version 1.0 by the end of the year.

Sequencer Parallelization#

The first step in our roadmap is to introduce parallelization to transaction execution. This was introduced in StarkNet alpha 0.10.2, which was released on the mainnet yesterday. We now delve into what parallelization means.

So what does "transaction parallelization" mean? Naively, it is not possible to execute a block of transactions in parallel because different transactions may depend on each other. This is illustrated in the following example. Consider a block that contains three transactions from the same user:

• Transaction A: Swap USDC for ETH
• Transaction B: Pay ETH for NFT
• Transaction C: Swap USDT for BTC

Clearly, Tx A must happen before Tx B, but Tx C is completely independent of both and can be executed in parallel. If each transaction takes 1 second to execute, then by introducing parallelization, the block time can be reduced from 3 seconds to 2 seconds.

The crux of the problem is that we do not know the dependencies of transactions in advance. In fact, it is only when we execute transaction B from the example that we see that it depends on the changes made by transaction A. More formally, this dependency arises from the fact that transaction B reads from the storage unit written by transaction A. We can view transactions as forming a dependency graph, where there exists an edge from transaction A to transaction B if and only if A writes to a storage unit read by B, thus requiring it to be executed before B. The following diagram shows an example of such a dependency graph:

In the example above, each column can be executed in parallel, which is the optimal arrangement (naively, we would execute transactions 1-9 sequentially).

To overcome the fact that we do not know the dependency graph in advance, we introduce optimistic parallelization into the StarkNet sequencer, inspired by BLOCK-STM developed by Aptos Labs. In this paradigm, we optimistically attempt to run transactions in parallel and re-execute them when conflicts are discovered. For example, we can execute transactions 1-4 in parallel from graph 1, only to discover later that Tx4 depends on Tx1. Therefore, its execution is useless (we run it against the same state as Tx1, when we should run it against the state produced by applying Tx1). In this case, we will re-execute Tx4.

Note that we can add many optimizations on top of optimistic parallelization. For example, instead of naively waiting for each execution to finish, we can abort execution when a dependency that renders it invalid is discovered.

Another example is optimizing the selection of which transactions to re-execute. Suppose a block containing all transactions from graph 1 is fed into a sequencer with five CPU cores. First, we attempt to execute transactions 1-5 in parallel. If the completion order is Tx2, Tx3, Tx4, Tx1, and finally Tx5, then we will only discover the dependency Tx1→Tx4 after Tx4 has already been executed, indicating that it should be re-executed. Naively, we might also want to re-execute Tx5, as its behavior may be different considering the new execution of Tx4. However, we can traverse the dependency graph built by the execution of terminated transactions and only re-execute transactions that depend on Tx4, rather than re-executing all transactions after Tx4 that are now invalidated.

New Rust Implementation of Cairo-VM#

Smart contracts in StarkNet are written in Cairo and executed in the Cairo-VM, which is specified in the Cairo paper. Currently, the sequencer is using the Python implementation of Cairo-VM. To optimize the performance of the VM implementation, we have initiated the work of rewriting the VM in Rust. Thanks to the excellent work of Lambdaclass, who are now a valuable team in the StarkNet ecosystem, this work will soon bear fruit.

The Rust implementation of the VM, cairo-rs, can now execute native Cairo code. The next step is to handle the execution of smart contracts and integrate with the Pythonic sequencer. Once integrated with cairo-rs, the performance of the sequencer is expected to improve significantly.

Sequencer Reimplementation in Rust#

The transition from Python to Rust for performance improvement is not limited to the Cairo VM. In addition to the aforementioned improvements, we also plan to rewrite the sequencer from scratch in Rust. Besides the internal advantages of Rust, this also provides an opportunity for other optimizations of the sequencer. For example, we can enjoy the benefits of cairo-rs without the overhead of Python-Rust communication, and we can completely redesign the storage and access of the state (currently based on the Patricia-Trie structure).

Other Issues

1. The StarkNet testnet has limitations on execution traces (number of computational steps), currently limited to 1 million, but higher limits will be opened in the future.

2. Customized applications for StarkNet (similar to StarkEx) can be developed, but currently, there are no known projects in the ecosystem using them because the code for generating proofs is still a black box and has not been open-sourced by StarkWare. These applications can enter the market once StarkWare opensources them.