ZK11: To Compute or Not to Compute on FPGA, That is The Question - Vladimir Marcin

Transcript

[Music] hello everybody my name is V uh and today I want to talk about uh some advantages and disadvantages of computing on fpgas in the context of zero knowledge proofs so basic motivation is that uh zero knowledge proofs right now and uh are slow and expensive so uh if we are talking about expensive we can di uh divide the costs into two categories uh first of which is onchain cost and this only holds if we are talking about ZK proofs in regards of uh scaling

blockchains and uh here we already have some kind of solutions by introducing blobs we were successfully able to uh reduce the cost of L2 transaction and the cost of verification can be successfully reduced by aggregating multiple proofs into the single one and amortize the cost of verification of these multiple proofs with offchain cost uh yeah we can divide this offchain cost into also some kind of categories we need to pay for the hardware we need to pay for the energy and uh we need to somehow manage this uh like heavy Hardware in order to accelerate the zero knowledge proofs and uh currently the trend is that the big

projects are willing to pay a lot of money for heavy Hardware in order to uh reduce the proving cost however uh from our point of view it's not vable to the Future so our goal is to build cost efficient appr uh without sacrificing the uh the speed uh next I want to talk about our uh fpga journey and in order to do so I am using the MSM as the main bottleneck everybody surely know what MSM is so I will just demonstrate our fpj journey using uh MSM this is the main bottleneck it can takes up to 80% of the

computation of proof uh within ZK snarks uh the best algorithmic way how to compute MSM is Piper algorithm it guarantees us minimal number of group uh addition operations and uh this Piper algorithm is splitted into three parts uh where the most computation heavy part is uh bucket accumulation you can uh notice that only bucket accumulation is dependent directly on the size of the instance of MSM and this size of the instance this big n can be pretty huge in practice we are talking about 2 to^ of 25 or 2 the^ of

26 for real-time use cases uh the other two parts of the algorithm are only depend dependent on this uh C constant and this C constant comes directly from the piper algorithm where Piper splits the big scars inside the MSM into these chunks and the bid width of one chunk is this C constant uh in practice we are talking about values like 15 16 17 uh the main uh point of the P panger algorithm is that each column of this bucket accumulation table can be processed uh for F independent and in parallel and each uh column have uh its own bucket Set uh which is also

completely independent now what's the main goal of uh this heavy uh computation heavy part this bucket accumulation part is to sorting the input points into these uh buckets so as you can see in the example uh the column uh the cell value of our uh bucket accumulation table gives us the index of bucket and we just add this point inside the bucket and uh by adding uh points to the bucket I mean we are performing uh elliptic curve addition operation this is static operation where the inputs are fixed uh

there is no branching inside this operation so it's like textbook example for fully pipelined architecture uh with fully pipeline architecture for those who are not familiar we are just splitting this one operation into multiple stages and each line uh in the slide represents the independent instance of uh uh our elliptic curve addition so we are processing multiple uh elliptic curve additions in parallel and with each clock cycle uh once the pipeline is uh fully filled we will get new results by with PR clock cycle and this fully pipeline

architecture is like tailor made for implementation on fpga as we can achieve Almost 100% resource utilization to achieve this 100% utilization we need to be able to fill this pipeline uh like uh at all times uh and in our design the main uh point is this EC Point Adder which is the yellow part in the image you can see so it's like the biggest part of the whole design so we need to be able to uh fill the pipeline at all the times of this e uh problem where uh we are not able to feel uh to achieve this 100% utilization is when

there is a conflict in the input data and by conflict in context of pipe panger I mean uh there can be a situation where we cannot use like uh input data directly uh inside the erer so let's simulate our uh uh uh pipeline architecture so at the first stage uh we are start uh we start by adding 0 Z to the bucket 3 next stage two we are going to start adding 0.1 to the bucket 10 and uh at the stage three there is a conflict uh as I told uh to finish the elliptic curve Point

addition we need 100 stages so the result for of the first addition will be available after 100 stages uh so the third line will get us the wrong result as we are using the old value for bucket 3 not the new one so there is a clear data race and the result will be wrong uh we need to postpone this uh bucket uh after these 100 stages and uh we need to find 98 other non-conflicting additions in order to fuly utilize our Pipeline and now uh let's take a look what can be achieved with this pipeline architecture so let's imagine this 100% utilization which is uh not uh like

achievable in practice but we are very close and uh let's imagine that one stage is for NS it means that our fpj will operate on 250 MHz frequency and uh if we take an example of MSM instance of size 2 to the^ of 26 which is 1 billion EC editions we can process these 1 billion EC additions and 4.3 seconds uh the like Clear Choice how to speed up the this operation is to increase the frequency however then the memory will became the bottleneck so we were we were not able to fill up the pipeline because the is too slow to keep up with the

E so what's our solution is uh to use this multi- channel design which we came up with I won't go into the details uh but the main idea of our multi Channel design is to process multiple Columns of our bucket accumulation table at the same time so with more data available uh we can fill the adder uh easier and uh quicker than just with one Channel design uh as I said at the beginning all the columns are independent so there is no conflict between uh uh The Columns itself also the EC add is completely independent component

