ZK9: Optimizing the MINA prover with learnings from zPrize top performers -Jiannan Ouyang (Snarkify)

Transcript

foreign [Music] from snarkify [Applause] uh thank you for the intro Alex and thanks for everyone for being here uh today I'm going to talking about our work on reporting the price top of top organizations to the mean approver the result is a library we call it Arc MSM it's a MSM implementation on artworks a little bit about myself some PhD in operating systems specialized in HPC and cloud computing a former Facebook

research scientist from 2018 I started to work on GPU and fpga based crypto mining so I have years of experience on gpuf and fpga acceleration starting from last year with uh pivot to zkp and start building snarkify our vision is to trying to scale out the ZK infra so on building large-scale proof systems for the decentralized future as well as ZK applications I'm also an empty collector okay about the background of the problem we are solving so we're putting the Press results through to artworks so the price of the right as you may already know is open source DK Hardware

acceleration competition it has two problems mainly one is MSM one is NTT uh MSM uh as I I will talk more about later uh has the sub has tracks on wazam which is rather than being a browser on mobile on GPU and on fpgas in this work we focused on the awesome side because we focus on the CPU implementation especially in this work I'm more focusing on the algorithm algorithmic organizations which is uh generic so it works on wasn't it works on x86 as well so it's um you can rent on on your native environment not just your browsers and we use bis12 381 in the stock our goal is to import the top

organizations to artworks used for Minna okay about the MSM problem basically it's a vector is a Dos product of two vectors one Scala vector and the one point Vector on the elliptical curve so for our work the Scala is 255 bit well the point has two coordinates well both of them are three eight one bit field the input size can be up to Millions okay this is a perpendra algorithm that's used in the Baseline as well as almost all the implementations of MSM including CPU GPU and fpjs so the idea

is of uh the type engine algorithm is to divide those K into multiple partitions we call it multiple windows so you can treat this as k0 K1 K2 and then you depends on the value of the K you put it into different buckets so for here the K you divide it into four bits windows so we need uh two to the 4 which is 16 buckets however you do not need back zero because zero multiply the point is zero zero so don't mean that bucket then you depend on this value you put the points into different buckets for example this one is here 14 then the other one are all put in this bucket

then you add those bucket it adds points in the same bucket together and then you add the buckets together with a wheat so you can see that g0 is I minus multiplied with bi then add them together this is the idea of the perpendra algorithm and this visualization from 5jk um so with an example more concrete example if we are going to calculate this MSM problem depends on the uh factor of the the Scala of this point you divide those into multiple pockets and then add this bucket together and finally you get the final result p and we call this a

procedure packet accumulation because you you are adding the points in the same bucket together and we call this procedure bucket reduction because you are adding the final value of different buckets and reduce them to one result as you can see in this example we will use the number of modifications from eight to four that's the idea of Passenger I need to emphasize that our organizations are built on top of this Baseline so the Baseline is already fairly fast but we achieved even more performance Improvement on top of this Baseline so about performances um first of all I need to acknowledge all the contributors uh first of all the price without this open competition

initiative um there won't be those much high performance source code and algorithms out there for us to use I'd also like to thanks Neil ayoma from the real software who is a first place winner as well as Gregor from over Labs who is the second winner both of them have their code Amazon and give us a lot of technical guidance on this project and finally this implementation is founded by Mina Grant okay those are all the techniques we implemented um as you can see the top the first place and the second place winners pretty much implement the same techniques um on top of the Baseline they Implement around five organization techniques

um well in this work in my talk we Implement all these four for the last one it was on specific basically you change the big integer representation in the field instead of using the default 32-bit nymph or on x86 it could be 64 Nim size we use 30 bit Nim size in for wasm because it was um instructions does not support certain properties especially to handle carries for other implementations we have other four tricks the first one is to use batch addition of fine points in bucket accumulation I mentioned before the second one is treat the bucket indexes or sign the integers a third one is to use bucket Edition Apache Edition again

in the bucket reduction step and the final one is use a technique called the glv decomposition so without further Ado I'm seriously introduced that we have achieved over up to 2x performance Improvement on a single threaded speed up over app works on x86 CPUs uh here is a graph of the detailed performance Improvement so the x-axis is the input size range from 2 to the a to 2 to the 18 and the y-axis is a speed up result um each column each color is um an organization you can see from the Baseline with one one organization

technique and two three and all of them we achieve different performance results as you can see there's little or almost no regression when we apply one optimization on top of the other each time we will achieve some kind of performance Improvement and overall our final result is from 1.6 times faster to two times faster that's the result we got and I'm going to talk a little bit more about the algorithms and organizations we used uh first of all the basic one batch addition we use it twice um I will discuss why it works so here is how the the equations how do you calculate two points uh with a fine

