Could/should a wallet move away from turn-taking for consensus updates?

[AndrewStewart]

Due to the turn-based behaviour of a ForceMove state channel, the current wallet design must behave differently, depending on the order of the participants property of the state channel.

Example

Suppose Alice and Bob want to open a channel C1.

1. They choose the ordering [Alice, Bob], and exchange pre-fund setups
2. Now, they must decide whether to fund the channel with a direct deposit, indirectly through a ledger channel between [Alice, Bob], or virtually through an intermediary Henry the hub.
   • Currently, Alice’s wallet is responsible for behaving like a “coordinator” for the funding process.
3. Concurrently
   a. Alice’s wallet asks Alice for her choice. Say she chooses virtual. Alice’s wallet tells Bob’s wallet that she chose virtual.
   b. Bob’s wallet asks Bob for his choice. Say he chooses indirect.
4. Depending on whether a happens first, or b happens first, Bob’s wallet goes into either
   a. Wait for Bob to choose.
   b. Wait for Alice to tell Bob her choice, and then respond with “Reject – I wanted indirect”
   Likewise, after 3a, Alice’s wallet goes into:
   • wait for Bob to respond with his choice, and then try to find a common hub

This works for two-party channels, and is manageable for three-party channels. That’s enough to virtually fund C through a single hub. However, it’s very procedural, and doesn’t scale well: to fund C through two intermediaries requires three 2-party guarantor channels, three 2-party ledger channels, two 3-party virtually funded channels, and one 4-party virtually-funded channel. Continuing with the above technique seems unmanageable. Furthermore, since each participant must wait for all prior participants, funding C would take an unacceptable amount of wall time due to lag in communication.

Observations

While moving in-turn is important for safety in a general ForceMove channel, it’s not required in some specific rules

Example

Take the ConsensusApp, whose rules are currently here.

For those not familiar, the ConsensusApp simply changes the outcome of the channel once everyone has voted on that channel.

I’ve made a toy model of it here – watch the “STATES” tab as you click on the diagram. This implementation doesn’t take into account the fact that only participant turnNum % numParticipants is allowed to take an action.

Turn order – filling the gaps

In Alice and Bob’s channel C, even states are Alice’s turn, and odd states are Bob’s turn. Suppose they both have s5, s6, where

s6 = {
  turnNumber: 6,
  currentOutcome: '0xabc',
  proposedOutcome: '0xabc',
  votesRemaining: 0
}

Suppose Alice wants to propose a change to the outcome to 0x123. Currently, she’d have to ask Bob’s wallet to move, and then propose 0x123:

s8 = {
  turnNumber 8,
  currentOutcome: '0xabc',
  proposedOutcome: '0x123',
  votesRemaining: 1
}

Then, she’d wait for Bob to vote in s9, which updates the outcome.

Until at least one of them has both s8 and s9, the channel can only finalize in outcome 0xabc, which they both agree to. In a world where they both agree to switching the outcome to 0x123, they’re ok with either outcome until they both have s8 and s9. At that point, 0xabc is now a stale outcome, and they can forget about it.

However, it’s actually safe for Alice to simply sign

s8 = {
  turnNumber 8,
  currentOutcome: '0x123',
  proposedOutcome: '0x123',
  votesRemaining: 0
}

Note that s8 isn’t supported. Bob currently has sole control over using s8 in a support proof. He can do so in the following ways:

1. Sign s7 = { turnNumber: 7, currentOutcome: '0xabc', proposedOutcome: '0x123', votesRemaining: 1}
2. Sign s8 itself
3. Sign s9 = { turnNumber: 9, currentOutcome: '0x123', proposedOutcome: '0x123', votesRemaining: 0}
4. Sign s9 = { turnNumber: 9, currentOutcome: '0xabc', proposedOutcome: '0x456', votesRemaining: 1}

In other words, Bob can only choose whether to update the outcome to 0x123, or keep it at 0xabc. He has no more or no less power than if they sign states in order.

Implications

The wallet standard can be designed around Alice’s ability to safely broadcast a state out of order, and have Alice and Bob’s wallets make exactly the same choices:

• If Alice wants to change the outcome, she can choose the most efficient path that updates it, sign her state in that path, and send it out.
• If Bob agrees, he can fill in the gaps (if needed), and the outcome has changed.

Valid transitions

Another observation is that it’s actually safe for Alice to simply sign

s7 = {
  turnNumber: 7,
  currentOutcome: `0123`,
  proposedOutcome: `0x123`,
  votesRemaining: 0
}

Note that s6 -> s7 is not a valid transition.

This is a bit subtle. Bob can either:

1. Sign s7. This makes it supported
2. Sign a valid transition from s6

