'Procedural Generation in a zkSNARK' - Brian Gu

We are in the final stages of this summit. This is our last report today, and I am very pleased to present it. So, without further ado, I want to invite Brian to talk about procedural generation using SNARKs. He will talk about this using the example of the game Dark Forest. So, Brian, you can begin.

Perfectly. Hello everyone, I'll share my screen now I'll share my screen now , thanks for inviting me. To the EthGlobal team and Kartik, it's great to be here. We are glad to have you with us. OK.

Perfectly. Hello everyone, my name is Brian. I'm working on Dark Forest. I also do applied research and development of zero- disclosure technologies at the Ethereum Foundation. Today I will talk about procedural generation in ZK-SNARKs, including some of the challenges we encountered during our experiments.

Steeply. To motivate everything I'm going to talk about today, I want to start with this question. How could we build Minecraft on Ethereum? I think many people are fascinated by the idea of decentralized worlds that are rich, expressive, and that many people can participate in and build on. One of the best and most familiar examples for many is the game Minecraft—a many is the game Minecraft—a three-dimensional three-dimensional sandbox game.

With a rich and diverse landscape, a bunch of different objects, blocks, and things to build with. One of the key features of Minecraft is its extensive use of procedural generation. When you enter the world of Minecraft, you are presented with an environment with forests with an environment with forests , oceans, deserts, and various structures on a local and global scale global scale . With Ethereum and other decentralized platforms, we have quite strict limitations, for example, on the amount of data storage. How many can actually fit in an EVM?

We have limitations on transaction bandwidth. Therefore, today it seems that we are still very far from creating a full-fledged and rich game like Minecraft on Ethereum. But our theory at the Dark Forest team is that by combining certain techniques with ZK-SNARKs, we can get closer to realizing this vision. So, to dive deeper into the context of what we're talking about today, we'll specifically discuss some of the difficulties we faced when trying to implement Perlin noise inside zk-snark. This is a technique we use in Dark Forest.

And that's why we've been exploring more complex variations over the last few months and throughout the rest of this year. So, Perlin noise is a procedural generation algorithm for creating a rich and diverse game landscape. You can think of it as a function that can map an arbitrary pair of x,y coordinates, say x,y coordinates, say , to a terrain height. ZK-snark allows you to perform verification of the execution of arbitrarily complex functions on the contract side in constant time. In other words, if I have a function that would cost a lot of gas to execute in Solidity, say hundreds of thousands or millions of gas units, if I can wrap it in zk-snark, then the cost I pay to execute that function is essentially just the cost of the verification, which on-chain would be a few hundred thousand gas units.

Combining these two things, if you want to have rich procedurally generated worlds on the blockchain, one idea is to put Perlin noise inside zk-snark. So a quick overview for those who may not be very familiar with it. ZK-snark familiar with it. ZK-snark is a tool that essentially allows you to prove knowledge of the input data of a function that corresponds to a certain known output. For example, on this slide we have a very simple function: f (x) = x1 + x2*x3-x4.

A ZK-snark for this function would allow a closer to prove that, a closer to prove that, say I'm a closer, I'll give you the claimed result of this function f(x), for which function f(x), for which I claim I have four inputs x1, x2, x3, x4, and then I'll also give you a proof that you can check that convinces you that I do indeed know the four inputs that, when properly computed, give this result. The zero- disclosure property of ZK-snark ensures that I can do this without telling you anything about these four inputs; all you're making sure of is that I have this input and that I've executed it correctly. But it turns out that for the procedural generation we're interested in, this part is n't really that important. The important thing is that signature verification takes constant time. So, more specifically , ZK-snarks prove the limits of what can be considered the computational graph of this function.

So, in our previous example, we have the function f (x) = x1 + x2*x3-x4. You can think of it this way: if I want to do these calculations step by step, I create an intermediate value y1 that is the sum of x1 and x2, then an intermediate value y2 is the product of y1 and x3, and the result is just the second intermediate value minus x4. So, what minus x4. So, what snark "sees," what I feed it, are the input values ​​x1, x2, x3, x4, the intermediate values ​​y1 and y2, and the output value. In fact, snark generates a signature that is valid only if the constraints corresponding to these intermediate execution steps are met.

So when we think about doing calculations, we're like going through this computational graph in a forward direction, starting with x1, x2, x3, x4, calculating intermediate values, and eventually getting the result. The snark “digests” all seven values involved in the calculation and produces a valid signature if the condition is met that the first intermediate value is equal to the sum of x1 and x2. The second intermediate value is equal to the product of the first intermediate value and x3. And the output value that I publish is equal to the second intermediate value minus x4. So snark essentially processes these seven inputs.

