ZK Paris: Omer Shlomovits - Gnark on Ice, ZK Acceleration in Golang using ICICLE

Transcript

so next up is um narc on Ice ZK acceleration in golang using icicle by Omar schlemovich at inganyama thank you so for those of you who joined and by way of introduction um to the company I want to present to you a sneak peek into the first ZK movie okay go ahead modern stock markets information has always been our most valuable currency today general information is easily accessed and personal information easily shared with the world at our fingertips

the need for trust can be an unnecessary obstacle slowing the pace of progress zero knowledge proofs remove these obstacles as they remove the need for sharing trusted information that could be leaked or lost eliminating the risk of attack or exploitation zero knowledge has the magical ability to guarantee data integrity and removes the need for storing and keeping track of users information reducing costs and freeing up resources [Music] and it doesn't stop there zero knowledge technology is applicable to any field where trust is involved and will revolutionize how we interact with

countless domains nyama develops cutting-edge Hardware necessary to make this technology accessible for all [Music] right full movie is coming soon this was just a trailer no seriously it was generally it was done by the way with generative AI if anyone wants to learn more about it please find me afterwards so yeah um let me tell you the motivation for this talk a few facts okay so first snacks are slow okay let's acknowledge it proof generation uh is uh quite slow to do this is like very

natural it's part of the trade-off space so we need to deal with it the second thing is that modern snack Frameworks right so we're going to talk about gunak but also Halo 2 corks happy snacks natively they support CPU and CPU alone right it makes perfect sense this is how we start when we build software but that is the case third Hardware accelerators are very accessible right they are cheap cloud gaming gpus right so they are here fourth we know that from experiments that were conducted publicly and like results were shared such as the price we

know that we can take Primitives that can be found in zero knowledge in snarks and accelerate them using specialized Hardware therefore the conclusion is that we should try to merge these two things right let's bring zero knowledge accelerators into these Frameworks these snack Frameworks okay and today I'm going to talk about one kind of integration that we've done in some shares of the insights that results that we've seen on how it works obviously spoiler it works nicely so before jumping into that one previous attempt that kind of led us to where we are today was an experiment we've done

uh jointly with geometry and uh back then it was we took our quarks so another zika framework specifically we targeted gold 16 and bn254 which is the same Kelvin protocol we're going to use also for this uh talk and today and we use the spgas that can be found in the cloud right so it's like the same uh kind of like accessible Hardware and we just took the msms right the G1 and G2 MSM then basically move them to the fpgas and you can see that for different number of constraints we actually get some performance boost it's not it's it is not much but it gives you kind of like the hope that something can be done here right maybe more professionally one thing to note is this

like component called spark Works which was designed or something that we noted that was needed to kind of like make everything very clean in terms of API we want the hardware to be indifferent to the exact um protocol and a framework and on the other end so that you know we can switch hardware and on the other end we want Frameworks to kind of like be insensitive to what Hardware they are running on so it should be also very simple so now let's kind of like take this ID to The Next Step which is um you know kind of like productize it in a way so the ideas is high level uh API that would allow developers whoever they are to add this dimension of GPU acceleration to um

to the work they're doing on whatever ZK application that they are developing okay so here of course we need to Target the real world circuits so it's not just like an experiment let's do something that actually can be used and we do need to kind of like I guess evolve these spark walks to some Library so this is what icicle is going to be about and um we've done this kind of switch between fpga to GPU for several reasons gpus basically are more commutized very easy to program so the cycle kind of like the iteration is can be quicker and they actually provide better performance although I mean uh that's the point to discuss but but let's uh assume that they are very good candidates for this

kind of like um goal okay so as I said today I'm going to talk about canal and uh so let's give a bit of background about that so it's a very fast Library it's uh um zika it's not library that is written in go okay go language as you can see on the right this is a benchmark that was done by by seller team and excluding the outlier uh Starkey which you know it's kind of like a different place on the trade-off space you can see the gnocchi is very very efficient compared to other framework sites so we wanted to aim to aim high kind of like start with the best there is uh knock supports gold 16 and plonk you can see uh that also they have a very

