Anatomy of Fault proof test

# Anatomy of Fault proof test **By [Po @ QuarkChain](https://x.com/sanemindpeace)** Using the simple [Alphabet program](https://github.com/ethstorage/optimism/blob/5137f3b74c6ebcac4f0f5a118b0f4909df03aec6/op-e2e/faultproofs/output_alphabet_test.go#L19) as an example, specifically TestOutputAlphabetGame_ChallengerWins, the workflow can be summarized as follows: 1. startFaultDisputeSystem launches the relevant RPC node services. 2. StartChallenger starts a [Challenger thread](#Challenger) that monitors the game for any false claims and automatically submits an attack transaction if one is detected. 3. For each game, a false claim ({0xaa}) is submitted and attacked, then the system waits for the challenger thread to respond via WaitForCounterClaim. 4. This continues until the game ends (WaitForGameStatus), at which point it is checked whether the challenger or the attacker won. # Challenger The part of **op-challenger** that responds to false claims is somewhat deeply nested. You can trace it starting from the [main function](https://github.com/ethstorage/optimism/blob/5137f3b74c6ebcac4f0f5a118b0f4909df03aec6/op-challenger/challenger.go) along the following chain: ``` Main → NewService → initFromConfig → registerGameTypes → fault.RegisterGameTypes → registerAlphabet → NewGamePlayer → NewAgent → Act (op-challenger/game/fault/solver/solver.go) ``` This path essentially shows how the challenger service initializes, registers the supported game types, creates the game agent, and eventually invokes the `Act` method where false claims are detected and countered. # op-e2e ## How to deploy and interact L1 contracts ### Contract depolyment procedure In fact, the contracts are all deployed when the L1 chain is initialized. The detailed flow is as follows: ``` [StartFaultDisputeSystem](https://github.com/JustXxx/optimism/blob/8a548ae992df856c7b4868fcaa5d9c787baae92e/op-e2e/faultproofs/util.go#L50) → [cfg.Start](https://github.com/JustXxx/optimism/blob/9eb5f880ee92f52161112fab1b897e57cdd00ce7/op-e2e/setup.go#L433) → [geth.InitL1](https://github.com/JustXxx/optimism/blob/9eb5f880ee92f52161112fab1b897e57cdd00ce7/op-e2e/setup.go#L563) → [createGethNode](https://github.com/JustXxx/optimism/blob/3124c8f05ce4d2eb27e61ef02a642add8666c745/op-e2e/e2eutils/geth/geth.go#L45) → [eth.new](https://github.com/JustXxx/optimism/blob/3124c8f05ce4d2eb27e61ef02a642add8666c745/op-e2e/e2eutils/geth/geth.go#L121) → [core.NewBlockChain](https://github.com/JustXxx/optimism/blob/3124c8f05ce4d2eb27e61ef02a642add8666c745/op-e2e/e2eutils/geth/geth.go#L121) → SetupGenesisBlockWithOverride → genesis.Commit → flushAlloc ``` This chain shows how the L1 node is set up: starting the fault dispute system, initializing the chain configuration, creating a Geth node, initializing the Ethereum backend, creating the blockchain instance, setting up the genesis block with any overrides, committing it, and finally flushing the initial allocation. ```Go for addr, account := range *ga { if account.Balance != nil { statedb.AddBalance(addr, uint256.MustFromBig(account.Balance)) } statedb.SetCode(addr, account.Code) statedb.SetNonce(addr, account.Nonce) for key, value := range account.Storage { statedb.SetState(addr, key, value) } } ``` ### Deploy contracts on L1 DemoContract: https://github.com/ethstorage/optimism/tree/po/e2e-contracts-demo ``` cd optimism make devnet-allocs ``` The command line actually runs: `forge script packages/contracts-bedrock/scripts/Deploy.s.sol --sig runWithStateDump()` It uses the dumpState function from forge-std ([source](https://github.com/foundry-rs/forge-std/blob/c28115db8d90ebffb41953cf83aac63130f4bd40/src/Vm.sol#L1598C14-L1598C23)) to dump the allocs of the genesis JSON file to disk. 1. Add deoply command in [packages/contracts-bedrock/scripts/Deploy.s.sol](https://github.com/ethstorage/optimism/commit/4864e0dadd784437bc18c66bf7be724f76a34c66#diff-8fe8403a6124761aa8f0a0ac133579ed84d86ee7ba25011ee84dfcb505a7ad77R60) 2. Add config in [L1Deployments ](https://github.com/ethstorage/optimism/commit/4864e0dadd784437bc18c66bf7be724f76a34c66#diff-84a80a67cc3ff9961747a5c800b64b347fef38ebaef9d40b50c63e442e3f3af0R717) ### compile contract & gen bindings ``` cd packages solc --abi ./contracts-bedrock/src/dispute/Demo.sol -o ./contracts-bedrock/forge-artifacts/Demo.sol cd ../op-e2e abigen --abi ../packages/contracts-bedrock/forge-artifacts/Demo.sol/Demo.abi --pkg bindings --type Demo --out ./bindings/demo.go ``` ### test calling contract ``` go test -run TestSendDemoTx ./faultproofs -v ``` # Contracts # Test cases ## Actor_test ### nary==1 `test_static_1v1honestRootGenesisAbsolutePrestate_succeeds` ``` trace_index: 16, output: 16 trace_index: 16, output: 17 dishonest move------------------------------------------> trace_index: 16, output: 17 trace_index: 8, output: 9 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> trace_index: 16, output: 16 trace_index: 8, output: 8 trace_index: 8, output: 8 trace_index: 4, output: 4 dishonest move------------------------------------------> trace_index: 8, output: 9 trace_index: 4, output: 5 trace_index: 4, output: 5 trace_index: 2, output: 3 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> trace_index: 4, output: 4 trace_index: 2, output: 2 trace_index: 2, output: 2 trace_index: 1, output: 1 dishonest move------------------------------------------> trace_index: 2, output: 3 trace_index: 1, output: 2 trace_index: 1, output: 2 trace_index: 7, hashAt: 35010703481443363862807397422646547926725586950496545168642673637966215389758 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> trace_index: 1, output: 1 trace_index: 7, hashAt: 83120635561198363924954260977965339660781053297720025809293478075485854608086 trace_index: 7, hashAt: 83120635561198363924954260977965339660781053297720025809293478075485854608086 trace_index: 3, hashAt: 92167397554250848837249875385363347950516434462644014474241869555464797459887 dishonest move------------------------------------------> trace_index: 7, hashAt: 35010703481443363862807397422646547926725586950496545168642673637966215389758 trace_index: 3, hashAt: 50834667954227266551364005785080844385770916729960059149089593973039465549782 trace_index: 3, hashAt: 50834667954227266551364005785080844385770916729960059149089593973039465549782 trace_index: 1, hashAt: 112184463887855387625706455566336483721184980394246774268494129152218621047050 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> trace_index: 3, hashAt: 92167397554250848837249875385363347950516434462644014474241869555464797459887 trace_index: 1, hashAt: 92458281274488595289803937127152923398167637295201432141969818930235769911599 trace_index: 1, hashAt: 92458281274488595289803937127152923398167637295201432141969818930235769911599 trace_index: 0, hashAt: 78338746147236970124700731725183845421594913511827187288591969170390706184117 dishonest move------------------------------------------> trace_index: 1, hashAt: 112184463887855387625706455566336483721184980394246774268494129152218621047050 trace_index: 0, hashAt: 1735202219674964179331318602900500622719544520133731366411170596106087346015 trace_index: 0, hashAt: 1735202219674964179331318602900500622719544520133731366411170596106087346015 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> trace_index: 0, hashAt: 78338746147236970124700731725183845421594913511827187288591969170390706184117 dishonest move------------------------------------------> ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> ``` ### nary==2 `test_static_1v1honestRootGenesisAbsolutePrestate_succeeds` ``` traceIndex: 16, actor: 0, output: 15 traceIndex: 16, actor: 0, output: 16 dishonest move----------------------------> determine direction for claim, parentIndex:4294967295, pos:1 =====owned subClaims===== traceIndex: 16, actor: 0, output: 16 =====attack with subClaims===== traceIndex: 4, actor: 0, output: 4 traceIndex: 8, actor: 0, output: 8 traceIndex: 12, actor: 0, output: 12 move, pos:4, atk_branch:0, claim:56505394830265723433472437494585254818789718438817829740444552478538656569879 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> determine direction for claim, parentIndex:4294967295, pos:1 =====owned subClaims===== traceIndex: 16, actor: 0, output: 15 determine direction for claim, parentIndex:0, pos:4 =====owned subClaims===== traceIndex: 4, actor: 0, output: 3 traceIndex: 8, actor: 0, output: 7 traceIndex: 12, actor: 0, output: 11 =====counter subClaims===== traceIndex: 4, actor: 1, output: 4 traceIndex: 8, actor: 1, output: 8 traceIndex: 12, actor: 1, output: 12 =====attack with subClaims===== traceIndex: 1, actor: 0, output: 0 traceIndex: 2, actor: 0, output: 1 traceIndex: 3, actor: 0, output: 2 move, pos:16, atk_branch:0, claim:48618243720168466562137882340993744132561456157076490531705777241933804455145 dishonest move----------------------------> determine direction for claim, parentIndex:0, pos:4 =====owned subClaims===== traceIndex: 4, actor: 0, output: 4 traceIndex: 8, actor: 0, output: 8 traceIndex: 12, actor: 0, output: 12 determine direction for claim, parentIndex:1, pos:16 =====owned subClaims===== traceIndex: 1, actor: 0, output: 1 traceIndex: 2, actor: 0, output: 2 traceIndex: 3, actor: 0, output: 3 =====counter subClaims===== traceIndex: 1, actor: 1, output: 0 traceIndex: 2, actor: 1, output: 1 traceIndex: 3, actor: 1, output: 2 =====attack with subClaims===== traceIndex: 3, actor: 0, stateAt: 255 move, pos:64, atk_branch:0, claim:627941761484697441925024003970071840017134316342470835106032157108381994966 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> determine direction for claim, parentIndex:1, pos:16 =====owned subClaims===== traceIndex: 1, actor: 0, output: 0 traceIndex: 2, actor: 0, output: 1 traceIndex: 3, actor: 0, output: 2 determine direction for claim, parentIndex:2, pos:64 =====owned subClaims===== traceIndex: 3, actor: 0, stateAt: 3 =====attack with subClaims===== traceIndex: 0, actor: 0, stateAt: 0 traceIndex: 1, actor: 0, stateAt: 1 traceIndex: 2, actor: 0, stateAt: 2 move, pos:256, atk_branch:0, claim:50418643324133943859200024492399139023325534202942671003635887555792790158454 dishonest move----------------------------> determine direction for claim, parentIndex:2, pos:64 =====owned subClaims===== traceIndex: 3, actor: 0, stateAt: 255 determine direction for claim, parentIndex:3, pos:256 =====owned subClaims===== traceIndex: 0, actor: 0, stateAt: 255 traceIndex: 1, actor: 0, stateAt: 255 traceIndex: 2, actor: 0, stateAt: 255 =====counter subClaims===== traceIndex: 0, actor: 1, stateAt: 0 traceIndex: 1, actor: 1, stateAt: 1 traceIndex: 2, actor: 1, stateAt: 2 traceIndex: 1, actor: 1, stateAt: 1 traceIndex: 2, actor: 1, stateAt: 2 traceIndex: 0, actor: 1, stateAt: 0 step, pos:1024, atk_branch:0, index:0 ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> determine direction for claim, parentIndex:3, pos:256 =====owned subClaims===== traceIndex: 0, actor: 0, stateAt: 0 traceIndex: 1, actor: 0, stateAt: 1 traceIndex: 2, actor: 0, stateAt: 2 dishonest move----------------------------> ***honest move++++++++++++++++++++++++++++++++++++++++++++++++++> ``` ro: outputroot tr: trace ``` 1(trace: 16) depth: 0 4(ro:4 ) 5(ro:8) 6(ro:12) 7 dis depth: 2, 1 Claim | | | 16(ro:1) 17(ro:2) 18(ro:3) 19 20(ro:4) 21(ro:5) 22(ro:6) 23 24 25 26 27 28 ... hon depth: 4 (SPLIT), 4 Claims | | | | | | | | 64 68(tr:3) 72 76 80 84 88 92 ... .... dis depth: 6 (SPLIT + n_bits), 1Claim |(proof index: 1) 256(tr:0) 257(tr:1) 258(tr:2) 258(tr:3) hon depth: 8, 4 claims | (proof index: 2) attack: post_stae: S_265 dis step() ``` How to determine a stepProof given an existing trace? (Directly calculated based on the position) ### find Prestate and post state ![image](https://hackmd.io/_uploads/SkYptuDs0.png) Prestate: 1. branch=0, first find the attacked claims's ancestor whose position % 1 <<N_BITS is not 0， the left of its ancestor is prestate 2. branch > 0, attachBranch - 1 is the prestate Poststate: 1. branch=MAX_ATTACK_BRANCH, first find the attacked claims's ancestor whose position % 1 <<N_BITS is not MAX_ATTACK_BRANCH, it's the Post state 2. branch<MAX_ATTACK_BRANCH, attachBranch is the poststate Cases: atk: 76, prestate 18 = 76/4 - 1, poststate: 76 atk: 80, prestate 4 = 80/4/4 - 1, poststate: 80 atk: 83, prestate 82， poststate 20= 83/4 atk: 95, prestate 94, postate 5= 94/4/4(整除) ## attacking the last branch with non-root-claim ancestor _findExecTraceAncestor() ``` 1(trace: 15) depth: 0 4 5 6 7 depth: 2 (SPLIT) | | | | 16 20 24 28 depth: 4 (SPLIT + n_bits) 64 65 66 67 80 81 82 83 ... .... depth: 6 | (the proof index is 1) 264 265 266 267 depth: 8 | (the proof index is 2) attack: post_stae: S_66 ``` ## _verifyExecBisectionRoot forge test --mc FaultDisputeGameN_Test --mt test_move_incorrectStatusExecRoot_reverts forge test --mc FaultDisputeGameN_Test --mt test_move_correctStatusExecRoot_succeeds gameImpl = new FaultDisputeGame({ _gameType: GAME_TYPE, _absolutePrestate: absolutePrestate, _maxGameDepth: 2 ** 3, _splitDepth: 2 ** 2, _clockExtension: Duration.wrap(3 hours), _maxClockDuration: Duration.wrap(3.5 days), _vm: _vm, _weth: delayedWeth, _anchorStateRegistry: anchorStateRegistry, _l2ChainId: 10 }); ``` n_bits = 1 (bisection) 1 depth: 0 2 3(x) depth: 1 4 5 6 7 depth: 2 8 9 10 11 12 13 14 15 depth: 3 16 17 18 19 20 21 ... depth: 4 (SPLIT, array of outputs - block transition state hash, disputed output) 32 x 34 x 36 x 38 x ... depth: 5 (SPLIT + 1, root claims - VM execution result) ``` _verifyExecBisectionRoot(claim_of_32, challenge_index_of_16, parentPos=16, _isAttack=true) _verifyExecBisectionRoot(claim_of_34, challenge_index_of_16, parentPos=16, _isAttack=false) ``` n_bits = 2 (quadsection) 1 depth: 0 4 5 6 7 depth: 2 | | | | 16 17 18 19 20 21 22 23 ... 28 29 30 31 depth: 4 (SPLIT) 64 68 72 76 80 84 88 92 ... 112 116 120 124 depth: 6 (SPLIT + n_bits) ``` _verifyExecBisectionRoot(claim_of_64, challenge_index_of_16, parentPos=16, _attackBranch=0) _verifyExecBisectionRoot(claim_of_68, challenge_index_of_16, parentPos=16, _attackBranch=1) _verifyExecBisectionRoot(claim_of_72, challenge_index_of_16, parentPos=16, _attackBranch=2) _verifyExecBisectionRoot(claim_of_76, challenge_index_of_16, parentPos=16, _attackBranch=3) _verifyExecBisectionRoot(claim_of_124, challenge_index_of_28, parentPos=28, _attackBranch=3) ## attacking the last branch with non-root-claim ancestor _findExecTraceAncestor() ``` import "forge-std/console.sol"; n_bits = 2 (quadsection) 1 depth: 0 4 5 6 7 depth: 2 (SPLIT) | | | | 16 20 24 28 depth: 4 (SPLIT + n_bits) 64 65 66(tr:7) 67 80 81 82 83 ... .... depth: 6 | (the proof index is 1) 264(tr:4) 265(tr:5) 266(tr:6) 267(tr: 7) depth: 8 | (the proof index is 2) attack: post_stae: S_66 ``` ## test addLocalData() on the right mid branch ``` n_bits = 2 (quadsection) 1 depth: 0 rootclaim(last block) s-- worldstate 4 5 6 7 depth: 2 -- worldstate | | |(attack) ... 16 17 18 19 20 21 22 23 24 25 26 27 ... depth: 4 (SPLIT) -- worldstate | （attack） 64 68 72 76 80 84 88 92 108 109 110 111 depth: 6 (SPLIT + n_bits) --vm_output | (attack) startingOutputRoot: 26 disputedOutputroot: 6 ``` ## test addLocalData() on the right most branch ``` n_bits = 2 (quadsection) 1 depth: 0 rootclaim(last block) s-- worldstate 4 5 6 7 depth: 2 -- worldstate | | | |(attack) 16 17 18 19 20 21 22 23 ... 28 29 30 31 depth: 4 (SPLIT) -- worldstate | （attack） 64 68 72 76 80 84 88 92 ...112 116 120 124 depth: 6 (SPLIT + n_bits) --vm_output | (attack) startingOutputRoot: 30 disputedOutputroot: rootclaim ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.