Introducing Etherships – Using state channels to scale Ethereum games

August 7, 2018

What follows is a rather long post describing in detail why we decided to build Etherships, the problems we’ve ran into as well as the solutions that we came up with during this process. If you just want to play the game, feel free to visit game’s website straight away (you might also want some Kovan ETH for this, so our faucet could be helpful).

The problem

There’s a huge expansion of games powered by the Ethereum blockchain going on at the moment and, while the hype is definitely there the actual quality of the games and available solutions is still trying to catch up. One of the main reasons why blockchain gaming still hasn’t truly taken off definitely has to do with scaling issues.

Pretty much everyone in the community is aware of the Ethereum’s currently lacking scaling possibilities and that’s why the foundation team is focused on permanent solutions such as Sharding and Plasma. However, while these solutions are undoubtedly great, they aren’t here yet, so the questions stands – what can we do about it today? And as you may have guessed from the post title, we believe there is a lot of unused potential in state channels to alleviate some of the scaling issues. What state channels can provide is a way for peers to interact in a safe (guaranteed by blockchain security) and decentralized manner (no server involved) while massively reducing the stress on the Ethereum blockchain.

Etherships match interface

How exactly do state channels work?

Before getting into all the technical solutions used in Etherships, let’s do a short introduction to state channels and how they can help us. As already mentioned, the main idea is to minimize the number of necessary transactions and to settle things off-chain, making it possible to only use 2 transactions per game session – one to open and the other to close the channel. More transactions would be needed only in the case that one of the players attempts to cheat.

To better understand the whole deal, let’s try and explain it with an actual use case. One of the best use cases of state channels are payment channels, so here goes one example of exactly that.

Let’s assume that Alice hired Bob to do some work around the house for her. And there’s a lot of work to be done, so they created a list of 20 things – 20 stages of work to go through. As they go through the stages, Alice can pay Bob stage by stage, but the issue here is that they would have to do 20 transactions, meaning that they’ll be paying fees for each of them and unnecessarily congesting the network at the same time.

State channels to the rescue. Instead of doing it the old way, they can lock the funds for the whole job in a contract at the start and then upon completion of each stage Alice can send Bob a signed message releasing part of funds that has been assigned for that stage. You can think of this as sending checks, except Bob can claim his ETH immediately. Now, if it happens that at stage 15 Alice is no longer satisfied with Bob’s work, that’s fine, but she can’t undo any of the previous actions – Bob is still paid for the first 14 stages, but Alice can refuse paying for the remaining 6. This ends their interaction with only two transactions made.

This is a very simplified example of the state channels concept, but try imagining this core idea being applied in other ways, not only for certain amounts of money, but any pieces of data that can have a certain state.

The application potential is huge.

State channels and games

Since we like pushing the limits of blockchain technology with games (you may have come across Cryptage Origins already), we started thinking about applying state channels to enable complex player-vs-player gameplay. Having analyzed classic games like Chess, Tic-Tac-Toe, Go and Battleships, we realised that there are 2 types of games based on their outcome:

  • Score based games
  • Winner takes it all games

This categorisation is very important from a technical point of view, because score based games can be implemented using a basic payment-channel-like implementation, while the other kind of games that require a winner would need a different dispute method developed. So we picked one of the score based games to work on as a start.

Introducing Etherships

We decided to create something very similar to the classic game of Battleships as a Proof of Concept for our state channels solutions. Besides being easy to play and fun, it actually also imposed a few very interesting technical problems.

The rules of the game are pretty straightforward. The game is played on an 8×8 grid and each player places 5 ships at the positions of his choosing at the start. The game creator chooses the stake in ETH that both of the players put in and each of their ships is then worth a fifth of their stake (or one tenth of the entire pool). At the end of the game a player wins funds assigned to all their ships that survived in addition to those belonging to all the opponent’s ships they have destroyed.

For example, let’s say that our Alice and Bob decided against doing any work and sat down to play a game of Etherships instead. They set the stake at 0.05 ETH, so there was a total of 0.1 ETH in the game, making each of the ships worth 0.01 ETH. Bob came out victorious, sinking all 5 of Alice’s ships, with 2 of his ships surviving, too, meaning he’s got 0.07 ETH in the bag. Alice, on the other hand, hit 3 of Bob’s ships, winning the remaining 0.03 ETH. Good game, guys.

Back to state channels now. How exactly do they help us in this case? Well, we’re glad you asked.

We don’t want to send a transaction to the Ethereum blockchain every time a player makes a guess or sinks a ship during the game. This would be expensive and would make for a terrible user experience with constant MetaMask popups. With state channels, however, we can create a system where users keep signing the current score (the number of ships they hit) and, since both players sign the number of their opponent’s ships they sank as the game progresses, we can use the final signature sent to close the state channel and resolve the whole game even if one player quits.

