MUD - How we built an EVM application framework from the ground up

All right, hello I'm Daniel from Nethermind and this is a Julian from ERIKS and we're here to present CircleStark GPU acceleration. So what is a CircleStark? We're gonna start pretty high overview Well, this is your classic proof system. So CircleStark is a proof system. You have two sides, a prover and a verifier.

And the prover wants to send over some proof, usually some obfuscated data of like private input and some computations as a verifier. And the verifier, you know, sends back either accept or reject and it does so in a series of challenges and usually in production we don't really use the challenges in these queries we instead replace it with some hash function and just going over the acronym for those who are not quite familiar zero knowledge just stands for the fact that we hide all the private input in the computation away from the verifier the scalable stands for the fact that we hide all the private input and the computation away from the verifier. The scalable stands for the fact that as the computation increases in size, the verifier and the prover run faster and faster. And one of the key things is that the verifier runs much faster than the prover. Transparent just stands for the fact that we rely on public randomness, so think hash functions.

And one thing about the difference between this and ZK-SNARKs is that ZK-SNARKs use some trusted setup. And usually there's some data remnants that you need to take care of, and if you don't, it might nullify the system, whereas for ZK-SNARKs, we don't actually have this. And finally, arguments of knowledge, just referencing the soundness of the computations. So this is just making sure that everything is secure within the technology that we have today. So let's talk about a matter of efficiency.

For ZK-STARKS, we use field sizes that are really large. These are two to the power of 256, and they use it because the elliptic curves that they use underneath require this for the actual security. Whereas for STARKs, we don't really need to use all of this space because we are not actually using elliptic curves. We're instead working over just the field itself, and the computation size that we're usually using in production is around 2 to the power of 28. So we have a lot of, like, we have exactly 2 to the power of 228, like, as the upper bound bits of unused space.

And something to think about is that about a 4x increase in the actual field size, and you can think of field size as, like, a prime number, is equivalent to about a 9x increase in the actual computation size. So where do we go from here? We want to decrease the field size while also keeping in mind that the lower bound of this like 2 to the power of 28. So we need some field size that is still greater than this. But at the same time, we want to get low enough such that we keep in mind computer architecture.

So 32-bit CPU arithmetic operations are very, very efficient. So if we can find something in this area, then that's very ideal. So just looking into previous primes that were used, we start with Stark Field Prime, which is 2 to the power of 252. And slowly we make our way down lower and lower. And until we finally get it to the Mersenne 31 prime, which is what we use actually in the circle Stark.

And one thing you'll notice is that there is a plus one, basically, for all the primes before Mersenne 31, and this is on purpose. This is to unlock, basically, one of the core features or core functions that Starks use, which is a fast Fourier transform, or if you're thinking in terms of like finite fields, it's a number theoretic transform. And in order to actually use this, it requires as a generalization that the field, the prime, minus one is really easily divisible by two a large number of times. And with the Mersenne prime, if you see, if you subtract 1, you get 2 to the power of 31 minus 2. And this isn't really divisible by 2 other than a single time.

And so what do we do? Mathematicians actually instead map this field onto coordinates of the circle. And by doing so, we gain one extra point. And this one extra point is what allows us to actually use the Mersenne 31. And that's why it's called Circle Start, because we're using the circle as the kind of the group in order to unlock this FFT that we're using.

And so the Mersenne 31 is very efficient on 32-bit architecture. There's lots of optimizations that you can do to really, really bring this out. And as opposed to like baby Bear Prime, which we saw in the previous slide, it's the next higher field size. It's basically a 1.4x performance increase.

All right, thanks Daniel. So some basics on GPU optimization. To be honest, GPUs are used because they can handle many simultaneous calculations, but there are also many uses for this. So we will fall in the first two categories, which are data-intensive computations and algebraic operations. There's also the original purpose for GPUs, which is point number three.

