Fault Proofs in the OP Stack

Base recently launched fault proofs on mainnet, marking a significant milestone in our journey towards progressive decentralization. Fault proofs allow anyone to participate in securing Base, creating a more trusted and open economy. A core property of fault proofs is that if there’s at least one honest participant, or “challenger” engaging in the fault proof game, then the game should resolve correctly. They are a critical component of the Base stack, and as we continue to increase throughput on Base, we need to ensure that our scaling efforts do not introduce any incompatibilities with fault proofs. Therefore, we launched a dedicated initiative aimed at analyzing how the Fault Proof System in the OP Stack would be impacted by our scaling efforts, and ensuring that we can continue to scale fault proofs safely. Today, Base’s Fault Proof System leverages the Cannon Fault Proof Virtual Machine (FPVM). You can read more about fault proofs in the OP Stack here.

Cannon is the first Fault Proof VM (FPVM) supported by the OP Stack. It combines onchain and offchain components in order to effectively run the EVM within the EVM, ensuring that any state transition can be audited, and permissionlessly challenged. Unlike typical Ethereum implementations which only ensure that a transaction has a deterministic output (e.g. balances and token transfers), the Cannon FPVM emulates a computer which behaves deterministically - down to the individual MIPS instruction - all while running its own instance of the EVM.

Identifying the constraints

Given the complexity associated with fault proofs, today’s Cannon implementation contains certain simplifications. Cannon implements a minimal set of unix system calls - just enough to allocate memory, read and write to a preimage oracle, and exit gracefully. Notably, this excludes syscalls related to creating and managing threads, or other concurrency primitives. As Cannon is written in Go, a garbage-collected language optimized for concurrent code, this has a few drawbacks. Most importantly, Cannon is unable to clean up memory once it’s no longer needed, causing the footprint to grow until either the program completes or it hits the hard limit imposed by the 32-bit MIPS architecture. This means that each Cannon execution has a hard constraint on the available memory. Because the execution behavior is entirely deterministic (an essential property of a Fault Proof System), any input which causes Cannon to run out of memory will always cause it to fail.

Cannon isn’t only racing against its memory limit, but also against the clock. Base provides a set window of time for anyone to verify or challenge the state published back to L1. In a fault proof dispute game with two players, each player has just over 3 days to run Cannon from start to finish in order to participate. Because Cannon provides several layers of virtual machine abstraction, and optimizes for determinism, block execution is many orders of magnitude slower on Cannon than on a standard Base node.

In order to safely ship fault proofs to mainnet with these restrictions, we needed to ensure that all blocks would always be provable - especially as we raise our gas target. In other words, no combination of blocks could “break” Cannon by taking too much time or memory. This of course meant we needed to stress-test the system in as many ways as possible.

Introducing new tooling

To address this challenge, we built an open source tool to generate repeatable fault proof test cases within a local devnet. We first generated and executed these tests outside of Cannon to develop and iterate more quickly, and then ran them in the slower Cannon environment for comparison and metrics collection.

Each test scenario consisted of a single transaction configured with a given gas target. This transaction would deploy a contract that would repeatedly perform a specific operation pattern until the gas target was met or surpassed. Each contract and associated forge script is defined in the testing repository, linked above. These test scenarios were executed at 4 gas targets: 1Mgas, 2Mgas, 3Mgas, and 20Mgas, in order to produce and validate a linear scaling model, which then allowed us to forecast the impact of a block containing 100Mgas with the same characteristics. Test coverage included ETH Transfers, ERC20 Transfers, Storage Writes, Storage Reads, Contract Deploys, as well as the majority of precompiled contracts. We omitted precompiles that do not pose a risk to resource constraints in Cannon, such as those which can be offloaded to the L1 EVM.

For each test case, we specifically evaluated the Cannon MIPS instruction count, memory usage, and wall clock runtime. We performed these tests on a less-performant runtime environment than our production challenger. From this baseline we again rounded down to an extremely conservative 10M instructions per second execution speed, in order to forecast the worst case challenger proof time for each test fixture.

What we learned

From these tests we identified two specific usage patterns which stood out the most in terms of resource constraints, the p256Verify and ECAdd precompiles, which are detailed below. Importantly, we validated that these constraints will not limit our scaling efforts below 60Mgas/sec.

p256Verify: Time intensive

