Playing the state channel exit game

In the previous post, we introduced the concept of a state channel outcome: a piece of data that instructs the chain as to how to move the funds held in a state channel. In order for the chain to act on the outcome, the outcome must first be finalized.

Today we’re going to be looking at this other half of the process: how participants go from the states they hold, to finalized outcomes on-chain. Another way of saying this, is that we’re going to be looking at the ‘exit game’ of a state channel. Understanding this process is key to the off-chain funding we saw last week. Participants need to be able to understand which outcomes could be finalized, in order to construct the equivalent outcomes necessary to fund/defund channels entirely off-chain.

This will involve a deep dive into the format of the off-chain states, including how participants can use them to drive the chain from one state to another.

A Toy State Channel System

A large part of our work on the statechannels project has been to design a state channel system that allows rich state transitions, is robust against a full range of adversarial behaviours, and is gas efficient. We’ll talk about this work in future posts, but for today we’re going to focus on a much simpler, ‘toy’ state channel system.

What do we mean by a ‘toy’ system? The system we’re looking at today is deficient in a number of areas. First up, it requires complete agreement between the parties in the channel to progress the state: new states are only valid if every single participant signs off. It’s a common misconception that state channels only proceed via complete consensus. As we’ll see next week, in order to support the richest state channel behaviour, a participant needs the ability to unilaterally progress the state a short distance, according to a pre-agreed set of rules. Secondly, the system we’re looking at today has no interesting state. The only data that each state contains is the current outcome, meaning that our state channel system is actually a payment channel system. Finally, we have the simplest possible on-chain behaviour. Once a challenge is launched, there’s no way to recover and continue the interaction off-chain - the only way forward is for the channel’s outcome to be finalized on-chain.

In spite of all this, the system we’re looking at today captures most of the important features of state channel systems, and will allow us to see what it means for an outcome to be finalizable.

We start describing the system by looking at the state. State is a very overloaded word, but when we talk about a state channel state, we mean ‘the data that the participants sign and exchange off-chain’. To progress the channel, a participant will sign and broadcast a new state. In our toy model, the state has the following format:

type State = {
  participants: Address[]   // state-signing addresses
  channelNonce: Uint256     // chosen to make channelId unique
  turnNum: Uint256          // increments as the state updates
  outcome: Outcome          // e.g. [Address, Uint256][] for an
                            // allocation outcome
}

The state contains an array of participants, each defined by the address corresponding to the private key they will use to sign channel updates. Note that these addresses don’t have to correspond to accounts that hold ETH on the main-chain - they can even be emphemeral addresses that exist only for the length of the channel. There’s then a channelNonce, which is used to ensure that the channelId for each channel is unique:

function channelId(s: State): Bytes32 {
  return keccak256(s.participants, s.channelNonce)
}

It’s the responsibility of each participant to ensure that they don’t enter into a new channel with the same address as a previous channel. There are several ways to accomplish this, including storing the highest nonce used for each set of participants, or using a different signing address for each channel. The channelId encodes the notion of what it means for states to belong to a given channel, and is also used to identify the channels on-chain. By defining it in terms of the participants and channelNonce, we ensure that these properties don’t change over the lifetime of the channel.

The last two properties, the turnNum and the outcome, can vary from state to state. The turnNum introduces an ordering on the states, with states with higher turn numbers considered ‘more recent’. The outcome is the data we introduced last week, which instructs the chain how to move the funds. The outcome on a state corresponds to the outcome that would be finalized were the channel to end in this state. For the purposes of understanding the finalization mechanism, the format of the outcome doesn’t matter - we can just consider it an arbitrary chunk of data that we’re trying to write to the chain.

In order to write the outcome to the chain, we need to look at the next part of the system, the state of the chain. To do this we’ll introduce an object called the Adjudicator, which will be responsible for managing the state channel finalization process. We will talk about the adjudicator as though it’s a single smart contract that manages every channel in the system, but there’s nothing to say it needs to be architected this way - it could just as easily be a contract per channel for example. The adjudicator contract might or might not also play the role of the asset-holder, holding the funds deposited in the channel, and handling payouts from the system, though in general its only responsibility is to produce finalized outcomes, and pass them to the asset-holders for processing.

The adjudicator can be considered to be a big lookup table, that stores the on-chain state associated with each channel:

type Adjudicator = {
  storage: (channelId: Bytes32) => ChannelStorage
  launchChallenge: (state: State, sigs: Signature[]) => void
  counterChallenge: (state: State, sigs: Signature[]) => void
}

type ChannelStorage = Empty | Challenge | Finalized
type Empty = {}
type Challenge = {
  finalizesAt: Uint256   // block when outcome will be finalized
  challengeState: State // state that launched the challenge
}
type Finalized = {
  outcome: Outcome
}

In our toy system, the on-chain channel storage for a given channel can be in one of three states: empty, challenge, or finalized, and there are two methods which can be called to trigger transitions between them. The system is summarised in the following diagram:

In order to trigger the finalization process, a participant calls the LaunchChallenge method on the adjudicator, providing a state that is signed by every participant in the channel (‘fully-signed’). This stores the challengeState in the adjudicator, and also sets the finalizesAt property to be the current block number plus a challengeDuration, which, for our toy system, is hard-coded into the adjudicator.

