Incomplete Information Game on Bitcoin: Solving Blockchain Privacy Dilemma Using Zero Knowledge

This post was first published on Medium.

We show how to develop games with incomplete information about Bitcoin using Zero Knowledge Proof (ZKP), which is generally considered unsuitable on a transparent blockchain. We use two games to exemplify the key processes.

Paradox

There are two categories of games:

1. Complete information game. All players know everything about the game state. For example, in chess, both players know where all the pieces are.
2. Incomplete information game. Poker is such a game, because you don’t know what cards your opponent has.

Most massively multiplayer online (MMO) games fall into the latter category, such as Starcraft, Minecraft and World of Warcraft. A “fog of war” hides information, where areas of the game map are hidden until explored by the player. It makes a game more fun and attractive since it enables social dynamics and game-theoretic strategies such as bluffing, deception, coordination and decision-making based on incomplete information.

It seems paradoxical to build incomplete information games on blockchains like Bitcoin:

• On the one hand, we want the transition to the game state to follow the game rules and no player can cheat. For example, a poker player cannot use cards he does not have or use a card twice. A blockchain is ideal for this as both data and calculations on it are publicly verifiable and auditable.
• On the other hand, we need to keep parts of the state private for each user. But blockchain is open and transparent by nature.

ZKP comes to the rescue

ZKP provides a solution to this apparent paradox. Game state transition is a calculation. ZKP allows the blockchain to verify the result of the computation on private state, while keeping it confidential off-chain. More specifically, because Bitcoin supports ZKP as zk-SNARKs, it opens doors for all kinds of games with incomplete information to be built on top, which were previously considered impossible.

Why not just commit and disclose?

In a commit-reveal scheme, game information is hashed and temporarily hidden, and finally disclosed at the end of the game. It doesn’t work for many games, because:

1. In games like Battleship or Mastermind, one player makes several moves in a round, and each move depends on the conditions in the middle of the game. It is not enough to simply know the final state when the game ends.
2. In other games, information can be hidden indefinitely. For example, a poker player may choose to fold their hand and not show their cards.

Battleship

Battleship is a classic guessing game for two players. It is played on a grid where each player’s fleet of warships is anchored. There are two steps:

1. Placement: each player places 5 ships on a 10×10 grid. Each ship is a rectangle with width 1 and variable length. It is important that the fleet’s location is hidden from the opponent.
2. Shooting: players take turns guessing a coordinate on the grid. Their opponent then tells them if that coordinate contains a ship. If yes, it’s a “hit”, otherwise it’s a “miss”.

A ship is sunk if all squares are hit. A player wins if he sinks all of his opponent’s ships.

Battleship

In an offline setting, two players sit across from each other and cannot see each other’s fleet. To simulate hiding digitally on Bitcoin, each player hashes the fleet’s location and commits it to a smart contract.

Using zk-SNARKs, each player can submit a proof to the smart contract whether the other player’s guessed coordinate is a hit or miss, against the public hash without revealing his fleet. The smart contract verifies the proof and updates the global game state only if the proof is valid.

Dark forest

Dark Forest is the first MMO real-time strategy game in the chain, based on the second novel of the same name from the Three Body Trilogy. In this Roman conquest game, players can develop planets, build fleets and conquer other planets in the universe.

Dark Forest UI

What makes it more fun than traditional blockchain games like CryptoKitties is that each player has knowledge of their own game state, but not the game state of other players as they are hidden by the fog of war.

To achieve this, each player commits the hash of their location to the blockchain, as in Battleship. It uses zk-SNARK to enforce a player’s moves and follow the rules of the game without sharing information about the moves of other players. For example, when a player chooses a home planet, it must be within the boundary of the known universe.

Summary

Games with incomplete information can be developed on Bitcoin today, since we have implemented zk-SNARKs on it. Because smart contract transactions on Bitcoin are cheap and instantaneous, it is an ideal platform for building such games. We will be releasing more examples and tools to facilitate zero-knowledge application development on Bitcoin.

References:

See: BSV Global Blockchain Convention presentation, Scaling Games at Layer One: Why It Matters

New to Bitcoin? Check out CoinGeeks Bitcoin for beginners section, the ultimate resource guide for learning more about Bitcoin – originally envisioned by Satoshi Nakamoto – and blockchain.