ZK8: Fantastic Beasts: unfolding ZK hardware - Omer Shlomovits - Ingonyama

Transcript

foreign I'd like to introduce Omer shomovitz to the stage from igonomia I always have trouble pronouncing it sorry um he's going to tell us about Fantastic Beasts and ZK Hardware welcome thank you thank you so my name is Omer I'm the founder of fincon Yama this is how you pronounce it The Talk today is uh going to be packed I'm going to try to get as much uh information I can and Infuse it to you if I'm missing something or if you have questions feel free to reach out later

um I'm going to start with the scope of what do I mean when I say zero knowledge ZK zkp I'm going to use uh this word many times in the talk and obviously we have many zkps like in different shapes forms and um we can I don't know maybe divide them into several families so we have this line of work quick silver mistake Wolverine Ant-Man which is not the focus here it's not about these are I think uh you can classify them as interactive zero knowledge proofs we have also zero knowledge based on NPC in the head kind of line of work like and so on uh well fantastic work with really great performance

um again not what we look into right now when we talk about ZK in the context of hardware and even not Mali Nova got 16 and variations of Planck which are the protocols that we base most of our systems on what I'm trying to or what I want to focus on is actual systems that are let's call them production already or close to it and we have many examples to this in in the space right um here I give few of them so these are systems that besides just the ZK uh protocol that is in like the back end or something there's also significant software engineering effort that were put into making them uh meet real-world uh criteria

right um so we are used when we talk about zkps we used to kind of discuss or to mention the benefits and all of the advantages we get with ZK and ZK snarks stocks and so on right it can be in a small proof fast verification and so on however in Real World Systems we deal with asymptotic complexities that are no longer right now everything becomes concrete so we need to take into account all of this um uh into uh um into a situation right so what I mean by that first uh we want to focus on the approval overhead uh the computation of the povert which is the

obvious um kind of goal for acceleration in Hardware based on uh Justin teller block for s16z he estimated seven orders of magnitude uh overhead in terms of comparing to just running the computation on on a CPU right um he's done it kind of based on analysis of a front-end backend as you can see in in this figure now what it means is that we want to try and accelerate metrics such as matrices such as latency throughput and even memory I mean this is uh surprising there's this quartile for one of the papers that is not coming from the uh it's more from I

think from one of the systems that are for interactive snarks and and then I'll adaptive ckp and they asked them to in the reviewer ask them to kind of try and compare the memory for um to other systems there's a huge blow up I'll touch a bit on this later but we also want to uh try to optimize at least the memory consumption while Computing a proof okay now to do all of that we obviously have algorithms which have been around for a few decades now we have software engineering and we have Hardware which is what we want to focus here so as I mentioned ZK poover is the main the main goal of what we want to improve

is computation and try to accelerate it to make it more optimized or efficient and let's try to analyze what does it mean okay so um let's look at the cake this is when we look at the actual computation that happens inside of a prover so we have basically three parts we have the multi-scal multiplication we have the Fourier transform the entity and it is uh for a transform over finite fields and we have what I call here fluff right so this is the rest of it and I'll explain a bit about it later so to give a concrete example this is uh data from Rapid snack Rapids knock is a back-end based on goal 16 so we know

that there is pairing so we have basically two elliptic curves so we have two times MSM as you can see for G1 and G2 and the G2 is even more complex because it's over extension field computation and you can see that roughly for different sizes of circuits we get here like 90 MSM and and uh five percent to seven NTT and uh so it means that there's also flat fight so it's I guess similar I mean don't it's an estimation obviously it's it's nothing here is going to be uh concrete it's just kind of to give you a high level ID now another thing that's important to say is that this is what let's let's name it snark okay just for the sake of this

conversation um we can also look at something called the stock where um basically we eliminate MSM and we are left only with entity we still have fluff all right we cannot ignore it uh and also there are systems like like Nova where there's uh the opposite either there are no entities uh only MSM okay so basically all of them are based on the same uh computational problems now once we understand that let's try to build together some some idea on how to accelerate this prover computation okay let's um do it like step by step step by step together so we have the host and we have

