WHIR Performance

Transcript

Okay, we're going to start the second session on especially talking about the implementation, the performance, the engineering and we're going to have to help us entertain this session. >> Yeah. So, yeah, let's get started. So I imagine the session I don't know >> problem. >> So [laughter]

in this session we are going to try to to talk about wheel it implementation the the details and try to see how we can move forward and yeah advance about different topic. So just as the core architecture of the repo. So we have we have a repo where we have basically all of the implementation of we um including the the primitives the provers the verifier and we are currently trying to upstream that into block history in order to maintain that as a public good more h into the code and more performance optimization.

So basically I will let Jako explain you about we just after that because I will not theory of having in the room. Yeah, of course. [laughter] >> So, we have like this uh we have basically one folder when we have all of the constraint system. will explain you what it is but basically it is some some constraints that are then transformed into like a lot polomial before going into the same check. We have a prover folder also where you can find all of the prover logic including everything run by round

the the same check calls and everything around the prover to the final generation of the proof. We have a verifier folder that contains all of the verifier logic. That should be really fast. Uh after receiving the proof with all of everything related to verifying, verifying the sum check, verifying the run baron thing, verifying the marker things. Um we have also like a committer dedicated file. This is at the beginning of the of the run where the pro where the user just transmits a polomial that needs to be committed in order to provide a weakness that then is proven by by the prover. We have a specific sum check protocol folder where

we have everything related related to the implementation of the sum check all of the tricks uh all of the tests uh yeah and we have also poly folder where we have all of the primitive related to polomials. So how do you define a multilinear polomials? How do you define multilinear points? How do you evaluate the test and all of this? We have also a fat chamir that is a transcript management things. We will have like maybe a short discussion today about this fam how we can upstream that into blank history in the most possible efficient and secure way. So basically these are all of the small parts of we implementation today.

If we go to the polomial representation we still have like a coefficient coefficient file and a wavelength transform that is that is here to do the integration and the transformation between the evaluation form and the coefficient form. So basically you can just represent the multilinear polomials as a vector of coefficient or as a vector of evaluation and both can be exchanged. But at the beginning of the implementation what we have done is that we we have worked about with the evaluation domain and then each time we needed to do FFT then transform into the coefficient domain and then go back to theation domain. But we found recently like a kind of some tricks to completely

remove the coefficient domain and just use the evaluation domain by by having like a separate DFT that is currently implemented in a separate file as basically a copy paste of long history version but just working on the evaluation domain. Um yeah and >> can I can I quickly ask you like what do you mean by that? Like the principle of the DFT is kind of like the purpose of the TFT is kind of to change between one from one form to the other, right? So yeah, but when you when you provide as an input the the elements that you want to to DFT, you can pass them as a coefficient of the multilinear polomial or evaluation of the of the multilinear polomial and then the DF the the secret

source inside. This is not the problem of the DST. This is a problem of the input that you provide of the DT. >> You can think of it about like basically the you have the input data the input data which is a polomial but is a multiar polomial and when we're doing the FT the FT is kind of like a universe physic and we don't really need so we're taking just the data of the multire polomial as the thing that we need to encode but we So we do but we also need to figure out what is the right representation of the multilinear to keep in our system and for the subject we usually want to do say an evaluation this is what we're doing and the encoding kind of like just takes the

data and the new but it's kind of like yeah so there are different evaluations and and coicient for the same >> yeah because when you see like the FFT uh that is the one we call from just as just the data as unar things. This is this different >> unar is the one maintained in our current repo that we plan to deletate.

Yeah. Just that you take the data which in the system is the for evaluation of a multin but you just take it as a vector of length to the n and then I encode it with a unariable. So the itself is always just the data interpreted remotely. >> Yeah. >> Yeah. Yeah. I I think this is also what people have been talking about. But for most polomials you can think of the coefficients as the evaluation of the zero infinity like hyper cube.

>> Um so so that this you don't need to convert anything. Yeah. And an important point to consider is that uh we have like a constraint system in the implementation with some statements. So you can see that Jako will explain more of the data after but like we have to have some equality constraints that mean at the beginning of the of the of your implementation you have like your polomial at certain points equal to certain to a certain number. a lot of these constraints and then you have to manage all of these statements and transform that into so we have this we just initialize the statement and then

we had some constraint points that means that at this point I should have a certain evaluation and then we combine all of these constraints into a big evaluation eval polomial that is then put into the DFT into the sun sorry and this part is a huge part currently of of the implementation if you run like a complete complete wheel run by round it represent like 25% of the of the cost roughly. So this is a huge part we are trying to to optimize this um then we have >> the constraint system is not air >> no no this is just constraints in the