Let's say, as an example, that we take the input data 2, 4, 8, and 5. The result I get if I plug them into the function is -43. Snark will actually see these seven numbers that were obtained during the calculation. And it is able to generate a valid signature of the calculation if three constraints are satisfied for these seven numbers. And since these constraints accurately reflect the course of the calculations.

In this way, snark essentially proves the correctness of the function. So, uh. It is important to note that SNARKs can only produce such proofs for constraints involving addition and multiplication. So in the previous example, this function is very simple and only involves addition, multiplication, and, you know, subtraction, which is just the reverse of addition. But most of the functions we encounter in reality and that we might be interested in involve other, more complex operations, such as division or modulus.

This means that in general, if we are creating a zk-SNARK scheme to allow people to prove the correctness of a function, we need to understand how to express the correctness of that function in terms of a set of constraints that only involve addition and multiplication. So in this example we have a function that is very similar to the previous one, except that the second intermediate value y2 is equal to y1 value y2 is equal to y1 /x3. Since division is not a valid operation that we can use inside the constraint for zk-SNARKs. We need to express this stage of the computation as a constraint involving only multiplication. So, previously we had the constraint y2 equals y1*x3.

In this case, the expression is satisfied when the constraint y1 = y2*x3 is satisfied. This is an example of a situation where the execution of a function does not exactly match the system of constraints that proves its correctness. I hope it's clear enough that the SNARK that processes these seven values ​​and checks these three constraints is essentially checking the correctness of the calculations of whoever used these inputs, substituted them into these two intermediate values, and got this result. In other words, the correct execution of this function corresponds to fulfilling these three constraints for these seven values. Yes.

I won't go into too much detail about this . But when we move on to more complex operations, such as converting an integer x to its bit string in an array representation array representation , we will have to use this trick or similar ones even more intensively. Because there is no simple way to go from an integer to its bit string using addition and multiplication by the usual computational method. But we can create a system of constraints that holds if and only if what we declare to be the bit representation of the integer x really is. And the last caveat to all of this is that in the SNARK schemes that in the SNARK schemes that we use—and we use circom and snarkjs, developed by iiden3—all of these operations are done modulo a 254-bit prime number.

So, essentially, you can think of the problem as being that addition and multiplication will overflow if you go beyond the p-value that is somewhat built into the protocol. This often means that if we are performing overflow-sensitive operations, we will need to add constraints that ensure that each step of the computation does not actually result in an overflow. Okay, that was a brief overview of ZK-SNARKs. Now I'll talk a little about Perlin noise. So, as we mentioned, Perlin noise is an algorithm that allows game developers to create rich and varied terrain that looks random on a global scale global scale , but has local structure.

In other words, you see that this landscape is generated by some function, say f, which takes a coordinate pair x, y and outputs a height h. The guarantee provided by this function is that points located close to each other have similar heights. So it's not just a random scattering of points, but if you zoom out, you get some global features, as well as global randomness. Now let's take a closer look at how the Perlin noise algorithm works at a high level. The idea is that to create a height map of this landscape, the Perlin noise algorithm first divides the area into a square grid, and then randomly selects a unit vector and assigns it to each corner of the grid.

As you can see, we have a small table of grid squares. At each corner, we chose a random unit vector. That is, a random direction vector of length one, pointing in a random direction. These gradient vectors will essentially correspond to the terrain gradients at each of these points. So once we've selected all these terrain slopes at each grid point, we'll simply perform interpolation to determine what the values ​​should be at all the intermediate points.

In this example, we have a heat map overlaid on top of this grid. Green means higher, and purple means lower. So you can see if you look at this grid square that the three vectors assigned to each of the three corners are each of the three corners are pointing inward; Accordingly, this means that in the terrain we are creating, at these three points the slope when moving towards the center of the grid square is generally directed upwards. You can see that this corresponds to the darker green area right here. In this square, you can see that the four vectors are directed outward.

This means that the slope, i.e. the gradient directed inward, will be downward, and this essentially creates a depression or valley in the relief feature. So, Perlin noise is essentially a sampling of gradient vectors at each corner followed by interpolation, which gives a very realistic relief function. There are a few more tricks, but this is essentially the basic foundation, the first level of the algorithm.

So, what does this look like mathematically look like mathematically ? Essentially, this means that we need to be able to pseudo-randomly choose gradients, i.e., unit vectors. This is difficult to do using only addition and multiplication, but we will discuss some methods for implementing this.

