WHIR Performance (workshop)

Transcript

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 are easy games to to go to go on what things are harder games and then we can see and can you guys see Okay. >> Okay.

>> Okay. So I'm going to talk like there are also the current optimized version of work with some of the things that are not in the paper but then we found out later and then uh yeah we can tell you a bit about what's going on. So we're going I'm going to think it for a PCS for the moment. There's some optimization that where we don't think it about as a PCS but then we can go on later. Okay. So suppose I'm giving some multivariate polomial multilinear polomial in I'm going to say m variables you want two >> uh I'll start with this one and then it will just keep rotating for those things

>> exactly mirror I can yes okay so where we have like two parts so a commit space in an evaluation phase. Okay, what's the commit phase? Okay, the commit phase. Uh, so first of all, we're going to be choosing some R sol say over a same field over some domain and my and I will want it to so the first thing I want to introduce is some value K. Okay, then this will be the folding factor.

The folding factor is important because this is like how how much can the word fold in the first round. So at each step when we're going to be so k so if I if k is one I'm going to be folding by two. If k is two is going to be folding by four. If k is five I'm going to be folding by 32. This read solomon code needs to be able to encode two to the m minus k values. So this is to the m values. I'm gonna like think of it as like this is a matrix in which I have like 2 to the n minus k and k right this is what I should have in in mind all right my commit procedure will be

that I will commit to an inter resolver so uh effectively what this means is that like uh I'm going to let the code f and will be equal. This notation is means they inter things and I'll explain what this means. This means that I basically look at each row and I encode each row individually. This is fine. Then I will send like um row. So I will do a miracle commitment of ESA. This is my commitment.

This is not actually done because we're working in list decoding. So you need something more. Need an out of domain sample. What's an out domain sample? Well, the verifier will send me will send me some randomness and I'm going to keep it a bit unspecified because we actually have a lot of freedom in how we choose this and it's not exactly clear clear what's the best way for efficiency and soundness. a fire will choose some challenge and then the prover will send the value of P on this challenge. So in this case, okay, let's say for this one I'm going to just say I sample a multi a multiar challenge and

I'm going to just the prover will just send this. So my commitment is the Merkel root plus this value and of course it will be done by Kimir in reality of course. do this point. Can we live in a smaller field and then to verify a larger field? >> Yes, absolutely. Absolutely. Like we can say that this is over B and over S. >> Yeah, I think this this is one of the first optimization we have made because this is more convenient to have everything directly transferred to the extension field but this is not performant at all. Yeah. So up to this point we keep in the base field.

Exactly. So these are like kind of like base large field modifications. Yeah. Alternatively, you can also play around with this. So in reality, I can also choose S1 up to S L and roughly if I do this like I get like I can choose smaller like sample sets. So for example I could choose this to be field elements but then I have to do more of this. So there is one trade-off I think in some of the old version of PL something you can also do in fry is not really learned but usually what we end up doing we sample uh two I think in the current implementation two main samples so think

that two out of domain samples and so this invokes two multilinear evaluations okay so this is basically the old commit phase of work so here there is Not that much you can do to optimize, right? There's the FFT, you know, you make a you make a better FFT, you get a better protocol. There's a Merkel tree commit. So if you have a Merkel tree, better Merkel tree, you do this. We we also gain there by doing packing inside the ML tree. Initially, we add no packing. But then when when you h the leave and everything of the M tree, you can do packing of the hash function you

choose. case and you gain a lot. >> Also something is that in our case we need to have like for the recussion reason and so if you choose check or black trees there it will be much faster but we cannot and you also of course like when each of the leaf of the miracle tree will have side to so this is like a miracle tree. >> Sorry I was just gonna ask you what you're saying. No, I'm just saying like the the Merkel tree I want to commit with like leaves to do the K. H. So depending on my choice of K this might be a bit of a base elements but this is the Yeah, you have to take care of this.

>> Okay. So row is what the flattened multiar coefficients >> this one. >> No no the row hat or whatever >> row. Yeah. uh I'm going to be thinking about is the d represented in row is the evaluation of row over the binary iq. >> Yeah. So lrange but you implicitly flatten it or maybe not but regardless then read solen this is c to the k. >> Yeah. Didn't they interle okay and then >> okay >> okay and then two the verifier samples two points. Yes.

Yes. I called >> I don't know why there are dot dot dots, right? >> Because you could do more. So basically the error of this step roughly is the uh the list size of a anyway it's the same matter times ms. So this is the error you get in this in this uh step. So uh roughly you can you can very efficiently amplify like if I instead of this is >> okay >> and then row hat of s means what like a

univaried evaluation. >> No no in this case I'm doing a multilinear. >> Okay. >> But you can also do a univariat you can do a multilinear. You can do your favorite thing like in fact Does the verifier even read that or is that only used by the emulator? Like what does verifier do with with row hat of s? >> Uh so at the moment it doesn't do anything in the commit phase. It just reads it and starts it. >> Then later on when we do the evaluation we will prove this as well. >> This should be si for each si you right? >> Exactly. Yeah.

>> Yeah. >> Y is equal to so you do all of them and this is the old commit phase. So like my output of this is Uh the the commitment to f and then y1 to y point of freedom here is that this thing actually works for anything which is a epsilon bias generator. So you can choose like univariat evaluation, you multilinear evaluation. You can you have a lot of freedom of this. You can use select actually funny enough. You can also use select here.

There's a bunch of different choices that one can make here. Each of them will give you like slightly different errors and slightly different things over here, but I think the multilinear setting gives you a pretty good error without much uh drawbacks. So to me, this is a a relatively good one to start with and it'll go kind of well in this point because so this is the commit phase. Yeah, there's another optimization here which I can tell you in a moment. So in our protocol right we will have prover and verifier like at some point the prover will send a commitment to its witness which I'm going to assume

is some multiar polinomial something will happen usually a sum check so there will be some check here and then at some point I will have to prove the the w at some random challenge that comes out of this check say gamma is equal to some for simplicity. So, so I run this commit phase and now I want to prove this. >> So, >> sorry. >> Yeah, >> a small question. The bigger the bigger a list is the larger the commitment.

