You sank my battleship!

A case study to evaluate state channels as a scaling solution for cryptocurrencies

tldr; a copy of the paper and project github

Cryptocurrencies do not scale. At the heart of public blockchains is a fundamental scaling dilemma between the network’s public verifiability and the affordability of transactions.

It is true that by changing the underlying the blockchain protocol or by introducing sharding, the network can strictly increase its throughput (i.e. 5k tps). However this reduces the set of peers with the computational, storage and bandwidth capacity to verify every transaction on the network. This raises the question whether it is worth sacrificing the set of users who can verify every transaction in order to increase the set of users who can afford to use the network?

Thankfully this post does not seek to answer the above question. But the scaling dilemma has motivated us to explore an alternative scaling approach for the past two years called Layer-2 (or off-chain). This approach promises to reduce the number of transactions processed by the global network by letting a group of parties transact amongst themselves instead of sending every transaction to the public blockchain. Two proposals for off-chain solutions include non-custodial sidechains and channels.

State Channels

We focus on state channels. A channel lets n parties, via unanimous consent, to agree new states of an application without publishing the new state to the public blockchain. It promises instant finality of transactions after all parties have agreed and no transaction fees as there is no central operator to reward. Crucially, every online party is protected against a full collusion of all other parties in the channel. If one party does not cooperate, then the underlying blockchain guarantees safety as each party gets the coins they deserve and liveness of the application to ensure it will always progress.

In the past, we proposed one of the first state channel construction with Sprites that could be adopted for most applications and the first accountable third party with Pisa to help alleviate the pesky always online assumption. At the same time, there are several teams world-wide publishing and deploying state channels including Perun, Counterfactual, CelerNetwork, Funfair, Spankchain, Magmo etc. Back in June 2018, many of the teams came together at the Master Workshop to showcase their protocols, implementations and vision for scaling cryptocurrencies via state channels.

I (Patrick McCorry) was simply amazed at how far state channels have come along. It is exciting to see real-world deployment of state channels and several subtly different state channel constructions. However I also realised the state channel constructions were often intertwined with the application and the real-world implementations were very bespoke in nature. This led me to ask the following questions:

• Can PISA benefit from the subtle difference in the state channel constructions from Perun/Counterfactual?
• What are the minimal modifications required to deploy an application as a state channel?
• What applications actually make sense in a state channel?

The above questions has led to our new research paper to further understand the capabilities of state channels as a scaling solution for cryptocurrencies. I’ll explore the above questions one by one.

Kitsune: An Application-Agnostic State Channel

One contribution of PISA was a new application-agnostic state channel contract that can be re-used for any application. This is required to help scale the services of an accountable third party to ensure a Pisa Tower is only required to verify the state channel contract’s bytecode before accepting a job instead of verifying the bytecode for every application. During the workshop (and after some discussions), I realised the dispute process for Perun/Counterfactual was slightly different to the dispute process in Pisa.

Briefly, the dispute process for Perun/Counterfactual lets the state channel decide the final authorised state before closing the channel. The application can be deployed with the final state and its progression can continue via the blockchain. Whereas for PISA, the dispute process focused on keeping the channel open, retrieving a list of commands from all parties, and self-enforcing the state transition. The former is useful for applications with a lot of transactions, whereas the latter is useful if a side-effect is required (i.e. to withdraw coins).

The above realisation led to our new state channel construction Kitsune. It lets parties turn off the channel and continue an application’s execution via the blockchain, but the state channel contract itself is application-agnostic. I created a code example back in July 2018 and I privately discussed the state channel construction with the other teams during the workshop. I’m glad to see the application-agnostic approach is being adopted by others.

Minimal Modifications Required to Deploy an Application as a State Channel

At the IC3-ETH bootcamp this year, I (Patrick McCorry) and Surya Bakshi proposed to build a battleship game within a state channel. We chose battleship for two reasons:

1. Andrew thought it’d be cooler than a pokemon-style game
2. It is a fantastic example of an application that is not reasonable to play via the blockchain, but should work in a state channel.