The second part is that we will have to do a lot of dot products because we are doing interpolation. So, we're just multiplying a bunch of vectors. Fortunately, this is fairly easy to do using addition and multiplication, which is why we chose this algorithm to begin exploring its implementations in SNARKs. OK. So now I'll discuss some of the specific challenges of putting all of this inside a SNARK.

The first problem is that you need to be able to pseudo-randomly choose these gradient vectors at each corner of the grid. So why is it difficult? Essentially, we need a function f into which I can plug in the coordinates of the corner of the grid and get a random unit vector as the output. I need something that guarantees that for each corner of the grid, regardless of whether they are close or far apart , the vectors associated with those corners will be uncorrelated. So, how do I do this?

So, I'm going to use a snark-friendly hash function, effectively as a random oracle. There are snark-friendly hash functions such as mimc and poseidon. They are optimized to produce output that looks random, while being very cheap to verify within snark. For example, mimc looks like a set of successive additions and raises to a fixed power. By substituting these corner points of the grid into the mimc function and performing some processing, we obtain a source function that acts as a random oracle from which we can derive a random unit vector for each corner of the grid.

The second challenge we face when working with the Perlin noise algorithm is that we often have to perform division and modulo operations. For example, to perform this interpolation, you need to determine which square you are in, and this essentially boils down to operations similar to finding the quotient and remainder. The reason why this is difficult is due to several factors. First, you are already implicitly working in a field where all operations are performed modulo p for the baby jub jub protocol with prime p. This means that if you are not careful with overflow, your ZK overflow, your ZK modulus proofs become vulnerable to attacks where attackers can pass off a certain value as the result of a modulus operation, even though it is not.

Therefore, we have the following modulo scheme following modulo scheme , which takes about 100 lines in circom, where we perform overflow checks at each step. The second thing to remember is the sign. Since we are working modulo p, we have no concept of negative numbers . So you need to implement some convention where, for example, we will consider all the remainders from P times two to P as negative, and the remaining remainders from 0 to P times two as positive. And then you need to perform the overflow checks associated with that.

So even something as simple as proving that three is congruent to eight modulo five inside a snark turns out to be more difficult than one might expect. The third problem we face is essentially converting the randomness we generate, or the pseudo-random values ​​obtained using MiMC, which we use as a random oracle, into random unit vectors. Inside snark, we need to be able to assign to each grid point the coordinates of a vector of length one with an arbitrary direction determined by randomness. This is difficult because usually when you try to pick a random direction it involves using trigonometric functions like sine and cosine. The first approach we tried was to use the value obtained from a random oracle as input to the Taylor sine and cosine approximation .

For various reasons related to the fourth problem, which I will briefly touch upon which I will briefly touch upon . This is actually impossible. So we ended up using a scheme written by our colleagues at Semaphore that allows us to select values ​​from a list. We have hardcoded 16 direction vectors and using this selection scheme we can index this list and select from the set of vectors. For any grid point any grid point where we are trying to select a unit vector, we take that point, insert it into MiMC, and get the randomness.

We take this random value modulo the length of the list and then use a selection scheme to choose one of these unit vectors from the list. The last difficulty we encountered and which I will discuss in this talk is that with Perlin noise you will be working with non-integer values. For example, a unit vector is a vector whose coordinates will not both be integers unless you are at the points (1, 0), (0, 1), (0, -1), or (-1, 0). So, we tried several approaches to solve this problem. The first thing anyone tried was to implement a series of fixed-point arithmetic schemes in CIRCOM.

But it turned out to be too expensive to be practically feasible. So we ultimately decided to do all our calculations inside ZK-schemes using fractions. We represent this as follows: we store as a global constant in our schemes the maximum denominator D that any computation will ever encounter. We calculated this in advance, essentially by running a Perlin function in JavaScript and figuring out what the maximum denominator would be. We have rigidly fixed this value, and now all the math inside the circuit is performed on the numerators, understanding that these are the numerators of fractions divided by the denominator.

So, we keep track of this global constant denominator D and do all the calculations with the numerators. This means that when we add two values in our scheme, we know that we are adding a/d + b/d and we get the value (a + b)/d. This also means that when multiplying two values, we need to multiply them and then divide by an additional factor d, since a/d*b/d equals ab/d ^ 2. This is how we got around the complexity of these calculations not being integers. The result was a basic version of the Perlin noise function implemented in Dark Forest, which those of you who played the last two rounds have probably seen.