>> Yeah. >> Is can we actually fold them into like one field element by taking a random element and just you know taking >> the biggest You can but this thing this L will be two or three so it probably is not worth it like I don't think of a setting in which L can should be bigger than two. >> Well I mean there is a world where you make a large you sample the base field. >> Yeah absolutely >> like I think that that might be very interesting because then your base >> exactly potentially work a lot better.

>> I think so especially because the sound check will we'll see the sound check. >> Exactly. >> That might be something we should do. >> Yeah. then >> yeah we we can get to >> yeah yeah >> let me think why out of doain why need to be out doain you said two of the things should be out of do >> yeah so these things are the other main sample >> why why should be out >> so because effectively when I'm doing reduction so I want the prover to commit to to my witness and to me it's important like when I commit there's only one thing that the prover has committed to So in particular, you know, suppose here like the prover could send you like something which is like not a

real code word but something which is corrupted and then there might be many different close things to it. >> You're helping the emulator you're giving the emulator more content to work off of. Yeah, but my question is like since this stuff is like not interactive, what happens it starts to be into the main because like in the in normal like fry you use like what is this like deep deep? >> Yeah. >> Do you have a trick that you >> so this is effectively is like deep okay it's like deep to you need to you know >> another domain sample to eliminate pretenders. I just want to make sure there's a single one and I'm happy with that.

>> Right. If you didn't then just for intuition the emulator has nothing to go off of except for this row. And by list decoding there can be many um code words that are near um sorry not row but what did you call it? >> F yeah >> there can be many code words near F. If you didn't submit more information then there's no way for the emulator to narrow down out of the whole list which is is the right one. >> Exactly. So now we have like this is the initial part.

>> So one one small question. What does out of domain here mean out of the hyper cube doain >> out of the L? So for me like I will queries >> slightly different but yeah this makes more sense in the unar setting but it will make sense. So if you think about the R Solomon code >> right Solomon code they're evaluation of some univarial polomial and I know them on L. So this is my in domain things. >> Oh I see >> if I were testing them in the rest of the field they would be out of domain in this case this doesn't really match because this is a multilinear point and not a unitary point but uh it's because morally this they come from the same

place. So we still count them as out doain like >> so each component of that multilinear point is coming from the from the outeration. >> You here are bit things are a bit muddy for the reason that basically originally when we were doing these things these were actually we would tell you the the prover to interpret as a univarious thing and then each one of them will be a single field element.

>> Okay, >> turns out you don't need to do that and you get better soundness but the name stuck without the domain. So, so this is like I'm thinking of the I'm keeping everything multilinear the univariat part is going to be important and it comes in because of the rich Solomon but not for this part. >> Okay, >> but I'll explain where this comes in. Just just a quick question from my side because I'm trying to sync with my own variant of word that I have in the base paper. Uh so the difference is you directly commit interle so that you spare the cost of a large FFT.

>> Exactly. >> And uh where's the folding refer randomness? I didn't get that one. >> No, we're not there yet. >> We haven't folded yet. >> So you so you because I I have it in a in a different order. So in my version I first get the folding randomness and then it's about the out of domain. >> No for me first I commit I do the out of doain sample and only after that I start folding. >> We haven't started word yet. >> Ah so this was already forecast. >> Right now we're encoding a polinomial P.

Yeah, we're taking it out of domain and later we're going to use word to prove that P is close to >> so nothing no verifier randomness yet >> so far just for the out of domain. >> Yeah, but that's already different than to to the version. >> So we're just setting up the statement. The statement is I have something that's close and the evaluation at these points is why I did it differently. So for for this like we can chat about it later but the way I think about it when you commit you then you do the auto main sample because that fixes a symbol weakness and then only later on at the very end when you know which point you want to prove then you start the the things which also will go to the main samples I will see.

>> So I I just switched >> only commit comes folding. So you commit uh with only the start with other domain then you fold and you doain >> then then then you fold to get the folding randomness and then uh then you get also the question for the out of off the fold of the fold. So it's >> yeah I think it probably also work. Yeah I think it should >> what's the security proof is I hope that this is not a big >> yeah no no I think uh yeah should fine but the advantage is that the auto out of demand sampling is on the So it's like easier to compute in your case >> for that

>> maybe >> the adversary now has many polomials close to you fold them he has like higher probability of something bad happening with the folding >> that I was thinking that that way so whatever you have committed you know uh just as set values don't talk about approximates and pol it's it's it's it's the predictor for for not in domain evaluation for the next oracle. >> It's really the predictor >> like I think what would happen if you do that >> uh you actually needed to if if you say you have a proximate for a new oracle >> I needed to choose one of them to have

consistency with let's say not just few samples but with a large subset of of No, I think you can do with that. What you get the difference is that in the with this approach you get the error of the polomial does not depend on this side. What the way you would do it in the case you work with like a list IOP so you pay like some more errors there you still can handle them and then later on uh you can do a cheaper automation sample. Both things work but let's continue. I'll finish the >> Yeah. So okay. So now we have like we want to open with were and it's important to figure out what are the claims that we care about. So as a PCS

so we have like I'm going to actually rename the weakness to P just for consistency with other things. So you know we are doing multilinear we only have one tool which is check. So what we'll do it will turn all of these claims. So we have three claims well two claims. We have the auto domain sample and the commitment and we have the things that the that we want to show. >> Wait, sorry to to rush in here. >> So what's the S? So it's it's a multilinear. So so so is this the evaluation query?

>> No, this is the example. >> This is already part of work. So not of the plane to be opened. H this is part of the comma to be open >> claim that P of S equals Y. >> Oh okay. So so >> interactive commitment phase in which the verifier samples random evaluation points but these are not the evaluation points. We haven't we haven't even begun the evaluation. >> I'm just committing. >> Okay. So no evaluation proof yet. It's just it's just the preamble. I have committed to something.