s7_valid = {
  turnNumber: 7,
  currentOutcome: '0xabc',
  proposedOutcome: '0x456',
  votesRemaining: 1
}

3. Sign a different state that’s not a valid transition from s6

s7_invalid = {
  turnNumber: 7,
  currentOutcome: '0xabc',
  proposedOutcome: EverythingGoesToBob,
  votesRemaining: 1
}

In 1, Bob could sign s7 and send it to Alice, but then call forceMove([s6, s7_valid]). However, since it’s Alice’s turn next, she can create a valid transition by signing

s8 = {
 turnNumber: 7,
  currentOutcome: `0123`,
  proposedOutcome: EverythingGoesToAlice,
  votesRemaining: 1
}

She can then call checkpoint([s7, s8]).

2 is no different from Bob rejecting Alice’s proposal in the current wallet.

3 is always an option for a malicious wallet, but s7_invalid will never have support without Alice’s vote, either on s7_invalid, or a valid previous or next state.

Implications

Two correct wallets only ever need to sign states where votesRemaining: 0.

The safety in this case seems to rely on there being just two participants. Is there a neat way to take advantage of a similar principle in an n-party consensus channel? One way is for the participants to only ever sign states where turnNum % numParticipants == 0. That way, once all participants sign such a state, it takes priority over any valid transitions from any previous states, removing Bob’s s7_valid “attack”.

[AndrewStewart]

Note that these techniques are only safe because we’ve removed refute. This might, therefore, preclude the ability to penalize the challenger for signing a later state when they call forceMove.

However, the “Invalid transition” technique offers some gas-optimization.

• if all wallets are correct, then anyone can call forceMove with a single state supported by everybody
• this minimizes gas consumption for the challenger, since validTransition is not called during the execution of forceMove
• wallets can also minimize gas consumption calling checkpoint to respond to stale challenges, and to store progress while going offline

[AndrewStewart]

Suppose that for each channel, the wallet has a channel store which keeps two things:

1. The latest supported state s, and its support
2. All other states with turn number greater than s.turnNumber

Here is an example LedgerUpdate protocol that a wallet can run, if it is allowed to send states out of order. The LedgerUpdate protocol manages the state of a consensus app. It’s initialized with three parameters:

context: {
  channelID: string;
  goal: Outcome;
  maxTurnNum: number;
}

The logic of maxTurnExceeded works as follows:

• get the latest supported state
• computes the happy path to the goal, from that state
• returns false if the maxTurnExceeded is exceeded in that happy path
• otherwise, returns true

The logic of shouldVote works as follows:

• get the latest supported state
• computes the happy path to the goal, from that state
• returns false if we already have our state in that happy path
• else, returns !maxTurnExceeded(context)

Here’s a RespondToChallenge protocol that does not require communication with other running protocols. The state chat is a bit ugly, so in short, it:

• responds if it can;
• checkpoints if it can; else
• succeeds if it’s not my turn (it can’t do anything else); else
• asks the app for a response if it’s an app channel; else
• vetos any proposed change to the outcome in a wallet channel

These two protocols work well together, if the LedgerUpdate protocol gives a bit of wiggle room on the turn number: If your message was dropped, and someone challenges you, your challenge protocol responds or checkpoints with the vote that you made. If it can’t, it vetos; at that point, your LedgerUpdate protocol would receive CHANNEL_UPDATED and vote again. If, after say 3 rounds, it didn’t succeed, it’s probably unrecoverable, and your wallet recovers your funds.

I think it’s harder to create this kind of synergy under the constraint that the LedgerUpdate protocol only signs-and-sends updates when it’s your turn. To do that, I think the RespondToChallenge protocol

• either needs to check if there are any currently-running protocols that could figure out how to respond; or
• needs to always veto (which is ok, but slows things down)

[tom]

[In this post, I’ve focus mostly on whether it’s necessary/advantageous to design wallets that send states out of order. A separate question is whether the proposed changes are safe. I’m still thinking about this and will try to answer it in a later post.]

I don’t fully understand the motivation that you give here. In the first post, you talk about the problem of determining which funding strategy to pursue, and then observe that it appears to be ok to sign states out of order in the consensus game, and that the wallet could be designed around the principle of sending states out of order. I don’t see how this relates to the initial problem of determining which funding strategy to pursue though, as picking a strategy would likely be done before proposing any state updates.

Are you claiming that the wallet design will be simplified by allowing states to be sent out of order, and/or making it the default behaviour for participants to sign states that are not theirs? I don’t believe that turn taking is really the main barrier here. In your example you have:

@AndrewStewart