The p256Verify precompile (introduced in RIP-7212) consumes the largest amount of Cannon instructions per gas unit, and cannot be simply accelerated in the onchain MIPS.sol contract using the existing L1 precompile preimage execution pattern, as it is not yet deployed on L1. At around 10,000 Cannon instructions per gas, and using an extremely conservative execution estimate of 10,000,000 instructions per second, the p256Verify precompile can consume around 1ms per gas. At a much higher block gas limit of 100Mgas, execution may take as long as 28 hours with these performance characteristics. Fortunately, this is still well under the challenge timeout of ~3.5 days, and minor improvements to the challenger’s setup, such as faster hardware or software optimizations can significantly reduce this duration.

p256Verify: Memory usage and runtime in ms given actual and estimated gas usage

ECAdd: Memory intensive

The ECAdd precompile shows the largest rate of memory consumption with respect to gas usage, at around 7 bytes per gas. Verifying a 20Mgas block primarily consisting of ECAdd precompiles required roughly 250MB of Cannon memory (inclusive of ~135MB of L1 block overhead), suggesting that a 100Mgas block following this pattern may use roughly 690MB of memory. This is still well below the 32bit MIPS Cannon heap limit of ~1.1GB, and will allow for up to a 2x margin of error on top of typical consumption from real-world L1 blocks.

ECAdd: Memory usage and runtime in ms given actual and estimated gas usage

Instruction count, memory usage, and wall clock runtime were not materially increased by modest increases in gas consumption attributed to accelerated precompiles, storage reads/writes, contract deploys, or transfers of ETH or simple ERC-20 tokens. Other non-accelerated precompiles such as SHA256 and ECMul consumed relatively larger amounts of instructions and memory as compared to simple EVM bytecode, but not enough to pose any risks to the integrity of the fault dispute game, even at greatly increased block gas limits.

Span batch implications

One more important finding is that Cannon’s resource usage is not only influenced by the contents of a single L2 block being validated, but also by the contents of all L2 blocks contained within the same span batch. This means that even if a single block might need to contain ~200Mgas of ECAdd precompiles in order to break Cannon, far exceeding today’s gas limit, a span batch containing 10 blocks can easily surpass this with room to spare. To mitigate this risk, we’re setting an extremely conservative span batch gas limit of 120Mgas for Base mainnet, and limiting the number of L2 blocks per batch based on the per-block gas limit.

Looking ahead

With Base building one block every 2 second, and at a limit of 120Mgas per block, we can scale to roughly 60Mgas/sec with the current version of Cannon. This is roughly a 3x increase from where we are today, but far below our north star goal of 1Gigagas/sec. Fortunately there are a number of workstreams in progress which will help to scale fault proofs alongside our goals.

OP Stack contributors are developing two major upgrades to Cannon which will address the memory constraints, on top of plenty of smaller improvements and optimizations: Multithreaded (MT) and 64bit Cannon. MT Cannon will introduce runtime garbage collection, preventing the memory usage from growing in an unbounded fashion. Additionally, migrating Cannon from a 32bit MIPS architecture to a 64bit architecture will allow the heap to grow by many orders of magnitude, effectively providing unlimited memory to the runtime. Multithreaded and 64bit Cannon are currently undergoing audit and should be ready to go live on testnet in the next couple months

In addition, the Base engineering team is working alongside other OP Stack Core Contributors to develop the upcoming Holocene OP Stack hardfork. This upgrade adds partial span batch validation, which reduces resource constraint by removing the need for fault proof programs to execute all L2 blocks in the batch  

Now that we’ve developed a foundational set of fault proof tests, tooling, and reference data, we plan to benchmark all future changes to the OP Stack, ensuring that we can continue to safely scale Base and the broader Superchain, and bring the world onchain.

Appendix

In the interest of transparency, we’ve included the raw data from each of our tests below. All tests were performed using Cannon and op-program binaries built from the v1.9.1 op-stack release using go 1.21.

ETH Transfer

ERC20 Transfer

Storage Writes

Storage Reads

Deploys of Tiny Contracts

SHA256 with small inputs

SHA256 with large inputs

Deploys of Tiny Contracts

RIPEMD160 with small inputs

RIPEMD160 with large inputs

Blake2f

ECAdd

ECMul

ECPairing (accelerated by op-program)

P256Verify

Identity

Modexp