It might be even non-random the S. No, >> no, you need it because I need I need to for short zip the the list. >> No, no, no. Because I need to identify one single element of the list >> for what? >> Well, because I need to to do the automated sample. This is like I need to identify one single element in the list. I mean the commitment could be thought in a wider sense. No, >> but so you don't like that's what's in in the red sheet paper. It's it's yes. So if you if you so here I'm for a polinomial IOP in which the provers a single unique polomial. This is what the analysis is. You can think of like list commitments and this is what red shift

does. It's true. You get some worse error. But I'm doing this at the moment just for >> you want to have really a standard PCS. I want to have I exactly I want to compile that standard. >> So then we we're talking about completely I was addressing completely different. >> Exactly. Yeah. This is for like the unique case. >> Yeah. I agree. We can do it for the list but we need Yeah. Okay. So we have some claims and the claim that I have is that for all I in L pi at SI is equal to Yi. And then the claim that comes from this commitment stream which is that P at GMA which I'm actually going to call it F0 because I'm lazy is equal to Y Z. So I'm going to

move here. these claims by standard uh by standard standard tricks in multilinear this is a they're equal to like the claim that um uh for all I now I'm going to put in up to zero up to L the following some checks go s i b * p is equal to i Is it the usual trick that you do in like into in the multiar subject? I'm just rewriting these things in this way.

>> Right now, so s is going to be right. >> S not is going to be an >> s is the actual evaluation. >> Yeah, exactly. >> So there is another trick we can do to turn that turn that bottom one into like a selection of base field things which I think we do do in which >> because you do like uh you do you run many sound checks. Well, like an extension build point is the same as like N base field point just P base field. So you split it up into >> So if we do that then the egg that is on the subject base field and then it will be much more friendly to the unar >> because right now like the step between like on the right and on the top between

the the constraint that you wrote there and the egg polymer that you there is 25% of the of the total. >> So like getting getting back to the base might be >> yeah it's something that we definitely should try. The other thing you can do which is what also saying is that basically if you avoid the domain samples and you pay a bit more errors over here which you often can afford. You can often avoid this to have like these initial domain samples in this part of the protocol because you can work like with the yeah you pay a bit more errors here but it's kind of usually fine.

S S S S S S S S S S S S S S S S S S S S S0 Z. Yeah. >> Is it also the verifier? >> Yeah. S usually what happens is that you run a sum check and the sum check randomness will become your S0 and I just Yeah. Yeah. This is like what happens in the protocol. I just reindex because I'm lazy. Okay. So now we can start thinking about the open phase of work where I kind of like open these kind of things. So the protocol itself is I want to say not too bad.

So okay, what's the first thing? Well, I have many claims. I don't want many claims. I'm going to take a a random combination of them. So this becomes uh the claim that uh whatever sum over epsilon to the i of some bah is equal to some epsilon to the i of yi. So this is this is the first step and I can do it. No, there's not a problem. Then I'm going to start reducing the problem size. So what I'm going to do I'm going to do a sum check. So but not a full sum check. I'm going to stop it.

When I'm going to stop it after k rounds. So my like K will determine how many rounds of some check I do. So I can do you know simply H1 then I get gamma one up to HK and then I go up to gamma K. Here there are some tricks that you can play with K the variable K. So you can stop soon or later like the sun check so that you can give more work at the beginning and less at the end.

>> Exactly. So yeah here you can do you can play a lot a lot of tricks around here. You can also defer typically the there's going to be another FFT well another few FFTs. So also having this large that are like cheaper and not bad like the trade-off is that later on when we query by the verifier the verifier will need to read the column so we don't want to make this too large because otherwise each query the verifier will read a lot so there is like a a proverifier time tradeoff like if you make this square root of n for example then you get big error I mean which is nice okay so cool So what do we do now? Now we you know we we folded a

bit and if you think about it if you look at these claims what does subject do? Subject will fit some of the values of beta to the gamma z turns out that if you look at the at the evaluation is multiar polinomial this will also get like folded in exactly this the the same way. So what I will do now I will send and I'll tell you exactly you can even just I I I will run here commit of pa sorry not alpha

gamma where gamma is gamma one to gamma k. So what I'm basically doing here I'm uh taking so taking my my subject sorry my my evaluation I'm folding them by gamma step this is exactly what the subject does and then I I arrive to this and I commit >> that the same as >> well baseball >> yes well yeah >> yes isn't that the same Yeah, they can. Yes, >> this is also what you would do >> at this point. Yes, but there will be some differences here. So >> you can see in a nutshell you can see

where is a base fold with increased redundancy commit. >> Yeah. So I'm going to actually choose like some other code which is going to be RS star which will be like over now the actual station field. I'm going to choose another doain l doesn't really matter and I will want it to encode messages of size two to the m - k minus k prime and k prime is the new folding factor.

So k prime would be how much I want to fold next. And here I can really choose whatever I want like I can ch I mean with the same constraint as before but my valuation domain can be whatever I want. So now again I will do exactly what I have before but now with respect to so I'm going to say that G actually Q is P evaluated at at gamma. So the size of this is exactly 2 to the m minus k coefficients and I'm going to again shape them as a matrix where here I have 2 to the k

prime row and 2 to the m minus k minus k prime rows no columns columns >> this is I think that this is where difficulties start with unar because in the univer You don't have like gamma 1, gamma 2, gamma 3, gamma. You replace the 4k gamma by one gamma. >> Yeah. >> And then everything is modified start. >> But can I I thought that what you can do here is like suppose that here I P is I fix the first variable to be of degree to the K or K which one of the two

then everything just follows out. because I'm kind of like evaluating that part. I think there's some coefficient evaluation there. But let's we go back to university later on. >> Yeah. Yeah, sure. >> Yeah. Okay. So, this is what I do and then I'm doing this commit working. >> Yeah, I'm doing this commit phase again. So, I send you this matrix of course as a miracle route. H I do my auto domain samples. So S1 up to S.