This comes with some problems. So GPUs and CPUs have different memory spaces. One cannot access the other's memory space, and copying data from one to the other is expensive. This means that we have to be efficient when working with memory in these different spaces. It's also the fact that memory accessing is not trivial.

So memory accessing in GPU is best used to go at least, which means GPUs benefit from the use of consecutive memory accessing. And sometimes our algorithms are made so that memory access is complicated. This means that we have to find a balance in which we play around with our algorithm's memory access and the most efficient memory access, which is Coal East. There's also benefits to this. We wouldn't be doing this if there weren't.

When we launch threads to process our data, they will run concurrently, so they'll compete to use the resources of the GPU. But the GPU can handle some threads at the same time, and this is what benefits us. So this will help our calculations be parallelized and run fast. There's also the fact that some architectures, we'll talk about CUDA here, bring you some particular optimization heuristics or optimization tools. We won't talk about them much here, but here are some of them.

Consecutive memory access operations, ensure registers are stuff that are like tools that are very specialized. But yeah, not much focus on them for this talk. Just putting some notes on to the actual problems that we have. So one of the main things that we have for problems is the efficiency of data transfer. So from CPU to GPU and back and forth.

And when we're working with really, really large computation sizes, really think two to the power of 28, copying back and forth anytime we want to actually offload the functionality of the prover onto the GPU comes at a very, very steep cost. The solution is really quite simple. We keep most of the data on the GPU to run throughout the prover time. And yeah, that's pretty straightforward. But let's look at a different problem.

We have a problem of memory access. So the way just GPUs work is data that's close together, you can think about it. Accesses are very, very efficient, but for things that are really, really far across, it can lead to a lot of overhead and lots of downtime. And for, at least for our use case, when we're doing FFTs, we have to access data from this really, really large set that's really, really far apart. And this poses a problem of all this extra overhead.

There's a few solutions to this. One is the fact that we can kind of break down the data sets into smaller chunks so that the data access is a little bit more similar or nearby. And the problem with this, though, is that you introduce a little bit of overhead for actually reorganizing the data, right? Reorganizing and having copying on the device itself. Well, another solution that we can have is breaking down the functions into smaller and smaller kernels.

And by doing so, you introduce the overhead of actually calling these functions. But I think more than anything, the optimizations that we're working on and that we're continuing to improve on is a combination of the three, right? We want to minimize these data transfers. We want to have efficient memory access. And we want to reorganize and break down these functions as few times as possible.

And one thing to note about, I guess, other hardware that's in the ecosystem is one is FPGAs. They also work similarly to GPUs in that they work in parallel. The advantage is that they're a lot low latency. The con, however, is that there is a high developer complexity. So there are a few teams, but I think as we get further down the year, we'll see more and more teams actually working on this.

And as for ASICs or any other ZK-related hardware, we need to manufacture these and design them way in advance. So until we actually have ZK systems kind of converge to a single point and have mass adoption, then we'll kind of have to wait and see. Okay, so for a real-life case study of this being applied, we're going to review first a sequential algorithm, which is a component of the circle stock prover, then we're going to make it parallel, and then we're going to review first a sequential algorithm, which is a component of the CircleStark prover. Then we're going to make it parallel, and then we're going to compare both of them to see how they fare in terms of performance. So BatchInverse is the name of the game.

It's a SU component we'll parallelize. This is a CircleStark prover. Its purpose is to calculate the inversion for a lot of numbers, a lot of field elements. But since calculating the inversion for a field element is an expensive operation, we'll use something called Montgomery's trick. This Montgomery's trick is the sequential algorithm we're talking about here.

So let's start with four field elements. I chose four because it's simple to explain. We calculate the accumulated products for each of these field elements, which means beta 1, beta 2, beta 3, and beta 4 are the accumulated products up to A1, A2, A3, and A4, respectively. But this is inefficient because if we calculate it this way, programmatically, we can see that we multiply a lot of them repeatedly. So we can rewrite this as is, right?

