Ethereum State Channel Games - Part 1

In the first part of this state channel tutorial / demonstration, we’ll explore some simple use cases for turn based games like tic tac toe or chess.

I’ll skip the basics — if you don’t know what a state channel is or does, please read up about them before moving on.

Furthermore, this article aims to be a conceptual guide on implementing state channel, without much copy-paste code.

If you are looking for an easy-to-use state channel framework, I am shamelessly self promoting my OpenArcade game engine which comes with state channel support without requiring much effort from game developers.

State Definition

The first step is to define the state of our game. Take tic tac toe for example, our game state can look like this

struct GameState {
    address[9] board;
    uint next;
    address[] players;
}

In this state structure we defined,

• board: a flattened 3x3 cell array, with each element holding the address of the player who owns the cell. We use zero address on empty cells.
• next: the next player allowed to make a move, and is an index into the players array
• players: an array of participants.

Those 3 state variables are sufficient for a simple tic tac toe game to work. Now let’s define a very basic game interface (more state channel stuff to be added later):

function deposit() external payable;
function play(uint cell) external;
function withdraw() external;

In the game interface we defined:

• deposit: players call this function to deposit funds
• play: once all players have deposited funds, players call this function to select a cell to mark. Should fail if a move is invalid.
• withdraw: when the game is in terminal state, winning player can call this function to withdraw earnings.

State Serialization and Deserialization

Once we have defined our game state, we need to make it serializable and deserializable. Let’s define a Serializable interface:

function serialize() external view returns (bytes);
function deserialize(bytes data) internal;

• serialize: this function basically converts the game state to a stream of bytes. I’ll explain how it can be done shortly.
• deserialize: this function takes a bunch of bytes and sets the GameState we defined in the first step. Note that this function is internal, because it’s supposed to be called internally through a Fastforward process (more on that later). If we make it public or external, anyone can just change the state of the game, and that won’t be good.

In our case, we have a fixed-length array, an uint, and a dynamic-sized array. There’s many ways to serialize the state, but since we only have 1 dynamic element in the state, we can simply use packed ABI encode:

abi.encodePacked(board, next, players);

The layout of the output byte stream looks like this (assume there’s only 2 players)

[board[0], board[1], ... board[8], next, player[0], player[1]]

You can see that it’s basically all the arrays concatenated together. Also, note that every element is word-aligned (32 byte aligned). Even though addresses are only 20 bytes, they are padded to 32 bytes, with a bunch of zeros from the most significant bits.

Fun fact: if you just use ABI encode without packing, your output will be different in the last few words. This is because dynamic arrays are encoded differently when not packed. See my other article on Solidity ABI encoding if you are curious.

Deserialization is a little bit tricky, since Solidity doesn’t come with anything to slice or deal with raw bytes. I’ve written a library to manipulate byte arrays using inline assembly, but if you can certainly roll out your own solution if you want.

Anyway, here’s the pseudo-code to deserialize the state (or real code, if you use my solidity-bytesutil library)

// using BytesUtil for bytes;
require(data.length > 11); // 9 for cell, 1 next, 1+ players
uint[] ins = data.toUintArray(); // here i use my solidity-bytesutil
uint i = 0;
for (i = 0; i < 9; i++) {
    state.board[i] = ins[i]; // restore board
}
state.next = ins[9]; // restore next
uint playerCount = ins.length - 10;
for (i = 0; i < playerCount; i++) {
    state.players[i] = ins[10+i]; // restore players
}

State Signing and Recovery

The next thing we need to take care of is some client-side code to sign the state. We can either have the players sign the entire serialized state, which is a 12-word byte array for 2 players, or have the players sign the keccak256 hash of that byte array. It’s probably easier to sign the hash.

This can be easily done with Geth RPC sign web3.eth.sign, or if you have the private key, you can use ethereumjs-util.

Something along these lines…

// const eutil = require('ethereumjs-util')
const state = myGameContractInstance.serialize.call()
const stateHash = web3.sha3(hash, {encoding: 'hex'})
web3.eth.sign(aliceAddress, stateHash)

On the game contract side, EC signature recovery must be implemented. You can use ecrecover. Basically, when someone submits a state hash, and an EC signature to your contract, your contract must be able to verify that the signature is indeed from one of the players.

I’m not going to cover all the details here, you can read my other article about EC signing and recovery, along with some code samples.

Fastforward Consensus

Now our game contract can serialize and deserialize, and we have a way to sign the serialized state, as well as recovering signing address from signatures, we can implement state fast-forward. Simply put, state fast-forward is setting the state forward using a byte array serialized from a future version of the game contract. Of course, the state in question must be signed by all players to prevent cheating.

We define a Fastforwardable interface as just one function:

// ... contract Fastforwardable is Serializable ...
function requestFastforward(
        bytes state, bytes32[] rs, bytes32[] ss, uint8[] vs)
        external;

Note that a Fastforwardable contract must also be Serializable. Here’s how it works:

• The function should check that the state is a forward (future) state.
• The function should check that the hash of the state is signed by all the players.
• If the state in question has consensus among players, the function simply calls deserialize with the state, setting the state forward.

A very important detail here is: state should only be deserialized forward thought a fast-forward request — non-forward states should be rejected, even if signatures are all valid. You can implement this however you want, either by checking the number of empty cells, or adding an explicit turn number in the game state.

This is maybe the most important bit in this type of state channel implementation. We get to skip all the transactions calling play if we can simply fast-forward to the terminal state, which means the winning player can just withdraw from there.

Some Observations…

Now you may have noticed that I have not talked about the game logic at all. One observation is that, your play function may not get executed at all on-chain, because players simply play the game off-chain in state channel. If things go smooth, it will look like this, if Alice wins the game:

• Alice deposits into the game contract
• Bob deposits into the game contract
• Alice sends a TX to fastforward to terminal state with Alice’s and Bob’s signatures
• Alice withdraws her winnings

play doesn’t get executed at all, and you may be wondering why you even write play function in the first place… Because rules only have to be enforceable (or believed to be enforceable), and not actually to be enforced. You simply won’t cheat if you know you’ll be caught.

Timeouts

To make the state channel actually work, the contract must have some timeout mechanism, so when a player drops out or decides to cheat, the other player can fast-forward to the last consensus state and trigger a timeout. I’ll leave that in Part 2.

Client-Side Implementation

Also coming in Part 2, I’ll explain how to actually play the game on the client-side with JavaScript and Geth / TestRPC.

The basic gist is this: we can easily run the game in our local EVM (in TestRPC), with Alice and Bob’s inputs exchanged through a state channel (say a TCP connection between them). Alice would serialize the game state in her local EVM, sign the state, then send that signed state with her input to Bob. Then Bob executes Alice’s move in his EVM, serializes and signs the updated state, and send the signed state along with his move back to Alice.