>> So encoded row wise, right? You didn't say this. >> Yes. Encoded row wise. Again, sorry. H. Okay. So we've done that and now you know we're in a bit of a pickle because uh I need to, you know, here the prover could have sent me whatever he wanted. So I need to check consistency of the two things. And now I told you that this L star can be whatever it wants. I tell you all these kind of things like uh Jack what how does this what does how do I check consistency?

Well, it turns out that there's some tricks. So uh I'm going to like first sample I'm going to sample some location some spot checks that are the same as in F. So I'm going to uh of course here I get the answer to the out samples. Then I sample Z one up to ZT and this will be elements of this domain L. So uh I'm going to say I'm going to just look at one of them. This will be in the domain uh L. >> Okay.

>> The out of domain sample is done of the previous round. >> No. So the out domain sample is over the entire building. >> Okay. >> Yeah. And it's done on this thing here. So the main sample is with related to to the thing that you just sent always. And now I have this X is in L. I can uh you know if I sample one of these columns the X column I can compute something which is called the folding the same thing as the fly as the Folding. So I just compute uh the fold of f at randomness gamma with x.

What does this means? This is exactly mean I query as a verifier. I query the column and then I take a multilinear evaluation of the column. You can also do other things there but let's that do that. And now I want to check consistency of this thing with the fold. Well, how do I do it? Well, if these are the if this is really the thing that I want about that I want that means that is it's encoding as a read solomon thing will agree with will agree with um with default at that point. So in particular I can think of it like okay so let grs

be the generating matrix of uh this code here. So I can exactly write. So what I want to check is that uh uh the rich solommon encoding of q at the point x is equal to this f which I'm going to call zed. So this is what I what I want. So the nice thing is that this is again something that I can rewrite as a site claim. So I can rewrite it as sum of like G RS at X B time Q at B is equal to Z. And here

I'm thinking of this as the a matrix with oh god I thought I thought RS of Q goted to explicitly. So yes, this is what we commit Q is this thing here. So if this is equal to to the message behind the if it is equal to this, this will have the same encoding. So what what I'm saying is like this this condition can be checked as a subject lane.

What I thought you were going to say, which is what Fry does, is relate uh this guy to a bunch of values of the last oracle. >> Yes. Is that what you're doing here? >> Fold f of gamma is the values of the last oracle. >> Yeah. Uh yes. >> And I'm I'm relating the new oracle with the values of the last oracle. And I'm writing this as a subject constraint. >> So I'm expecting a sum over a co-et. Uh, in other words, >> but we don't have codex here because I'm doing things interl. So my >> Okay. Then then shouldn't shouldn't that just be the tensor combination of of the column sitting over?

>> Yes. >> So this this fold f gamma what I'm saying what you do is that uh fold of f gamma is exactly like I I look at the at the committed the miracle tree in the first round. I read a column >> and then I comput the ML. >> Yeah. Yeah. Exactly. So you tensor hold it that column. Right. >> Yeah. >> So then why is why is RS >> because this P in the honest case is Q.

>> Okay. in the honest case because in the honest case this is like I I have also folded the sorry not this yeah this is a Q >> and this is a my Q's and P sometimes they become the same letter I apologize I have I also do very bad lambdas >> I'm not sure if I uh understand uh Ben's question but the main difference is the big domain.

It's where you know the projected domain is not where we commit uh the new uh function. So the so that so so it's for technical reason you could do do it that way but we have a blown up second domain anyway. >> No I think I'm good. It's just combining two steps. First is the is the tensor fold of the column but then there's also an RS encoding. that column itself should be the RS encoding of something else >> like well the column is not under >> it's outside outside the RS domain so it's so the previous oracle >> so what what I'm saying is that so I have this matrix this is the matrix of f

right this is the matrix F which is the c to the k of >> then I will f multilinear up to I get like some f tilt there let's say which is equal will be equal to the encoding of rs of p fix gamma this is what this is what I have so okay now I I claim you that I have actually sent you I send you q which is equal to p of gamma right so my my claim sorry gamma is equal to Q. How do I

do this Q then you think I sent you? So what I do? Okay, I check that for all I in T the number of repetition I choose here that the encoding of P gamma this is equal to the encoding of Q. Well, this part here is exactly the fold of the original oracle at gamma. So this side and xi so this is just yeah cq at xi and then here I'm just rewriting this condition here which is exactly this as

a sam query and this is what I have. So now what do I get? Well I get these original subject queries. So this original subject query through the subject they get turned and into a single subject query of the form sum of uh epsilon i time sum of b equality si gamma b times I'm going to just to this is the first s length And then we have like more subject lengths one for

each one of them because like for all I in T we end up having that sum over B of GRS s B * QB is equal to Z I >> Yeah. So we haven't read from the second oracle at all yet. >> Not at all. No. So we we we never we will read that in the next >> in the next. Yes. Yes. Exactly. So the difference >> the difference from fry is instead of reading something from the second oracle and comparing to fold of the first oracle to this >> you instead get the virtual value that

the second oracle should take and express that as a some claim >> it's even out of domain for a second. >> Correct. >> What do you what you want to read is Q at X. X is in domain at X is in some domain or something right? >> Um but instead of reading it or any oracle, you you write down this sum claim that tells you what the value of Q should be. >> Exactly. Exactly. You never read the oracle. You just say look look I believe this oracle should have this should satisfy this constraint. Let's write it down and then we'll check it out.

>> How the oracle gets the conraint >> like uh the value of the constraint x is derived from the first oracle >> exactly. So this is how I set the consistency with the first oracle >> and I live another board. So we're going to be continuing with the and of course here I'm also forgetting that you also have like a dagger thing which is the out of the main sample that you have there.

>> So just to you know originally I start with I start with L + one constraints now I have L + one plus T + one constraints and then I just keep continuing it. Okay. So, what do I do? Yes. >> I just want to make sure that we leave a little bit of time for Nico to speak as well. >> Sorry, I didn't. >> No, no, it's not planned. >> Unplanned serendipitous. >> Okay.

