State channels with state assertions

tl;dr In the worst case scenario state channel applications need to be played out fully on-chain at high cost. We can leverage ideas from optimistic contracts to reduce the cost of this worst case scenario. The full paper is available here and the code can be found here.

Optmistic contracts

A smart contract is a state machine. Given input data, it will transition to another state computed by the contract’s application logic. The problem with smart contracts is that performing computation on the blockchain is expensive.

A smart contract transitioning to new states. Input is provided as part of a transaction (green arrow) and transitions to a new state via the smart contract application logic (blue arrow and cog)

Optimistic contracts are smart contracts that accept the result of a state transition, rather than computing it themselves. An optimistic contract differs in that it accepts input data and an assertion of what the next computed state would be. It then transitions the state by simply updating it to the asserted one instead of computing it with contract logic. The pro here is that the potentially expensive on-chain logic need not be performed, the con is that it’s now not possible for the contract to be sure that the asserted state is a valid, i.e. if the provided input were used to compute the next state, would it be equal to the asserted one?

The idea behind optimistic contracts is to add a challenge period giving time for other parties to run the computation locally to check if the optimistic update is correct. If it isn’t then anyone can notify the contract to challenge the new state and execute it directly on-chain. Given that this process is expensive, and should be discouraged, parties wishing to submit state updates to an optimistic contract are also required to supply a deposit. If the update is later proved to be invalid then the deposit is forfeit.

An optimistic contract transitioning to new states. Input (green arrow) is used to directly transition to a new state (red arrow). Application logic is available to be used by other participant to prove that the state update is invalid and if needs be transition back to a previous state (blue dashed arrow).

Optimistic contracts optimistically accept a state and only discard if it is proved wrong, whereas a normal smart contract will not accept a new state unless it is proved correct.

So, given the caveat that other participants need to be able to verify state submissions and be available to trigger the contract into disproving false states, optimistic contracts can allow state transitions to occur whilst avoiding costly application logic.

One downside to this technique is that it trades time for gas cost. Participants are required to wait until a timeout is reached before an update can be considered final.

State channels

State channels allow a set of known, cooperating parties to execute a smart contract amongst themselves, without relying on the blockchain to process every transaction. Given that state updates don’t occur on-chain they don’t suffer from the high gas costs, and low latency of on-chain transactions, and can thus scale to much higher throughputs.

However, state channels rely on the blockchain for safety and liveness. If cooperation between the channel participants should break down, parties have the option to use the blockchain to force correct continuation of the smart contract running inside the channel. This article describes how in the worst case scenario this can result in all the state updates for that smart contract being run on-chain, an expensive and slow process.

State channels with state assertions

So state channels are potentially expensive, and optimistic contracts are potentially slow. But state channels applications have some properties that make them ideal candidates for optimistic contracts. And in fact they can remove the optimistic contract caveat that participants need to wait for a timeout for considering a state final.

First, participants are already assumed to be online in state channel protocols so they will be available to validate the optimistically submitted states.

Second, the set of participants is known and to avoid race conditions they are often ascribed turns. These properties make it easy to reason about when an optimistic state can be considered final since if a party takes their turn and uses it to submit a new optimistic state instead of using it trigger a verification computation on the previous state, the contract can safely assume that this participant considers the previous state to be final. When all participants have considered a state to be final, then the contract can accept it as such, releasing the deposit provided by the state submitter. In a two-person channel this happens as soon as the counterparty takes a turn. Or n turns in a n-party state channel that proceeds round robin. Parties now don’t need to wait for a timeout to consider a state final, they just have to wait for all other parties to take their turn — something that in a state channel they were going to do anyway.

We recently wrote a short paper describing this technique, we called it “state assertions” since future states are asserted rather than computed. Parties assert new states, whilst all other channel participants check and validate them before deciding whether to challenge or continue.

A page taken from Pierre-Henry Gomont’s comicbook adaptation of Antionio Tabucchi’s “Pereira Maintains”. State assertions are constantly being questioned and checked, like the eponymous character in “Pereira Maintains” who is questioned and judged by himself and everyone else.

We measured the cost of a state assertion to be approximately 40n+60,000 gas, where n is the number of bytes supplied as input to the update. This means that the worst case cost in a state channel is now a function of the number of turns the application requires, and to a small extent the input required at each of those turns. The worst case gas cost is now independent of the computational complexity of the application. State assertions also only require a hash of the future state to be submitted, which is why the assertion gas cost also independent of state size.

A cautionary note…

One thing to note is that state channel participants are assumed to be online as they need to check that stale state is not provided to the channel contract. If this were the case the channel could potentially close with an old state. With the mechanism described above, if a party is offline, it is now possible for a malicious counterparty to assert a state that is an invalid transition which if accepted could allow the channel to finalise in a new state that the party never agreed to and could not be validly transitioned to. This is a danger associated with all optimistic contracts, and provides further reason for channel participants to stay online.

Thanks to Jeff Coleman for his feedback and for an interesting conversation regarding combining state channels with optimistic contracts.