Fault Proof
Table of Contents
Overview
Interop introduces the Super Fault Dispute Game as a new dispute game type. It is based on the pre-interop fault dispute game with some modifications:
- Claims at and above the split depth are commitments to the state within the super root state transition described below instead of output roots.
- The L2 block number is replaced by the timestamp of the proposed super root.
- The
l2BlockNumber()
method has been renamedl2SequenceNumber()
inIDisputeGame
interface to reflect that this is an arbitrary identifier within the fully ordered sequence of chain states.
- The
- The L2 block number challenge is removed. The super root state transition is now able to invalidate all proposals with an incorrect proposal timestamp as part of the state transition.
- While claims in the bottom half of the game still commit to the state of the FPVM, the fault proof program being executed changes to verify the disputed step of the super root state transition instead of the application of a disputed L2 block.
- The L2 block number preimage oracle local key now always provides the timestamp of the proposal.
- The L2 chain ID preimage oracle local key is no longer used and is never populated by the dispute game.
Super Root State Transition
The super fault dispute game defines a state transition from the current anchor state super root to the canonical super root at the game's proposal timestamp, if one can be derived from the available L1 data or the invalid state if not.
As the valid state transition always extends to the game proposal's timestamp, proposing a super root with a timestamp
less than or greater than game's proposal timestamp will be found to be invalid. Similarly any root claim that is the
hash of a TransitionState
will be found to be invalid.
To reduce the amount of processing required in a single invocation of the FPVM, the state transition breaks the
transition from the super root at one timestamp to the super root at the next timestamp into 128 steps. The claims for
these intermediate steps are keccak256
hash of a transition state. These 128 steps repeat to
transition between the super root at each timestamp from the anchor state until the proposal time is reached.
Transition State
A transition state is RLP encoded data consisting of:
SuperOutput []byte
- the encoded super output at the immediately prior timestamp. This is the super root that is being transformed from.PendingProgress []LocalSafeBlock
- the next block derived for each chain from L1 batch data, prior to validating executing messages.LocalSafeBlock
is twobytes32
RLP encoded, the first being the block hash and the second the output root for the block.
Step
auint64
recording the number of steps applied to thisTransitionState
since theSuperOutput
.
Invalid State
The invalid state is defined as keccak256(utf8("invalid"))
. This state is used to indicate a state transition where
there is no possible valid proposal. The dispute game contract MUST prevent a game from being created where the root
claim is the invalid state.
When the prestate is the invalid state, the post state is also the invalid state.
Local Safe Block Derivation
The first 127 steps derive the next local safe block for one chain in the super root using
the derivation process. Chains are processed in the order they appear in the super root
(ascending order of chain ID). The Step
is incremented after each step.
For each step, the valid post state TransitionState
is calculated by the algorithm:
- If the prestate is a SuperRoot, convert it to a
TransitionState
withStep = 0
andPendingProgress
an empty array. - If
Step
is less than the number of chains included inSuperOutput
, derive the next local safe block for the chain at indexStep
in theSuperRoot
using the derivation process. Executing messages are not checked at this stage.- No block is derived if
Step
is greater than the number of chains in the super root. - If the derivation process is unable to derive the next L1 block because the L1 head is reached, the post state is the invalid state
- No block is derived if
- Increment
Step
Since one step is required per chain in the dependency set, the current dispute game can support a maximum of 127 chains in the dependency set. If a greater number of chains are required in the future the number of steps can be increased.
Consolidation
When the prestate is a TransitionState
with Step = 127
, the validity of executing messages is checked and any
local safe blocks found to contain invalid executing messages are replaced with deposit only blocks. This includes
recursively replacing any blocks with executing messages that became invalid because of another block being replaced.
The post state is defined as a super output where timestamp
is the SuperOutput
timestamp + 1, and the output roots
are set to the output roots of the validated blocks (including any required replacements).
Fault Proof Program State Transition
Below the split depth, claims correspond to execution trace commitments of the FPVM, as with the pre-interop fault dispute game. A single ABSOLUTE_PRESTATE continues to be used, with the fault proof program identifying the type of step to perform based on the agreed prestate.
Security Considerations
TODO