>> So, apparently he's been working and that has a lot of parallels with this. >> Yeah. >> There's a bunch of performance optimizations. >> Yeah. Or at least just discuss like uh the comparisons like because it's it is interesting. It might help the implementation. >> Absolutely. Yeah. Yeah. We should do that. Okay, I'm basically done. I have the tricks to make this fast later to do. But uh this is this is basically where in freeboards this four point is currently not used. >> Really naive question. In the paper you said somewhere you use a proximity gap for powers. Where where here is that >> is in the paper but in here we only need for a fine we only need two for lines.

Could we only ever fold by two? >> Well, wait. But but for K bigger than one, let's say, right? And do you need some kind of tensor? >> Yes, they fold pairways. >> But but but but mutual implies tensor is fine. >> Like I like I I only need like if I look at the theorem in like word like I only need the mutual that I showed you for the word part. I only need the mutual that I show with two folding two two words together. If instead like the reason why we wanted the the many case is that in word we also have a compiler which by the way I can make this all black box and it's a cool trick h and in there in the compiler when I want to

batch I sometime want to batch many functions and there I want to have the proity gaps for like many functions >> so you're claiming that if one let's say we have k we have k what is it two the k rows >> so you'reing that using folding for aine lines alone you can assert that if let's say one of those is not close then the fold will not exactly so basically what's happening is that I'm applying like push row like so at this fold I'm going to be like folding this with this and then this with you know >> no I get I get that it's a bunch of folds consecutively the question is >> would you need to argue anything

>> so we we we need to do that like actually like um uh mutual gives a lot of mileage because mutual makes the sense that everything is very very aligned here. So this is what allowed us to actually uh do this. I mean I'm not sure I think that if you just have correlated agreement is a bit more of a subtle >> but the work paper does have a theorem saying like if you have pair wise folding then you can do this um like repeated pair wise folding and your error is going to be fine. >> Let me just put it this way like In the UDR you get mutual. Okay. I mean Angus and and I had to sweat a bit to to argue that you get tensor you get a proximity gap for tensor combinations.

>> Um even even to bootstrap the result for lines to the result for tensors. So are you claiming like that you can get this for free or >> I think so like in the paper we do it and it's uh >> if I don't use it should be even more straight forward >> like with mutual like I think you can do this uh quite well. Yeah I don't believe that but maybe like I mean >> we should double check if you want. Yeah. >> Yeah. like uh but I'm pretty sure that we can at least in in the paper we have like uh we do like uh we do this tensor combination in many rounds uh and it works out >> if there's no bug in the paper.

>> Yeah, theorem 4.20 in the paper that you might be looking for. >> All right. >> Yeah. 420 that's also nice. >> 10 minutes early. Yeah. Very very confident. Okay. So, how do we finish all of this? Well, uh oh well, we have committed to something here. We've run something which gives us a bunch of linear claims. I wonder if we have a problem, a protocol which combines a lot of linear claims and does things with it.

>> Turns out you do. So, you just run war again >> and you do it a bunch of times until you get to the end. at the end you will have like you know this at the end you just send whatever you have to the final value and then you check the subject claims about it so there's one last trick that you need to uh think about or no that is like you know suppose I have this claim over here so okay this claims here when I like finish a subject they're really easy to evaluate because this is just This becomes equality of SI at gamma where gamma is the entire randomness. So I just evaluate it an equality

polinomial is easy to evaluate. Let's look at the claim. So this claim is like sum of g rs of x beta time p beta. So when when I finish my subject, this will end up being like something like G the multilinear extension of GRS at gamma time P at gamma. This thing I'll actually get from work for free. So I need as a verifier to compute this. This is where like the tricks come in. So turns out that for Solomon code GS

at X gamma is exactly equal to the equality polomial of the power vector of X at gamma where this is the vector X² to the 4 um uh up to X to the 2 a minus one >> something like this. So this is like the binary the computation vector is either equal either the Q polomial or the select polomial depending on uh because this depends on which solommon encoding you do. So in the current word

implementation we are doing this encoding where I take my evaluations I convert them into coefficient and then I encode them. In this case, EQ is the right value. If instead I use the the other version, I have like the I have I I have this other cute polinomial which is called the select polinomial which is just product over I of what is it? x i * y i + 1 - y i uh for comparison the equality polomial

is x i + * y i + 1 - y i * 1 - x i. So yep, turns out this works. And the reason it does is because the select polomial basically you can think that it multiplies together the the like if you do if you do select at p it kind of like exponentiate this depending on the on on bit and it's a is a not too bad exercise to try

uh yeah and with this together like this is basically this is all work then the rest is just parameters and figuring out tricks to make this faster and maybe I can mention a couple of tricks I don't know how much time we have it's kind of lost track >> 15 minutes >> 15 minutes >> okay so okay one trick is that okay I'm going to need to do some checks of these kind of claims so a few of these claims They're like, you know, this equality time something this we have a lot of tricks about.

There's like the the the Justin's papers the you know these kind of like tensor structures like kind of quite nice things here is a bit more gnarly because these are like uh you know there are many of these. So first of all there are like uh there's still many of these claims in the first round. So there's usually 100 in the first round. I want to say 14 or 15 in the second round, then 10 and so on. So there will be a bunch of these claims. They're like on a smaller iter. So this makes things already easier. But also this is not trivial. The kind of nice of observation that you can do is that uh GRS uh time q you already have. This is the

encoding uh of um this is the encoding of u uh p you can get from the folding. So what you can do is you can reuse this to compute all of these at once. So you can basically do one one work to compute this value and then the various size don't really bother you in any way. It's kind of like the same trick that you do in hyper plunk when you want to batch like challenges over the binary hyper cube. So this is one trick that you can do to speed up this part here >> for the prover.