this uh box that um is our dedicated hardware and and the first thing that comes to mind is obviously let's just accelerate the MSM right so we need to add some memory and and then so my Pico for the MSM but this would give us remember that we have like maybe 80 90 MSM so the best we can get like 10x if MSM is completely eliminated we get the 10x Improvement and this is not why we do Hardware I mean 10x is um uh is not is not a good uh motivation for uh going into dedicated Hardware so the next thing that comes to mind is after MSM let's also accelerate uh entity right

obviously the second big uh like Stone here so let's imagine that we had another block of memory and then this IP core of entity right now here surprisingly we get another bottleneck which is uh in the interface between the host and the the hardware right so I mentioned there's a huge blow up in the data that we generate inside of uh or as part of the approval computation and uh basically what it means is that the new bottleneck will become the speed in which we can and sell information between the host and the hardware right so again we're going to get some we're going to get stuck

so the only way that makes sense now is to also add the fluff right so let's divide the fluff into two parts one is some modules that we can accelerate here I'm gonna use an example of hash function a ZK friendly hash function that might benefit from acceleration instead of the fluff again for some systems this might be much more than five percent but for our mental model this is enough and also for some just filled computations uh let's also add some uh CPU like uh arm risk 5 code okay so now if we look at what we

got we basically have this um chip right that has ZK end to end right we just give it the input uh the statement the problem and then we get the output the proof itself now once we have this uh ID in mind let's try and look at specific Hardwares that we have available for us today and the first two I want to discuss are gpus and fpgas okay so graphical processing units and field programmable gate array um and let's try to do like a very high level comparison between the two so one thing is that gpus are almost commodity at this point uh they are everywhere

most of you guys have uh GPU accessible to you um in your in your Mac in your phone and so on and it's not the case with fpga although now we see this uh um fpgas in the cloud this is kind of becoming a trend and it makes the accessibility of this type of Hardware um significantly better another thing is the technology in which we use to generate to to actually produce uh to manufacture these chips so gpus um a few Generations this is just an example you can find fpgas with different Technologies and also gpus but basically here you can see the GPU I mean just like out of the box gives you

a way better uh performance you know in terms of how many transistor you can transistors you can stick inside a given area which also impact power efficiency and so on so this is another Advantage for GPU um another thing to note is that right now when we walk with gpus we usually use software uh we write like libraries on top of Cuda and such so it's a very smooth user experience or developer experience to uh to code in in a GPU while in fpga it's uh still conceived although there are ways around it but it's still conceived like a one-time uh programming thing and like each time you need a new design it takes like a whole uh a long time to actually get it done

and not as part of the same one however in both cases it's going to be hard to implement ZK end to end for different reasons right so FB so the GPU is uh simply uh not customizable enough when you think about doing together um the fluff that I mentioned the memory management the uh the MSM and the entity and for the fpga it's very limited in the resources that you get right so even elliptical Edition which is very important as I'll show in a few slides is something that can take up to half of the of an spga right and this is just like one very simple um mathematical operation so one thing that I want to also share is like where do we stand today in

comparison of performance between the two so I'm going to show you uh some of our results from our latest paper called pipe MSM and um what we chose to highlight here is uh like the cost per running one MSM so again first it's not an entire ZK it's just like one multi-scale multiplication of given sizes um you know the the size the the lens of the MSM is so much representative although we are interested also in uh lengthier msms but for example Elio is focused on the 250 to the 15 to the 16 and such so it's kind of like in in the same where we are it's in the interest area and you can see that there's like this efficiency um that you get will when you use this

fpga again what we measure here is this like integral of the um over time of the power consumption now few disclaimers uh one there's a huge variance when it comes to gpus I mean in in Hardware it's like the same thing uh every time but but the GPU really different if it's a consumer GPU or if it's a data center GPU and and so on second as I said larger vectors are also interested and interesting and finally um I already know that both in spga and GPU they're already way better results than what is presented here and I hope that maybe in Z price and other will see some of them right so this is a good point also to

