Understanding Force Move from the code

1

Hi

So I’m trying to make sure I fully understand the current implementation of the force move protocol. I’ve been through the code, and this is what I understand. Could someone quickly scan this and see if I’ve got it right? I’m skipping some trivial validation stuff

forceMove()

Checks:

  • The turnnum record on chain matches the supplied turnnum, and that the other data stored is blank (which implies no current challenge)
  • The turnnum of the last supplied state is greater or equal to this
  • that the state chain up to this point consists of valid state transitions and signatures
  • that the challenger is one of the participants

Does:

  • stores the hash of various data relating to the challenge, flagging the channel as being challenged

respond()

Checks:

  • that a timeout hasn’t passed
  • that the hash of the supplied challenge state matches what’s stored on chain
  • that the proposed new state has a turnnum of strictly one greater than the challenge turnnum, and is signed by the participant who’s turn it is
  • that it’s a valid transition to a new state

Does:

  • clears the challenge, writing the turnnum of the challenge + 1 to the chain

refute()

Checks:

  • that a timeout hasn’t passed
  • that the hash of the supplied challenge state matches what’s stored on chain
  • that a supplier turnnum is greater than the turnnum stored on chain
  • that some data that represents a later state is signed by the participant that initiated the challenge

Does:

  • clears the challenge, writing the turnnum of the challenge to the chain

repondWithAlternative()

Checks:

  • that a timeout hasn’t passed
  • that the hash of the supplied challenge state matches what’s stored on chain
  • that a new state chain consists of valid state transitions, is correctly signed, and ends up with a final state with a turnnum exactly one greater than the one being challenged

Does:

  • clears the challenge, writing the turnnum of the challenge + 1 to the chain

That correct?

Thanks, Jeremy

2

The only thing missing is that refute, respond, and repondWithAlternative also currently check that a challenge is ongoing, and revert if the channel is open (ie. finalizedAt == 0.)

It might be worth keeping in mind this alternative, “minimal” protocol:

forceMove()

Checks:

  • The turnnum record on chain matches the supplied turnnum, and that the other data stored is blank (which implies no current challenge)
  • The turnnum of the last supplied state is greater or equal to this
  • that the state chain up to this point consists of valid state transitions and signatures
  • that the challenger is one of the participants

Does:

  • stores the hash of various data relating to the challenge, flagging the channel as being challenged

checkpoint()

Checks:

  • that a timeout hasn’t passed
  • that the hash of the supplied challenge state matches what’s stored on chain
  • that a new state chain consists of valid state transitions, is correctly signed, and ends up with a final state with a turnnum greater than the one being challenged

Does:

  • clears the challenge, writing the turnnum of the final state in the state chain to the chain

This minimal implementation theoretically does everything needed by the protocol. The respond method above is cheaper since it only has to validate a single signature and transition. The refute method can be implemented with some kind of penalty that provides an economic incentive for the challenger not to call forceMove with a stale state. The respondWithAlternative method above seems sub-optimal – there’s no benefit to forcing the responder to increase the turn number by exactly one.

3

The respondWithAlternative method above seems sub-optimal – there’s no benefit to forcing the responder to increase the turn number by exactly one.

Indeed. If you remove that requirement you pretty much end up with the checkpoint() method.

So - if I get this correctly - the de minimis approach looks like:

(defining “Valid State” as a sequence of states with correct transitions, and correctly signed by a quorum of participants; and its turn number as the turn number of the last of these states)

  • The channel starts with “last valid turn number” of 0
  • unless the channel is being challenged, any participant can post a forceMove() with a valid state that has a turn number >= to the one stored on chain.

Then, either:

  • the next participant can respond() with the next state
  • or, anyone can post a checkpoint() with a valid state which has a strictly greater turn number than that of the challenge

in either case the turn number on chain is updated to that of the new state and the challenge is cleared.

Does that work?

Edit - you could add a checkpointAndForceMove() call as a gas optimisation, but it’s not strictly necessary as you can call checkpoint() followed by forceMove() to achieve the same effect.

Edit #2 - if you want to penalise posting stale state, you can simply add this to checkpoint() by counting the number of additional states and checking if the challenger must have signed an additional state after the challenge state. Or: checkpoint turn number - challenge turn number >= num participants

4

So - if I get this correctly - the de minimis approach looks like:

(defining “Valid State” as a sequence of states with correct transitions, and correctly signed by a quorum of participants; and its turn number as the turn number of the last of these states)

  • The channel starts with “last valid turn number” of 0
  • unless the channel is being challenged, any participant can post a forceMove() with a valid state that has a turn number >= to the one stored on chain.

