Multi-Section Fault Proof Game: Catch-all Discussion + Q&A

[qizhou]

Goal

The objective of the proposal is to develop a multi-section fault-proof game on top of the existing bisect FaultDisputeGame.sol with minimal changes. The idea is to use EIP-4844 BLOB to carry 4096 claim/state hashes in each move(). As a result, countering a claim by calling a move() can create 4096 sub-claims with the following features:

• The number of move() calls to complete a game is expected to reduce from 73 (MAX_DEPTH of Sepolia testnet) to 7 (3*12=36 for SPLIT_DEPTH, and 4*12=48 for EXECUTION_DEPTH). The potential main benefit will be a significant gas reduction for the challenger over the whole game and a reduction in fault proof window.
• We expect the additional gas cost of move() will be minimal: the additional fee will be mainly BLOB fee for each move(). This is done by reusing existing data structures, e.g., in each move(), the claim hash is replaced by the hash of sub-claims - resulting in no additional storage cost.
• The code changes to FaultDisputeGame.sol will be minimized, and the existing definitions such as Position, Depth, MIPS.sol, etc will be retained. Further, the N-section fault-proof game would subsume bisect FaultDisputeGame.sol when N=2. Therefore, all existing tests (unit tests, e2e tests) for FaultDisputeGame.sol can be also used to test the new multi-section fault-proof game.

Materials

• Proposal
• Draft Spec
• Code in progress

[qizhou]

Some updates on our multi-section fault dispute game (FDG) progress:

• Given the testnet FDG gas cost https://sepolia.etherscan.io/tx/0xb92621eb9ea7b2e9c57962041a9158ee318dd011237e290209b820bf4b6a9510, we summarize the expected moves and reduced gas cost using multi-section FDG:

	Moves	Per move gas cost	Total gas
Current (N = 2)	73	~250,000 (link)	~18,250,000
N = 16 with calldata	19	~258,192	~4,905,648
N = 256 with calldata	10	~381,072	~3,810,720
N = 4096 with calldata	8	~2,347,152	~18,777,216
N = 4096 with EIP-4844	8	~250,000	~2,000,000
N = 16384 with EIP-4844	7	~250,000	~2,000,000

• We gave a talk at EthPrague about the proposal on June 2, 2024. The official stream link is here https://www.youtube.com/watch?v=vbCSqdB-D8g
• We have implemented LibDA.sol - a general library to support DA (calldata / EIP-4844 / others) for different multi-section claim hashes https://github.com/ethstorage/optimism/pull/29/files
• We completed a draft multi-section DFG Support Nary=4, draft version ethstorage/optimism#31, which is compatible with N = 2 case.

Future actionable plans:

• Add 4-section DFG tests
• Add EIP-4844 DA support

[dajuguan]

Major updates on Multi-Section Fault Dispute Game (FDG) from EthStorage team:

Completed Enhancements:

• Fully Featured Multi-Section DFG: We've successfully integrated a multi-section fault dispute game(DFG) with minimal code modifications to FaultDisputeGame.sol.
• Key Migrations in FaultDisputeGameN.sol:
  • Migrated step() to stepV2()
  • Migrated attack() and defend() to attackV2().
  • Adapted addLocalData to support adding subClaims of the attacking Claim.
• Internal Function Adaptations:
  • _findStartingAndDisputedOutputRoots
  • _verifyExecMultisectionRoot
  • _findExecTraceAncestor
  • _findTraceAncestorV2
  • _findTraceAncestorRoot

Completed Testing for 4-Section DFG
Implemented and passed all test cases in the original FaultDisputeGame.t.sol. We've also added and successfully tested new edge cases, see ethstorage/optimism#40 ethstorage/optimism#41

[lucadonnoh]

and a reduction in fault proof window

the challenge period has little to do with the number of steps needed in a game, as it needs to be set as the maximum time needed to coordinate and activate a hard fork on L1. this upgrade should not shorten the challenge period

[dajuguan]

Thanks for your correction, our wording here is not precise. The challenge period is primarily related to the time needed for coordination. However, the lower bound of the challenge period can indeed be affected. According to the article by @smartcontracts, if a malicious actor aims to censor every block to prevent challengers from sending transactions, the lower bound of the challenge period is proportional to number of steps (or txns):
challenge_period_blocks = amount_at_risk / max_challenger_spend × num_challenger_txns.
Given that multi-section fault proofs require significantly fewer steps (transactions) to resolve disputes on-chain, the lower bound of the challenge period can be substantially reduced. This reduction not only enhances faster interaction but also significantly improves the safety margin of the fault proof mechanism.

[lucadonnoh]

@smartcontracts’ article misses the fact the length of the challenge period is primarily chosen because of 51% attacks on consesus that can only be resolved with an hard fork. the soft censorship attack you report is not relevant here

[dajuguan]

I don't think 7 days is sufficient to activate a hard fork. Optimism could simply activate the global pause function to prevent withdrawals.

[lucadonnoh]

if you want to rely on the pause button, then you can set the challenge period to the maximum time needed to activate it, which could be even hours. if you want to be stage 2 and think than 7d is not enough to activate a hard fork, then it should be >7d.

[dajuguan]

If there are no issues with the dispute game program itself, but rather the honest challenger's transactions are being censored by malicious actors, a challenge period measured in hours might not be sufficient if malicious actors can censor transactions for, say, a full day.