Suppose Alice wants to propose a change to the outcome to 0x123 . Currently, she’d have to ask Bob’s wallet to move, and then propose 0x123 :

It seems that the implication here is that the first Bob knows about the intent to move to 0x123 is when he receives the first ledger update, as would be the case if all interwallet communication had to take the form of state exchange. It’s pretty unlikely that a wallet would be designed like this though; in particular, it seems unavoidable that wallets have some way to signal their intent to one another, outside state updates. This ledger update would probably form part of a larger intent e.g. to fund a given channel with that ledger channel.

If you assume Alice and Bob share the intent to update the channel from 0xabc to 0x123, the issue of Alice having to request an update from Bob disappears: if it’s Bob’s turn, he proposes the first update to the ledger, and Alice responds when it’s her turn.

It seems to me that the main problem here is how wallets coordinate intent. Once the intent exists in all wallets, it seems relatively simple to exchange the states to implement that intent - and also to detect when the one of more parties have deviated from the plan - regardless of whether you use turn taking or not.

[AndrewStewart]

@tom

In the first post, you talk about the problem of determining which funding strategy to pursue,

No, I talk about the problem that the wallet behaves differently depending on which participant you are. Choosing the funding strategy is one example of this. So is updating a ledger channel: currently, the ledger-update protocol takes a different action based on whether it’s your turn, according to your channel store. We haven’t tested (or even considered?) what happens when this condition is true for both participants, or when it’s false for both participants, and I honestly have a hard time thinking through all such cases.

The initial problem is that the wallet behaves differently depending on which participant you are. This leads to more complexity, and less scalability, especially when you consider the time waiting for a round to complete.

@tom

It seems that the implication here is that the first Bob knows about the intent to move to 0x123 is when he receives the first ledger update, as would be the case if all interwallet communication had to take the form of state exchange.

If it’s not Alice’s turn, then Alice can’t exchange a state, unless it’s
A. not her state
B.

not the next state
I am arguing that allowing Alice to do one (not necessarily both) of these, means that Alice can include a meaningful state in her message where she expresses intent to change the outcome to 0x123. This is literally an example where she cannot do that, if she does neither A nor B.

@tom

If you assume Alice and Bob share the intent to update the channel from 0xabc to 0x123 , the issue of Alice having to request an update from Bob disappears: if it’s Bob’s turn, he proposes the first update to the ledger, and Alice responds when it’s her turn.

It seems like this assumption holds for the existing protocols, but we haven’t haven’t yet answered “How do we choose a hub?”, and I’m not sure this assumption holds in that case.

There are also cases like: what if Bob is the hub, and it’s Bob’s turn? (This is currently never the case with a live hub.) Or, what if Bob’s the hub, it’s Alice’s turn, and Bob wants to do a partial checkout due to business decisions?

@tom

Once the intent exists in all wallets, it seems relatively simple to exchange the states to implement that intent - and also to detect when the one of more parties have deviated from the plan - regardless of whether you use turn taking or not.

I agree that it is relatively simple to exchange states: you can just exchange them in order. This post argues, with an implementation of LedgerUpdate, that it’s even simpler. I also off a dispute/responder protocol that works well with this LedgerUpdate, and handles something we currently don’t: challenges in a wallet channel. (Though, it doesn’t seem like you couldn’t write a turn-based LedgerUpdate protocol that has the same effect.)

Also, once you remove special participants, you gain access to different consensus protocols for eg. agreeing on funding. Currently, we do something like two-phase commit.* If you remove turn-order, then you can do something like a dynamic two-phase commit.

On top of this, wallets always need to handle states coming in out of order, regardless of whether they were sent out out of order. So, wallets need to do the hard part anyway.

To summarize, I’m arguing that ignoring turn-order gives you the following benefits:

• simpler protocols
• less latency when opening a channel
• more flexibility in expressing intent
• lower gas cost (in the version where everyone signs a single state)
• more flexible multi-party decision making

I’m interested in hearing the benefits of only ever sending states out in order.

[zakalwe]

I find it a bit odd to construct a protocol where people are signing “invalid” transitions. Can’t you just make them valid?

If you removed the requirement for participants to act strictly in turn from forceMove and pushed it into validTransition(), then you can construct your consensus algorithm more cleanly by allowing anyone to advance the state from a votesRemaining = 0 state, and then anyone else can advance it if they’ve not voted until they’ve all voted.

This means, of course, that you need to keep track of who’s voted, but it feels less like you’re hacking the protocol.

In both cases, however, you need to find a way to handle the situation where more than one participant tries to advance the state at the same time.

