Disclaimer: I’m not an expert on this topic. All the content written below is my understanding of what I’ve read in the Github repository.
An introduction to zk-SNARK
zk-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge” which sound extremely complex, with good reason, because it is, but happily for us, there are libraries that help us use it without having to understand the mathematics behind it.
In easy terms, if I have a function F(X) = Y, where X is an input, and Y an output, with zk-SNARK a subject can prove that he knows some X that makes the function return some specific value of y, without revealing the required value of X.
Let’s consider that F(X) is not something that can be reversed, if you know some value of Y, it’s impossible to know the value of X that generated it.
Then I say, “The person who discovered the highest value of y before the end of this year will receive a million dollars, but if more than one has the same number, the prize will be divided between all the winners”.
In addition, I will also participate in my own game, and if get the highest number, I won’t be paying anything.
If you send me your X value, I can just tell you that I’ve got the same, so I don’t have to pay anything. How can you tell me the number you got without revealing me or anyone else your X value?
Well, zk-SNARK allows you to prove that you know the value of X that generates a certain Y, so you would be able to publicly show that you got the highest Y without ever revealing which value of X you used.
This can be extended to a lot of use cases. Imagine a transaction. You could prove that you are the owner of one wallet with enough funds to transfer a certain amount to another wallet but without revealing your wallet address, the destination wallet address nor the amount of the transaction.
Isn’t that amazing? Zcash is an example of this.
''A Z-to-Z transaction appears on the public blockchain, so it is known to have occured and that the fees were paid. But the addresses, transaction amount and the memo field are all encrypted and not publicly visible''
How all of this applies to Dark Forest?
Dark forest is a space exploration game where players compete to conquer planets and acquire resources. It has two main components, the exploration of the world and the conquering of celestial bodies.
Exploration
Every player has it’s own map of the zones they’ve explored. This information is extremely important since it reveals the location of planets and other celestial bodies.
The exploration is made by “mining”. It’s offline and it doesn’t interact with the blockchain. (Only to check if a planet is already owned by another player)
Basically, by choosing a set of coordinates (x,y) a hash is generated, and decoding that hash reveals if there is a planet there. Let’s make an easy algorithm like that one as an example.
So, if the first number of the hash is a 0, a planet is generated in that place, and the level of the planet will be the second number of the hash.
If we use a completely unpredictable hash function with equal chances of any number on any position, we can say that there is a 10% chance of finding a planet in any location, and every level has an equal chance of 10%.
So, by that definition, you would have a 1% chance of finding a level 9 planet in a location.
Since the only way to know if there is a planet in some location is to resolve the hash, the exploration speed depends only on the speed of your PC to calculate hashes.
If it can resolve 1 hash per second, you would on average find a level 9 planet every 100 seconds.
So, no one knows the locations of the planets before the exploration starts, and the only way to find them is to “brute-force” the locations.
Conquering
There are other actions in the game, but let’s just focus on a very simplified version of conquering planets.
Let’s assume your planets have a certain amount of power that can be used to attack, and that the power decays with the square of the distance between the planets.
If the resulting power is higher than the enemy planet power, the attack is successful and the planet is yours.
Now, let’s remember that no one else knows the location of your planets nor the planet you are trying to attack because they haven’t explored that area.
Also, you don’t want to reveal the locations, because other players could come here to attack you and steal your planets.
How can the smart contract validate that your attack can be done without knowledge of the locations?
Let’s write a very simple resulting power function.
power = initial power - distance^2
And the distance is calculated by:
distance^2 = (x1 - x2)^2 + (y1 - y2)^2
power = initial power - ((x1 - x2)^2 + (y1 - y2)^2)
Now let’s subtract the enemy power from that power, if the result is greater than 0, we won the battle, if not, we lost it.
battle result = my power - enemy power
battle result = init pw - ((x1 - x2)^2 + (y1 - y2)^2) - enemy pw
Initial power and enemy power are known variables, but (x1, x2, y1, y2) are not, and we don’t want to reveal them.
So, following the idea of zk-SNARK we know it’s possible to make a proof that we know a set of (x1, x2, y1, y2) that generates a certain battle result that in case of being higher than 0, allows us to conquer the planet.
Now, it’s easy to see in this example that we could just lie about the locations to win every battle, so, in a real scenario, we also have to provide a proof that we know the location of both planets and that we are using those locations for the attack.
The full code of that is a bit out of the scope of this article, but you can check the circom repository which is a library for building those proofs, and of course the dark forest repositories for more information about this.
Also, in the dark forest blog you can find some articles about zk-SNARK implementation in the game.
Zero-Knowledge Proofs for Engineers: Introduction
ZKPs for Engineers: A look at the Dark Forest ZKPs
This article is my attempt as a complete noob in the blockchain world to explain ZKPs in a simple way. It doesn’t show the real-world implementations of these algorithms.