>> For the prover. Yeah. >> Yeah. For the very the very far >> have to do this thing. >> Yeah. The very far the only thing you can do is like JKR all this stuff together if you like JKR. Correct. Yeah. So that's one optimization. Another optimization is that if you look at all these things like the only thing that the verifier needs to do at the very end is evaluate these equality polomials. So in fact this protocol like war based for the similars like gita as well they give you really a pro an inner product commitment scheme. So what I can usually do is that in a lot of protocols I have like you know I send the witness

say say Spartan for example Spartan does one first pro check some check it's kind of like a s check of the for to check a epz minus t z is equal to zero and then it does a l check protocol and then it does a pcs protocol but it turns out that since these things are like this is a inner product of commitment what you can also do is like just do this so the the PCS you can like like roughly this link check is kind of like a check to check that gum like some some claim of this form

and yeah I mean the the name check reduce usually reduces this to a claim on a gamma beta and a claim on f beta. This is what these things usually do. And usually you prove this with a PCS. Instead, you can just forget about this and just run a word on this claim directly at the start and this allow you to save like uh one round of like like the round of check that you would do here. So if this was a from three login round you get to two login rounds.

So this is one optimization you can do and this is good to save latency for example. Uh yeah can I oh I was going to open up the the liorto bag of tricks. >> Yeah. Um so now that you have were in three boards you can get liorto in just as many. Um the first thing they do is comes from a different line of work. So there's no out of domain samples and they just do more repetitions to get you know like smaller distance bounds. The next thing you can observe is actually we've been using RS codes but they're not special other than for their distance property like the only thing we needed was interleaf codes. Um so lito says use any code you want.

>> Well you need a proximity gap too. Yeah, exactly. You need a proximity gap, but otherwise that's it. >> Which all codes >> up. >> Yeah, the only difference you have is like this statement here, this GRS, which you might not be able to express in a nice way. Um, and this is where like you said you can use GKR and these are protocols like blaze essentially that's what it does. >> Yeah. Um the other thing to observe with the implementation is actually they don't really think about polomials. Um they just care about the evaluations of the initial thing over the hyper cube and that's kind of all you need. Uh you need polinomials in the sense that

you're going to be encoding and that's the only time you have to think about FFTs. Um but otherwise you never really need to think these multilinear polinomials don't need to be materialized ever. Um and I don't know if that's something you do in the code. We are working with the operator. >> Yeah. So I think you can just work with >> um sorry >> data. >> Yeah data. You treat your polinomial first as a vector and then you'll reshape it into a matrix to then be encoded. Um likewise when you're doing these partial evaluations in your sum check um it is just about reshaping the initial thing into a matrix and I think it's just a matrix vector product afterwards.

Um I think from Ben's papers you'll find like this tensoring structure to have EQ as a vector. Um and I think you might be able to save some time there. >> Save some time in the construction of the EQ polomial right >> um yeah or just in the evaluation of um this p of gamma and the rest is free. >> Yeah, >> you don't need to think of polomials here. This is still like matrix vector operations. >> So if you have a fast matrix vector like back end that's that's all you need to do >> instead of having >> instead of materializing some multilinear and partially evaluating the multilinear

>> and then yeah having that as your cue. >> Yeah. Yeah. I think there's a lot of tricks that you can do for like good like if you good man vector things >> that that's all you need and the only time you get out of that is when you want to encode. >> Yeah. >> It has something better than naive matrix vector multiplication. >> Exactly. Like if you think about it, this is like this protocol is actually a very surprising thing that you these are in a sense they're code agnostic protocols in the sense like that you don't really use much of the structure of the code apart from it being linear.

The rest is kind of like you yeah you get it for like efficiency for the good and all of that but in reality what you really need is the any code will work here with different verifier like efficiency. >> Exactly. And very very surprising that you know you would think that like if you use a protocol which leverages very much the structure of the code you would expect to get something better than a protocol which kind of like could pick any code inside there and you know >> like you do leverage the structure of leaving and this like pair wise folding like that's where the structure exists.

>> Is a generic technique you can put on any code. >> Yeah. It's the pair wise folding. Yeah, but it's still like >> but it's still like you know >> so you would need more structure if you wouldn't put it matrix wise but a single row >> because then you need structure to decon into smaller things >> but actually so when you take a polinomial univariate um RS and then you sort of fold it you are kind of >> you're taking this matrix you're putting it in one row and then you're breaking it back down right Yeah, for me this is a new learning actually. You don't >> Yeah, it's kind of interesting to me.

You can like take any code and bootstrap foldability on it and then >> you don't even have to talk about foldability. >> Yeah, because you just commit inter smaller chunks per say >> inter is all you need. >> Yeah. >> And uh it's very surprising and doesn't >> make sense to me. code switching idea is also that right like R's paper like >> Angus I don't know if you agree but if we treat that like no more as a polomial but vector matrix product maybe we can even apply packing this kind of strategy even faster

What is >> Yeah, that should work. I also think I think smart things we can do with the first round as well >> because right now we just applied seem for the very low primitive like hash function and multiplication of x but maybe for stuff like matrix vector matrix vector multiplication >> that's all you need all you need is very fast matrix vector product >> yeah the issue is that matrix matrix vector product is also bound Yeah, not my problem. I just told you what I know then the rest is for you.

Yeah, I think in general like these are protocol that could also be minimizing the number of memory passes that you that you do in these things and that like for example one of the thing that we saw as step is that in the GPU setting so I'm not sure how much transfer to the CPU is that the stack polomial computation doing it at the same time as which you're doing the folding of the challenges is something that turned out to improve latency quite a bit. So this is like when I computing. So I comput H1 then when I get gamma one and I need to compute H2 like I both fold and compute the H at the same time and this turns out like reducing like memory like classes turns out to be

quite nice. So in um one of the slides before there was paralization strategies. Uh that's one of the issues with Ryan today. It doesn't support um spawning uh and syncing. It only supports par loops I think. Uh and there was some kind of Ryan plus future that has been pending for like six years now. Quick question maybe oriented towards word 2.0. Have you guys been looking at fix or facts? I forget which one is the OP. They have like just a different patching technique. Is this something