In your example, you have a resolution to this which boils down to Bob can always have the last word. ie if Alice signs an invalid state 7 proposing a new outcome, and Bob doesn’t like it, he can always veto it by signing a valid state 7 with a different outcome and Alice can’t do anything about it.

In my example you’d just get stuck - which isn’t great either…

I suppose in both cases you’ve just failed to reach consensus which is the point of the exercise

[AndrewStewart]

The cleanest consensus algorithm turns out to not have a validTransition function at all. If appDefinition == address(0), or if validTransition always returns false, then the only way to increase the turnNumRecord is for all participants to sign a single state.

This has many nice properties:

1. If my wallet only ever signs one state at turn n, then because of the ForceMove rules, my wallet can guarantee that a finalized channel outcome is either
   • the outcome on the latest supported state
   • one of the outcomes on a later, unsupported state, that my wallet signed
2. If my wallet has a supported state s, and refuses to sign any later state, then my wallet can guarantee that the channel doesn’t terminate except with s.outcome.
   • In the nitro paper, this is termed “finalizable”
3. There is no turn order, so it’s safe-by-design to support a new outcome in any order.
4. Gas usage is optimal: validTransition is never called, and appData is always zero-length.

It’s worth noting that this is the second type of channel in the Counterfactual framework, but it turns out that it’s (unintentionally) built into the ForceMove protocol. This didn’t use to be the case, since in the original protocol, I could only sign my own state.

The existing consensus app has this problem

imagine that s3, s4, s5 are a round of consensus states between [Alice, Bob, Charlie]

• Alice proposed outcome1 in s3, where the current outcome is outcome0
• Bob votes in s4
• Charlie votes in s5
  Then outcome2 is finalizable by Alice and Charlie, but not Bob.

The problem is that after signing s5, Charlie could sign s5’ with outcome2

• If Bob calls forceMove(s5)
• Then Charlie signs s5’ proposing outcome2
• Alice signs any valid transition s6’ from s5’
• Alice calls checkpoint([s4, s5’, s6’])
  At this point, Bob cannot enforce the outcome of s5. ie outcome1 is not finalizable by Bob, even though he has the support for it.

In other words, some modification of the existing ConsensusRules is needed so that outcome1 is finalizable by Bob in the case where all parties have support for s5, and never allowing a valid transition is the best way to do that.

[zakalwe]

um… ok. This is going in a slightly unexpected direction.

I think you need a new name for this - “Outcome Channels”? as you’ve basically ditched the state completely!

In your consensus example, what’s supposed to happen when consensus is reached? Is the channel allowed to progress past this point, or is implicit that it’s finished?

If it’s the latter, then surely being able to present a supported S5 should be enough to end the channel regardless of turnNum, because any higher turnNum would be invalid?

either way, how does ending a channel work in this model?

[AndrewStewart]

@zakalwe

um… ok. This is going in a slightly unexpected direction.

Agreed!

@zakalwe

I think you need a new name for this - “Outcome Channels”? as you’ve basically ditched the state completely!

State hasn’t been ditched. What’s ditched is the ability to unilaterally change the state, from the adjudicator’s point of view.

[edit: perhaps you mean “application state has been ditched”, and this is correct. But the ConsensusApp doesn’t have any meaningful application state past “Does everyone agree to this outcome?”, and in this case, a signature on a later state with the proposed outcome is good enough.]

I’ve been calling them a “Null” channel, as the rules are absent. “Outcome channel” might be a good word for it, though it accomplishes exactly the same thing that the existing ConsensusApp aims to: update the outcome precisely when everyone agrees to update the outcome. In that sense, it might be best to simply call it a “Consensus channel”

@zakalwe

In your consensus example, what’s supposed to happen when consensus is reached? Is the channel allowed to progress past this point, or is implicit that it’s finished?

It’s just a regular channel, and can progress as normal, past this point.

Any ForceMove channel has the same property, that you can support a single state with arbitrary appData, and never call validTransition. In this case, it’s on the client to ensure that the appData is valid, though we might add a feature to the framework that lets application rules expose a validateAppData function.

The only thing that the “Null channel” does is limit the channel mechanics to only update the state with everyone’s explicit buy-in. At that point, app data is meaningless: your client can use arbitrary rules to decide whether to agree to a later state. You wouldn’t do this to play chess, of course, since there’s no way to enforce the off-chain play in a new outcome. But in a case where the only purpose of the channel is to change an outcome (payment channels, ledger channels, guarantor channels) it works fine.

@zakalwe

either way, how does ending a channel work in this model?

None of the ForceMove rules are different: A channel is ended when either:

• someone supplies the adjudicator with a supported state with isFinal == true
• someone calls forceMove with a supported state, and nobody responds or checkpoints with a later supported state in time