We can rewrite this by using the previously calculated accumulated product. This is simple to see, but it's also relevant and very important because when we want to parallelize this, this will be a limiting factor. Then when we're finished,ize this, this will be a limiting factor. Then when we're finished, we take the biggest accumulated product and invert it using the extended Euclidean algorithm, which is this expensive operation I was talking about. And then we see this little trick to calculate the inversion of the last, the very last element at first.

So intuitively, because there's no division in field operations, we take beta 4 inverted as 1 over the product of all the numbers. This is intuitive, once again, but it helps to see how when we multiply it by the previous accumulated product, we cancel out all the numbers that we don't want and end up with 1 over A4, which is, once again intuitively, the inversion of A4. The same thing can be done to calculate the inversion of the previous accumulated product this way, by multiplying the inversion of the whole accumulated product by A4, getting 1 over the accumulated product from A1 to A3. And this helps us calculate the inversion of every single number we have in our list. A4 is calculated there.

A3 inverted is calculated there. A2 inverted is calculated there. With the same intuition, with the same trick. And then A1 is an edge case. So, yeah, it's easier to calculate.

Now, this turns a potential n field inversions, right? So for an array of size n, it replaces n field inversions with three n multiplications and one inversion. This is way cheaper, and we like this trade-off. Now, as I mentioned, Montgomery's trick cannot be parallelized as is, because calculating any accumulated product means you need to have the previous one. And that means strictly, sequentially, you need to calculate each one.

And we'll adapt this algorithm for it. We'll parallelize it so we can compare them later. This is the adaptive trick to be able to parallelize it in GPU. We start the same way with four field elements, but we'll make an assumption that will help us adapt it, which is we'll suppose the amount of field elements is a power of two. We take those elements and multiply them by pairs.

Multiply them by pairs, and we have beta 1 to 2, beta 3 to 4 as the accumulated products by pairs, and beta 1 to 4 as the whole accumulated product. Now notice that this tree can be parallelized in the sense that one can calculate each node of the same level of the tree at the same time. This is useful because then we will want to send those calculations to run in parallel to the GPU. Now we take the whole thing, the whole product, and invert it with the expensive algorithm, just like before, and we decompose it with a similar intuition than before. We can calculate beta 1 to 2 with beta 1 to 4 inverted and beta 1 to 4 inverted, and beta 3 to 4 this way.

Okay? It's the same as before, just that the numbers in the numerator change. A3 and A4 are in the numerator and cancel out with A3 and A4 in the denominator, and this is what we get. 1 over A1 times A2, which is intuitively the inversion of beta 1 to 2. So the tree is completed by doing the same thing in the other side and finally decomposing the calculated product for each of the elements that we wanted to invert.

And we have all the inversions here. So once again, this same tree that I showed you here can be parallelized the same way as the previous one. Now, apart from parallelizing it this way, one can optimize it further with CUDA-specific or architecture-specific optimizations. But even then, you can see the difference. It's ridiculous.

This is compared against CPU using AVX. AVX is a technology that lets you handle single instructions with multiple data in GPU. So that's even better than CPU by itself. And the difference is still ridiculous. This is for 2 to the 24 element to be inverted.

And this is how it scales bigger arrays. So what did we learn? GPU parallelization is very powerful, and a simple heuristic goes a long way. So a simple parallelization can handle a lot of data very quickly. This is a circle stock prover, and we see how GPU makes a difference here in accumulated time measurements.

So this is a time that it takes to run the prover up to that point, so it's accumulated, and you see that the differences are abysmal. This is in the order of milliseconds. So the GPU prover is way faster than CPU using AVX. So summary, like takeaways from the talk. What did we learn in the talk in general?

