Circle STARK GPU Acceleration: An Analysis of Performance and Implementation | Devcon SEA

[Music] all right uh hello I'm Daniel from nethermind and this is uh Julian from Eric and we're here to present Circle start GPU acceleration so um what is a circle Stark we're going to start pretty high overview um well this is your classic uh proof system so u a circle Stark is a proof system you have two sides a pro and a verifier and um the approver wants to send over some proof uh usually some off fisticated data of like uh private input and some uh computations to the verifier and the verifier you know sends back um either accept or reject and uh does so in a series of challenges and usually in production we don't really use the challenges um in these queries we instead replace it with some hash function and just going over the acronym for those who are not um quite familiar Ser knowledge just stands for the fact that we hide um all the private input and the computation away from the verifier the scalable um stands for the fact that as the computation increases um in size the verifier and the um prover uh run faster and faster and uh one of the key things is that the verifier runs uh much faster than the prover transparence uh transparent just uh stands for uh 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 um 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 Starks um we don't actually have this and finally arguments of knowledge just uh referencing the soundness of the computations so this is just um making sure that everything is secure within the technology that we have today so let's talk about a matter of efficiency for ZK snarks um we use field sizes that are really large um these are 2 to the^ of 256 and uh they use it because the elliptic curves that they use underneath uh require this for the actual security um whereas for Starks we don't really need to use all of this space uh because we are not actually using elliptic curves we're instead um uh working over uh just the field itself and um the computation size that we're usually using in production is around 2 to the^ of 28 so we have a lot of uhu like um uh we have exactly two are of 228 like as the upper bound bits of unused space and something to think about is that uh about a 4X uh increase in the actual field size and you can think of field size as a like a prime number uh is um 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 uh while also keeping in mind that the lower bound of this like 2 to the^ of 28 so we need some field size that is still greater than this but at the same time we want to get um uh low enough such that we keep in mind computer architecture so 32-bit uh CPU arithmetic operations are very very efficient so we if we can find something in this area then that's very ideal um so just looking into um uh previous primes that were used we start with Stark Stark field Prime which is uh 2 to the^ of 252 and slowly we make our way down lower and lower and until we finally get to the IM meren 31 prime which is what we use actually in the circle Stark um and one thing you'll notice is that there is a plus one basically uh for all the Primes before meren 31 and this is on purpose this is um to unlock basically one of the core features or core functions that Starks use which is a fast foror transform or uh if you're thinking in terms of like finite Fields it's a number theoretic transform and um in order to actually use this uh it requires as uh generalization that the field the prime minus one is really easily divisible by two a large uh number of times and with the Merm Prime if you see um if you subtract one you get 2 to^ 31 minus two and this isn't really divisible by two uh other than a single time and so what what do we do uh mathematicians actually um instead map this field onto coordinates of the circle and um by doing so we gain one extra point and this one extra point is what allows us to actually use the meren 31 and that's why it's called Circle Stark because we're using using the circle as the uh kind of the group um in order to unlock this fft that we're using and so um the meren 301 is very efficient on 32-bit architecture uh there's um uh lots of optimizations that you can do to really really um uh bring this out and um as opposed to like baby uh bear Prime which we saw in the previous slide it's uh the next higher uh field size it's um basically a 1.4 x uh performance increase all right thanks Daniel so some Basics on GPU optimization um to be honest uh 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 albic operations there's also the original purpose for gpus which is uh Point number three um this comes with some problems so uh gpus and CPUs have different memory spaces uh 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 there's also the fact that memory accessing is not trivial so memory accessing in GPU is best used coal East which means um gpus benefit from the use of consecutive memory accessing and sometimes um our algorithms are made so that memory access is complicated this means that we have to find a balance uh in which we uh play around with our algorithms memory access and the most efficient memory access uh which is goal East there's also benefits to this we wouldn't be doing this if there weren't uh when we launch threads to processor data uh they will run concurrently so they compete to uh use the resources of the GPU but the GPU can handle some threats at the same time and this is what benefits us so uh this will help our calculations be parallelized and run fast there's also the fact that some architectures we'll talk about Cuda here um bring you some particular uh optimization uh heris stics or optimization tools uh we won't talk about them much here but here are some of them consecutive memory access operations and share registers are stuff that are like um tools that are very specialized but um yeah not much Focus on them for the stock uh just putting some notes onto the actual uh problems that we have so uh one of the main things that um uh we have for problems is uh the efficiency of data transfers so from CPU to GPU and back and forth and when we're working with really really large um computation sizes really think 2 to the^ of 28 um 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 uh the solution is really quite simple we keep most of the data on the GPU to run throughout the prover uh time and uh and uh yeah that's pretty straightforward but let's look at a different problem um we have a problem of memory access so the way just gpus work is um data that's uh close together if you can think about it um accesses um are very very efficient but uh for things that are really really far across uh and lead to a lot of uh overhead and lots of uh downtime and for at least for um our use case when we're doing ffts we have to access data uh from this really really large set that's really really far apart and this uh poses a problem of all this uh extra overhead there's a few solutions to this one is the fact that we can kind of break down uh the uh data sets into smaller chunks so that the data access is a little bit more um uh uh similar or uh nearby and the problem with this though is that you uh introduce a little bit of overhead for actually reorganizing the data right reorganizing and uh having um copying on the device itself well another solution that we can have is uh breaking down the functions into smaller and smaller um uh uh kernels and uh by doing so you introduce the overhead of of actually calling these functions um but I think more than anything uh the optimizations that we're working on and uh that we're continuing to approve on is a combination of the three right we want to minimize these data transfers we want to have efficient memory access and and we want to reorganize um and break down these functions uh uh as um few times as possible and um one thing to note about uh I guess other Hardware that's um in the uh ecosystem is uh one is uh fpgas they also work similarly to similarly to gpus and that they work in parallel uh the advantage is that they're a lot low latency the um the con however is that um there is a high uh developer complexity um right so there are a few teams but I think as we get further down the year we'll see more and more um uh teams actually working on this and as for A6 or any other ZK related Hardware um we uh 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 see okay so for a real life case study of this being but we're going to review first a sequential algorithm which is a component of the circle star prover then we're going to make it parallel and then we're going to compare both of them to see uh how they fair in terms of performance so bat Chambers is the name of the game uh it's a su component with parallelize this is a circle star prover its purpose is to calculate um the inversion for a lot of numbers okay a lot of field elements but since calculating the inversion for a field element is an expensive operation we use something called Montgomery stri okay this Montgomery stri is the sequential algorithm we're talking about here so let's start with four field elements uh 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 um but this is inefficient because if we calculate this way uh programmatically we can use that we can see that we multiply a lot of them um repeatedly so we can rewrite this as is right we can rewrite this um by using the previously calculated accumulated product this is simple to see but it's also uh relevant and very important because um when we want to parallelize this this will be a limiting factor then uh when when we're finished we take the biggest accumulated product and inverted using the extended ukan algorithm which is this expensive operation I was talking about and then uh we see this ear trick to calculate uh the inversion of the last the very last element at first so intuitively because there's no division in field operations um we take uh beta 4 inverted as one 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 the inversion of the whole accumulated product by A4 and getting uh one 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 there and then A1 is an edge case so yeah it's easier to calculate now um this turns a potential N Field inversions right so for for an array of size 10 it replaces N Field inversions with three end multiplications and one inversion this is way cheaper and and we like this tradeoff now um as I mentioned Montgomery trick cannot be parallelized as is because calculating any accumulated product means you need to have the previous one uh and that means uh strictly sequentially you need to calculate uh 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 uh we start the same way with four field elements but we'll make an assumption that'll help us adapt it which is we'll suppose the amount of field elements is power of two um we take those elements and multiply them by pairs okay multiply them by Pairs and we have beta 1 to2 beta 3 to four as the accumulated product by Pairs and beta one to 4 as the whole accumulated product now notice that this tree can be paralyzed in the sense that one can calculate each node of the same level of the tree of the same time okay 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 a similar intuition than before right we can calculate beta 1 to2 with beta 1 to4 inverted and beta 3 sub4 this way okay um 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/ A1 * A2 which is intuitively the inversion of beta 1 to2 so the tree is completed by doing the same thing in the other side and finally decomposing the accumulated 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 what you hear can be parallelized the same way as the previous one now uh apart from parallelizing it this way one can optimize it further with C specific or architecture specific uh optimizations but even even then you can see the difference it's ridiculous um this is compared against CPU using AVX AVX is a a technology that lets you handle single instructions with multiple data in GP in CPU 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 uh bigger bigger arrays so what did we learn GPU paration is very powerful uh and a simple heuristic goes a long way so a simple parallelization can handle uh a lot of data very quickly this is a circle starover and and we see how GPU makes a difference here uh in accumulated time measurements so this is a time uh that it takes to to um run the prover up to that point so it's accumulated and you see that uh the difference the differences are a vismo this is in the order of milliseconds okay um so the GPU Pro is way faster than CPU using ABX okay 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 uh 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 um okay some due thanks uh we wanted to thank the etherum foundation for allowing us to be here um and organizing Devcon from Erics we wanted to thank nethermind for letting us work with them uh that was amazing we appreciate it very much and and yeah I think that's all thank you very much um you have some resources on Eric sqr and you have also nethermind socials here I hope you appreciated the talk I hope you you learn something and yeah thank you so very much yeah 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 if we take some questions um so the first one since modern CPU of 64 bits y 32 bits field are more efficient so at least for the um operations that are um uh on that architecture um um I understand that it's your concerned for like 64bit but a lot of the actual arithmetization for the um underlying fun functions uh is optimized for 32 uh bits so we can work with 32 bits um very efficiently okay so next question is is this GPU PR open source works with metal good question yes this GPU prover is open source uh you can find it I believe in nether mind socials probably um um it's separate from like the prover itself but uh yeah the GP 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 so yeah oh sorry yeah we cannot go back but yeah and last slide then we can uh put it up later those QR codes can be followed uh in any case at Eric's Co up and at nethermind F yeah and also after the the talk you will find the video on the dev Devone passport so you can find oh yeah definitely so next question comparing M31 and baby beer which is more GPU friendly and why uh so the M31 would be um much faster just because it utilizes that uh 32 bit um of kind of space um more efficiently and in the improvements that you saw over just the baby ver you get about 1.4x and it's just um because it's it comes down to a trick that you can use with the meren prime specifically the 2 to the^ of 31 minus one um I won't get into further details but if you want to look look it up online there uh is a easy way to uh do modular arithmetics on it cool cool um next question is how Erics and nethermind involved on Circle star and stwo okay okay yeah uh so Eric and nethermind work together in the two GPU implementation um nethermind worked with seret and Eric worked with nethermind to uh develop this two GPU implementation and the St provs and the Stover uses Circle Stars that's how it's related okay um so if we can just scroll down or maybe I can check it on my phone yeah is anyone working on webg to acceleration of Z Capo generation I honestly don't know uh that's an interesting question uh we can talk about that later and yeah we can take this offline then I'm sorry um Can GP you be used to speed up ZK ol Ops finality I believe it can uh I mean what target has achieved this impressive so I believe most is possible I think it keeps going yeah yeah is it any better if we go to even more smaller Fields example 16 bits so the ones you presented were like 32 bit Yeah so um we still want to keep in mind the actual size of the computation so in production usually we use uh 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 U arithmetics yeah and I think for the next question you also talked about but how does GPU compar to fbga and also he talks about ASX for Circle stocks maybe specifically yeah at least there's no fpga for Circle Starks um that might be an interesting Avenue to really uh look into and research but um in Theory the fpgas um should have lower latency than gpus so it should perform marginally faster but the since we don't really have anything on that we can't really say for sure uh so we have time for one more question and I can I can read I remember it um so the next questions was regarding the Montgomery trick uh we swept under the rug uh the fact that we assumed um the elements we worked with were a power of two well this is why this is because um 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 adapted trick in GPU and then discard the rest of the elements uh we know how many we added it's easy it doesn't matter it's a trivial thing to adapt your your array to be a power of to so it shouldn't really matter I believe that's what we're referring to all right so that's it for the Q&A if you have more questions you can