very clean and easy way to kind of like use the the library um and we specifically for the sake of this talk but of course it's going to work with every circuit we use cellular circuit uh actually the old version of it for bls6 so just like you know many many uh signatures and again we use gold 16bn254 and something that is a bit more than two to the 23 constraints so it means that when it comes to entity you need to kind of like count it to 2 to 24. we'll see more about it soon okay so I mentioned code 16 therefore I should probably give some relevant background so this is got 16 is this ugliness okay luckily um today we're not we don't need to actually understand

everything that's going on here we need to focus just on the prover remember this is the part of the trade-off space that we care more about so double clicking on that and this actually by the way this is a diagram that we have in the company kind of like helps us to um you know make reason with with gold 16. so you can see there's a nice division between uh step one which is the question polynomial and step two which is kind of like where ellipticals becomes more reflect to finalize the proof and you can also see the it's also kind of divides nicely between the heavy operations the entities and the MSM okay so you can see that in the quotient polynomial we have several ffts and um on the other side we have msms okay again these are like the heavy lifting

of the computationally heavy parts of gold 16 and obviously the uh immediate Target for us to move to the GPU so let's do a proper breakdown okay so as a matter of fact we have five msms and seven entities or one MSM is in G2 so it's a bit more expensive like 3x okay it's like over extension field and our entities are actually like four of them are ints okay um now one point to note is that msm's you can see it from this like diagram can basically be run in parallel okay so there's no really dependency between them which is interesting and I will address it later about the entities so um there's something here also kind of

that is hidden and this is that entities should run or should be or using something we call like Twitter factors um and and and also like they can on the cost that are in sometimes and basically we kind of like ignore this uh the time to generate those we just assume it was like pre-computed and was like already loaded to the device GPU memory okay finally and this is important point is that there is an interesting distribution and when we move into a real world use case or applications you see there are like interesting distributions of the of the msms okay so some of them are easier to handle like zeros like ones um some of them are more tricky and I'll talk about it uh in a few more slides all right so now let's talk about what

exists today in gunak in terms of CPU acceleration Okay so we have few levels of acceleration first um is the parallel execution of msms as I mentioned they can add in palette and you can see on the table on top that the MSM total time basically takes uh the same or roughly the same as the um most expensive MSM okay so that's kind of like a high level uh nice trick and obviously it works when you have like this is a very powerful CPU by the way which we took for like our test steel uh you know 24 cores and so on so yeah you can take advantage of that lower level you have some primitive level uh acceleration and parallelization and this happens in another Library called crypto okay

remember that and here both for MSM and NTT uh you know state of the art algorithms are being used buckets method also known as pipinger and they take advantage of some multi-threading okay at different levels so bucket so MSN bucket metal this is very uh it's like embarrassingly paralyzable uh with entity it's a bit more challenging but still there's some kind of like core things that help you do that now the other part I need to introduce to you is icicle okay so what is icicle so this is a library for zika acceleration using Cuda enable gpus Okay now the idea is that we want to move as much as we can to the GPU I to the device from the um from the host we have two apis at the moment right so we have the rest API now

we also have go uh API and basically the design we have two like levels of of this like API so one of them is higher level like you can imagine uh facing developers uh where you can do you know polynomial arithmetics some operations like interpolation polynomial multiplication and so on and those the low level API MSM entity and such and I'll show you um very soon why we need both of them okay it will make sense and other than that we do have just like a lot of calls to GPU functions which are called GPU cameras now the library supports uh again vectorized arithmetic as I said MSM entity polynomial arithmetic level so watch functions and some like complex

structures like ecntt which is basically NTT but coefficients are elliptical points uh benched MSM like many many smaller messages and so on one reference application that we developed ourselves is for face down sharding obviously uh it's like third place it's not us it's like built on shoulders of giant Giants and we just like use this Library here to help introducing GPU into this Frameworks so now let's now that we understand the components let's understand the architecture which is very simple this is like the the goal here um so on the host side we had before gnark and Grinnell crypto remember now crypto entities are being actually

implemented now we um instead of icicle first we have the API it's called what we call go icicle and second we have the actual like Cuda um and chords to the device itself and to switch between the two we have this kind of like flag right it's very simple should be very easy for a developer point of view you don't need to think about like I'm working with GPU or what do I do we just need to say I have a GPU I want to support it right very simple there are two trade-offs that I want to just mention quickly one is about utilization so one point to consider here is that once you go to GPU and you get the GPU to become busy CPU becomes ideal all right so this is something that we might want to take advantage of uh at some later point because when you