mention to mention a third type of Hardware which is Asic right this is a an integrated circuit that is very specific uh to the problem at hand and this is probably the best chance we have to um to get this ZK end to end okay we know it's kind of one uh one signal that we have is that at least we know in terms of power consumption which is supposed to be 10x better uh when it compares to an fpga which is already better than a GPU so this is kind of comparing two papers that one was on Asic one on uh fpga it does not exist today one of the reason is that there's uh it takes like forever like few years to get it done to get actual uh Asic in

the market it can take two three years even and also there is this thesis that says that ZK it's a risk because ZK product was like a moving Target now I don't think this is the case but I won't try to argue with therapy to talk about it later all right so now I want to talk about specific implementations of in Hardware of physique Primitives of the computation that we saw before and kind of give you a sense of some intuition about what it means to write them down in Hardware so we'll start with the modular multiplication so this is like a very basic primitive we use it for all of the computation we

do so it's very useful to accelerate it basically it's just taking a times B and do some modular modulo queue okay so let's develop it a bit right so basically it's a b equals to some number that we don't know of times that we need to repeat Q come back do you want to try this okay so as I said this is the uh when we try to uh open it up this is what we get

in equation three this is our estimation so we don't know this number l so we need to estimate it uh so here we estimate it to be this L hat and we also have an arrow right because we might have some estimation error which we note as k just rearranging the elements we get that what we need to compute is this residual which equals to this expression at number four so what was commonly done before is the estimation was really tight like we wanted the estimation or at least like previous generations of modular multiplication wanted the estimation to be as good as possible our idea was to uh have more um slack in the estimation so we allow

the estimation to be with higher larger Arrow which eventually translate into this block here at the bottom it means that we need to try different values of K now what we gain is that in this estimation above L1 head we are able to break it down into two multiplications that are smaller Over N or n plus 1 bits so this becomes very efficient right so this is the trick that we are doing we kind of pay in a editions but saving multiplications which is exactly what we want to do in hard work another primitive that I want to discuss is what I mentioned about the EC Edition I'll show you I'll show you next how it

can be used but first let's try to think um what's the best way to implement it in Hardware so in Easy Edition we basically have coordinates and to represent an elliptical point we can have fewer presentations it can be two coordinates three coordinates we use the projective version which has X Y and Z coordinates and this is the um the equations that basically gets us from X1 y1 Z1 and N2 to the result to X3 Z3 Y3 now this is the circuit that we chose to use now there are two things interesting about it that makes it Hardware friendly one there is some redundancy in this equation so you can

reuse some of the operations the second thing is that it is highly parallel right as you can see here even visually it's very easy to parallelize this circuit and compute it in parallel which gives us Advantage when we walk in Hardware okay so this is the point I want to make here now let's move on to multiscal multiplication this is the expression above which is kind of like a product between let's say two vectors of one of vector of scalars one is a vector of elliptical points the common way to do it is by something called the buckets method which is a variant of pipinger and this is um this is our circuit this is the the core of on how we are doing it so I want

to explain it there are three parts to to the bucket methods um and basically the the concept is very simple right so we want to break again do highly something that is highly paralyzable so right now the way to paralyze it is first to break each color into uh segments or chunks of size C bits C can be I think here is nine and we can even do farther than that like what what's in Step number two which is segmentation even after we break each one of the scalaras into many segments we can break it even farther and parallelize it more when we do the actual buckets computation so

to be concrete as possible in this case let's say that scalar are size 253 beats and we take c equal 9 bits so it means that we have 29 buckets uh bucket accumulators this is the this is this block in um I don't know what color it is and each one of these bucket accumulator can be broken down as I said into let's say m equal eight segments so in each one we need to do we have like 64 buckets so this is exactly now what you can see is that first we have this easy Edition uh here in green at the end so this is something that we keep doing over and

over again this is like the um the main computation that's being done so we translated MSM entirely into easy Edition operations that are happening in parallel all the time finally by the way we need to accumulate all of the things together this is Step number three this is the final accumulation um which uh also like takes some computation time there is this cost function uh here at the end that uh kind of takes all of these parameters into account and uh allows us to also simulate and test many of the parameters I mean usually you don't want to just Implement in Hardware before you have your parameters are fixed okay let's move on to uh to entity so