that's applicable here and will make any savings? >> Yeah. Can you let us know >> what you think about 2.0? >> Sure. So >> it's >> so I think like so fix a wonderful paper they didn't normally focus on concrete efficiency so there are some deals but you can think of it in many ways one of the initial way you can think about is that it does like a blaze like uh step of course switching and then kind of like changes to the to the yeah change it to work exactly And this is kind of nice because uh the

only thing in the in the large alphabet regime the only thing which is not optimal for war is like the prover time. So using a different code which a better encoding at the start ends up helping. So the batching technique that they have is about like the when you have multiple evaluation you bring them together right. So I think this is something that you can do like when you do all so here when actually here yeah the batching that I did here is kind of like the most naive possible version of batching >> because if you think about it the complexity of the claim you know the verifier still has to work a lot at the end because it needs to kind of like uh do like you know if I had t1 and t2

claims I I have to work t1 plus t2 I think we shouldn't batch in the first round. >> Sorry. >> I think we shouldn't batch in the first round. >> That is also possible. Yes, >> I think we can make this a lot faster. >> Yeah, because you don't do any extension field multiplication. >> Don't do any extension and then also let you play around with AQ like if you just if you start in the first round proving B subject and only batch after the first round. >> I agree. I agree. I think that's nice. >> So everything in the first round will be >> well two things. Not only that, also we can get rid of all FFTs in the We can get rid of the the painful stuff in the first round >> because you can pull out the EQ like you can factoriize the subject.

>> Yeah. Because you don't have the F anymore. >> Yeah. But you can also do it like virtually, right? I just compute everything on the B on the base. I comput the subject polomials for each one in the base and then I >> polinomials is painful, right? >> But you know there's time they're free. >> They are polomials. >> No, like I mean H1 and H2 and H3. I'm thinking of you skip where they're now potentially. >> Sure. Sure. I was thinking of like the the multi. Yeah. >> Uh what was >> Yeah. So for example when we were doing accumulation later later on this type of folding the does not work because if you're accumulating things then the number of claims is growing and at one point the verifier is like too much to think to do. So there we had to use a

different folding. is the Iber long stale of batching which is similar to the one that fix and fact two and it the kind of annoying part is that as I can tell for that batching you require like login around you because you need to run a sound check >> so you know uh so in this particular case because these EQ polomials are also cheap to evaluate >> he doesn't really matter if you if these were expensive they were RA for example claims what you would want to is actually batch them in a similar way so that you only have one claim at the end to care about.

>> Well, one claim per array code that you use. So this is the one of the issues. >> Okay. So >> so not super helpful. >> So as far as I can tell not super >> sorry >> there is something here when computing the subject polinomial here it's a degree two it's a degree two. So we need three points and the implementation we use the fact that we know if we call it f we know f f of 0 plus f of one equals and we know this value but I believe um with some work we can actually know f of zero and f of one because we already computed before exactly

>> and so for instance when about the out of domain samplings when you compute the value you need to evaluate your polomial out this on this out of domain point. But you have like the obvious algorithm is recursive approach on which you will evaluate half of your polomial on the point and half here half here and you combine the two. But instead of combining and for and forget and forgetting the evaluations, you keep track of the intermediate evaluations and using this fact you can know f of zero f of one and so you only need one evaluation of this check polinomial and so you divide the work by two because in the current

implementation you need two to the power of n um sums and you can do to the power of n minus one. >> Yeah. >> Yeah. Yeah. This is something that we should try and I think it's a very worthwhile like thing to do. Similarly here the encoding gives you already some things that so you probably can also use it here >> like uh you if you draw the matrix vector things you can see these things quite nicely very very nice. >> So okay regarding 2.0 maybe I can give you like some intuition some things which are true something which are not true and some open problems.

um you know you'll have to figure out which one is which. No, I'm kidding. Okay so I said before like when I talks like uh IOPS and codes have a lot in common and in particular now we have IOPS and codes end up having like you know I can make if you give me any code I can give you an IOP which is almost as efficient as the code. So it's true in asytoically and in practice. So uh there are many so first things folding. So I I want to distinguish two different regimes in which we can do

uh because there are the only two you know is how many times you encode the witness. So I give you a code and you have a weakness and I have to figure out how many I will have to encode it at some point because error correcting codes are uh necessary and I want to figure out uh you know how many times I encode it and there's two ways of doing things. So this word is in like this single encoding pass. So if my witness size is n my like I will commit to something of n divided by the rate of the code in this setting there's only one thing that I know to do which is out which is to solve so it is to do something which

either in the solommon case or like in the case I just I want to shape my stuff in a matrix like this and I end up having this fundamental trade-off that h I would like to like if I want to fold a lot. I need to set my K to be large, but then my my verifier pays a lot. So I can set this to be square root of N, but then my verifier pays G of N and then I get Lero. If I choose K to be like constant, I get one version of war, one version of Lorito.

The optimal setting in word that we could find is setting uh this to be around log of N. And this gives you like you know the very far log event things who cares. It's like 30 field elements that's fine. If I do more than that then my like I turns out that I can play a bit get something slightly maybe better as just very slightly but it doesn't really do much. So in this setting like I like yeah this is all that I know to do and in that sense like if you look at the the asytoic things like words got like quas encoding time this can be improved but I'll come back to that for a moment.

Uh the query complexity is all lambda. So in in fact it's like I want to say it's probably just uh lambda plus uh little of lamb something like that. I don't I don't know exactly what we have but it's basically lambda. It's not the constant is either one or two >> in this direction. >> No >> but but al we don't do constants. So it's yeah so the number of query that that you end up getting there is like almost optimal. And if you look at the verifier time, the verifier time is roughly like uh the number of queries times how much you read in each query.

And you know we know that each verifier, you know, if you read something and doesn't use it is a two bit verifier. So this is kind of like a lower bound of what we can do. So in that sense in this setting where I set where I only encode once, you can think of world being extremely close to optimal. Even if I look at like the to just send if I send a code word at cert return rate or like the first round of fry without anything else later if you look at proof size this is like kind of like is like 1.4 times worse than this thing which is obviously too good to be true. So yeah, the encoding time like you can choose different codes. Different codes have better encoding time than with Solomon codes. And the kind of issues that you usually end up getting are worse like