The team members consisted of Surya Bakshi, Karl Wüst, Frank Sauer, Matthew Salazar, Oded Noar, and Deepak Maram. All team members had a crash-course on layer-2 and state channels before getting to work on designing the battleship game and how it can fit with the application-agnostic state channel construction. While the team won third prize at the bootcamp, the primary challenge was designing the battleship game to minimise on-chain storage and execution as opposed to adopting it for deployment within a state channel.

Myself (Patrick McCorry), Chris Buckland, Surya Bakshi, Karl Wüst and Andrew Miller continued the challenge of building a proof of concept battleship game within a state channel [github] after the bootcamp. In this work, we proposed a simple life-cycle for deployment on how to lock the application, deploy the state channel contract, conclude the final game state and re-activate the application. The details can be found in our paper, but what is more interesting to explore in this post are some of the empirical evaluation observations we encountered in the case study.

Empirical Evaluation Observations and Future Work

Funfair Dilemma. During the workshop, Funfair and Counterfactual debated about an interesting chicken-and-egg problem:

Should state channels be able to create and destroy applications off-chain, or should a state channel first require an application to already exist on the blockchain?

Fundamentally, this question alludes to the financial cost of the dispute process to support re-deploying the application, setting the full state and continuing its execution via the blockchain. Our experiment highlights that it costs approximately $10.87 to deploy the battleship contract and $1.56 to complete the dispute process (i.e. store full game state and reactivate the contract). While the cost of deploying the battleship contract could be reduced using special opcodes in Ethereum, this isn’t actually the most critical metric to consider when designing an application for a state channel.

We discovered the greatest pain point was actually the case where the channel is closed and both players must complete the application’s execution via the blockchain. For battleship, it costs between $16.27-$24.05 and up to 200 transactions per player to finish a single game. Even worse, it may take up to several hours (i.e. up to 5 minutes per move and 200 transactions is approximately 16 hours) to complete the game due to the blockchain’s latency. Both the financial cost and time to complete can easily be leveraged by an attacker (i.e. an automated bot) to force human players to give up playing the game.

Hare and Tortoise Protocols. The above pain point highlights that deploying applications within a state channel is in fact very similar to tortoise and hare protocols.

The state channel is a hare. It is fast (i.e. both parties cooperate, the battleship game is free/instant finality) and agile (i.e. create/destroy apps at any time). But hares are also fragile, and it simply breaks down if one party aborts for whatever reason.

The blockchain is a tortoise. It is slow (i.e. battleship takes several hours to complete) and expensive (i.e. battleship costs $16.27-$24.05). But it is very reliable and guarantees that parties can finish the application if they can afford it and they are patient.

The future task for teams working on state channels is to understand how incentives can be aligned to ensure the hare doesn’t break down. Incentives are notoriously tricky to get right as demonstrated by Gas token. At Financial Cryptography 2017 Silvio Micali summed up it up quite well with (paraphrased): “designing incentives is like a lion chasing a dog, a dog chasing a cat and a cat chasing a mouse”.

Applicable Applications

We observe two restrictions for applications within a state channel.

Difficulties with unanimous consent. A state channel requires all parties to remain online throughout an application’s entire execution. If one party aborts, then the channel breaks down. This implies that state channels are only suitable for a small number of parties to reduce the risk of aborts.

Unreasonable to execute. Our experiment highlights the pain point for resolving disputes in a state channel is completing the application’s execution. Unless incentives can be aligned to prevent one party from closing the channel (remains an open problem today), then state channels may not be suitable for applications which are typically considered unreasonable to execute via the blockchain.

Today, state channels appear useful for applications with a small set of parties, applications with a small number of rounds per party, and the parties will want to repeat the application’s execution more than once. Some applications in this direction include payments, boardroom voting, auctions and casino games.

In the Spirit of Open-Source

We received funding from the community (Ethereum Foundation and Ethereum Community Fund) to support the research/implementation of state channels. In the spirit of this funding (and the open-source community), we kept our experiment open-source while it was in progress and we presented whenever possible about our on-going results. To complete this transparency, we have decided to make the github repository for our paper public as well.

Hopefully by making the experiment and paper-writing open source, it will serve as a useful reference to new PhD students and the wider-community about how ideas change when a person is forced to write it down/when new evidence becomes available. After all, papers are about adding to the wider-discussion and not about being “right”.