Then, either:

  1. the next participant can respond() with the next state
  2. or, anyone can post a checkpoint() with a valid state which has a strictly greater turn number than that of the challenge

in either case the turn number on chain is updated to that of the new state and the challenge is cleared.

Does that work?

Yes, that does work, but it’s not quite minimal. Rather than calling respond with just one state, you can call checkpoint with that new state, as well as enough previous states to achieve quorum.

Edit - you could add a checkpointAndForceMove() call as a gas optimisation, but it’s not strictly necessary as you can call checkpoint() followed by forceMove() to achieve the same effect.

Correct. You could also alter forceMove to only require that it increases the turn number – ie. it would overwrite an existing challenge. I think this makes more sense from a theoretical point of view, as it allows you to make this guarantee:

G2: The turnNumRecord stored on-chain is the turn number of the most recent supported state seen by the adjudicator.

Practically, it might have an effect on how a wallet watches and manages challenges: if Alice and Bob simultaneously call forceMove, Alice’s wallet would now have to listen for two types of events:
E1: The challenge is cleared
E2: The challenge is superseded by another challenge

However, given the possibility of orphaned blocks, I think Alice’s wallet still has to listen for E2 during a challenge, even with the current forceMove.

Edit #2 - if you want to penalise posting stale state, you can simply add this to checkpoint() by counting the number of additional states and checking if the challenger must have signed an additional state after the challenge state. Or: checkpoint turn number - challenge turn number >= num participants

Also correct. The checkpoint could also be smart enough to check if the penultimate state provided matches the challenge state, if exists, and use the same logic as respond in this case. In other words, checkpoint could, in principle*, implement refute and respond.

But the caller would already be aware of this, and can perform that logic off-chain, resulting in simpler implementations (less branching, and fewer chances for bugs) and lower gas costs (fewer on-chain checks).

*The one edge case I can think of is, in this “minimal” framework, is:

  1. Let’s say Eve signs even states.
  2. Eve calls forceMove(s9,10)
  3. Alice calls checkpoint([s99,s100]) in tx, expecting the adjudicator to penalize Eve
  4. Eve front-runs with checkpoint([s10,s11]). checkpoint uses “respond” logic, since the penultimate state matches the challenge state. The challenge is cleared without penalty.
  5. Since there’s no challenge ongoing, when tx is mined, checkpoint does not use “refute” logic, and Eve is not penalized.

This is a pretty contrived situation, and Eve still wouldn’t be penalized if you replace checkpoint with refute(s100) in (3), since Eve would still clear the challenge before tx is mined.

5

For reference, I’ve implemented a different ForceMove protocol in a setting where turnNumRecord and finalizesAt are un-hashed.

forceMove()

Checks:

  • that the channel is not finalized
  • that the challenge state is supported
  • that the challenge state’s turn number is not less than the turnNumRecord in storage
  • that the challenger is one of the participants

Does:

  • sets turnNumRecord to be the turn number of the supported state.
  • sets finalizesAt to be now, flagging the channel as being challenged
  • sets the fingerprint to be the hash of various data relating to the challenge

checkpoint()

  • Replaces respondWithAlternative

Checks:

  • that the channel is not finalized
  • that the final state provided is supported
  • that the supported state’s turn number at least the turnNumRecord in storage

Does:

  • sets turnNumRecord to be the turn number of the supported state.
  • sets finalizesAt to be 0, flagging the channel as being open
  • (arbitrarily*) sets the fingerprint to be the hash of (turnNumRecord, finalizesAt)

conclude()

  • Replaces concludeFromOpen and concludeFromChallenge

Checks:

  • that the channel is not finalized
  • that the final state provided is supported
  • that all states are marked as final

Does:

  • (arbitrarily**) sets turnNumRecord to be the turn number of the supported state.
  • sets finalizesAt to be now, flagging the channel as being finalized
  • sets the fingerprint to be the hash of (turnNumRecord, finalizesAt, finalState)

* The mode of the channel is entirely decided by finalizesAt, and he fingerprint is never needed when the channel is open (<=> finalizesAt == 0), so it could set the fingerprint to be anything. A nice consequence of this is, since channelStorageHashes[someRandomBytes32Value] is bytes32(0), all possible channels are initially open with turnNumRecord == 0 and finalizesAt == 0.

** Once a channel is finalized (<=> finalizesAt > 0 && finalizesAt <= now), its data in storage can never change. So, the turnNumRecord is no longer relevant.

6

Yup - well we’re better than we were before - Eve can only grief once here before the channel is brought up to date.

And the other stuff all makes sense to me!