How to write a tic-tac-toe zkapp posted January 2022

(photo by @micheile)

Zkapps (formerly known as snapps) are zero-knowledge smart contracts that will launch on Mina this year. You can learn more about them here. This tutorial teaches you how to write a tic-tac-toe game using snarkyjs, the official library to write zkapps on Mina.

Set up

You can quickly create a project by using the Snapp CLI:

$ npm install -g snapp-cli
$ snapp project my-proj

you can also follow along this tutorial with the following command:

$ snapp example tictactoe

Hello world

To write a smart contract, import what you need from snarkyjs and simply extend the SmartContract class.

import {
  Field,
  State,
  PublicKey,
  SmartContract,
  state,
  method,
  PrivateKey,
  UInt64,
  Int64,
  Bool,
  Circuit,
  Mina,
  Party,
  shutdown,
  Optional,
  Signature,
} from 'snarkyjs';

class TicTacToe extends SmartContract {
    // your smart contract
}

A zero-knowledge smart contract, or zkapp, is very close in concept to the ones you see on Ethereum:

• it has a state
• it has a constructor that initializes the initial state when you deploy your zkapp
• and it has methods that can mutate the state

Let's start with the state.

A state for a tic-tac-toe

Zkapps, at the lowest level, only understand field elements, of type Field. Field is a type similar to Ethereum's u256 except that it is a bit smaller. Essentially it's a number between 0 and 28948022309329048855892746252171976963363056481941560715954676764349967630336. Every other type has to be derived from Field, and we provide a number of such helpful types in snarky. (You can also create your own types but we won't use that here.)

First, a tic-tac-toe game needs to track the state of the game. The board.

The state of a zkapp can only hold 8 field elements. This is not set in stone, but the more storage a zkapp can contain, and the harder it becomes to participate in consensus (and thus the less decentralized the network becomes). Zkapps that need to handle large state can do so via Merkle trees, but I won't be talking about that here.

A tic-tac-toe board is made of 9 tiles, that's one too many :( so what can we do about it? Well as I said, a field element is a pretty big number, so let's just encode our board into one:

class TicTacToe extends SmartContract {
  // The board is serialized as a single field element
  @state(Field) board: State<Field>;
}

We'll also need to keep track of who's turn is it, and if the game is finished (someone has won):

class TicTacToe extends SmartContract {
  // The board is serialized as a single field element
  @state(Field) board: State<Field>;
  // false -> player 1 | true -> player 2
  @state(Bool) nextPlayer: State<Bool>;
  // defaults to false, set to true when a player wins
  @state(Bool) gameDone: State<Bool>;

  // player 1's public key
  player1: PublicKey;
  // player 2's public key
  player2: PublicKey;
}

Notice that the public keys of the players are not decorated with @state. This is because we don't need to store that information on chain, we can simply hardcode it in the zkapp. If you wanted to be able to start a new game with new players, you would store these on chain so that you could mutate them via a method of the zkapp. But we're keeping it simple.

Also, PublicKey and Bool are two types provided by the standard library and built on top of Field. Bool is built on top of a single field element, so in total our on-chain state has 3 field elements. That'll work!

A constructor

Next, we must initialize that state in a constructor. let's look at the code:

class TicTacToe extends SmartContract {
  // The board is serialized as a single field element
  @state(Field) board: State<Field>;
  // false -> player 1 | true -> player 2
  @state(Bool) nextPlayer: State<Bool>;
  // defaults to false, set to true when a player wins
  @state(Bool) gameDone: State<Bool>;

  // player 1's public key
  player1: PublicKey;
  // player 2's public key
  player2: PublicKey;

  // initialization
  constructor(
    initialBalance: UInt64,
    address: PublicKey,
    player1: PublicKey,
    player2: PublicKey
  ) {
    super(address);
    this.balance.addInPlace(initialBalance);
    this.board = State.init(Field.zero);
    this.nextPlayer = State.init(new Bool(false)); // player 1 starts
    this.gameDone = State.init(new Bool(false));

    // set the public key of the players
    this.player1 = player1;
    this.player2 = player2;
  }
}

The constructor does two things that might look weird. First, it takes an address as argument, this is the address where the zkapp will be deployed (this might disappear in future versions of snarky). Second, the constructor takes an initialBalance, which might be needed to pay the account creation fee (if you haven't already). The rest should be pretty straight forward.

Adding methods to the zkapp

We really only need one method: a method to play. We can create one with the @method decorator:

class TicTacToe extends SmartContract {
  // ...

  @method async play(
    pubkey: PublicKey,
    signature: Signature,
    x: Field,
    y: Field
  ) {
        // ...
    }
}

The method takes the player's public key, two coordinates, and a signature (to make sure that they own the public key) over the coordinates.

The board can be visualized as such:

The logic, at a high-level

Let's look at the logic that we will have to implement:

class TicTacToe extends SmartContract {
  // ...

  @method async play(
    pubkey: PublicKey,
    signature: Signature,
    x: Field,
    y: Field
  ) {

    // 1. if the game is already finished, abort.

    // 2. ensure that we know the private key associated to the public key
    //    and that our public key is known to the zkapp

    // 3. Make sure that it's our turn,
    //    and set the state for the next player

    // 4. get and deserialize the board

    // 5. update the board (and the state) with our move

    // 6. did I just win? If so, update the state as well
  }

Does that make sense? In the rest of this tutorial I go over every step

Step 1: Game over is game over

if the game is already finished, abort.

To do this, we have to read the state of the zkapp with get. When you execute the program locally, this will go and fetch the state of the zkapp from the blockchain (hence the asynchronous call with await). Your execution will then only be deemed valid by the network if they see the same state (in this case the value of gameDone) on their side.

const finished = await this.gameDone.get();
finished.assertEquals(false);

Using assert functions like [assertEquals()] is the natural way to abort the program if it takes the wrong path. Under the hood, what happens is that the prover won't be able to satisfy the circuit and create a proof if the assert is triggered.

Step 2: Access control

ensure that we know the private key associated to the public key and that our public key is known to the zkapp

First, let's verify that the public key is one of the hardcoded key:

Bool
    .or(pubkey.equals(this.player1), pubkey.equals(this.player2))
    .assertEquals(true);

Next, let's verify that the player truly owns the private key associated with that public key by verifying a signature over the coordinates.

signature.verify(pubkey, [x, y]).assertEquals(true);

Step 3: taking turns

Make sure that it's our turn, and set the state for the next player

Earlier, we encoded a player as a boolean, with false describing the first player and true the second one. So let's derive this first. In zero-knowledge proofs, we can't have branches with too much logic. The program pretty much always has to do the same thing. That being said, what we can do is to assign a different value to a variable depending on a condition. For example, this is how we can get the boolean that describes us as a player:

// get player token
const player = Circuit.if(
    pubkey.equals(this.player1),
    new Bool(false),
    new Bool(true)
);

Circuit.if() takes three arguments, the first one is a condition that must be a Bool type, the other two are the returned values depending on if the condition is true or false.

Now that we have the player value, we can use it to check if it our turn:

// ensure its their turn
const nextPlayer = await this.nextPlayer.get();
nextPlayer.assertEquals(player);

And we can update the state for the next player via the set() function:

// set the next player
this.nextPlayer.set(player.not());

Step 4: fitting a board in a field element

get and deserialize the board

There's many strategies here, but a simple one is to deserialize the field element into bits (via toBits()) and interpret these bits as the board.

const serialized_board = await this.board.get();
const bits = serialized_board.toBits(9);

We can simply flatten the board like this:

Yet, this is not enough. A bit can only represent two states, and we have three: empty, false (player 1), true (player 2).

So we'll use two lists of size 9 instead:

• one to track who played on that tile
• and one to track if a tile is empty or not

As you can see, it is important to track if a tile is empty or not, because in the first list 0 represents both the empty tile and a move from the player 1.

const serialized_board = await this.board.get();
const bits = serialized_board.toBits(9 * 2);
const bits_not_empty = bits.slice(0, 9);
const bits_player = bits.slice(9, 18);
let board = [];
for (let i = 0; i < 3; i++) {
    let row = [];
    for (let j = 0; j < 3; j++) {
        const not_empty = bits_not_empty[i * 3 + j];
        const player = bits_player[i * 3 + j];
        row.push([not_empty, player]);
    }
    board.push(row);
}

To make the rest of the logic easier to read, I'm going to use the Optional type to encode the [not_empty, player] array. It looks like this:

class Optional<T> {
    isSome: Bool;
    value: T;
    // ...
}

It is simply a Bool that describes if it's empty (no one has played that tile yet), and if it's not empty the value associated with it (a cross or a circle, encoded as the player Bool). Here's what the full deserialization code looks like:

const serialized_board = await this.board.get();
const bits = serialized_board.toBits(9 * 2);
const bits_not_empty = bits.slice(0, 9);
const bits_player = bits.slice(9, 18);
let board = [];
for (let i = 0; i < 3; i++) {
    let row = [];
    for (let j = 0; j < 3; j++) {
        const not_empty = bits_not_empty[i * 3 + j];
        const player = bits_player[i * 3 + j];
        row.push(new Optional(not_empty, player));
    }
    board.push(row);
}

Step 5: Updating the board

update the board (and the state) with our move

Before we do anything, we need to check that the coordinates are valid:

x.equals(Field.zero)
    .or(x.equals(Field.one))
    .or(x.equals(new Field(2)))
    .assertEquals(true);
y.equals(Field.zero)
    .or(y.equals(Field.one))
    .or(y.equals(new Field(2)))
    .assertEquals(true);

Now here comes the trickiest part. Zero-knowledge smart contracts have some constraints: they don't allow you to dynamically index into an array, so you can't do this:

board[x][y].isSome = new Bool(true);
board[x][y].value = player;

instead, you have to go through every tile, and check if it's the one to update. (Note that you can't have dynamic for loops as well, they need to be of constant size).

for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
        // is this the cell the player wants to play?
        const to_update = Circuit.if(
            x.equals(new Field(i)).and(y.equals(new Field(j))),
            new Bool(true),
            new Bool(false)
        );
    }
}