There then starts a period of time where another participant can CounterChallenge. In order to do this, they must provide another fully-signed state, which has a larger turnNum than the challengeState.turnNum stored on the chain. If a successful CounterChallenge is performed, then the challenge period restarts, to allow another CounterChallenge if required. With the possibility of multiple counter-challenges, it might seem that the channel could be stuck in the challenge state for quite some time. In actual fact, this isn’t a problem: all it takes is for one honest participant to challenge/counter-challenge with the most-recent state, and no further counter-challenges are possible.

When the block number exceeds the finalizesAt time, the channel will ‘automatically’ transition into the Finalized state. In practice, this is a virtual transition - nothing changes on chain at that moment, but after it has passed the chain treats the channel as finalized. The finalized outcome can then be passed off to the asset-holder(s), to trigger the release of the funds held for the channel.

Finalizable Outcomes

In order to understand when value has been transferred in a state channel, it’s important to be able to understand which outcomes are possible, given the states/signatures that have been exchanged. We will now do this analysis for the toy state channel system introduced above.

Last week, we touched on the concept of a finalizable outcome, saying that there were some outcomes that we could reason about as though they’d been finalized, even though that they weren’t yet on-chain. We’ll now make this concept more precise:

An outcome is finalizable for a participant, if that participant has an unbeatable strategy for getting the outcome finalized on-chain, given the set of states they hold and have signed.

By ‘unbeatable strategy’ we mean that, regardless of the actions any other party takes (provided these don’t break the liveness of the chain), the participant has a sequence of actions that they can take, which will lead to the outcome being finalized on-chain.

In the toy system above, it’s reasonably easy to figure out the conditions when an outcome is finalizable. An outcome, O, is finalizable for Alice if:

• Alice holds a fully-signed state, S, with outcome O.
• Alice hasn’t signed any other state with turnNum greater than or equal to that of S.

Why is this? Because Alice knows that she could call launchChallenge with S, and no-one can counter-challenge, because they can’t possibly have a later fully-signed state, and so the outcome will finalize after the challenge period. If someone else were to pre-emptively launch a challenge with a state S' != S, then Alice knows that S'.turnNum < S.turnNum and she can therefore counter-challenge with S, after which no-one can counter-challenge, and the outcome will finalize after the challenge period. Either way, she can get the outcome to finalize on-chain.

What happens if Alice now signs a state S'' with outcome O'', where S''.turnNum = S.turnNum? Alice no-longer knows which of O or O' will finalize on-chain. By launching a challenge, she can ensure that one of those outcomes occurs, but she can’t control which one. In this case, we say that both of O and O' are enabled for Alice.

As a channel progresses, the ability to finalize an outcome is passed back and forth between the participants. When sending a new state to their opponent, a participant typically temporarily loses the ability to finalize a specific outcome, and their opponent gains that ability. This orderly transition of power is important. It is possible to end up in a ‘chanarchy’ situation where no participant has the ability to finalize any state, which normally means a race-to-the-chain situation, where the first outcome to be registered wins. When designing a state channel system, you should try to avoid these situations arising.

Instant withdrawals

One obvious shortcoming of the toy system is that the only way to finalize an outcome is to wait for the challenge period to expire. Because the outcome has to be finalized before funds can be withdrawn, this imposes a limit on how quickly funds can be withdrawn from the system. It seems like we should be able to do better than this - in the case where all participants agree on the outcome of the channel, it should be unnecessary to wait for the challenge period. It turns out that we can indeed do better, and in this section we extend the toy system to allow for instant withdrawals.

In order to enable instant withdrawals, we need to add the ability to explicitly mark a state as being a final state. We do this by adding a boolean isFinal property:

type State = {
  participants: Address[]
  channelNonce: Uint256
  turnNum: Uint256
  outcome: Outcome
  isFinal: Boolean
}

We also need to add an extra method, conclude, to the adjudicator.

type Adjudicator = {
  storage: (channelId: Bytes32) => ChannelStorage
  launchChallenge: (state: State, sigs: Signature[]) => void
  counterChallenge: (state: State, sigs: Signature[]) => void
+ conclude: (state: State, sigs: Signature[]) => void
}

This method will allow the challenge period to be bypassed if all participants sign an isFinal state:

The conclude method accepts a fully-signed, final state and causes the channelStorage to transition directly from Empty to Finalized. If there is a challenge in progress, conclude will also transition the state directly to Finalized. A fully-signed final state trumps everything.

How does this change the criteria for a state being finalizable? When we take final states into account, we reach the following criteria for an outcome to be finalizable:

• Alice holds a fully-signed final state, S, with outcome O, and hasn’t signed any other final states, or
• Alice holds a fully-signed final state, S, with outcome O, and hasn’t signed any final states, or any states with turnNum greater than or equal to that of S.

In practice this means that once any participant has signed a final state, it doesn’t make sense for them to sign any further states, and the channel is done. It’s easy to get into a chanarchy situation if you don’t follow this rule: for example, if two fully signed final states with different outcomes exist, then no participant has a finalizable outcome. It’s ok though, as if participants act in their own interests these situations will never arise, and if one participant decides not to, they only disadvantage themselves.

So we’ve taken our toy model, and modified it slightly to allow for instant withdrawals in the cooperative case. Neat!

What’s next?

In this post, we introduced the concept of a state channel system, defined by the state format, the on-chain channel storage, and the methods on the adjudicator. The system we introduced was only a toy system though, and didn’t have any meaningful state or rich state transitions. In the next post we’re going to be showing how to add genuine state channel behaviour, with state transition rules, and unilateral state advancement.

See you then!

Written by Tom Close, Magmo team lead @ Consensys R&D