Applied zero-knowledge (ZK) cryptography on Ethereum has advanced by leaps and bounds in the last eighteen months. New tools like iden3’s SnarkJS have for the first time enabled efficient, in-browser ZK proving and verification. These recent advancements in applied zkSNARK technology have allowed us to build Dark Forest: a fully decentralized and persistent RTS (real-time strategy) game.
The First Beta
Dark Forest is an MMO space-conquest game where players discover and conquer planets in an infinite, procedurally-generated, cryptographically-specified universe. While the final Dark Forest universe will eventually be persistent, the first editions of the game will be timeboxed, and beta universes will be refreshed regularly.
We are releasing the first beta edition of the game (Dark Forest v0.3) on Ethereum’s Ropsten test network on Friday 8/7/20; this edition will last one week. This beta will be whitelisted and semi-private, and includes only a limited featureset; future editions will follow quickly.
We have allocated a prize pool of 1024DAI for the winners of this first beta round. However, in the first beta round, planets and game assets will not have real economic value.
You can read more details here.
Dark Forest v0.3
Hidden Information Games and zkSNARKs
zkSNARKs are a powerful cryptographic tool that can be used to verify computations on secret data. A zero-knowledge proof used in a chess-like game might prove something like: “I’m moving my knight from secret location A to secret location B. I’m not going to tell you where locations A and B actually are, but this proof proves that the move from A to B is indeed a valid L-shape.”
To understand the implications that zkSNARKs may have for digital worlds, it’s important to understand the distinction between two types of games: complete and incomplete information games.
Complete information games are games where all players know the full state of the game universe. For example, checkers and chess are complete information games, since all players always know where all pieces are on the board. Similarly, CryptoKitties is a complete information game, because all players know who owns what kitty, and what the properties of each kitty are.
Incomplete information games (also known as “hidden information games”) are games where players may not know the full state of the world. For example, poker is an incomplete information game, since you don’t know the cards your opponent has in their hand. Strategy games like StarCraft and EVE Online also fall into this category. In StarCraft and other RTS games, information hiding is enforced through a “fog of war” - areas of the game map are obscured until they are explored by the player.
Incomplete information games allow players to explore a richer and more dramatic space of strategies. Information asymmetry enables things like deception, conditional coordination, complex social dynamics, and large-scale emergent player behavior. Because of this, nearly every popular MMO game is an incomplete information game.
Up until now, it has been nearly impossible to build incomplete information settings on decentralized systems (with a few very limited exceptions - see note). This is because the data layers of most decentralized systems are, by design, completely open and transparent. If the full game state is stored in a transparent data layer which anyone can inspect, there can be no notion of private information.
Zero-knowledge cryptography changes this. With zkSNARKs, players can keep private state while publicly submitting verifiably-valid actions. This allows us to build games like Dark Forest, which relies on a “cryptographic fog of war” secured with zkSNARKs.
Private state on a decentralized system, with ZK Proofs
Note: There are a few exceptions. One is commit-reveal games, where temporarily-private information is eventually made public. Such games are possible to implement in decentralized settings; these include games like poker. All cryptocurrencies also do have a very limited notion of private state built in, in the form of private keys. Note that public-key signature schemes are technically a zero-knowledge protocol.
A Cryptographic Fog of War
A core idea behind Dark Forest is the SNARK-secured cryptographic fog of war. In Dark Forest, players don’t submit the coordinates of planets they conquer to the core smart contract - rather, they submit commitments to their planet locations (by hashing the planet coordinates), along with zero-knowledge proofs that the hashes are valid. This keeps planet locations secret.
Similarly, when a player wants to make a move, they submit the hash of the planet they’re moving from and the hash they’re moving to, along with a zero-knowledge proof to prove that this constitutes a “valid” move.
Since hashes are hard to invert, inspecting the Dark Forest contract will tell you nothing about where other players actually are. The only way to find other players is simply to brute-force search. In Dark Forest, this means “hashing” regions of the game universe, looking for coordinates corresponding to an already-published hash. This construction introduces a fog of war that can only be uncovered by computation.
To give the world texture and other interesting properties, we compose a number of more complex zkSNARK “tricks” on top of this core idea. We’ll explore these tricks in future blog posts.
Acknowledgements
Dark Forest was inspired by Liu Cixin’s Three Body Trilogy (三体), particularly the second novel Dark Forest and a thought experiment by the same name.
For updates and announcements, subscribe to our blog or follow us on Twitter.
The seed of civilization has been planted. It will germinate and progress through the unpredictable world of Dark Forest. We invite you to log on in the future.