walk only on CPU you can get like 100 utilization so we want to make sure that we are not like losing anything there another thing is about power considerations right so GPU introduces another device it has its own kind of like um power consumption that needs to be taken into account when you look on your like application and end-to-end solution okay so now let's start to uh understand how we do the integration itself so obviously the first step as I mentioned is just do a drop in replacement let's take the msms um let's take the entities and let's just switch right between before before we had in our crypto now let's call it Go icicle problem here's an interesting part of the diagram I showed you before so as you can see uh on top we have ffts and these ffts are on Grim they are executed

on the device then we are sending them sending them back to the host on red right then we do this kind of like polynomial operation this Vector operation right so we need to compute the points of H tilde and then we send it back to the device right for the ifft now what happens is that this data transfers actually take quite a lot of uh of time to do like compared to the computation itself so we want to eliminate those so the solution is very simple and this is exactly what icicle helps you to do with this like higher level API we just move this like part of H tilde also into uh the GPU so now we actually managed to save on this like back and forth between the host and the

device there's actually a few more benefits on doing that one is that the age is actually um very it's embarrassingly paralyzable so as you can see below we kind of like eliminated completely the running time of this like computation what we call the apollyops and also we need to account for the fact that might be that for GPU we do some kind of like conversion or we like mode to work with some kind of like coordinate system or do some kind of like different multiplication than the representation that happens at the host or like some framework decides that it's the best decision for her for it and we can save that as well by kind of like staying in the GPU okay so now let's talk about performance and for the sake of this specific example I'm using RTX 39 DTI

uh it's like last generation GPU but still starting with the entities Okay so what we realized is that well in the CPU running entities was done in serial this would what made the most sense here there's actually a higher level parallelization that can happen right so we can run this ift fft pairs you can see it like the the lro uh together and if you actually want to get to this like bottom like you know the four four one number uh you need to kind of like take the most expensive pair and add to the ift and some kind of like time it takes to kind of like move the data that is not really represented in the table but it's nice to know that like the design space changed a bit right once you move the entity to the

GPU all of a sudden it's not just a different algorithm it also makes sense to conflict change the parallelization I to fully utilize the GPU with msms so here on the other end while on CPU it made more sense to want them in serial uh so in parallel here actually it makes more sense to run the msms in a Serial fashion okay so why is that I'll touch a bit on that later but basically it has something to do with how we utilize the GPU if the GPU is already like fully utilized with one MSM like adding one more and adding another MSM palette won't help us okay and um here just for like sake of clarity I've kind of like made this uh table for

translation to kind of like show that like there is how we Define our msns like how we call them and there's how the uh how they are called in gnark code there's also some kind of like theoretical understanding of the size of those and also a lot of filtering that is happening which is very interesting uh to notice but I won't have enough time to go into the details of why this is what happens in real life like code 16. finally there's some kind of result and and what I want you to take from this is that I guess this is like three point something X I think that today we have like I don't know like 6X or something or more but it really really depends on the problem uh that you are trying to solve so remember

right now we used a very powerful CPU also um like class generation GPU with certain parameters it can be very sensitive to how we choose our setup and what we are trying to optimize for and to make this point again so let's look on CPU one which is the one we just used um and we can see the total approval time below now I'm going to use another CPU cpu2 which is even more powerful right more cores higher clock and so on and you can see to get a better proving time overall um I'm going to use now cpu3 which is much slower okay so you see the slower cloak although like number of calls is quite equivalent this is the OWN silver and you see that like approving time like jumped and on the other now with my

previous result of cp1 and CPO and gp1 we can get much better if we go into cpu2 and gpu2 which is again just like newer Generation Um still less string processing elements but higher frequency so it's really up to what is your design goal where you want to get um and and it's important to note that like basically what we've done here is we added something to the design space now if you have gpus you can kind of like uh I don't know think a bit more realistically on on your entire like uh application and how you want it to run final uh uh like departing thoughts some like implementation details in future work so first I think it's worth to

