Symmetric dispute game

[kerzhner]

This branch converts the dispute game to be symmetric.

1. The challenger initializes the ChallengeManager with a set of commitments.
2. The proposer finds the commitment with the largest step that the proposer agrees with. The proposer then calls split to dissect the commitment range between the agreed commitment and the disputed commitment.
3. The challenger and proposer alternate calling split until the agreed commitment is the commitment before the disputed commitment (or until disputeFraud can be invoked without running out of gas).

Interesting work remaining for this PR is:

• [x] Eliminate the explicit step field from the StepCommitment
• [ ] In Solidity, it will be impractical to store the list of commitments. Instead, we'll store the hash of (consensusIndex, highestIndex, merkleRootOfCommitments)

[andrewgordstewart]

While adding more robust testing, the following issue was discovered with dispute witnesses. Assume that correct states are [0..19] in increments of 1. Assume that incorrect states are [0..9, 15.1..19.1] in increments of 1.

The following sequence of calls can occur:

1. Challenge manager is initialized with [0, 9, 19] by the challenger. Challenger uses correct states.
2. Split is called with consensusWitness of 9, states of [14] and disputeWitness of 19. disputeWitness needs to be a witness for the merkle root of states recorded on chain.
3. The challenger does not disagree with any of the states in the challenge manager.

(3) should be an invalid move, shouldn't it? The game should assume that Alice & Bob:

1. agree on S_0
2. disagree on S_n

And, at each round in the game, this invariant should hold:

• Alice & Bob agree on S_low and disagree on S_high

Given this, it seems like the dispute witness is needed.

[kerzhner]

The game should assume that Alice & Bob:

1. agree on S_0
2. disagree on S_n

And, at each round in the game, this invariant should hold:

• Alice & Bob agree on S_low and disagree on S_high

Given this, it seems like the dispute witness is needed.

Agreed with a caveat! Let's say that the merkle root stored in the contract contains leaves [S_0..S_i, S_i+1..S_n]. I am not seeing the benefit of the split caller providing a witness for S_i. It seems that the caller needs to provide:

1. Witness for S_i. The caller agrees with this state and shows that the state is part of the stored tree.
2. A new set of states that splits the range between S_i and S_i+1
3. S'_i+1. The caller needs to record its version of this state so that the next caller has the opportunity to split the range between second-to-last and last states.

[andrewgordstewart]

Agreed with a caveat! Let's say that the merkle root stored in the contract contains leaves [S_0..S_i, S_i+1..S_n]. I am not seeing the benefit of the split caller providing a witness for S_i.

Do you mean

I am not seeing the benefit of the split caller providing a witness for S_{i+1}?

It seems that the caller needs to provide:

1. Witness for S_i. The caller agrees with this state and shows that the state is part of the stored tree.
2. A new set of states that splits the range between S_i and S_i+1
3. S'_i+1. The caller needs to record its version of this state so that the next caller has the opportunity to split the range between second-to-last and last states.

I thought it was important for the dispute game to validate that S'_{i+1} != S_{i+1}. Otherwise, can't the caller realize they were wrong, and commit to S_{i+1}? The other party can no longer prove fraud.

[kerzhner]

I thought it was important for the dispute game to validate that S'_{i+1} != S_{i+1}. Otherwise, can't the caller realize they were wrong, and commit to S_{i+1}? The other party can no longer prove fraud.

I see your point. I believe that the split caller needs to provide S_i+1 as part of the state list (or, in the future, the hash of the encoding of S_i+1) AND a witness for S'_i+1. In this case S_i+1 is the state the caller believes is correct and S'_i+1 is the state recorded on chain by the previous caller.