Zero-Knowledge Proofs: Adventures in the Dark Forest

An RTS game on Ethereum… WHAT?! That's possible?!

That’s exactly what the Dark Forest, an innovative blockchain game named after Liu Cixin’s eponymous second novel of the Remembrance of Earth’s Past trilogy, is. In fact, it is the first real-time strategy game running on Ethereum in existence.

Lucky for me, I recently had the chance to play the beta of this strange game and learn more about how it accomplished such a feat.

And I found it fascinating.

Though understandably bare-bones in gameplay features due to its beta status, Dark Forest must be the first time I can honestly call an Ethereum game fun, and this fun is made possible thanks to its interesting use of zero-knowledge proofs.

Let’s see what makes Dark Forest so special. It will teach us something about Zero-Knowledge proofs in the process.

Oh, and don't worry, this article won't contain any crazy mathematics. 😉

What You Don’t Know Can’t Kill You

Day 1 in the Dark Forest

My eyes scan a little planet called Bear Harm.

Home.

From this small corner of the universe, I will build a great empire.

I drag my mouse from Bear Harm to the neighbouring planet of Cure Dock. Metamask pops up in my browser to confirm the Ethereum transaction.

Like a small ant my fledgling fleet crosses the stars towards Cure Dock.

And that's how it starts:

an adventure in the Dark Forest!

To understand what makes Dark Forest so appealing, we must first understand what kind of game it is.

Games can be categorized in two main groups.

First, we have games in which the players know everything about the game state. For example, in chess, both players know where all the pieces are. Each player has the same amount of game state knowledge as his opponent. Winning or losing depends on the computational ability of the player to calculate all the possibilities. There is no bluffing, no making decisions based on incomplete information, no wondering what the opponent is doing.

The second type of game is one in which players have incomplete knowledge of the game state. Think of the very popular (at least it used to be) real-time strategy game Starcraft. Players control units and build bases in a game map obscured by a fog of war. The fog of war is a large part of what makes that game fun since it hides each player from the other unless and keeps them guessing.

The players don’t know what lies ahead. Their minds are always on high alert as they wonder: “Where is my opponent? What is he doing? What is he building? What does he thinks I’m doing?”

This creates complexity. Tension.

FUN.

But what about blockchain games? Most of them fall into the first category. Users know everything about the game state.

And that’s understandable.

After all, Ethereum is a public blockchain and all its data is available to anybody. It is therefore very difficult to hide information. For that reason, games on Ethereum lack surprises and have a tendency to be limited to the trading of non-fungible collectibles such as playing cards.

Until Dark Forest, that is.

How Dark Forest uses Zero-Knowledge Proofs

Day 2 in the Dark Forest.

I grabbed yet another planet. This one produces a large amount of silver which I can spend to further expand my empire and its reach.

And I am always in need of more planets.

I can only think of what lies ahead, what treasure lies under the fog of war.

I wait. The fog wafts away pixel by pixel, revealing planets ripe for conquest.

There. I see a big one!

And as the edge of the fog further expands, my heart sinks.

That planet belongs to another player.

And he leads a massive fleet.

If only I had known, I would never have ventured there.

The big innovation that Dark Forest brings to the table is providing a fog of war on Ethereum.

You do not know what your opponents are doing at all time. You do not even know where they are or how strong they are.

The fog of war hides them.

How Dark Forest manages to do that is through use of zero-knowledge proofs. Now, this subject can be quite deep and heavy on the math, but the concept itself is very simple.

In short, zero-knowledge proofs allows a verifier to perform a verification that a certain computation has been performed honestly without performing the computation himself.

That’s it.

In the case of Dark Forest, users submit proofs of actions they did to the blockchain. They do not have to disclose their location or amount of resources. They simply need to perform an action that respects the rules of the game and submit their proof.

This allows each player to have knowledge of his own game state, but not the game state of other players if they are hidden by the fog of war.

In other words, players make public proofs and their private game states, thus allowing each player to stay hidden behind a fog of war.

And THAT is what makes the game fun.

Yet, during the seven days of the Dark Forest beta, there was a tiny little problem...

In the span of only seven days, players made over 140,000 Ethereum transactions, burning over 7,000 ether equivalent to more than 3,000,000 USD based on the price at the time.

Luckily, no blockchain - nor any user's wallet for that matter - was harmed in the making of this article. Since the beta occurred on the Ropsten Testnet and not on Mainnet, valueless testnet Ether was the only casualty of war.

But the incident highlighted an important problem with Ethereum: How can the network support such frenetic activity, when Dark Forest is just one of its many applications?

And in this matter, zero-knowledge proofs provide the answer yet again.

Not Just For Fun and Games…

“The universe is a dark forest." -Cixin Liu, The Dark Forest

Do not make the mistake of thinking that zero-knowledge proofs are only for creating blockchain games.

They are capable of much, much more: they could be the key to scale Ethereum to millions of users.

In effect, zero-knowledge proofs make it possible to verify that arbitrarily complex computations have been performed without performing them ourselves. As such, ZK proofs allow for the fast verification that many, many transactions have been been correctly processed in a relatively time and space efficient manner.

Projects such as Loopring, for example, leverage the power of ZK Rollups, an innovative scaling solution based on ZK proofs, to process even more transactions on Ethereum, by a factor of 1000x of what is possible on-chain.

It's easy to see why zero-knowledge is at the forefront of Ethereum scaling research and also why Vitalik Buterin himself loves it so much. The best part? ZK-based solutions do not depend on the eventual rolling out of Eth 2.0. They can be implemented today.

Furthermore, as gas fees on Ethereum continue to rise ever higher, ZK-based solutions could alleviate the fiscal burden faced by Ethereum users. In effect, if 1000 transactions can be batched together privately and sent publicly to the blockchain as a single transaction, the users would need to pay only 1/1000 of the fee they would normally pay. What a better user experience!

Yet, zero-knowledge is also at the core of another important facet of blockchain research: private transactions.

Zcash is a great example of this. The protocol masks transactions thanks to zero-knowledge proofs. While Zcash is its own blockchain separate of Ethereum, the same principles apply to create private transactions on Ethereum.

These lessons in private transaction-making were harnessed by Ernst & Young in the making Nightfall, an Ethereum-based technology for private transactions.

Yes, zero-knowledge proofs are THAT cool and it is in no small measure due to their use in Ethereum scaling and private transactions.

The Proof is in the Pudding

Last day in the Dark Forest

After much needless bloodshed with my neighbouring opponent, our relationship has settled in a sort of tense cold war 2.0.

Neither of use dares remove our fleets which we defensively parked on the mutual border of our empires.

Aside from a few skirmishes here and there, we both understand that full-scale conflict would means only M.A.D. (Mutual Assured Destruction)

Yet, I did not sit by passively.

I aggressively upgraded my planets, optimised my transport routes for ferrying silver and braved the fog of war in search of better planets.

With only a few hours left before the end of the Dark Forest beta, I see my rank rising in the leaderboard.

And I smile.

It has now surpassed my nemesis' rank.

I have finally won.

Zk proofs are a fascinating concept that can be as deep as you want it to be. Anyone interested in blockchain should learn about it and know about their possible applications.

After all, the proof is in the pudding. Not only are ZK proofs instrumental in creating the very first Ethereum RTS game, but they are also at the core of Ethereum scaling and private transactions.

Zero-knowledge creeps on you with amazing ideas and streams of possibilities.

Just don’t get lost in the dark forest as you explore its intricacies.

Previously published at https://codeclimbing.com/zero-knowledge-proofs-adventures-in-the-dark-forest/