inside the design so there is only one fifq which is filled by all the controllers so the data is uh available for this e to process uh instantly uh and uh faster than with one channel design what are the main advantages uh the first of all we can reuse the same point uh multiple times uh all the points are stored inside the main memory inside the DDR memory which uh is pretty slow and uh with one channel design we are going to use every Point only once uh with multi- Channel design we can use uh one point number of Channel times so that's the big

advantage and the second advantage is as I told uh as I said uh each column is independent so uh there is uh quicker way how to fill the pipelines without uh collisions uh some results with our multi Channel design we are able to achieve up to 800 million EC additions per second so we can uh clearly like easily utilize two e adds at a frequency of 400 MHz if we have enough ources inside the fpj so we if you have big enough card to uh fit up two eers uh with this frequency uh it is like possible to go up to 800 million e

additions per second uh again if you translate this into our 2 to the^ 26 MSM instance uh we can process all the 1 billion EC additions in 1.3 second and now uh what what uh is our takeaway from working with fbga I will compare the fpga and GPU as only uh two possibility of how to accelerate ZK proofs right now because as6 is still working progress so uh from the development uh side of uh side of things uh the cost of fpj development is much

uh higher than GPU development as uh it is the direct consequence of the time we need to finish the fpj n2n solution opposed to GPU as with GPU is basically software development uh plus some uh uh you you just need to write Cuda code right and with fpga uh just uh creating this uh image building and testing and debugging it can takes you to tens of hours uh just to just building process regarding the hardware price uh also so you can notice that fpj can be like uh almost two times uh uh more expensive than GPU

cards uh and what I want to emphasize is that uh the end to endend proving is fast so we did the benchmarks where we used the GPU accelerated MSM and NT for nend to end prover and you can see the utilization uh in the image uh there is a lot of idle States in uh end to end proving and with f with GPU you can reuse the same device to accelerate also these uh Parts by just calling different carels uh but with fpga you need to buy like new hardware implement the new algorithm and somehow uh connect this to your endtoend approver so the cost of fpga end to

approver can be much much uh higher than the GPU approver and also what I want to point out is that in practice even for MSM only there are architecture we are using like multiple fpg for only uh msms and uh here are my very rough uh estimate of the cost what can we buy uh for more money if it's justifiable uh it's the question for you if it's good enough to pay this kind of money for gaining uh not a lot of time and uh what I want to uh also emphasize is that uh this is MSM so even if we get rid of completely of uh without MSM we have ENT

improving without MSM we can achieve only five times speed up uh if the MSM takes uh 80% of the computation uh so our main takeaway is that uh N2 proving is hard and we need more General Hardware uh than just uh uh fpgas which can Implement only the specific part of the algorithm so we believe that uh the margin Hardware is the right way to take right now also uh the other thing is that uh we still don't know uh with the what Pro is the Clear Choice who will be the winner and with marginal Hardware you have to you you can uh like accommodate accordingly

so uh yeah end to proving is hard and uh we are working on improving the uh other parts of uh uh of improvers as the msms and entities are not only battl right now okay thanks a lot yeah we have time for one quick question hi uh thanks for an interesting presentation um I have a question about like typical uh

typical use case for fpgs and if you've tried uh different different kind of things so uh I mean these these fpjsangprobinsyano so what about and and we heard today like an interesting talk from uh uh from from Justin Drake uh about like having the foolproof uh essentially on a dedicated Hardware so what about like using uh the the the the other uh type

of fpgs that have already like a general purpose computation uh uh course uh to perform uh for example the the other tasks to perform the front end uh from the from the prover and then using uh uh the programmable part of of fpga uh really for the dedicated uh acceleration of critical functions so so that's that's one question and another you mentioned I'm I'm sorry for sticking two questions into into into one uh uh another one is that there is also like an argument uh for that fpga's uh versus asix they can be reprogrammed and and today's fpgs can be re program very

quickly in a in a ballpark of couple of seconds so if the workloads allow this we can also have multiple functions it's not of course as fast as having like multiple course on gpus but you can actually reprogram have have you maybe tried this and like if you can comment also on this one thank you yes so I will start with the second question we we haven't tried the reprogram fpgs but uh still with uh if I compare fbga to ASC uh the cost of ASC will be much much lower than fpj so these highend fpj cards can cost a lot so that's the main reason why the fjs will not be used I guess in the long uh long run and uh regarding your first question you asked

uh about the fpga with the arm course yeah yeah yeah so there is still a question that you would need like again highend fpga to to be able to fit all the accelerated part uh to the fpga and offload uh as we can see now the problem is that uh The Accelerated part the MSM and entities takes like uh they are pretty quick right now so the heavy task is on CPU so we need to somehow accelerate also those parts and not to offload them to the uh like bigger cards or something like that okay thanks a lot everyone and let's thank again Vladimir if you