Fault proofs research

[PaulRBerg]

In optimistic rollups, fault proofs (FPs) are used to challenge the assumption that the new state has been generated correctly.

For simplicity's sake, FPs won't be enabled in Genesis. Arbitrum supports them, but OP Stack doesn't. And if the Optimism team hasn't been yet able to ship this feature for vanilla EVM rollups, we should have no expectations to pull this off by the EOY.

In this discussion, I will explore the implications of the streaming opcodes and the subgraph data structure for FPs.

FPs work by employing a multi-round interactive proving game. The core idea is to replicate the EVM execution in a L1 smart contract, but do it using a 'bisection' protocol where incremental steps are provided by both the asserter and the challenger. It's kinda like binary search for finding malicious VM instruction steps that never existed in the calldata posted on Mainnet.

Now, on SabVM, the existence of the streaming opcodes poses two challenges:

• Dynamic balances are lazily evaluated
• The cold<> warm state duality means that subgraphs have to be traversed fully

More research needed to confirm that such computations can be performed in a challenge game in a L1 smart contract.

For now, I suggest disabling fault proofs in both Genesis and Odyssey, letting this feature to be handled in a future milestone.

Note

Switching to a ZK stack would solve this problem, but we cannot do that per the arguments provided here.

[PaulRBerg]

This is definitely a looong-term feature for SabVM. From Optimism's docs:

Problem: Withdrawal claims rely on a trusted set of chain attestors.

Proposed Solution: It is possible to replace the trusted set of chain attestors by introducing permissionless proofs—such as Cannon—where dispute resolution is entirely onchain. However, the challenge with entirely onchain proofs is there is no fallback mechanism if they were to break. To ensure that they will never fail, it is possible to introduce a multi-proof system which provides safety through redundancy.

Also relevant is this article:

Optimism: Our pragmatic path to decentralization

[PaulRBerg]

From Optimism's Security FAQ:

Q: Can I use fault proofs?

Not yet. The OP Stack does not currently have a fault proof system. Note that fault proofs do not meaningfully improve the security of a system if that system can be upgraded within the 7 day challenge window ("fast upgrade keys"). A system with fast upgrade keys is fully dependent on the upgrade keys for security.

Fault proofs are a key milestone and top priority for the OP Stack. In the meantime, the OP Stack can be shipped with several other excellent security options for systems that want to improve security before fault proofs are available in production.

[PaulRBerg]

Relevant page from Optimism's documentation:

Fault Proof Overview

The key section is the Dispute Game Protocol.

The standard is the bi-section game. We bisect over output roots (which each correspond to single L2 blocks), until we get to a single block n -> n+1 state transition. Then, we bisect over a single block state transition's execution trace as described before. This is an optimization to reduce the runtime of the off-chain VM. After bisection has reached commitments to the state at individual trace instructions, the FaultDisputeGame executes a single instruction step on chain using a generic VM. The VM's state transition function, which we'll call T, can be anything, so long as it adheres to the form T(s, i) -> s', where s = the agreed upon prestate, i = the state transition inputs, and s' = the post state.

[PaulRBerg]

Important observation made by Georgios here:

The great thing about this is that the on-chain verifier works for anything compiled to MIPS. So if you wanted to, you could write some other logic and run a fraud proof for that. Maybe another VM, or maybe a specific program.

Also, from Optimism's docs:

The OP Stack's unique, modular design allows the decoupling of the FPP and FPVM, resulting in the following:

• development of multiple proof systems, unique dispute games, and a variety of FPVMs in the future.
• custom-built fault proof systems comprised of any combination of these isolated components—including validity proofs, attestation proofs, or ZKVM.

[PaulRBerg]

Good research materials:

Short form

• Ben Jones on Twitter: next-gen fault proofs
• Georgios Konstantopoulos on Twitter: Summary of MIPS proofs
• Walkthrough: OP Stack Fault Proof System

Long-form

• Arbitrum: scalable, private smart contracts
• a16's formalization of Permissionless Bisect Game
• Gabriel Coutinho de Paula: Fraud Proofs are Broken
• Optimism Specs

[PaulRBerg]

It appears that fault proofs are a no-go for Sablier Mainnet. One of the assumptions that optimistic rollups make is that there is precompile parity between L1 and L2. The pre-images need to be verified on L1:

ethereum-optimism/specs#211 (reply in thread)