coordinates you first need to calculate the K which is Delta y divided by Delta X then with this K you can calculate the final XR and x y y r um this inversion is very expensive it's over 100 times more expensive and then the modifications here so that's why we want to immortalize this cost the way to immortalize this is to multiply all the data X together get a final result and do one inversion then you can calculate the Delta X the the final tags you want from this one inversion through this equation so basically you achieve the immortalized inversion cost depends on the number of

pairs of additions you batch together if you batch 100 additions you get uh um like um one one over at 100 or multiple cost then how do we apply batch addition in bucket accumulation as I mentioned earlier you first distribute those points different buckets as we show in this figure then we figure out how to add the points in the same bucket together um the the default or the matter used in some other implementations are tray based addition basically you build a binary tree of all the points and then use log n times of addition login times of addition to get the final result or sorry login layers of addition to get the final result

um the way we implement this is a list based addition you need to do more round of additions every time you only add the accumulator in the bucket and the top of the list and you can batch all the additions together because all of them are independent and in parallel so you can batch the additions from different buckets and achieve a multiplied cost with this implementation it's easier to implement than the tree based Edition because you do not need to handle the tree also we achieved constant extra memory usage because you do not to capture all the packets at the same time actually you can maintain for example we maintain maximum 4K batch size so as

long as we get 4k points in this green area we can start to do batching instead of waiting for you distribute all the points including millions of points into the green area then we need to handle the purple area we maintain a list of this uh we call the conflict points then we handle them later so that's the first trick the the other one is the same thing batch addition in bucket reduction so if you still remember that equation uh here I give an example of bucket reduction of 15 16 buckets and there's a visualization here and like Gregor from onavsk this gives this great visualization so basically this equation

is basically add all the squares or blocks here you add this last bucket uh 15 times where you add this first bucket one time so get the square of addition so how to add them with this batch addition first of all you participate those partition those buckets into groups here I'm giving an example of group size four then in try to like each of the group are then independent and we can calculate the additions in parallel so first of all we can sum of the calculate the sum of each bucket then we calculate some of them then in the end of this iteration you got this yellow area uh in installed in

the sum of sum and then we try to figure out how to calculate the square of the squares is done by like for each group in the reverse order you add all the sums then you basically get the sum of the width of the right blue squares basically four four four four four here then you multiply those by four you get the area of this Square then you add all the squares together you get the oh you add back the yellow triangles with those squares you get the final addition where should we apply the batch addition is here because each time this addition is independent and in parallel you can add them

in a batch and achieve a mortalized immersion cost that's the second important important trick um because of the the third one because of time I'm not going to all the details of the each trick for the Java accommodation because basically you'll find a property in the curve where you calculate Lambda multiplied by a point the result is uh equals to Beta and multiply by the way basically you reduce uh Point multiplication to a field multiplication that's cheaper so to apply this trick you first decompose the 255 bit together into two 128 bit scalas so you've got half the size of the Scala then to actually to calculate the fast

the battery reduction is used for faster module and with this track with this decomposition you can see this original computation can be transformed to two smaller scalas multiplied by two points p is the original point where P Prime equals to those endomorphism Point that's how the decomposition works and the result is that you can have the bucket reduction cost because you you get the same number of additions in the particular accumulation stage where you get half of the number of buckets in your packet reduction stage so that you can have the half of the cost uh this is a the final Shaker website

called the signed bucket indexes um the idea is basically trade to the the trade the window uh slice we call it slice in each um window as a sign integer so that you can reduce the the volume the value from zero to half L to 4 minus L over 2 to L over two and you get half of the bucket size that's a finer trick I'll put this online so you can check it later what's the learning scale first we need to really to document those tricks because even if I have the source code available I have to like re-digest what the tricks are there they don't have detailed

implementations however luckily all the authors they gave me a lot of instructions on how this algorithm works on every details for our implementation we actually have a per organization commit so that you can do regression tests on each of the commands each of the open relation tricks you can also study each of the tricks separately and finally we have a modular design with unit tests um it's like we are on the way to put it in a production ready track uh this is um like what I want to promote with open JK computer initiative thanks to the price um I was from the crypto mining award

where the increased mining is a zero-sum game people are very incentivized to get a Performance Edge over the community over the competitors so more often than not we see over 10 times of Advantage versus computer competitors because either of the project you have um like you have found around the community because you design algorithm you optimize it before others or when the communities are on CPU you can use GPU fpga or even build Asic and people are incentivized to not sharing the knowledge that's what I that's basically what I learned in the crypto community and across mining Community but this time in the JK Community with I'd like to and our company would like to do it

in an open way and after this work we are going to build a open source hello 2gpu acceleration solution for anyone who's interested in this work please talk to us okay without further Ado I'd like to introduce you to Arkham SM it's now fully open sourced it's available on github.com snarkify slash Arc MSM so like feel free to play with it and if you can come with come up with more organizations just create a PR and start it of course uh and yeah we are hiring uh if you are interested in Nova have two GPU acceleration fpga stuff uh please talk to us

yeah thank you [Applause]