sense of of weird this means like you also expanded but to replace basically the traditional like question things that you have in univariat in this case you just enforce the constraint directly as part of of the of the protocol and so you have like f of something equal something f of something else equals something else and this is what you have then to transform into into big pol like the the check module in the subject module this is also a place where We want to improve a lot because we have the standard sun check but on the top of that we can have a bunch of optimizations such as like the

univariate skip. This is a method like proposed by Angus Brien and the goal of this method is to do a lot of work at the beginning by skipping like end round something like five or seven and do a lot of work in the base field before switching to the extension field. For now we are trying to implement that and find the the proper way to do this. But we have also other tricks that are also studied by lambda class guys uh with other possible optimization around this subject. For now this is a huge part that we can optimize with also CID instruction inside the subject to perform some more operation efficiently.

>> Yeah. Do you expect like the combination of to make some more efficient be some challenges. >> Yeah, I I think that for now we have made almost all of the trivial change I think the protocol then everything that remain will be kind of challenging but I think that if we organize the code quite well well tested well documented and is kind of nice modules we can make that manageable. But for example, if you look at the if we look at the universe keep

un is a good example of that because this modifies the way that you see your your IP cube things and so the way that you see your polomial as a wall and so this modifies almost all of the code. uh other optimizations such as the bag and hard optimization that are studied by lambda class guy are much less invasive because they did they don't modify the verifier so yeah some methods will be okay some other will not for example if you think about cd optimization inside the sum check this will require some per architecture hierarchy this means that you will not apply the same instruction for neon and for lin stuff for example so you will have to deal with these

various architectures. So yeah lowle challenges let us say but yeah um so yeah I I I will talk about the open problem um I have classified them a bit with different level let us say at the beginning the less invasive one and at the end the more invasive one probably so we have primitive optimization basically this means like finding a better way evaluate multilinear polomials finding a better way to do for for example like a mer tree or something like that. So basic primitives optimization sum check

optimization this is very important in my opinion because we will benefit from that both in the PCS at the PCS level but also at the PIP level and on all the level of the stack paralization strategy I think that sometimes we underestimate it but paralization is really tricky when you don't play properly with the parameters you have some threshold where the paralization is is no more efficient and aggressive. >> Actually have a question on that point.

Um what is the bottleneck? Is it CPU or memory access? And have we make benchmarks like what is the CPU utilization? What is the >> I I think it's more CPU. >> Okay. But we we need also to investigate memory much but more CPU but yeah. Yeah. Um the issue is that when you benchmark and the bench the bottleneck is memory uh your CPU is still like to 100% for example uh FFT is typically a memory bound algorithm uh and I don't know who said that it's hard to optimize or it's very optimized but um uh it might be true for big field but for small field um we we likely need

to take into account uh L1 caches, L2 caches etc. uh and this is done um in uh FFTW uh for um floating points but I haven't seen any implementation uh for finite fields uh that actually uh are aware of uh cashier. Yeah, I remember you you sent me like a PR that was done on on your repo about some guy like trying to optimize that for example to put the threshold with the aware of the L1 cache uh and different L1 cache for example for Mac or Linux because all of the machine don't have the same L1 cache and so you

can play with that bit. Yeah. >> Yeah. I can also say so at least in PL3 I think we've both put a lot of effort into the FG but I completely agree that like I think you could squeeze out a lot more performance just because memory management is a nightmare. So two example on that uh I implemented the bit reversal permutation with cache blocking and uh I had 30% per improvement uh on the x86 CPU and another one is transposition. So if you do the nice transposition uh and if you do uh two dimensional cache blocking for matrices transposition uh you can get a 10x improvement uh because transposition is a memory bound algorithm. Um this is

something that is usually not known um in academia and not represented in papers. One thing that was helpful for us is we >> there's a button on the bottom you can [clears throat] >> uh we benchmark basically report the FFT time as a ratio with respect to the uh estimated time if you only did that number of multiplications. So if you just compute raw the number of multiplications required for the FFT um yeah that's like a useful benchmark to basically see if your FFT is any good arithmetic intensive you know

>> yeah similar to the teraflops it's similar to the teraflops that you do for matrix multiplication uh except that it's fops I guess >> sure I'm just this as like a strategy to basically check if you're like if you have more to gain. >> Do you know how close you are? Did you get close to one or >> uh I think so for certain parameters. I haven't this was like an intern who did it. Um [laughter] I think the three is a long way off one.