here I want to I think I mean for me the best way to explain what is uh entity to begin with is by just speeding out the algorithm right for uh kulituke fft which is the standard way we do today this mathematical operation uh this is by the way used uh in in ZK mostly when we want to like multiply polynomials and so on and the interesting thing to look at is lines um 14 and 15. this is the the main computation that happens here like this is a recursive algorithm and you can see that you have this same operation of addition and multiplication in a constant right and the constant here is the roots of unity so let's try to take the hardware look into

onto this problem first thing we do is we unroll the um the recursion of kulituki and we have this nice structure so from this structure we can very easily see that there's this very basic building block right on the left that is in charge of or if you compose it in in in in the right way you can get a larger and larger entity or vector sizes of entity and this small building block what it does is just this operation that I talked about before it's addition and or multiplication in a constant in addition right so the idea here the the simple idea is just to have your Hardware with as many parallel

uh um we call them here sub entity blocks as possible obviously the sub entity block can be not just the basic operation but like uh one larger than that another uh parameter we can play with except of the number of sub entities we put in the hardware is also in Computing this um constants so one way to do it is by just writing all of them to Memory and retrieving them for memory but uh maybe you can also compute them on the fly so here in our um like cost function here we have this parameter that the parameter B that gives us uh this idea of how many we want to compute on the Fly versus how many we want to retrieve

for memory K here is is for the like let's call it parallelization factor and F is is just the frequency because obviously if we're running a higher frequency we can have like faster time finally I want to talk about the fluff so here I'm going to choose an example the Poseidon hash function which is a ZK friendly hash function and it's very common in today's ZK systems so basically hash function uh like Poseidon is composed of three different parts we have the non-linear part the s-box right like taking something to the power of five we have the linear part which is matrix multiplication and we have some uh manipulation with

addition of constants so here is our design and let me explain to you what we see here because uh I I know it's it's this is like probably the most complex uh that we have in in the slides so first thing to note is that this is uh a multi-core design right and why is that because usually when we use Poseidon in ZK circuits in ZK computation we have a miracle tree or this data structure that requires us to take one input or one output of a hash function to be the input of another hash function so this like ring design of uh ring topology allows us to take one output and connect

it to the next available hash module available that that can can take it it's also uh it's also multi-threaded right so here in the in green we have a few postal processors and the simple reason is that once you start processing a Poseidon hash then it takes more than one clock cycle so we have all of this operators or Gates available at some point so we want to utilize them as much as possible meaning that once we have something free we just start another thread with another hash so it's a multi-core multi-hash that allows us to handle um this tree-like data structures like

like mercury in a better way and uh what's happening in in like inside of this green box is a kind of like a general operation that allows us to do both all of the s-box matrix multiplication and addition of constants um like all of them fit into this uh this thing okay so obviously we need to handle memory um it's obviously important but basically by having this a times B plus c we can uh and like I can show you later if you want how every operation can be handled with like this specific box um yeah how much time do I have

okay so for final slides I want to wrap up by just pointing out some products like that are based on zika Hardware it's uh I don't know how much if it will make too much sense but kind of try to put it in a way from you know Hardware that takes huge proofs and make them like from hours to minutes all the way to uh you know just already very optimized and small circuits that you want to kind of run without um spending battery life at all right so obviously one of one of the uh products like the first one is this SAS kind of thing like uh running ZK proofs as a service

and this is something that that can can help for example ZK VM we also as I mentioned cloud based uh I Marketplace or fpgas is also something that we see on the rise it can be very useful for ZK app developers that don't want like they have the they don't want to do the um the devops they want just to get an infrastructure and and just have a ZK in their application uh there's also like physical let's call it mining uh machines for for some of uh ZK use cases today and as I mentioned uh there's IP core like take just one function let's say for decentralized identity that makes it like really really smooth and

just like use it in uh some other process so like like what you have in the iPhone that's it um I want to take to thank Lucas and yeah thank you [Applause]