First, Circle Starks use smaller fields to balance security and efficiency. Harnessing GPU power is vital and easier than you think for the computation of cryptography primitives. And of course, we should keep an eye on future hardware acceleration trends because the future is in FPGAs. Okay, some due thanks. We wanted to thank the Ethereum Foundation for allowing us to be here and organizing DevCon.

From Eric, we wanted to thank Nethermind for letting us work with them. That was amazing. We appreciate it very much. And yeah, I think that's all. Thank you very much.

You have some resources on Ericss QR, and you have also another mind socials here. I hope you appreciated the talk. I hope you learned something. Thank you so very much. Thank you, Daniel.

Thank you, Julian. It was a nice talk. I appreciated how you kept it high level, but also low level. It was nice. Thank you.

So why don't we take some questions? So the first one, since modern CPU are 64-bit, why 32-bit fields are more efficient? So at least for the operations that are on that architecture, I understand that it's your concern for like 64-bit, but a lot of the actual arithmetization for the underlying functions is optimized for 32-bits. So we can work with 32 bits very efficiently. OK.

So next question is, is this GPU prover open source? Works with Metal? Good question. Yes. This GPU prover is open source.

You can find it, I believe, in NetherMind's socials, probably. It's separate from the prover itself. But the GPU implementation has its own repo. And I don't know about Metal, to be honest. I wouldn't be the one to answer that question, I'm sorry.

So the last slide you had, it has the QR code. Yeah, oh, sorry. We cannot go back. Yeah, last slide, and we can put it up later. Those QR codes can be followed, in any case, at ericscoop and at nethermindf.

And also after the talk, you will find the video on the DevCon Passport, so you can find that. Oh, yeah, definitely. So next question. Comparing M31 and the BabyBear because it utilizes that 32-bit space more efficiently. And in the improvements that you saw over just the Baby Bear, you get about 1.

4x. And it's just because it comes down to a trick that you can use with the Mersenne Prime specifically the two to the power of uh 31 minus one um i won't get into further details but if you want to look it up online there is an easy way to do modular arithmetic on it cool cool um next question is how eric's another mind involved how ERIX and NetherMind involved on CircleStark and HTWO. Okay, yeah. So ERIX and NetherMind worked together in these two GPU implementation. NetherMind worked with Cernet and ERIX worked with NetherMind to develop the StuProvers GPU implementation and the StuProvers uses CircleStark.

That's how it's related. Okay. So if we can just scroll down or maybe i can check it on my phone yeah is anyone working on web gi to acceleration of zk pro generation i honestly don't know uh that's an interesting question. We can talk about that later. Yeah, we can take this offline.

I'm sorry. Can GPU be used to speed up ZK all-ups finality? I believe it can. I mean, what Stargate has achieved is impressive, so I believe most is possible. I think it keeps going.

Is it any better if we go to even more smaller fields, example 16-bits, so the ones you presented were like 32-bits? Yeah, so we still want to keep in mind the actual size of the computation. So in production, usually we use up to 2 to the power of 28-bits, and so we don't want to get anything lower than that, and also at the same time, we want to really unlock the 32 arithmetics, yeah. And I think for the next question, you also talked about it, but how does GPU compare to FPGA, and also you talked about ASICs for circle stocks, maybe specifically? Yeah, at least there's no FPGA for CircleStarks.

That might be an interesting avenue to really look into and research. But in theory, the FPGAs should have lower latency than GPUs. So it should perform marginally faster. But since we don't really have anything on that, we can't really say for sure. So we have time for one more question.

I can read it, I remember it. So the next question was regarding the Montgomery trick. We swept under the rug the fact that we assumed the elements we worked with were a power of two. This is because we can work with any number of elements and then just add elements until we reach the next power of two. Do the optimized algorithm, the optimized adaptive trick in GPU, and then discard the rest of the elements.

We know how many we added. It's easy. It doesn't matter. It's a trivial thing to adapt your array to be a power of two, so it shouldn't really matter. I believe that's what we're really referring to.

All right. So that's it for the Q&A.