Essentially, Perlin noise allows us to add texture to the universe, making some regions richer in resources than others. The goal is to get to the point where Perlin noise can be used to create very expressive and detailed landscapes, perhaps even resembling a Minecraft world. In addition to these difficulties, a meta- difficulties, a meta- complexity is that development environments and tooling for ZK tooling for ZK applications currently remain quite rudimentary. So I want to give a quick thank you to Jacob Rosenthal and Blaine Bubblets, who work on many of the tools for ZK ZK development workflows. Um, but all of these, uh, challenges are compounded by the fact that we're still in the very, very early stages of ZK application development.

Um, and the workflows we have are not very developer-friendly. So if anyone is interested in zero- disclosure application development, this is exactly the area where a lot can be done and which would be very, very useful. Yes. So, that's pretty much all I wanted to say. Um, if you want to learn more, we have a blog where we publish both content related to the Dark Forest game and materials about ZK development at blog.

zkga.me. You can also find us on Twitter at darkforest_e. Um, and we'll be releasing the next version of Dark Forest in a few weeks, sometime in mid- May. Um, and finally, if you want to contact me, you can find me on Twitter at BGU33.

Yes, thank you for inviting me. Surprisingly. Thank you very much , Brian, for such an interesting and, I would say, very technical, but extremely detailed and important overview of how this works. I think this is a key part of what makes Dark Forest special. Um, and that's the real natural appeal of actually using ZK using ZK technologies here.

This is very cool. If anyone in the audience has any questions, please questions, please feel free to ask them in the chat and we will answer them live . And so far, I think you've outlined a few recurring themes that I've noticed throughout the conversation. And my general question is: I would now characterize this as "code golfing", for lack of a better definition. Given how early we are in everything from tooling to development and the number of people who understand how it works to get something at the application level.

What do you think we lack the most? Do we lack a standard library, or do we just need more standards so that someone can do it all and we all use the same library every time? What does this repetition or abstraction look like? Yes. So, one thing I think is that developing ZK developing ZK applications, in my opinion , is quite inaccessible unless you have some level of mathematical training or a basic understanding of, for example, number theory.

For example, certain nuances of working with a modulo scheme and its defense will only become clear if you are well acquainted with the Chinese remainder theorem or have good intuition about it. Like, why do I need to do these overflow checks here? What can a malicious prover actually do? Well, what a malicious prover can do is, you know, thanks to the Chinese remainder theorem, he can apply the Euclidean algorithm to figure out what the malicious value would be for the modulo operation. I think, in short, we need a few things.

First, it is a standard library of schematics that people could easily integrate into their projects. Another would be a higher level DSL on top of, for example, circom, which is already doing a phenomenal job making all of this possible. It still amazes me that programming ZK-snarks is even possible. But the next step should be the accessibility of their programming. You don't need to be very familiar with number theory to create applications like this.

An example I've thought about a lot: cryptography "under the hood" is very complex. But we, as a community, have figured out how to properly abstract the mathematical operations mathematical operations that underlie cryptography and provide developers with a conceptual API so that they understand, "Oh, encryption has these guarantees, decryption has these guarantees, the message signature looks like this," and that manifests itself in many of the standard libraries for libraries for whatever language you use for cryptographic operations. And one more thing that, in my opinion, will be very important— will be very important— although it will take time, because even the protocols have not yet been defined, and it is not entirely clear what their guarantees will be in the future. But another thing I think about and that is always relevant is development tools that allow for faster iteration cycles and better feedback for developers. This is very much what Blaine and Jacob are working on , and I'm very passionate about it.

Um, it's a combination of many things, but I really think we're at a very, think we're at a very, very early stage. No, I fully, 100% support this, and I think it's a natural evolution of new technologies in general: like the transition from punch cards to the era of Python programming. That's right. Yes. Just like you don't need to think about how registers work.

Someone should abstract the number theory here. Ahem. True. Right. Um, with that in mind, I'm really glad to see that you've announced a new version of Dark Forest.

And maybe to clarify: what you were talking about is the analysis of the previous version or how you are using these things to create the next, more generative version of Dark Forest? Yes. These were some of the challenges we faced when trying to implement a very basic version of Perlin noise for the last few versions of Dark Forest. We're still using them and, you know, we're constantly working on improving them for future versions. But we are also interested in the fact we are also interested in the fact that, in our opinion, this technique can become the basis not only for Dark Forest, but also for other games.

Therefore, in the next few months, we will explore ways to implement this mechanic into other prototypes or concepts of simple blockchain games. Perfectly. Well, I want to thank you for taking the time on Friday to give this incredible talk. And if you have any questions that we have n't answered, we'll forward them to you directly. And for those who are watching this later or watching it now, we will post a short recording of this 30- recording of this 30- minute talk on YouTube later.

So you can catch up, review slides and math calculations. Thanks again, Brian. Thank you, Karik. Thank you for inviting me.