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 in 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 dependency graph 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, hence B must be executed before A. The following diagram shows an example of such a dependency graph:

In the above example, 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 detected. 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.

Please 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 the transactions from graph 1 is fed into a sequencer with five CPU cores. Initially, we try to execute transactions 1-5 in parallel. If the completion order is Tx2, Tx3, Tx4, Tx1, and finally Tx5, then we 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 yield results.

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, we expect a significant improvement in the performance of the sequencer.

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 methods of the state (currently based on the Patricia-Trie structure).

Other Issues

1. The StarkNet testnet has a limit on the execution trace (number of computational steps), currently limited to 1 million. The limit will be increased in the future.

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