ZK proofs are crazy.

I've never even attempted to understand them before, but today I'm feeling frisky so I'll give it a whirl. I always just assumed that this math-ninja magic was far too complicated and beyond my depth, but then again everything in crypto is complicated and convoluted until you take the time to understand it; then it becomes a simple fact of life. Learning is a progression.

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

A protocol implementing zero-knowledge proofs of knowledge must necessarily require interactive input from the verifier. This interactive input is usually in the form of one or more challenges such that the responses from the prover will convince the verifier if and only if the statement is true

Yeah, okay... that's all well and good...

But how does one actually accomplish this? Reading it and saying it out loud just sounds like nonsense impossibility within so many contexts.

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.

They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.

However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would become very small (1 in 220, or very roughly 1 in a million).

Hm... interesting!

So the entire basis of zero-knowledge proofs are founded on guessing and chance. You'll never 100% know for sure if the verifier is telling the truth, but the more tests you run and the more questions get asked and answered, the higher the chance that the verifier is telling the truth.

This makes a lot of sense within the context of crypto, because public/private key security work in exactly the same way. There are more possible Bitcoin keys than atoms in the universe. Brute-forcing a solution is not an option. In this sense, ZK proofs are very similar to cryptography in general given that we can never be 100% sure the system hasn't been breached, but we can be 99.999999999999999999999999999999999% sure.

It is quite interesting that this is how it works, and to be honest I actually assumed it would be a lot more complex. Of course this is just a generic description of what is happening in the background, so it actually is a lot more complex in the field depending on the goals of the proof and how they are specifically implemented. But honestly this description is enough knowledge to finish out the rest of my post and bring up the real issue I wanted to discus.

FOG OF WAR

One of the first companies ever to introduce the fog-of-war to real-time-strategy games was Blizzard Entertainment and the Warcraft series (Warcraft 1/2/3). I have a lot of experience in this department because I used to be a huge Blizzard stan. Of course when they got bought out by Activision that was pretty much the nail in the coffin for me, but this is another story.

One of the first games I ever bought with my own money was Warcraft 1. Maybe it was the very first, as I can't remember one before this. It was standing on the shelf next Warcraft 2 in full front-and-center display. The first game was $30 and Warcraft 2 was $50, so like the stingy fuck that I am I picked the cheaper option to see if I would like the game. This must have been in 1995 putting me around 11-12 years old in middle-school. This was also back in the days that all games were separated by PC vs MAC. Nothing was interoperable. Wild times!

Warcraft 1 is a very hard game.

The single player is challenging and the win conditions are downright terrible UX (kill every single unit on the map), but it was still pretty fun. I tried replaying it a couple years back and I was like wow I just can't do this lol. It's simply too archaic and dated for RTS standards (the original RTS). Maybe some other year.

In any case when I bought the second game I was like wow that was way more than worth the extra $20. You get what you pay for amirite? Warcraft 2 had made massive improvements over the first iteration, as is the standard with video games (at least it was back then). One of those improvements was the concept of what the fog-of-war should be.

In the first game fog of war existed, but once you revealed an area it was visible for the rest of the game even if there were no units in that area to rediscover the location. This created terribly imbalanced mechanics because being able to see miles away with no units around is kind of ridiculous.

Warcraft 2 fixed this by adding a second layer to the fog of war. The first layer was black and completely undiscovered, while the second layer still revealed the terrain but would not show enemy units if they were hiding in the fog.

It's no surprise that the "map hack" was the most popular hack among cheaters. Not because it was the best hack or because it guaranteed victory, but more likely because it was the easiest one to get away with. After all, it was more than likely that the client's machine already knew where the enemy was, the code was simply blocking the player from seeing it. Once hackers got in there and unlocked the fog locally on the client machine, nothing else needed to be done. No server-side hack required.

This was a problem in subsequent games as well like Starcraft as well. Map Hacks were the easiest ones to get away with. Today infrastructure has improved and servers are exponentially more powerful, so a lot of that data is stored server-side and can't really be hacked anymore. However, crypto and decentralization put us right back at ground-zero when it comes to gaming.

Now we are right back where we started!

Because how can we create a fog-of-war on a decentralized game in which all the information is public? We can no longer trust a centralized server to act as a trusted oracle to prevent cheating. Surly, zero-knowledge proofs are the solution we've been looking for, but how will they be implemented? Will they be fast enough to work for real time strategy? Or will we first need to employ the concept on turn-based-strategy to allow the tech to catch up to the gaming industry?

My vision of what Drug Wars should have been was wildly different than what got created a month later (just another ridiculous idle-mining Ponzi). How amazing would it be to play an actually decentralized game? To have multiple classes of players that compete against each other (like dealers and cops).

How crazy would it be if you, as an in-game drug dealer, could hide drugs at a location, and prove that you were at that location (or not at that location) using a zero-knowledge proof during a SWAT raid? Even more importantly: how crazy would it be if all this could be accomplished without actually revealing your true location? Proving that you aren't somewhere to a party that's actively trying to find you (competitively) is an interesting concept and pretty much the exact definition for fog-of-war implementation.

Of course this also implies that if you can't prove you aren't in a location: then the game has to assume that actually are there (unless their is a tactical reason to cheat in this regard). This could lead to situations where your wallet/node losing its Internet connection could lead to an automatic loss. It all gets very complicated quite quickly and 100% depends on how the game works and what the objectives are.

Conclusion

It becomes clear that ZK proofs and gaming are going to become intimately intertwined in the future, and I will almost certainly bet big on the first game that successfully implements privacy features into a blockchain game. After all: the fog-of-war is inherently a privacy technology. It only makes sense that ZK proofs would be employed to create a truly decentralized gaming experience.

How will it actually work? I have no idea. I just know that one day this will be a thing, and we should all be looking out for such innovation to strike the gaming world. This kind of open-source infrastructure will surely be forked and cloned a thousand times over. The grind for more infrastructure continues. Still early.

Return from Zero Knowledge Fog of War to edicted's Web3 Blog