And you can use the same tricks to make sure you can play on the tile, and to update the board:

for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
        // is this the cell the player wants to play?
        const to_update = Circuit.if(
            x.equals(new Field(i)).and(y.equals(new Field(j))),
            new Bool(true),
            new Bool(false)
        );

        // make sure we can play there
        Circuit.if(
            to_update,
            board[i][j].isSome,
            new Bool(false)
        ).assertEquals(false);

        // copy the board (or update)
        board[i][j] = Circuit.if(
            to_update,
            new Optional(new Bool(true), player),
            board[i][j]
        );
    }
}

Finally, we can serialize and store this update into the zkapp's state:

// serialize
let not_empty = [];
let player = [];
for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
        not_empty.push(this.board[i][j].isSome);
        player.push(this.board[i][j].value);
    }
}
const new_board = Field.ofBits(not_empty.concat(player));

// update state
this.board.set(new_board);

Step 6: Did I just win?

did I just win? If so, update the state as well

Finally, we can check if someone won by checking all rows, columns, and diagonals. This part is a bit tedious and boring, so here's the code:

let won = new Bool(false);

// check rows
for (let i = 0; i < 3; i++) {
    let row = this.board[i][0].isSome;
    row = row.and(this.board[i][1].isSome);
    row = row.and(this.board[i][2].isSome);
    row = row.and(this.board[i][0].value.equals(this.board[i][1].value));
    row = row.and(this.board[i][1].value.equals(this.board[i][2].value));
    won = won.or(row);
}

// check cols
for (let i = 0; i < 3; i++) {
    let col = this.board[0][i].isSome;
    col = col.and(this.board[1][i].isSome);
    col = col.and(this.board[2][i].isSome);
    col = col.and(this.board[0][i].value.equals(this.board[1][i].value));
    col = col.and(this.board[1][i].value.equals(this.board[2][i].value));
    won = won.or(col);
}

// check diagonals
let diag1 = this.board[0][0].isSome;
diag1 = diag1.and(this.board[1][1].isSome);
diag1 = diag1.and(this.board[2][2].isSome);
diag1 = diag1.and(this.board[0][0].value.equals(this.board[1][1].value));
diag1 = diag1.and(this.board[1][1].value.equals(this.board[2][2].value));
won = won.or(diag1);

let diag2 = this.board[0][2].isSome;
diag2 = diag2.and(this.board[1][1].isSome);
diag2 = diag2.and(this.board[0][2].isSome);
diag2 = diag2.and(this.board[0][2].value.equals(this.board[1][1].value));
diag2 = diag2.and(this.board[1][1].value.equals(this.board[2][0].value));
won = won.or(diag2);

// update the state
this.gameDone.set(won);

The full code is available here if you want to play with it.