Of course, things can get more complicated than that. We have checks in place (more on these below) to make sure that neither of the players is lying (e.g. saying that opponent didn’t hit a ship even though they did). In case it comes to that, the honest player can call the dispute method which would prove the opponent’s deceitfulness and name the honest player a complete winner, meaning the latter wins all of the ETH. Moreover, if your opponent is a bad loser and decides not to close a channel (make a move) on their end, you also have a timeout method on your side. If they don’t make a move for a certain amount of time (this is currently set to 60 blocks, which is around 6 minutes on the Kovan testnet), you can claim his stake in the game and walk away as the winner.

In summary, we created a system where players agree on the current state of the game off-chain, as they go along, while punishing the cheaters for any attempt to misuse the game.

All right, now let’s get to the geeky stuff on how this actually works.

The techy details

The first problem we ran into was right at the beginning of the game, when both players place their ships on the board, but have to keep those positions secret from each other. To overcome this, we used a so-called commit-reveal scheme, where each side has all their board’s squares hashed with a random number (nonce) and then sent to the other player. Now whenever a player makes a guess on a certain square, the opponent tells him whether it was hit or miss and reveals a secret nonce so that guesser can determine whether he is telling the truth. This solution is great for another reason: both the players have to submit their hashed boards when the channel is opened, which means that we also have all information needed for an on-chain dispute.

However, there is now a different kind of problem: storage on Ethereum is very expensive, with one memory slot costing 20,000 Gas. And here we are with each square of our hashed board taking 1 memory slot. Since the game has an 8×8 grid, this means that we would be using at least 64 memory slots and 64 slots x 20,000 Gas = too much gas.

Credit for the image goes to reddit user /u/PumpkinFeet

This is where the good old Merkle tree comes to the rescue. We don’t have to upload the whole board state any more, as we can take our hashed game board and create a Merkle tree from it. Once we have the Merkle tree ready, we just need to upload the root node to Ethereum and we can use Merkle proofs in our dispute method. This solution works well because when the game is in progress and your opponent tries to hit one of your ships, as a response to his action you send him a signed merkle path to that node, while also revealing the secret nonce. If the information the opponent sent your way doesn’t “fit” into the merkle tree you can call the dispute method where you send the invalidly signed merkle path as proof.

Therefore, if one player tries to cheat he will get punished by the opponent who will dispute the cheating move. Otherwise, if everything goes well, both players will close the channel in the end and the staked funds will get distributed according to the final score.

Ether.js and signing messages

Besides the challenges faced while building an efficient and bulletproof dispute resolution system, making a decentralized PvP game also means having to deal with peer-to-peer communication and players’ interaction with the smart contracts. Etherships is a web based game and as such it uses MetaMask to communicate with the Ethereum blockchain. While this works great, the problem we faced is that on each turn a player has to send 2 signatures – first, one for the current score and then the second for the merkle path. The way MetaMask works means that a player would be prompted about sending a signature on each and every turn, and that would be a rather poor user experience.

Our solution to this was to generate a new Ethereum account using the Ether.js library which will do all the signing in the background. Then when opening a channel the user specifies which signing address will be used. This way users still rely on MetaMask, which they are accustomed to, in order to open and close the channels, but another one-time address is generated for each game to handle the message signing.

P2P communication with WebRTC

In the spirit of decentralization we also decided not to use a server for communication between users and instead create a direct connection using the WebRTC protocol. WebRTC has been supported by all major browsers for more than a few years now and it seemed to fit the project great. Although, it’s not completely server-less and you still need a so called ICE/TURN server to connect the 2 users, but, after that, all communication is direct.

Moving forward

Etherships may be a simple game, but the idea, technology and solutions behind it are powerful. With the Proof of Concept successfully done, we now plan to extract and generalize relevant code in order to create a state channel framework designed specifically for building decentralized PvP games. This framework will act like a layer of abstraction that covers up all the complicated stuff we talked about above.

We see this as the first step to building an easy way for other creators to use this already known scaling solution in their (D)apps and push the adoption of Ethereum and open blockchains forward.

Etherships is a fully open source game, currently running on the Kovan testnet.

Play Etherships: https://etherships.co
GitHub repo: https://github.com/DecenterApps/MatchChannels/tree/master/etherships

Feel free to leave any comments below, we’d love to hear your thoughts!

Nenad Palinkašević

Makes software

Daniel Kraft says:

Very interesting – what you describe here is basically game channels (http://ledgerjournal.org/ojs/index.php/ledger/article/view/15). It’s great to see an actual implementation testing them out in practice!

What I believe is one of the main challenges is the timeout mechanism – namely how you prove that your opponent didn’t send a move in the 60 block window. (And, as part of this, that you *did* send your move to him 60 blocks ago.)

The best solution for this that I’m aware so far are “ephemeral timestamps” as described in https://medium.com/@XAYA/improved-game-channels-and-ephemeral-timestamps-e83c59810980. Unfortunately, you do not touch on exactly this aspect at all in your post (not even in the “techy details”). So how do you solve this with etherships?

Nenad Palinkašević says:

Hi we are aware of the timestamp problem, the way we solved it is that you don’t prove who left and if they left, the current score is signed and at any time you can resolve with that score.

So think of it as a payment channel where the score is in play, you have an online dispute if somebody is cheating or if they left you have a timeout method to close it.

Daniel Kraft says:

Ah ok, that makes sense (but as you write in the article, it only works if you have a score). Does that also mean that I can close and claim the win any time during a game as soon as I’m in the lead? Even if the other party is still around and doesn’t want to stop the game yet? That seems a bit unfair to me.

Nenad Palinkašević says:

You can close the game but you cannot claim the win, you can only claim that you hit X amount of ships if you have your opponent signature, so just like payment channels you can close it with your most recent signature.

We also keep an on chain “ranking” system where people who are involved in these kind of games which are closed early can have a “lesser ranking”. In short if you see that someone has played 5 games but 3 of those games where closed before a clear winner was chosen, you know that there is something going on with this player and you don’t play with him.

If the other player never closes the channel, you can close it after the TIMEOUT_PERIOD has ran out and get all the money in the channel.

If the other player is cheating (sending you a signed merkle path that doesn’t fit the tree you agreed on beforehand) you can call dispute().

If everything goes well both players close the channel and funds are distributed based on their scores.

Those are basically all the cases that can happen.

Daniel Kraft says:

Thanks for the detailed reply, very appreciated! What I mean is this situation:

Say that we both have made some turns and I currently destroyed two of your ships while you have not destroyed any of mine yet. Then you make a turn and destroy one of mine, but I’m still in the lead (2 : 1).

So instead of making my turn and finishing the game (which might mean that you turn the tide and win), I can just let the channel expire, right? You cannot do anything as it is my turn, and thus only I can send a move. But since the game is decided in the end based on the score, I know that I will win for sure after the timeout is over – unlike if I continued playing, where you might still win. So it seems that rational players would stop playing as soon as it is their turn again and they are in the lead.

Having a reputation system seems like a good first step to avoid that – but it is probably not a complete solution. (But please don’t get me wrong – I think it is fantastic what you have built. I’m just trying to understand how you solved the timeout situation and what limitations your solution has, as that is to me one of the most difficult parts.)

Nikola Klipa says:

Actually, if you are winning (2:1) you don’t have to wait nothing, you can just call method `closeChannel` and close it with 2 guessed ships, then other user will also close channel with 1 guessed ship, and then you will both get (numberOfGuesses / 10) * channelBalance, while the rest will be split equally, and you both will get unfinished game.

So yes, you will get 1/10 of channelBalance but you will lower your reputation. And in most cases it will be 1/10, because you won’t be willing to risk and see who will hit the ship next, and if you lead by two, you will probably just try to beat them and get and money and reputation.

Although we know its not a perfect solution, we are hoping that it will be good enough until we figure out something better. If you have any suggestions, feel free to contact us, we would love to hear it.

Daniel Kraft says:

Thanks again, that makes all sense. I agree that reputation is a good initial solution and might already work well in practice – so you should probably just see how it goes before considering further steps.

The solutions I have (so far just in theory, not implemented yet) are linked from my original reply. In the paper about game channels (see http://ledgerjournal.org/ojs/index.php/ledger/article/view/15 for full details), the proposed solution is that if your opponent does not reply, then you can post the current state with your last move to the blockchain without yet closing the channel. Then your opponent can either reply on-chain to resume the game, or you can claim the full prize money after the timeout as you can then prove that you sent your move but didn’t get a reply back.

This has of course the drawback that an attacker can routinely delay their move, force the opponent to post on-chain, and then resolve it again – which means that he can force the opponent to pay transaction fees repeatedly.

The solution we propose for this are ephemeral timestamps (see https://medium.com/@XAYA/improved-game-channels-and-ephemeral-timestamps-e83c59810980): They allow you to prove that your opponent knew about your move and still didn’t reply, in a way that does not cost transaction fees nor blockchain space; that way, if your opponent leaves the game and you have to post a claim on-chain, then you are already guaranteed to get the prize money (compensating for the fees you have) – a back-and-forth costing just fees is not possible anymore. However, this solution requires custom integration into the P2P network and blockchain – I’m not sure if it can be implemented (easily) on Ethereum.

Elie says:

Awesome piece