So I think >> would be worth knowing this number. >> Yeah. Yeah. Definitely. >> Yeah. Yeah. So yeah, this is part of this better implementation strategy definitely. Um, of course like the DFT is very important. I I don't know how much we can gain on the DFT. I in my opinion this was like very optimized for now. >> Yeah. Yeah. That might be maybe a garbage idea but just when you when I was now thinking through where I mean one of the costs for the DFT comes from that you do non-sistatic encoding that you know you

know you have this the first domain right >> second domain is shifted and even blown up. >> Mhm. >> So so what what makes a nonlinear time prover loosely speaking is you first do the folding uh you over over the smaller domain and then you need to extrapolate so two FFTs one one small and then all the calls at FFTs to evaluate so what about if you just take these values and do do again non-sistatic encoding it's it is not protocol but maybe something similar so because you so the way you ask this the new oracle outside by a point evaluation it's more

coefficient in that thing. So, I'm just putting this idea on the table. Maybe it's garbage because one has to be careful here. >> Yeah. >> But if I need to think >> something like this works out, it would mean you could save at least a fraction of the FFT cost. >> May maybe it's not a depends on the parameter. Maybe it's not worth it because you you increase the redundancy. step. So it's more like only small fraction for computing the coefficients from the values or if you had the coefficients >> how do you implement it actually

so so do you keep keep in mind like just on the univariate level >> you keep in mind the list of coefficients also besides >> and you do the folding just on the coefficients and then you we do that on the evaluation Okay, then my idea is uh forget this if you have any way that's probably the best way anyway. >> Yeah, we need to take back after this because we have also like a select trick that was proposed by by Jako where everything then will be played into the coefficient domain directly and we will remove the TFT uh that we have right now. And so yeah, at this time we we need to maybe revisit

what you just mentioned. Probably not. Probably not. Need to think about this. I need to think about this. >> If we keep everything in the coefficient domain, can we still do CD in the subject? Because CD is very natural in the subject if it's on the evaluation do. But will this still work on the coefficients? >> Yeah. Yeah. Exactly. >> You can't mod like you want to be in the valuation domain so you can multiply.

>> Yeah. That's that's why for me the trick is more natural if we keep it in the evolation doain to have CD easy. >> I think that this will not change for >> I think you have two polinomials you want to multiply them. >> Yeah. >> Yeah. >> That's what >> I think we defin but you could keep also with the coefficient just for the sake of >> but then you have to do like you have to a lot of jump back and forth >> because currently there is no coefficients at all. Yeah, currently I mean that's not worth it because it's memory plays a role but but currently you know you start with

with your values over the evaluation domain don't talk about the hyper >> thanks so so so maybe first better to settle uh to make things clear you identify you use this version of where you identify uh hyper cube values values over the hyper cube as univaried coefficients as normal coefficients right >> okay so so you take hyper cube values take them and direct these coefficients evaluate them over the evaluation domain uh for the code

>> so so now comes the first folding step >> so the thing is that uh we want to encode it's not like you know where where you just make the folding by value and get which is a quite cheap operation no FFT involved and you get the values of of the random linear combination of all them even over the smaller domain. Now we we we could do that also to forget about the uh about the coefficients uh but then we need for the extra relation step to increase redundancy we need to first compute the gain coefficients and then to the extraolated values.

>> So maybe it makes sense to keep >> I think currently what we're doing we're keeping the coefficient the the multilinear >> the valuation that are interpreted as coicient the sum check we already need to fold them so >> yeah so you have it and then but we already doing that and then we are encoding go with >> present round so you always like keep uh you need to keep So you don't you so you can skip one FD. We never do an invert back.

>> Understood. >> Thanks. >> Just a small thing. But if we suspect that there may be some problem with the cash, we can just measure it like maybe add to the pipeline something that measure like how many cash miss having and that's it. Yeah. >> Because I think going for a two theoretical approach maybe it's not needed like faster to measure. >> Yeah. Yeah. >> I and yeah maybe we could have like at the end Yeah. First Jakumo we talk about like reminder about we and everything like so that you have a clear

understanding and then maybe three topics that we could keep for the end. the fam maybe compatibility with PLR history. We discussed that a bit a bit yesterday but let's finalize the discussion here um also like uh yeah PR history integration it's directly dependent on this so this will flow naturally after that and maybe the very last question that we could keep for the end what could give like we have 2.0 yeah so yeah >> okay I mean So I think my plan is to give like my plan is to write down like a version of word like the simplest

version of it which contains some of the complexity. Then we can kind of like talk about what things right now there are indie games to to go to go on what things are other games and Yo.