Incomplete Information Games on Bitcoin
We show how to develop games with incomplete information on Bitcoin using Zero Knowledge Proof (ZKP), which is generally regarded unsuitable on a transparent blockchain. We use two games to exemplify the key processes.
Paradox
There are two categories of games:
- Complete information games. All players know everything about the game state. For example, in chess, both players know where all the pieces are.
- Incomplete information games. 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 regions of the game map are obscured until they are explored by the player. It makes a game more fun and attractive since it enables social dynamics and game-theoretical 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 game state transition to follow the rule of game and no player can cheat. For example, a poker player cannot use cards he does not possess or use a card twice. A blockchain is ideal for this since both data and computation on it is publicly verifiable and auditable.
- On the other hand, we need to keep parts of the state private to each user. But a blockchain is open and transparent by nature.
ZKP comes to the rescue
ZKP provides a resolution to this apparent paradox. Game state transition is a computation. 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 such as zk-SNARKs, it opens doors for all kinds of games of incomplete information to be built atop, which were deemed impossible before.
Why not just commit and reveal?
In a commit-reveal scheme, game information is hashed and temporarily hidden, and eventually made public at the end of the game. It does not work for many games, because:
- In games such as Battleship or Mastermind, one player makes multiple moves in one round and each move depends on the mid-game states. It does not suffice to only know the final state when the game ends.
- In other games, information can be indefinitely concealed. For example, a poker player can choose to fold hand and not show his cards.
Battleship
Battleship is a classic guessing game for two players. It is played on a grid on which each player’s fleet of warships are anchored. There are two steps:
- Placement: each player places 5 ships on a 10x10 grid. Each ship is a rectangle of width 1 and variable length. It is imperative the locations of the fleets are concealed from the opponent.
- Shooting: players take turns guessing a coordinate on the grid. Their opponent then tells them if that coordinate contains a ship. If yes, it is a “hit”, otherwise it is a “miss”.
A ship is sunk if all its squares have been hit. A player wins if he sinks all of his opponent’s ships.
In an offline setting, two players sit opposite to each other and they cannot see each other’s fleet. To simulate the hiding digitally on Bitcoin, each player hashes his fleet’s location and commit 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 disclosing 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 on-chain, based on the second novel of the same name from the Three Body Trilogy. In this space conquest game, players can develop planets, build fleets, and conquer other planets in the universe.
What makes it more fun than traditional blockchain games such as CryptoKitties is that each player has knowledge of his 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 follow game rules without sharing information about the moves to 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 instant, it is an ideal platform to build such games. We will release more examples and toolings to facilitate zero-knowledge application development on Bitcoin.
References
https://hackernoon.com/zero-knowledge-proofs-adventures-in-the-dark-forest-jij3xyn