distance rate trade-offs than Solomon code because RS codes are MDS. So they have like the the the optimal trade-off between between rate and distance. >> What do you think for example as example of other codes that you have in mind? >> So RA codes array codes are great. I really like them. >> They don't have a mutual agreement. >> Sorry you lose when you use even if they have the distance because they don't have good >> Exactly. That's the other problem that we don't know good mutual creator agreement for these other codes.

to 1.5 chance. >> We know to 1.5 but not to Johnson. Yeah. >> Yeah. So like my number of queries end up being like I think like for example in Blaze they need to do 1,000 queries in the first round >> while you do 100 with the with Solomon which is yeah >> just >> just a quick question back to that were seems to work for arbitrary codes right you just reshape the matrix and commit that way >> how do you interpretate you know the previous oracle >> now and the domain you know the projected domain in some sense which is

not uh which is not uh >> subset of the new commit domain. >> So how do you how do you interpret something that is out of domain in the uniar sense as in Solomon as how to ask what you have committed for that out of domain. So the in yeah so you just do this right. So say that P is what I my message and I want to say like when I encode P with an array code I get the same value as default I just use here the generating matrix of the array code.

I follow your notation but >> yeah evaluating out of like a multilinear out of domain is a linear operation. Yeah, encoding I fully agree. >> Yeah, encoding is a linear operation as well. >> But here to point on domain we have something this is the commit domain of the code. There is there connection with the hyper cube or there is no >> I don't think it matters because these operations are both linear and you can do them in any order you want. >> You can first encode and then evaluate or first evaluate then encode. >> So wait a second. So so we have to domain of RA code for example >> and we have arranged already our our

long code word actually we have shaped as a matrix >> but still it lives over that domain. >> So how do I check consistency between the next code? >> So this is exactly what I have here. So >> if you have like so I have a code. So when I fold my folded code word is the encoding of the folded message, right? Because it's a linear operation. >> Yeah. >> And then what I want to check is that the h to check that the new message I'm sending is really the folded message.

I'm going to check that the encoding of the folded of the new message is equal to the encoding of the folded message. This part I can get from the queries from before because I I just get it from here. And this part I'm just going to rewrite it as this linear equation because I have like like you know I have G at P. This is kind of like and I care about the x entropy and this is exactly the equation that comes out here and this maybe should have been cub.

Yeah cube. So if I if I reinterpret the thing that I care about as a linear constraint, I just get exactly this equation which is a check thing. So I can just continue going on with it. >> I can't really follow but I I I can >> Yeah, we can we can do it later on. >> I don't want to block now. >> So, um technically speaking, we're above time. So, the we have 20 minute break time for anyone who wants to grab a biscuit or or drink, but if you want to continue the discussion, by all means, uh feel free to continue.

>> Thank you, Justin. Thanks. >> Yeah. So, just to finish this part on word 2.0, zero. Uh yeah, so the code with linear encoding time uh they typically end up having a worse distance rate trade-off and worse visual created agreements. So what this ends up being is that the verifier and the proof size end up being much larger and the worst distance trade-off also means that like you have to do more ashing and depending on your implementation the FFT is a bottleneck or the ashing is a bottleneck. For example, at SP1 SFTs were not a bottleneck. It was not really the thing that was um that was hurting us.

>> I think this is >> ah I think now >> I think for us also the case because we use for ash for >> so the ashing will be much more expensive. which is MDS. Is it possible or just don't know it? >> No. >> But it's not like >> no it's not it's quilar.

>> Oh sorry you mean sorry obviously but sorry which would be is it fundamentally possible or >> it is fundamentally possible. We have some codes which have linear encoding time and they're either MDS or near MDS but these codes they come from like a line of work on distance amplification >> if you like they're very practical. >> Okay. And is there a chance that someone finds like a good code which is linear time and MDS?

>> Sure. Okay. >> You can also win the lottery tomorrow. or you can solve the proximity gap. No, it's like it is possible like we don't know too much but uh you know it is my hope I would love to live in a world where you have like an MDS concretely efficient linear time encodable code but as far as I can tell this is like a big open problem coding theory which is has only seen well it's a closed problem but it doesn't have a concrete uh answer >> yeah as far as I can know and yeah which is very annoying by the way this is extremely annoying Um yeah the other option is like I can start

thinking of encoding more than once. So uh I can instead of having an interle code I have a tensor code. >> There's some beautiful lines of work in both like circuit proofs in both like theoretical computer science of using tensor code to get the structure. The issue is that as far as I can tell there like uh you get some some issues in that first of all if you think about the tensor code the distance deteriorates with like so distance the total of the distance of the code that you have and the rate also like squares. So what you end up having you also end up having like you know you can fold more and asintotically this folding allows you to

do better. You can get IOPS which are optimal in the small alphabet regime but concretely like the constant that you get on query complexity tends to be such that effectively like the the verifier time unless for like extremely or the argument size you know the don't really kick in until you have like an extremely large distance and until then like where is better so once we are like in a war where we're proving instit 40 to the 50 I don't know where the trade-off is like it seems like to me at least my intuition is that the the single encoding way is the the way to go. Now the exciting question is whether like we

can fold by more than logarithmic in each step by only encoding once and I have no idea whether we can do that. I have no clue whatsoever nor any ideas. So but uh you know I cannot rule it out. I I've tried proving some impossibilities but I haven't managed to. So it's uh this is still wide open. >> What do you mean by encoding once >> like like my proof size the proof size of the system is kind of like the weakness size divided by the rate. So you give me I give you any code and you can all you can only afford to write a proof size which is kind of like size o of n / rate

and I don't want to have like co of n / rate squared for example I really care about only performing one encoding yeah okay class is missed Thank you. What a master class. Thank you so much. Okay.