mention how the MSM works in the GPU so this is like a trace from from uh like a tool that's provided by by Nvidia I think the main point here it's like first no secrets I mean this is just an MSM like buckets algorithm um it's more or less what you had like as the winner of Z price okay so it's kind of like the same uh you can ignore the green part it's like just copying stuff to to the device again like we've done it like way before this is just like taking one simple MSM what's interesting to note is that most of the time spent in the GPU is like on this like um you know step where you need to accumulate and do many easy additions in different buckets in parallel right you sit here we spend a lot of time now I do

want to point your attention to uh one important detail that is not present in Z price which is this like non-uniform distribution okay so basically what you can see here in the in all of these traces like on the top you see what happens when you have uniform distribution okay so this is how we we think about MSM algorithms originally you want to say okay like let's say all the points are in the buckets basically of the same size which is very important for GPU because remember in GPU we basically take advantage of parallelism and you want everything to run in parallel and end at the same time it's critical however what we see in practice is that there's highly skewed distribution and not non-uniform distribution and we need to address it

so if we just choose the naive it's not naive but like the uniform algorithm for this like uh distribution we get much much worse times okay it's important and this is also after we do the like basic filtering of let's say removing zeros and like Computing the ones like someplace else okay so what we actually uh managed to do here to uh answer for that is tell the GPU to basically first do some complex sorting understanding like the different or understanding the distribution of a given circuit on the Fly and then we take the heavier workload the heavier buckets and we move them into a different kernel function which has more threads allocated to it so that eventually they can end at the

same time which for that we use something called streams okay so you can see that we are kind of like backing uh get back the times that we had for with the with this bucket averaging we get back the time of the uniform distribution okay the second point I want to make is that SMS today the MSM is at least for this type of circuit but remember this is just an example the Amazon fully fully makes the GPU fully busy like it's such a GPU so this is just the numbers you know it's just to show that we're launching we need so many more threads than what's available basically what it means that if you want to add more gpus you can cut the time right like 2 gpus would cut the time in half um finally there are obviously some points to improve some of them were

already improved compared to Z price our EC Edition modular multiplication uh something that can probably be optimized uh there is the thing about utilization of CPU so basically CPU is free for a lot of the time so we've noticed that moving stuff back to the CPU and running it in parallel to the GPU actually takes a nice advantage of the entire setup so this is important tight so as I'm saying try to look at it it's kind of like we had more Dimension to the design space um yeah and finally there's some kind of like uh different like you know components we can move and kind of like also optimize a bit more I think I'll stop with that uh happy to take questions and obviously big big

shout out to the uh Team for all the help and working together on this it was great amazing experience and you are also free to use like the libraries open source MIT icicle it should like we don't you don't need us just use it you have the API would love to help thank you foreign have you done any exploration on Hardware acceleration for Windows generation so I didn't I didn't get the question so have you looked into using a hardware acceleration for Windows generation oh okay thank you uh so if we looked into witness generation so I cannot say that

we've looked at uh definitely not like a delivery that we looked on proof generation it's definitely an open question at least for me and and my team uh I think in general like the point I'm trying to make it is that let's introduce gpus and let's see it and you know like improve the infrastructure overall and I'm pretty sure the Twisters generation can also benefit from it remember that we can also like make some impact I mean on the protocol designers like maybe there are like some you know best practices that can happen on how you do the witness generation so it's like for me a very kind of like open question like would love to explore it at some point hello

um I didn't fully get how you solved the latency bottleneck in terms of data transfer if you could quickly go back to that sorry you mean that you mean the uh this one yes yes um so again just like quickly reiterating we have here two parts like we just moved naively uh to GPU the entities but it caused us to at least like annoying um computation stuck at the host side that now we need to we need to address and it means that you need to take all these like big vectors like large vectors from The Entity result like you know back to the host and then from the host after computation back to the device that's an issue the The Simple Solution is to call the GPU

again but but you're not really going outside of the GPU you call the GPU staying on the device right you just like you know make different commands on how you want the GPU to be used so just like invoke a new kernel a new function that basically does this like in parallel this like computation of age and then like you keep everything in the GPU so you don't need to go back to the host thank you thank you and uh wait for the full ZK movie [Applause]