clabby
commented
1 year ago Hey! So this may be a bit long, but it'll be good to document some details about the game for future reference here.
Contracts
The two contracts that we'll need to deploy are the DisputeGameFactory and the FaultDisputeGame.
The DisputeGameFactory is responsible for keeping track of implementation contracts for different GameTypes, creating clone proxies of games with the create function, and bookkeeping of the games keyed by a unique identifier. When a faulty output proposal is submitted to the output oracle, the role of the off-chain challenge agent is first to create a new game via the factory to begin a dispute on the output proposal they deem faulty.
The FaultDisputeGame was outlined in my CMDX presentation earlier this year - that is the best place to go to get a long-winded explanation of its mechanics. To sum it up, it allows for n players to bisect over an execution trace generated by the op-program to find the left-most, deepest divergence point among the participants' claims. At the very bottom level of the bisection in the leaf nodes, players must resort to executing a single instruction step of the MIPS program on-chain in order to prove their trace as truthy. Many paths can be taken through this bisection due to the game allowing for anyone to play, but only one path is correct. This also introduces the mechanic that rational players with the same traces effectively act as the same entity.
A few smaller details that may help:
- Claims
Claims always disagree with their parents.Claims are effectively promises that commit to a value,true|false, that is revealed in the resolution process. At the time of creating aClaim, it has no objective concept of truthiness, only relative truthiness.Claims that are dangling and have never been countered after clocks have ran out implicitly resolve totrue.
- Clocks
- At the root claim (i.e. game creation), a chess clock is initiated with 3.5 days on either end (7 days total = challenge period). Both sides of the clock signify the total time a player has to make their moves. It works exactly like a chess clock - when a move is made, time pauses, and the opponent's begins ticking. Immediately on game creation, a potential challenger's clock begins ticking.
- Because the game is permissionless, many separate traces may exist within the bisection, causing forks. Because of this, moves always inherit the chess clock of their grandparent claims to ensure that all paths are time boxed to 7 days total.
- Resolution
- Once all clocks have ran out, resolution of the game is permitted. In this process, the left most, deepest non-countered claim that is not at the tree's maximum depth is found and bonds are paid out.
Agents
When fault proofs go live onchain, players will be incentivized to run off-chain challenge agents to challenge any faulty claims that present themselves via the bonds attached to the claims they counter. There are three types of situations that the challenger needs to respond to:
- Faulty output proposal detected - Create a dispute game.
- Dispute Game Created - Check to see if you disagree with the root claim. If you do, attack it. If you agree with it, do nothing.
- Claim Made in Game - Check the trace index that the claim commits to, run cannon to get the merklized state hash at that instruction, and check to see if you disagree with the claim. For any given claim that has a parent, consult the following diagram to determine the move(s) the agent needs to make:
As for agents we can implement in Arbiter, I think there are several strategies that may be interesting:
- Fully rational + honest. This actor runs a correctly synced rollup node and will respond honestly 100% of the time. i. Goal: In order for a dispute game to resolve correctly, whether an honest or dishonest root claim was made, an honest actor must be present to respond to invalid claims.
- Fully rational + dishonest. This actor runs an incorrectly synced rollup node and will respond honestly 100% of the time. i. Goal: It is possible that several participants in the network may, at times, fall out of sync with their peers while running the software. It would be interesting to see what a challenger that trusts a node that experiences a reorg deep enough to change the disputed block within the game behaves like, or one that was fully out of sync to begin with.
- Irrational + dishonest. This actor just throws whatever they can at the contract. i. Goal: Chaos test the system and ensure that even under adversarial conditions, the game may always resolve correctly if an honest actor is playing.
In general, the primary goals are:
- Shake out whether the game can always resolve correctly, even under adversarial conditions, assuming the presence of 1 or more honest challengers.
- Profile the game's footprint on the network.
- Future - In the alpha, bonds will be left out, which are required for making this thing incentive compatible and thus permissionless. In the future, it will be advantageous to model situations in which the bonds can be undercollateralized by adversarial actors as well as the re-collateralization mechanism to ensure that these situations can always be recovered from. This part isn't fully shaken out, but I think this is going to be a place Arbiter can give us peace of mind.
A lot of this is abbreviated, so please feel free to ask questions! Thanks for the interest in working with us on this - I think Arbiter will be very powerful in chaos testing / profiling this thing 😄
0xJepsen
Would be curious to think about what agents would need to be designed for this scope. I'm personally jazzed on this.