Zero Knowledge Scholars Assembly 2024 (Day 3)

Okay, let's uh the main problem when we are using the unary polomials actually we we used the unariable polomials until now we we had only x and the main problem here is that if you have a really big uh size of data then it's difficult to interpolate that and the most efficient interpolation is actually using the fast free transformation using the roots of unity but actually it's still pretty um slow uh for example actually it's small like if you have n data uh computing that result actually will end up as a end of there's a complexity of the best print transformation. Uh and because of that recently we started to have a another approach using multiple variants rather than using only one unique variant. If that actually we can express the same data in an efficient form. Let's see actually how it works. Um, let's Okay.

So actually we already tried to encode data into polomial multiple times. So uh gen vector is actually a poly uh try to encode this to a unicial it will result like this very actually we can use a uh two variables instead of using one variable to express this thing let's try to do This is something how we can do. So you have a two variable X1 X2 and Y X2. Then you have a four coordinates 0 0 1 1 0 1 1. So in this case in this four 0 0 0 1 coordinates we are mapping uh those points uh in in in this actually we're going to have a hyper surface in this case we are having a surface and if we have a one more coordinate uh we need to think about it a more in an abstract way.

We're going to have a ultra space and then in that hypers space we're going to have a hyper surface just like which actually will look like that. So we cannot visualize how how exactly that would like but uh we can think like okay if we have a x1 x3 three coordinates and if we use x1 x2 for their position vector and if we just um evaluate that at x3 it don't look like vector x. Yeah, we are getting on the same things right. How how how we encode vectors into a universe polomial just like this. But actually we can also include them in the form of a hypers.

But actually, yeah, it's not. Yeah, it looks like a mean. The reason why I'm saying hyper surface is that yeah, actually we can increase the degree. The degree of X1, X2 here is actually one. So actually it can be called plane but we can have a multi polomial where the degree of this x1 is two and actually becomes a hyper so you have curve yeah we're going to have expert so here is a transformation vector and polomial we are actually saying the same thing.

The first one is a we include data in the vector format and we are including the data into unary polomial format and also we can include the data into the multivari polinomial format. How do you go from unary? How uh actually We cannot directly transform unar polomial to multiar polomial. We are just thinking like okay we can create unary pol from the vector and also we can create multi polinomial from the vector. Oh okay.

So there exist interpolation method to from the vector to un polomial and also we have a interpolation method for unary polomial too. So we can let a multivariate polomial interpolate the the data on the given coordinates. 0 0 6 0 1 2 0 1 7 0 uh one one. So actually this is the yeah this picture shows the multivariate interpolation. So we can say these three formats are actually saying the same data.

Okay, let's see a little bit more detail. Let's take a look in detail. In vector we have index zero one two three here because think array and uh the index zero the value is six for index one the value is two like this and then unit polial actually we are using x instead of the index so we evaluate that pol x = 1 that it will output six and like those and Multivariate polomial uh we are using a vector I mean geometrical vector instead of the index or just an x value. So we are giving it a coordinate and actually that coordinate only kind of a as a position vector. So for each position vector we're going to value.

In this case, we have a four position vectors here. 0.0.1 1.0 1.

1 each position vector the corresponding evaluation value is 629 and using those we can vary pol. Okay, let's try to understand this in a more visually. Okay. Actually this is actually visualizing uh when a multivaried polomial has only a one dimensional hyper space. So we are expressing it in a uni proportion vector actually has only one.

So the value vector is one two three four and still a value like that. If you interpolate that we're going to get a unic. Let's try to increase the dimension for the domain one more that it will look like this. We increase the dimension a bit. So the position vector will look like 1.

1 - 1.1 - - one 4 - one and for each position vector actually we can assign value like 6 279 and if we interpolate them we're going to get this binary polomial result and let's try to increase our dimension one In this case we are using zero and one uh for the position vector. Uh in this case we have a we're going to have a eight a position vectors. We can also increase like we can also use not only zero and one we can also use two but in this case I'm just using 0 and one for the position vector value. Then we may have a uh assigned scalar values inside of the uh for each position vector.

You say some of us uh have heard of the uh multivariate subjects. No. Anyone heard of the boolean hyper cube? Actually this is called the boolean hyper. This is called the boolean hyper.

So it's it looks like cube right and it exists in the hypers space. hyper and we're going to assign the value to the method will be zero and one. So this form is actually called the boolean hyper cube. Why we dividing this boolean hyper cube? Let me show you a little bit more.

Um actually this is a pretty important that we have right now. Uh it means actually if we let some uh if you if you make some interpolation that interpolates a given data then actually uh there exist only one unique multi linear polomial that interpolates the given data just like unary polomial. In the unary polomial if you have a seven data points then we we uh can make sure that you have only one unique unar polomial with degree six but you may have a another uh unar polomials that interpolates the data which degree is more than seven. Right? So if you have a degree seven polomial you may have infinite number or the size of field.

Yeah, number of polomials then it translates the same data. But actually if we uh constrain the degree of your unic polomial to six then actually you may have a only one unique unic polomial. If you think about this in the unic polomial case it's exactly same in multivari polomial too. If you have a boolean hyper cube and if you assign values then actually there exist only one unique multi-linear uh polomial which means that the degree of each uh variable is at one and you're going to have a one unique multinear that actually that is set as a multilinear. Um let's say just move on.

Uh okay here we need to visit what the multilinear extension is too as in unary polomial let's say you have a 13° polomial then in un polate on a given multiplicate subgroup with sides of six then or with size of Let's say seven. Then we going to evaluate them and get the evaluation the seven evaluation values, right? And we're going to have a unique one unary polomial with degree six which those same which is the same thing in the multivariate set. There exists some multi- variant polomial uh which degree of x3 is maybe bigger than three4 right anyway if we evaluate all those values on the polon hyper cube just like we have uh evaluate that and then if we find a pol those values on the hyper cube. There exist only one unique multilinear polomial and that is the that is called the multilinear extension of the original.

I will show you that later. that interpolate a given uh data set over the polarity. So what does it mean by most efficient? So for example four points right then by this definition the most efficient structure would be to divide over a square but then in one dimension will be defining it over a yeah so what's the efficiency that we're gaining uh the efficiency we're gaining is that the coal interpolation drops down to n rather because the main reason is because we can isolate each dimension uh against each other. But in unarious setup actually uh we need to multiply terms and actually it could the logs in in multivariate setup we can actually isolate each dimension and then actually we can make make it much faster than unar given let's say if I have a um if I have like a degree seven pol and I interpolate it in a multilinear like in in multiple dimensions right like in so do I the most efficient one will be the seven dimension threeh okay so the three gives you eight points ah okay and you know seven degree polalation so Yeah, the cost of interpolation in multivariant is all n while the cost of interpolation in unar pol is all n but does this affect how we can so in univariate polinomials we usually use f oft to right data yeah but in this instance of like using multiple dimensions does it change that or we can use FFT.

Uh actually we are not using FFT. Okay, got it. Yeah. Uh and I think you may heard you may you may have heard of that the main cost of PL or something is kind of a creating the uh commitment. So we always ask why oh do we need to commit to the polomial?

It means like it's kind of we need to do interpolate and we need to do best transformation. all the end of speed. Yeah. So there's a main kind of challenges when we are uh doing the unary stuffs but in multiari multiar extension actually we can do it much in a much faster way. So actually I gave you the uh definition of the boolean hyper cube already.

So we usually denote the boolean hyper cube like this. V sub one is that it's a one dimensional boolean hyper cube and two is a two dimensional hyper dimensional. So we are evaluating our multic on those position vectors. Okay. Using this thing we can do the same polomial is what we have done using unary pol of uh we can also test the identities between two polomials via uh public protocol.

Let's see how we can do that. Um it's a pretty similar we actually uh pick a random number from from the field not from the boolean field. refreshes us. We are picking a uh some random number exactly same. We are picking a random position vector in the in the hybrid space and then evaluating them.

Um I'm sorry actually it's a it's a typo. should be both part. So theation of the two polomials actually are equal to each other. It means that we can use the same thing just like the subma and the uh possibility actually if you just uh isolate each coordinate then you can easily think about how those will work there. So the the t is the at most degree of any coate any variant there.

For example uh we have a polomial f uh which is a x1 squar + x2 + 1. Then uh if if you think about x2 as a constant then it's just a unic polomial about x1 and we can just use the same express and actually x1 doesn't affect x2 x2 also doesn't affect x1. So because of that we can think of the possibilities actually isolated with each other. It's a all of them are actually independent each other. So this will give us the uh same uh information just like in this case here is a two Definitely.

Yeah, we definitely think the better. You mean the best value? Yeah, we have that uh in the following uh slides and definitely we can examine uh much more complex relations of polomials too. Just like this. We pick some random uh vector from the field and test that.

What does that mean? Uh it means We may have a hyper surface not not the hyper plane. Hyper plane is for the multi linear polomial actually just for multivariate polomial which some has some degree over two actually we may have some uh hyper surface actually uh they got to interpolate those polomial on two hyper cube say two dimensional hyper cube in this Right two dimensional len hyper cube and it validations are look like will look like this and we have a hypersurface which is a multivariable polomial and we have a two hypers surfaces in this case like oh maybe it look like this and actually if they are exactly a same uh hyper surface then Okay, let's try to examine this surface at a random point like here. This is R1, R2. So we pick a random point and then examine that.

Okay, what is the value? What is the value? So if they evaluate to same point then actually it means oh it's a same hypers hypers surface it's a same multivariate polomial just like what we have done polomial using the super Yeah. Okay. Um you we have a four data point.

Yeah. Four data 6 2 5 seven for example to express this a multivariate form. uh we're going to map this data into a two-dimensional boo 0.0.1 1.

0 and 1.1. So to express them they become like 62 57. Yeah. So we have a uh yeah but actually this is when we are interpolating this into a multi polomial but in this case we We're assuming that we have a multivariate polomial.

We have a some multiari polomial and then actually that multivariate polomial is evaluated at uh at this point cube and their evaluation values are like this. We are yeah so that the hyper plane also yeah we are we are we are uh actually thinking about two different multivariant polomials. We are thinking about two different hypersfaces and um it's a hyper surface actually that interpolates the same uh data set but actually there will exist only one unique hyper plane that interlace. Yeah. So yeah.

For example, if you have a uh two points, there exist only. Yeah. If you have Yeah. Right. You have only one.

Oh, what does the I mean if you have a two point You have only one nine. But actually we can express a lot of like like this. Yeah. But there is only one nine. So in this case there exist only one plane that interpolates this thing one plane.

But actually there exist many surfaces that interpolate those points. So if we are thinking about for right now we are thinking about two different surfaces. We we may have two surfaces and checking that two surfaces are actually a same surface is that oh let's try to pick a random or just like un polomial and checking just like that we are picking a random random position vector and evaluate those two different hypers surfaces. Actually for right now we are not interpolating let's let's do not interpolate let's just say that we have two different high pressure surfaces and then checking that two different hyper surfaces are actually same surface is that checking them evaluating them at a random position vector R just like what we have done in the univer polinomial and then the evaluation equals each rather oh with that possibility they are actually a same hyper service doct [Music] so um actually I think I I think that if we choose R1 equals to R2 there may some uh vulnerability I think how do you know how many RS do you want to choose for this um check so you yeah yeah how do how many only one point but actually two yeah but one point needs to pick a two field element because it's we are having this because a bary polomial degree uh the atmost degree of each each variant at most. Yeah.

For example, if if this hypersurface looks like actually the D is three and in case Yes. These two or picking random. Uh yeah, definitely just pick one. I mean uh yeah maybe we can pick a one random and create a different randoms from there but actually if it has some algebraic structure inside of it then it may increase some algebraic some vulnerability because it may be able to get defected or something and those things actually increases the uh vulnerability. So because of that when we try to pick some random then we try to use the hash function as much as possible to break the algebraic structure inside of them because they are all about the addition and the multiplication.

So if you have if they have any algebraic simple culture a simple structure that actually it actually has some vulnerability inside of it. Yeah. And actually we are not using pairing uh when we are doing this this polarity check and I'm going to show uh how can we check this without using pairing Okay. Um and let's uh think about the how to find the range in unary polomial. Actually we have used the multiplicate subgroup to bind the range.

It means like oh your L R O you have L R O O and actually uh O* R is not actually O because L is a kind of a threederee polomial R is a threederee polomial and O is also threederee polomial so because of that definitely L * R might is definitely not equal to O but actually they will be evaluated to a same values for the given range. That is how we bind the range using Z of X. Right? Shall we visit that again? mapping image like L is kind of a Q R and O is something like Anyway, it's actually interpolating the values like 3 2 4 1 2 3 4 it's actually 3 4 12 4 we just wanted to express this relation using QAP.

So because we just wanted to make sure that oh actually this actually satisfy the hot product 3 * 1 is 3 2 * 2 is= 4 4 * 3 is 12 1 * 4 is 4 and we are interpolating this to l we interse and we interping that actually holds true was a QA one right But actually if we multiply these two polomial this is actually not oh as we can see the the degree is different the this this is a degree of six and this is degree of three so it's definitely different but actually they will be evaluated to a same value they will evaluate that same value for for the multiplicate subgroup for the multiplicative subgroup. So we are binding the range to this multiplicative subgroup. So how to bind L * R minus O actually will be evaluated to zero only for those ranges because of that Z that vanishes to zero in this multiplicative subgroup and times a quotion polomial is actually how we bind the range to to this sub multiplicative subgroup. So L * R will not actually evaluate to the same value to all out of this range but they going to evaluate to the same value for for for in in in this range. This is actually how we did the how we bind the range in univariate polomial and in multivariate polomial thing actually we bind the range using the boolean hyper cube.

So actually we have some limitation we cannot bind the range with like only 13 elements. We can only bind the range using 16 elements. with the powers of two. So actually we are actually wasting a three some uh sides there. For example, like uh if you have a 2 to the 30 to like very big value, it's about like 16 million, right?

And actually in this case uh maybe the you may be actually wasting kind of way around 7 billion points. It's yeah because we have a limitation how to buy in the range instead of 32 because it's in a multiple of two we try to go uh try to go lower to reduce the amount of space you wasting. You're trying to reduce the size of the thing the additional space you are wasting by trying to constrain it so that it's a lower value for this uh powers of two. Yeah, actually I didn't get your exact question. Uh so because we are using to uh do this and as you say we are wasting a lot of uh values right yeah there's some potential to waste the system you will try to not go to the next value like if it exceeds by a little bit we'll try to reduce it instead yeah actually yeah we need maybe we need to do that sometimes but uh even if actually We are wasting a little bit maybe we are kind of using a maximum kind of twice but actually it's less than the log end.

Why is the log end of this 32? Okay twice is much much better than 32 times. Yeah, actually the maybe the size of the data might be a little bit overwhelming sometimes. And now I'm going to introduce what the sum protocol is here. Uh actually we already did a pretty similar thing in unary polomial actually we have done the the grand product check.

[Laughter] Yeah, actually we have done the grand product check for the PL and actually because it is used for the grand permutation check and before we go to the grand product check and grand permutation check also actually we did the grand sum check too in unary polomial but actually we haven't used that but in multivari setup actually we are using the grandome check um let's I mean before we go to the sum check protocol let's think about why we are using grand sum check here we are actually checking the grand sum is zero almost in for for most of the day uh which means for example let's say we have a two different polomial two different multivariate polomial two different multivariate two different surfaces but actually interestingly they evaluate to same value for all of the boolean hyper just like um s that we have a two different hyper surfaces but actually Uh interestingly they are evaluated to a same value for a given temperature. Let's draw that again. Um let's draw. So we're going to use a two dimensional hyper field. We're going to have a 0 0 uh 0 one like this.

And then we have a two different hypers surface that looks like this. One looks like that and the other actually looks like that. Yeah, two general high pressurees. But interestingly, oh theation at the Harvard cube actually they evalate to a same building. Yeah, this is something related to LR evaluate to the same value with O.

Yeah. So L R R is this one. L* R is the red one and O is the blue one. Yeah. So L R actually you don't need Yeah.

Let's say L R O 1 2 3 4 this is the situation that we want to try to check. Yeah, we have two different hypersurfaces and they are actually interpolating each given point uh L L okay L R O and this red surface is kind of a L * R and blue surface This is just O actually they will get developed the same value for this only hyper cube. This this is actually what we are trying to do and uh we cannot use the same technique what we have done in uh unar here. The technique that we are doing here is that oh we cannot use the same technique. Um so what about this?

What about L * R minus O? Let's try to evaluate that at each boolean hyper cube. Actually they're going to evaluate to zero right for the boolean hyper cube. And okay for each boo hyper cube but there also exists some potential like before that let's try to uh summize all the evaluation it will return zero right okay this is actually called the grand sum of the evaluations of the multivariable polomial but actually even actually it outputs the grand sum to zero actually doesn't make sure that all of these evaluations are actually zero because some of the valuations like look like that and actually the random becomes zero right how can prevent this how can you prevent this [Music] Yeah. So what about multiply some random multiply?

Okay. Then rather than summate this thing right away, let's try to multiply this with a some random policy anyway. It should it should output zero anyway because they will return always zero [Music] or any polomial or any polomial. Yeah, we can think about this as a one polomial and actually it will return it will evaluate to some random point for the hyper cubes but actually uh the first term will always uh give you zero. So the grand sum will actually always [Music] Right.

Right. Yeah. Actually if this the first term is not giving you zero then the grand sum will not be zero. So this is the polomial that we want to check it evaluates to zero for the given volume hyper cube. We can check that by okay let's try to multiply that with a kind of a random polomial and then let's try to check the brand some of it and then if the brand sum actually gives you give us zero then oh it may be actually the all of these evaluations in the boolean hyper cube is actually zero.

Yeah, but actually we have a pretty uh effective technique to choose this polomial thing and I'm going to actually share that. Okay. So sum is that we are evaluating a given multivariable polomial for all over the elements of the boolean hyper cube. So in this case you can think the summation is 6 * 6 + 3 + 2 + 4 and actually becomes 37. in this case and what we are going to do is that oh the total sum is actually 37 this is actually what we're going to do then how can we check effectively this is uh the protocol this is called the check protocol to check in a very efficient way so actually we're going to uh we're going to actually use a divide four parts here but uh for each variate.

So for the first time uh this is we're going to think about only the uh x1 as a variant here and then let's try to summate uh all the values like from x2 and x And actually we are evaluating them there. We are just thinking that X1 is only the variable here. And if you compute them and summate them, you're going to have a one unary polomial. If you comput the polomial then you can evaluate them at zero and one and if you add those two values it should uh be equal to the grand sum. Does it make sense?

We are actually doing the boolean subject of the boolean hyper. So actually we didn't do the summation when x1 is zero or nation Or we can take this uh equation like this. Uh sum of when x1 = 0 to x2 x and x2 x is a nus plus sigma f_sub_1 comma x2 xn and x2 x actually it should equal to the sum it should equal to the total sum Let me write the total sum is definitely the sigma of x1, x2, xn This is the boolean cube cube right this is a grand sum we evaluating them the f all over the cube and we can divide this into a smaller thing like this equals X1 is zero plus when X1 is one. We can divide that into two. Does the hyper cube um can I assume that the essentially decides that if the value exists in that uh or if that variable is existing in that specific face.

So we are doing 0 and one because it's in the boolean hyper cube which um somehow acts as a selector that selects hey this value exists um or not is it or am I understanding wrong I was equivalent of this case in this case let's say okay let's say um In this case brand sum is 6 2 5 7 the what is the grand sum here plus 15 20 grand sum is 20 right then let's say this is the x1 and this is the x2 and I'm going to Yeah, let's try to divide them that x1 is a variable only the variable that we're going to think about here. Then uh when x1 is zero, this is actually when x1 is one. So actually we're going to sum this part first and we're going to sum this part later. This is when x1 = z. This is when x1 = 1.

So we can write this as a okay the value here will same that f zero and x2 x2 zero and this can be written like this right so it's a summation of this one and this one. This is actually the value is eight. This value is 12. So if we uh if we add these two value then it will give us 20 x1 is a variable is yeah in the in the in the in this hammer space why is [Music] Yeah. So if we divide these uh points uh into actually two parts and actually we can think one variant as a variable x1 in this case x1 is a variable.

So we can rewrite that just like this x1 okay we can actually think x1 is a I mean this part becomes a uh f1 X1. So this is actually one. I don't know what that is, right? I still can't know whe [Music] Actually we should go that uh to the the final round. This is the first first round and if we go to the final round actually we can make sure that this is actually from from the one question um when we do this calculation of using 0 and one for f1 um we are not directly operating on the init the the multivaried polinomial that well we have for this right we are basically taking the multivariate polinomial separate into multiple univariate ones and then comput.

So this step actually produces a value um produces a value from this unit variable instead of like perhaps another polomial because it's complete right. So in this case um the grand sum here from this single polomial um does it produce it doesn't produce the grand sum of the entire multivariable poly one. only computes for that dimension. Right? So in this case let's say zero it's 6 and two is lying on the zero part of this.

So in this case f10 plus f11 will be equivalent to 6 plus2 instead of equivalent to 20. Is that the case? Because we are operating on one dimension of this. Right? I mean in this case f_sub_1 of zero should be eight and f_sub_1 of one should be 12.

Okay. So because 8 + 12 becomes 12. Oh that's for the let's let's think about it this way. Um can you have a uh four points and would you please interpolate them into a multivariate polomial thing maybe it's okay that it's not a multilinear it's okay you have a multiar polomial then interpolate actually the the data points on the boolean hyperq please give me your sum what is your brand sum okay thank Actually I would love to check that uh you are saying the truth. So at at the final round you're going to give me a point at a random evaluation at at a at a random point I mean the evaluation of your polomial at a random point at the end at the final round and to compute that actually I'm going to ask you something first.

So you have your friends training. Uh would you please make a unary polomial regarding to the first variant x1 and how to make it? Okay. Um x1 is a variable and x2 x3 etc. actually will not consider as a variable.

They become constant. We going to we're going to make them kind of as a constant. How to make them constant? Okay. evalate them on the submerging and and give me the ransom of your all the evaluations.

Got it. Then you can give me the unary polomial only actually depending on xy. Got it. Yep. Thank you.

And then if you give me that polomial. Okay. Thank you. I'm going to evaluate that at zero and one and if you if you g if you gave me the correct polomial the sum of f1 of zero plus f_sub_1 should equal to the branch sum actually that you gave to me this is the first first round okay so uh if when if the evaluation of when comes first unic polomial f1 actually doesn't give me the uh ransom like that actually when cheating. Yeah.

Then you continue with the next two. Right. Exactly. And then how to continue that? This is the second round.

So to continue that. Okay. Thank you. I have a polomial f1 of x1. So in this case, okay, I will examine you with a random number.

Now I pick a random number or one and I'm going to evaluate your polomial. unaric pol actually you can do that same because you have the multivari by yourself okay so I'm going to I'm going to evaluate that at r1 but actually we can make x1 is also a constant putting some value fixing a value for x1 Basically you fix value for every other thing when you compute specifically for one variable. Yeah, got it. This is the second step because I pick a the first random value for the X1. I'm going to put the random together.

We're going to put the random together. Rank will put R1 to the X1 always and I'm going to put R1 to the X X1 always. And then we're going to think X2 is a variable for right now. We're going to do the same thing. Yep.

What if verify if if what the R values are saying? for the all the ROMs as it it introduces some algebraic vulnerability if the R1 R2 has some algebraic relation between each other it becomes a vulnerability so that extremely random yeah in a very random yeah so you usually use hash function for that from the field. R1 is randomly from the field and then okay would you please uh put R1 to your X1 and then uh would you please try to compute your second unit of f_sub_2 of x2 by uh doing a grand sum regarding to the x3 to the xn from for solid cube. So, yeah, thank you so much. I got your F2 and uh if you gave me your F2 correctly, I'm going to actually test your F2 by evaluating that at zero and one.

And if I actually add them both, it should actually return the F1 value. F1 of X. Yeah. Yeah. In this case is R because we are choosing a random value for this case.

We are fixing a random value for F1 X1. Y. Yep. Got it. So for the first round actually we check the consistency using the grand sum.

In this case, we are checking the consistency with the evaluation of W's first uh un F1 at the random R1. So if w gave me the correct f_sub_2 univer polomial then if I examine that by evaluating at zero and one and sum actually the value equals to f_sub_1 actually oh and then uh you're keeping the consistent we can keep this thing until the final round and definitely this is for the Third round we for the for the third round we put actually I put another random and do it do do that again do that again do that again and then the final round actually look like this when I actually give give the final unar polomial f nus one of x n - one and then f of n and x x n then I'm going to evaluate that at r and after that I will ask to that hey mana would you please give me your opponent proof of your multi polomial at r1 r2 r3 at rn let's check the So we need additional polomial scheme for multivari polomial here and we need a opening scheme for the multi very pol. We are assuming that we have that already. We assuming that we have already a multivariant polinomial commment scheme and it's uh appropriate opening proof method for multiar polomial. So I'm asking oh when actually you already committed your polomial.

Thank you. And then using the oracle I'm asking you evaluate that at a random vector r1 r2 rn. Oh thank you so much. You give me the value with the with the correct proof and then oh actually this is actually exactly same what we have examined during during the sum protocol these steps. Can you explain R1 with this example R1?

Yeah. How that changes? So that f_sub_2 plus f_sub_2= f_sub_1. Uh in this case maybe we are checking r1 here. Uh and ration will give a uh pol un polomial for uh un polomial and actually it will look like this.

I mean uh we are just looking at we technology over here and actually when we when we pick the R2 it's something that we are looking at this space in this way. I mean at first if you actually take a look at the uh this space in this direction actually it will look like this and we are actually making that into a one line by summing everything to one line. I mean in this case let's say we have a let's say in this way we got a first line here and we have a actually second line here when x1 = z and when x1 = 1 right actually if you see the space from this point and when I mean I'm sorry this is when x2 When x2 = zero, we can see this line and x when x2 = 1, we will see this line. And we asking when I come back, oh just give me one nine, right? Just give me one nine.

Actually, we are actually using that as a multilinear setup. So maybe it might be kind of b some curves or something. But anyway, oh when I actually seeing a duplicated curves or lines here. Just give me one line actually giving me this line. This is the f_sub_1 of x1 and then f_sub_1 of zero actually should I mean the the line means that the summation of these two line should give you f1.

Yeah, it actually f10 gives us eight f11 to uh 12 and actually I'm examining that at r1 and actually it will give some random number f1 right in the first round when you are calculating for x1 um everything else is fixed at a I guess a certain default value that we know will result in the grand sum of 20 I guess and then Um then in the second and subsequent round instead of using the first grand out of 20 from the first round of zero and one you start calculating um let's say just choose a random number so that you get to connect them without without directly using the same number. But actually I think uh this is a really good explanation. Let's try to draw again without Okay. And let's say actually this is I say there is some we have four evaluations. Okay.

And if we try to see only the x1 is the variable then actually we are seeing like this like this in this case we can discover two lines here we are just covering two lines yeah uh let's say 65 uh four three for example what we want to do actually what we want to do is actually uh summing everything right so we are asking right now oh I would like to check only x1 first but actually I am seeing these two lines would you please sum this two add to this line into one line actually when is giving me okay there is a if you like this you are 6 4 5 3 you are seeing like these two lines this is x1 and this is ying these two line and this is when x2 = z this is x x2 = 1 you're seeing these two lines okay rather than having these two line uh would you please Make one me by add these two lines actually like this line. This is actually uh the sum of these two line. So actually the value here is a should be 11 and 43. The value here should be I'm sorry it's kind of abstract or so we are having a new line. This is the f_sub_1 of x1 in this case.

Okay. Thank you. Let's try to examine that. I'm going to put zero. So you're going to be 11.

I'm going to put one. You're going to give us seven. And the sum will be 18. Actually, it is actually equal to this sum. Okay.

Thank you so much. Then I let me pick one random here. If I pick a random here, actually it will give me the F1 R1. Right? Okay.

Then let's try to take a look at the x2 as a variable this time and okay x2 as a variable. Uh okay actually we have a these two line. So if we y and x2 it will look like okay when x1 goals zero five six and three four three four five six four we have these two line if we just see x2 but we also don't want to actually actually don't want these two lines rather than actually having these two lines. Uh let's see this at R1. This is when x1 = z.

This is when x1 = 1. What is actually x1= r1? Let's say that actually this like this is x1= r1 and this line becomes the f2 x2 we are seeing actually we are fixing x1 but thank you Chris I think this explains what's actually intuitive calculating essentially each each slice of the plane. Yeah. And then you're introducing random numbers so that there's no if you don't introduce that just I guess Yeah.

Why don't I just use that too? Okay, we don't actually want to check only the f_sub_2 uh to to make x2 as a the only variable here. Consider x1 is now constant. We already checked the X1. I mean, yeah, I mean F1 of X1 actually gives us the uh information about the grand sum already.

So we already checked the grand sum if if W man gave me the F1 correctly and I am checking WO actually giving me F1 correctly. So to check the F1 is correct actually I'm just for doing repeatedly until it can give me the final evaluation. So yeah is actually to check. Yeah. And So we may have the last fn of xn actually using that we are checking fn minus one is correct and how to tell fn fn of rn actually will equal to f of r1 r2 r n using this when I need additional proof of your opening.

of your multi polomial. Please evaluate polomial at R1 R to RN and give me that give me your proof for your opening. Then we can make sure that each of these intermediate unar polomial consistently actually correct while checking the sum for the first option. You're right. We only use the comm Um okay I think that before we go to the uh detail other polomial IOPS I think it'll be uh it is crucial to understand the subject protocol step by step.

So let's have a lunchtime plus breakout sessions to understand actually the subject how the subject protocol works. Y thank you I I example of a how to do the best transformations for just picking the next frame first. Yeah. And this is about the uh multi-linear extension actually that I uh explained in the morning that just like univer uh polomial that interpolates those values on the given boolean hyper cube. That's a multilinear extension and actually it it means that uh we can derive a multilinear extension obeying some hypersface.

So each any hypersurface will have a one unique hyper plane that interpolates the same uh point over the boolean hyper cube. Right? So this is a uh this is called multilinear extension and uh yeah this is the exact some definition of the multiar extension. So we have a multiple here and actually you you're going to have a multilinear extension. So it is kind of a you will have some degree more than two or three etc.

the hyper surface but actually this is a it's corresponding hyper plane unique hyper plane actually that evaluates to the same value for all of the hyper. So we have one plane but we may have a infinite number of a hypers setting to place the same points there exactly same for paris there and we we use the f tilda uh for the notation. So if you see the f tilda actually the tilda means that oh it's a multi-linear uh polomial. So the atmost degree is one always if you see okay there is some f to oh it's a something corresponding multilinear polomial for a given surface and here is actually how to make the multilinear extension in a in an easier way. Uh we can define a uh special polomial.

So actually if the f has a n variant polomial we can try to define a 2 n variant polomial. eq is a two nar polomial. So the first n variate is we can actually uh name that as x and then for the later part uh let's denote them as y. And this is actually how we uh design this special polomial. So EQ is a unique uh multilinear polomial.

So we have only one EQ polomial for a given boolean hyper cube. And actually uh it interpolates the voltages like this. It gives you zero. When the first part and the later part actually different. When the first part and the letter part is equal to each other, it gives you one.

This is a polomial. Then what happens if you just multiply this uh special equal polomial to the original polomial then actually it will give you always the same value or the boolean hyper but actually but it will not give you some uh values or the other vertices out of the boolean here Because of that, if you think about that, the sum of the f of x multiplied by equal polomial is a multilinear polomial regarding to y. And that f tilda of y actually will give you the same value for all of the boolean cube with the original f of x. This is actually how you can make a multilinear extension. fa of y is a is a multilinear polomial and when x is multiple with y it will return you zero.

So anyway if you sum everything it will be zero only except when x = to one. Um it's because of the actually it's it gives you the same value compared to the f of x. Yeah. This is the multilinear extension and do you have any sense here? I mean Uh let's see the example of the QAP L say L is a multilinear polomial that interpolates some point uh let's say 6 R is a multi-linear polomial that means a place like something then let's say that okay L is a multivariate polomial of X1 X2 and X3 R is also the multiar polar polomial.

Oh, I'm sorry. Like this. What do we want to do? We're going to do the product, right? So we would love to multiply them and it's not multilinear polomial anymore, right?

But actually it will be evaluated to the same number with the output polomial. So we look to minus this without polomial and then we're going to bind the range only to the boolean hyper cube. We're going to bind the range only to the boo hyper cube using the equal poly. The cube is so it's all the zero and one values right you're using that to bind this exactly saying you know look like This why is the two y uh is an uh additional variables and you know that we explained about the how to find the range uh before here actually this will be uh the kind of a random numbers here. I mean we are actually examining this relation only for the boolean hyper cube only for the elements on the boolean hyper cube right?

If this holds true, it will become zero. If that is true, right? It doesn't matter actually what is multiplied by behind. So it will always return zero. So if we do a sum check, if we do grand sum check of this thing then actually the grand should equal to zero regardless actually what is multiplied by the the second term.

So it will hold true to always zero and actually we are just uh choosing the second term as the equal polomial here. Then let's see actually what happens here. Uh we're going to put random vector to the y. Let's say we are actually putting some random vector to the y and if we examine that and for example if you evaluate that at some point on the volume hyper cube then actually this will give you some random number because because of this the second random term because this equal polomial gives you zero or one for the polar hyper cube but actually it will give you a different some random number for uh out of the boolean hyper cube on the on the uh field hyper cube. So actually it should hold true to zero.

Uh even if we just put some random R into the second letter part of the equal polomial. Actually if it holds true it means that L R will actually evaluate to all well all over the Band not recommended. So it's too random. This one check actually we can do that but not recommended. So we need to we need to actually pick another random which is different with this random.

Okay after that we're going to do the sum check. We're going to do the sum check. Then uh we're going to pick another random from the interactive protocol. So we're going to pick R1, R2, R3. Actually that will be different with the with this random actually picked by the verifier at the beginning of this protocol.

Does it make sense to everyone? Can you elaborate a little bit on evaluating on the boolean hyperloop for that specific L * R. Okay. Uh L R - O uh for example let's say we are evaluating at 0 0 1 0 1 0 for the speed L R O 3 5 actually this is actually what we want to see so if we minus this actually it will give us zero right but what if three four and five and And I 2 485 three right? No 11.

What about this? That's actually a plus one. I'm sorry. Three. is negative three.

So if you look like that if we sum every evaluations actually it will still hold zero but this is actually not the uh this is kind of the it's holding some false. We love to check that every L values times R values should equal to this output values. This is actually what you want to check. So to prevent that is actually return zero. I'm going to multiply a random value here which is probably three or four.

Oh unfortunately Yeah, maybe maybe something different. 2 1 - same I mean Oh, I'm sorry. You have to have different arm. Yeah, different different random. Yeah, different.

Yeah, not the same random. So, like multiplying eight, multiply one, multiply two, multiply three, multiply So it become kind of so random right how to make this random is using kind of equal right is to make sure but also to reduce yeah exactly so the reason why we using equal polomial is that uh actually it's adding this multiplying this random number so actually we can show that it to zero all over the boo hyper cube along with if you think about the only the second part it's still a multilinear polomial it's a multilinear extension so we can do something very easily uh only for the boolean But actually we are putting random arc which is out of the boolean. So actually it starts to output some random field there pol or actually if Multiply the single polomial actually we can achieve two things. First one. Okay.

If actually after multiplying this polomial it still if if it still satisfy the grand sum equals to zero it means that each uh evaluation at the of the element of the boolean hybrid cube actually holds true. And also we can uh do some song protocol easily using this uh think you just thinking this as a kind of a uh multilinear extent thing. So this is actually what you have done for and I mean Isn't it? We just designed L, R and O. This is actually what you have done.

So it's all so if we use this technique then we can transport the existing PL protocol to a hyperlunk protocol. You may heard of the hypernova, hyper blanc, hyper something. It means like okay we are using multi polomial and you know we can design these polomial equations polomial relations in so many creative way. We are just dividing the multiplication relation between three polomials. We may have kind of a five six polomials and we can try to define the relation between them.

In this case using this approach of the version yeah it's very efficient to interpolate them to this small L. I mean this multilinear Linear Raline O is very efficient. When you say designing different versions of polomials, what are the advantages that you have different? Uh, okay. It's a Yeah, let me share a little bit about the local.

Oh, uh, sorry, one more question about this. So, um, is it hyper cube um it will always be 00 01 and yeah zero or one. Okay. So can I increase the dimension of the hyper cube to do more than three like three variables? Sure.

I see. But actually when we try to I mean compare I mean uh this L or O actually should exist on the same dimension. Okay. But yeah, so one more dumb question. Why is this uh why why is the cube having the dimension of uh 0?

Like why is it a cube so to say? Actually we can also try to use minus one and one or maybe okay we can try to use a two degree multi- variable polomial for example okay not only just interpolating polomials to 0 1 what about 0 1 and two we can make it definitely definitely we can do that but that is not ah okay this is not a question actually if we just uh if we analyze the complexity of our computation the optimal is actually when we are using the boolean hyper where it's linear and it's very nice to deal with because of and also yeah rather than using one and minus one actually using zero and one is the most efficient for many cases yeah because actually if you put zero it cancels the terms every every every terms you can always stretch the dimensions such that you can always you pick a weird shape, you can still become just Yeah. Yeah. So definitely actually we can also use the uh we can try to interpolate those things within uh another hyper cube not the boolean hyper cube using the multiplicated subgroups hyper cube. But like for example using it Third root of unity maybe okay omega zero omega one and omega two and then we can let some surface in the points using those things but actually yeah the the the most efficient case is that actually we make it boolean case that is the reason why we using boolean hyper cube instead of the hyper cube And maybe uh should we introduce the kind of the other uses of the uh defining the polomial relation?

Uh okay. So actually this is something a very new research that we are doing and we actually haven't accomplished this yet. [Music] So let me share that. Okay, [Music] it's recorded. Is it getting recorded?

Yeah. Yeah. Uh don't don't worry. I'll I'll I'll make sure to let you take a look before I send it anywhere. So, uh yeah, just please keep this not being public published.

Okay. I I I can stop recording. Yeah. Okay. I mean actually everything is based on this zero check because uh we are actually checking the identities and if we just move something from the on the uh opposite side then we are just checking zero every time.

So zero tech actually uh plays a really foundational role when we are dealing with the polomial IOPS. So this is actually what we have done and I just introduce the uh we going to put the random r to the y and actually we're going to get the f hat there and we are using we are actually doing the sum check for f head actually if the f the grand sum of the f head uh is zero. It means that f of x will evaluate to zero all over the boolean hyper cube. It doesn't mean that f of x is a zero polomial. It will have a different point for other vertices in out of the boolean hyper cube.

So it's something like this. So we have a boolean hyper cube here. And we have a another point here. So the surface actually like look like this. And just uh interpolating these zeros at the boolean hyper cube.

But actually interpolating other values out of the within the constraint of the cube. It's always zero. Within the constraint of a cube is always zero. The boolean cube. Yeah.

So actually this is actually what we've done. I mean the R and R prime is something that uh R prime is picked by the verifier at first and R is a uh random during the subject protocol. So R1, R2, R3 that we are picking during the process and this is about the uh multiple polomial schemes and basically we can use the same approach using KGA. Yep. And this is about the product chart.

Actually we can we should be able to do the product check to do the permutation check to do the pock wiring. Okay. Right. So if you can do product check it means that we can do permutation check. It means that we can wire some failings and the I mean the permutation check with the index permutation check.

So we should be able to define which index is a permutation of which index element with each other. Okay. Um Yep. This is actually very clever in uh invention from the hyper pl. So can you get actually what does that mean exactly?

Still reading. Yeah. So uh we are defining a new auxiliary polomial just like what we have done in the plank. We define a t in this case we will define another pol. Yeah, just like we define T and a little bit differently with the unary polomial.

Actually in the univer polomial we started from one and then we move to the next root of unity next root of next root of unity by multiplying root of unity to the x value. In this case, we're going to say that oh, we have a some values and then just like MLE tree isolating each axis and just like ML tree, we're going to multiply them and then we're going to multiply them and we're going to multiply them. We're going to multiply them like that. This is the approach that we are doing here. Let's see.

Uh this is a the definition of the auxilary polomial for the product check. Mhm. So this is a it means it's a multilinear polomial. So tilda of 0 comma x1 to the x1 will evaluate to a same value to the fill steps and the value f at v tilda of one comma x1 xn uh will return the same value tilda of a x1 x1 to the xn comma zero and x1 to xna 1. Okay.

Uh and actually the reason we are doing the product check is that for the permutation check. So we're going to define the fill does like this f of x over g of x. So it's a just interpolating the same result of f ofx over g of x for the given polar hyper cube. You should be able to interpolate a unique multilinear uh polomial. So the grand product of f tilda equals to one then we can do the uh permutate we may we might be able to do the permutation text between f and g.

This is actually what you want to do. Okay let's move to the next sprite. Okay. Uh and then for actually uh for the first round we're going to define a r of x and uh the value will be look like that v tilda 1 comma x - va x comma 0 * uh x 1 because you We define the uh v polomial uh in to satisfy uh fx plus zero basically like like this to satisfy uh relation like this. Yeah.

So we can expect that this part will become zero for all the hyper cube. So which means that we are doing some zero check actually just on the hyper because the last the identity it wasn't specified just on uh specifying just on the hyper even for the B yeah even even for the B2 and then this is the first round and for the second We're going to define the second uh auxiliary pol as uh 0 x * g of x - fx. V 0 x to the 0 commute f to the Um, let's check. Oh, yeah. Correct.

Yeah, it's correct. Uh, let's see. I just move this. Um okay what I'm going to do is actually checking this the final auxiliary polar h all over the hyper cube with n + one dimensional cube uh which means that uh it will be zero on every case. Actually let's try to write down the white 1 - x0 times r1 x actually uh plus x0 0 * r x will equal to zero hyper right and then uh what does that mean?

Okay. So when x0 is one x0 is one it's just r2. When x0 is zero zero it's just one. Yeah. So yeah, we are doing the some for the R1 also something for the R2, right?

Yeah, doing some check for the R1 and doing something for the R2. Zero check, right? Yeah, zero check. Yeah, exactly. The zero check for the R1 is just for the R2.

So we're saying that if we do a pol [Music] check on we are doing a zero check on h head. Yeah. Actually, it'll be good to write down with the exact case. Let's say we have a two variables x1 and x2. And also we have a x0 here.

Let's say 0 0 1 1 0 1 1. And the uh in this case the vilda We'll have a eight point 0 0 to I'm sorry, by the definition. Find the definition for this case. Actually, we're going to make it uh exactly same with f_sub_1 2 3 4 for example. Let's say f0 comma zero.

So f_sub_1 f_sub_2 f_sub_3. Okay. So it will become f_sub_1 f_sub_2 f_sub_3 that is f_sub_4 and from 3 = 1 it will uh become the the values when the b ta 0 n1 is which means uh okay let's say this Let's say this is V1, V2, V3, V 4, 5, V6, V7, and V8. And then let's try to draw a line like this. Uh actually what we want to do is that V1 2.

34 is the f value right actually we want to make uh we we'd love to make the multiplication of them so when we think about that we can we should be able to multiply them v1 * v2 let's try to multiply them and actually we can also try to multiply Finally it should equal to f_sub_1 f_sub_2 f_sub_3 f_sub_4 actually what is the v1 and v2 here 00 0 and 001 this is actually the v5 right we are fixing the first two part and actually making zero or in one so this is actually be Five. What should be the phase six? We fix the first two coordinates with zero and one and change that with zero and one. So actually becomes a 36 and it becomes a base seven right is that correct no I don't yeah it's not B7 I think yeah V5 V6 one7 V1 comma 0 is V5 and 1 comma 0 0 is 0 0 comma 0 is one 0 0 comma 1 is one actually f_sub_1 * f_sub_2 Yes. So, F1* F2 is 35.

This is V6, V5 and V6 is we are actually uh fixing the first two using this zero and one zero and one. So V3 V5 and V3 V4 multiply the result will be V6 here. Okay, we have B5 and V6 and let's try to see what the V7 is. The V7 will be one comma 1 Z 1 Z comma 0 and one five and 36. So this should be the seven, right?

And what should be the V8? V8 one comma one comma one. So we have only this thing. So V8 equals to V7. No I'm sorry.

One comma V7. Okay. This is V7. V8 actually equal to B7 * V8 n one I think it's correct which means that it should equal to it should it should actually it will hold true then when only the 37 equals one I mean 38 should equal to 37 * 38 so it will hold true only when the value 37 equals to 1 v6 okay six uh the coordinate looks like one comma 0 comma 1 and let's see here 1 comma 0 comma 1 is a multiplication of 0 comma 1 and I'm sorry 1 comma 0 1 right 0 comma 1 comma 0 comma 1a 1 so 0 comma 1 comma 0 comma 1 comma 1 so this is three and four so actually six is a multiplication of three and Yeah, actually it's a little bit difficult to see the how the multiplication binary tree works before we actually write down the this equation. some some value.

What happens can So in this case is eight and + 8 is seven or eight for this one. For this one, for this example is the N seven or eight. N is seven. The N is seven. Here actually uh by the definition we can compute the V8 in this case.

actually VA equals to V7 * VA which means V7 is one. So the gram product becomes one. Okay. So it's the last term right because on on both it says that b is in the field where you know all the points are actually x to the x n + one but when you do that calculations I'm n and then we add one term is it because we add one term behind for both the polomials zero and one right so the s n plus one is technically or the zero that is technically xn plus Right. Yeah.

Imagine everything. Right. So, so um that corresponds to what has here. Thank you. Yes.

Which one you always It's 0 0 one right so in this case it's one one so I think that's the idea so that that that so go through and then become 01 011 and then you go to one yeah one then you combine Okay. Because of the zero x1. Yeah. So actually to make this into a polomial relation actually in this case we actually had two constraints. Mhm.

The first constraint was that V5 like if you just express it in a in a bitwise operate bitwise like expression then V5 is a multiplication of V1 and V2. V6 is a multiplication of V3 and V4. V7 is a multiplication of V5 and V6 and V8 will be a multiplication of V7 and V8 which means that V7 will be one. So this is this was the first constraint that we are trying to add here and the and the second constraint is that v_sub_1 will be equal to f_sub_1 v2 will be equal to f_sub_2 and v4 will be equal to f_sub_4. If that if we if this if we make some uh polomial relations that satisfy these two constraints then it will actually it means that grand product of f_sub_1 f2 f_sub_3 and f_sub_4 equals to one.

Okay, because the last one equals to one means everything else, right? I mean the V8 if the V8 equals to V7 * V8 it means V7 is one and then yeah actually this is the the I mean the R1 and the R2 was actually the constraint for each thing. The R1 is the constraint of the U multiplication of the binary binary tree and the R2 is the uh expression for the uh V1 of V23 V4 equals to the F in our case actually F is G over over I mean F over actually if you put here you put this instead of here it actually it'll uh return zero for every case. Yeah. So the R1 is expressing this binary trees multiplications and the root equals to one that is a R1 polomial there and all the polomial is expressing that okay V1 V3 V4 is equals to the F1 and F4 good we did the uh product check using multivariate polomial using some check because we are we can just do a zero check for R1 and R2 but this is a sum check zero check is a sum check but the whole thing is but actually you could yeah so in this case when we talk about gx and fx it's the two pol that we want to check if it's equivalent.

Right. Right. But actually we're going to do the permutation check here. So there will be a permutation relation actually uh if you add some randoms there and actually the grand product still exist some value. There will be kind of some permutation.

We need to think about the sigma permutation actually here. This is something pretty uh similar to what we have seen uh when I introduce the local argument using the sigma function right. Um, okay. Yeah, actually we are just doing the product check just by adding the sigma function additionally just like we did in the argument check. But in this case, you are so to say permutating the order of sigma, right?

Because sigma maps to another order. Yeah. Sigma actually will return only zero or one. Yeah. So actually we can make sure that it's transforming something in from a boolean hyper cube from another vertex in the boolean hyper cube.

Uh and in more actually in more detail uh we are adding a some uh random values there. Let's make sure that signal permutation works correctly. This is you remember the technique that we have used in the permutation check in the universe polomial. We actually yeah uh there also exist the sigma function actually and sigma function actually output the another root of unity. Because of that uh we actually evaluated polomial and we actually added the uh x value to the polomial while uh add the evaluation of the sigma value to the other polomial.

So you only use the unity on one side. Yeah. Um actually both are the root of unity but but one uses for f for f actually we are adding x but for g we are adding sigma of x. So and actually going to give you a root imunity actually it'll give you a kind of some transformation some root of immunity like X is the original permutation sigma X is another permutation. Uh and actually to make sure that we added some another gamma and we did some frame product check with each other.

In our case in the multivari case the root of unity is actually correspondent to the position vector and the position vector is actually the uh a un vertise vertex of one boolean hypers which means that we can express that in the bit expression. So we can express that you know uh it's it means that we are encoding a boolean hyper cube into a some number there. So in this case if you're using this since we are using boolean hyper cube. Mhm. If we have a lot of wiring we have a lot of wires that's a lot of permutation.

Does that mean I have to essentially increase the degree of my hyper cube? It doesn't. It doesn't. It's still the same size. It's still the same size.

So let's think about only the gamma f plus g comma and g plus g comma. If the brand product of f plus g comma and g plus g comma are equal to each other actually it means it's a permutation of each other. But actually we want to add some wiring. So we want to add some index and actually sigma function actually does that work. Sigma function is actually transforming the uh vertex in the boolean hyper field to another vertex in the boolean hyper field.

So it's not actually the exactly the just the vertices of the cube. It's the relation between the vertices encoded inside. So actually there might exist some vertex and we are expressing that into a bit operations. So we can express it another to another number and actually it's corresponding thereby it's corresponding vertex and we also expressing that to a number and actually uh if if it holds true it's kind of a index permutation without this it's a permutation definitely but if if it's al also holds true uh even after we add the position information together actually it means that it's an index fermentation so we can actually wire the fan out um delta You say uh to add the randomness why not actually. Yeah.

You can't control drama and drama is not right. actually I think there's one the final form of the univer case also has yeah actually I think uh if we if we don't use delta that actually we cannot uh separate the f and the relation between f and the sigma there so Maybe we we might be able to find another some sigma or polomial evaluation value that satisfy the the result. Why? It's actually not a kind of a sigma permutation, right? So, okay.

So, delta you're just proving f plus s is g plus f plus s is like a whole right like without the delta. proving is the sum of msal um actually we are checking the product brand product here the reason including delta. Uh without delta. Yeah. Uh I think we can try to make a some vector without a vector.

This one is not exactly the relation between asal as yeah actually I think we can try to find how to attack that when when if we uh didn't use delta I think I I'm pretty sure that we can find the uh attack case attack scenario without delta okay Yeah. So, we actually have completed all the parts that we wanted to cover during the workshop. So, we're going to have the final breakout session and then uh after that we're going to do the speed run from the day one part one to this multivariate subject. Okay. Hold on.

I'm going to share the multivariate uh slide in the telegram chat. So for the final 40 minutes of a breakout group session uh let's try to uh exactly do this product check and permutation check. Okay. And let's try to understand that how we can use this for a plot. Okay.

We had L polomial, R polomial and O polomial and actually we just wanted to wire the fan in and van out. Okay. Right. This is actually what you want to do. Okay.

So you want to calculate I want to understand how that works. Yeah. For hyperform basically, right? Okay. You know we already did a zero check.

Yeah. Yeah. We did we do need a some check. Uh we did the zero check for this over the previous breakout process. Some check zero check.

Yeah, some check. Some check. We did some check. Uh we did only some check. Okay.

Then let's try to do the zero check. Okay. And then also the product check, permutation check. Okay. Yeah, we can do that.

Okay. Okay. Let's go. You want to get We can do that. Okay.

First actually we have visited the abstract algebra on the first day. So what was the group? group is just a set actually which has a binary operation which has some properties. So we we are a group and if what happens if I if we add me and vent if it's a group like maybe Preston might be the result right basically any one this is just a group and we have binary operation and how why the result is present actually we can define any kind of binary operation role there so we have numbers or we can make the group with elliptical point and etc. So that was actually the group right.

So because of that we can also see that Caesar cipher was also a group the group elements are the alphabets and what was the result of the binary operation between alphabets actually it's kind of shifting them to another alphabet right so we could see that oh ca cipher is also a group but there was a one problem is that oh to use it as an encryption It's so easy right because of that how can you make much more difficult make it a multiplicative sub yeah actually we made it as a actually it was a addition group so we made it as a multiplicative group we actually choose cho actually we chose a generator G 19 and we mapped that using 19 to the exponent the corresponding number of the alphabet actually we mapped it if actually it is really difficult to see exactly what the is a number inside of the generator. So this was called the discrete logarithm problem right. So if we actually have the discrete logarithm problem it becomes much difficult to see actually what value inside of the uh exponent of the generator and then Okay, using this fast we're going to actually we we could define another called uh group using adaptive curve points. While we are actually defineing the curve points, we already did a pretty similar thing via the shame secret sharing. Right.

When we started the session actually we get we got the QR codes with the with the actually random looking X and Y points. Then we interpolated the polomial and evaluated that actually Z evaluated that at night and he got drained a 10 cups of coffee. Yeah. Actually when Ziki drained that Ziki needed to compute that but actually it was a really big number. So the degree of six but the number size was almost 254 bits which means if you multiply that by six times it's more than a,000 bits and it's it's a the computer cannot compute that.

So actually the method to avoid is actually using the field arithmetization. So when ZK drank that uh ZK actually did the field modularizations uh for every multiplications. So it was the reason why we can compute something in a much more efficient way. So using this fact we define electric curves on a prime field just like what we did in Shir and then actually we can compute the um the addition actually we define the additional points and then the addition of points is actually defined as a the multiplication of X XP XQ like YP and YQ etc. And actually we can compute that in field in the prime field in an efficient way.

Uh okay. So in elliptic curve uh we define the basic board of the elliptic curve which is called the bias transport which looks like this. And then we define the binary operation between the group elements by a geometric order. Like if this is P and if this is Q, we are defining that three points are on the same line. So we are defining that P + Q + Q P + Q plus R equals zero.

So we define okay uh p + q is minus sorry r this one. So we find this actually defining this uh line and then find the intersection and then reverse the y value was the way to compute the uh group binary operation in elliptic curve. But as we see actually it includes some edge cases right edge cases like this. Yeah, actually it doesn't uh have any intersection. So because of that we need to compute that uh by some blown control.

So it's checking that all the edge cases. So it's not that efficient in uh when we try to compute the binary operations because of that actually we introduced a much more efficient curve which is called Edward curves curve actually Edward curves actually look like that. So it works just like a unicircle. So we can use the order equation like this. So gamma is the alpha plus beta like that.

So without any edge cases. So because of that it's really convenient to compute the result and also uh we have a twisted edward curve and twisted adward curves introduces the uh pairing functions to there using Edward curve actually we can define some pairing function and what is the pairing function before we go to pairing We did the ECD. Yes. Ellis, Bob, call exist. Ellis know Ellis's secret key A.

Bob knows Bob's secret B. And Ellis share her public key in the form of G to the A. Bob shares his public in the form of G to the B. And they can create a shared key only symbol with G to the AB. And actually I introduced some real example that Carl comes in and accidentally car exploited this key hack this key and then Carl wants to check oh this is exactly from Alice's public key Bob's public key to try to use that how to check it we actually introduce the parent function here actually will result the same value like this one actually to uh be more precisely saying it's a it's in group one group two and the result is group T actually uh let's just get the intuitive sense so we are we are not saying about group one and group two so if you have a two things in curve points elements uh without knowing its scalar private we can compare the values.

Actually it is introducing our method in evaluating more polomial in group element form. Yeah. So what was the first case uh that we have done using the pairings on the first day the last the at the end of the day one first thing KG we did KG KG wasn't it we were debating about what what is group one. So actually what is the KG? KJ was that key.

Okay, you have a polomial and we don't want to share your polomial uh in detail. So we're going to share your polomial in a group form and uh I'm going to let commit to wan's polomial. So to let commit to the polomial I pick some random number r and would you please evaluate your polomial at r and would you please give me that in form. So wank give me g to the f of y it becomes wank's polomial commitment and then wank argues that uh that the polomial evaluates to some value at nine actually this is wink's argument and then uh not to be cheated by wanka actually we are requesting oh you please give me your proof that that is correct was actually what we are doing and to make If your polomial will is evaluated at y1 at x1 then let's try to subtract your polomial to y1 and we're going to say that this is the first point p1 right and then uh if your pol uh actually is f of x - y1 but p1 of x1 will value to zero. Right?

Because of that it means you should be able to write that in the form of x - x1 times some quotient polomial because it will go to zero anyway. It means you have a factor of the x - x1. So let's say this is the p2 p1. I think I can compute p1 as a verifier because you already gave me some your your uh commitment here. What I want to do is that okay P if P1 equals to P2 the evaluation of P1 at the random number R should equal to the evaluation of the random number R of the P2 right so I can I can compute the evaluation here in the group part because Ron G give gave them to me how do we compute this one gq is also in the group form yeah So to compute this bra need to give me the g to the q of rx and actually we are checking that using the pairing.

So you say in a group form group four group form we can check the pairing to check it all true. This was the kgj polom and when we are doing that uh we evaluated those polomials at a random number and what is the uh soundness of this uh argument here. What what is the soundness of this proof? Right. Right.

Because this is a P1, this is P2 and we may have P1 and we are saying that oh P1 is actually exactly same to P2. But if actually welcome cheated on us maybe P2 will look like this. And there might exist some maximum d + 1 + one right d + one uh intersections and actually it will be kind of some uh false cases that our examine actually saying true uh even it's not true it was the it was the the mean it was the sub Right. And actually rather than making it in a interactive form actually we can try to uh create this in a non-interactive board. So transforming interactive ping to a non-interactive ping is actually called the fias transformation.

And how how how did it do that in kg? Yeah, we made towel. We made a towel which might be Ellis, Bob, Paul, Davies, some some randoms. And then actually we could create the powers of towel through the multipart computations, right? And then if we have that towel, actually you can still create the we can still evaluate polomial in the group by doing group operations using powers of tow instead of knowing the exact value of the mysterious tower then uh it will actually successfully transform our protocol from non from interactive setup to a non-interactive setup.

This was the uh Pome transformation using the trusty setup and multiart computation. Thank you so much. Okay. And so basically what we have done is a checking word pairings I mean I mean we actually using pairings we have checked the multiplication of a polomial because we have we have done the f of x minus something y1 is a z of x and q of x and something so it's a multiplication of polomials And we are letting you share Z and Q in the form of a group element. And then actually we are checking the let's say G2 G2 is for Q and we are checking the pairing like oh it show like like this.

So we while we are having only this thing we can try actually this equation holds true on the group uh with the group elements using pairing. So we could do some uh pol multiplication of polomials there which means that we can design to check the relations between polomials many many things and we uh the first thing that we have done was the bench opening of KG polinomial. So rather than open only one values actually we can let open three values at once. So would you give me your three numbers and you will interpolate them in a new new polomial. So actually gave me a new polomial like this.

It will interpolate like three four five interplay some values. So we are sharing r of x and then we can also check that oh this w comes sharing 0a 3 1 comma 4 2a 5 is actually on the polomial f we can check it like okay w I'm going to subtract your polomial with the remainder polomial and it should be able to be uh divide by a zero polomial which is actually vanishes on on those values and you should be able to give me your quotient polomial. So we designed a new polomial relation between these four polomials. Before that we had some relation between three polomials and we now have uh added a one more polomial. So this thing is how to design polomial IOPS.

So it was a kind of our second polomial if that we have designed you know a bench opening and actually oh welcome already shared another thing that f of x minus y1 actually uh I mean f ofx is evaluated to y1 and x1 and this is the second information when shares with does. So rather than checking that twice, we can check it at once by doing a random linear combination. It introduces the batch evaluation of a multiple polomial relations. So now we know how to design the polomial IOPS using this fact. We're going to try to design a polomial of P to prove the result of a computation.

So in computation what do we have X or or N etc. And then we can say that okay let's try to uh prove some some binary operations and let's only try to focus on the multiplication at first. So we're going to have a left polom left input left fan in right fan in and it's multiplication will equal to fan out and actually if it holds true we should be able to make it like this and then okay uh how How can we uh check this equation in an efficient way? We need to make some range to check this equation. So okay, let's make L interpolate to a given values 3 4 5 at which values?

At which values? Huh? No, we we're going to we're going to let L interpolate three four five at some X values. Yeah. So L of omega zero will evolve to three four five like that and also for the right right polomial four four and the output will be like 12 16 20.

So we have a L of X now which is a degree which has degree two and R of X which has degree two O X which is degree two and then if we multiply L of X and R of X and then subtract this with all of X actually it will evaluate to zero for the given range the Z Q of X where Z vanishes to zero on the root of unities times Q of X some co polomial and if you use the root of unity the zero polomial is pretty easily computed. What is it? X to the X to the 3 - one, right? 3. Okay.

X. Yeah. So this is the QAP. We designed the the quadratic arithmetic program. We designed the quad arithmetic program.

But so because of that if we if we actually prove that oh w shared left polomial right polial and polomial and I asked that oh please give me your quotion polomial and then let me prove that using using pairing it means oh your left and right polomial is exactly a multiplication relation between your outputs. So we prove the quadratic arithmetic program but it's not enough to express a old kind of programs because we missed addition. So we invented some way to put something into this left polomial and right polomial in a way using that type is a it was next using alpha beta. No yeah using linear combination because we are actually constraining that with rank one. So using the rank constraint constraint system uh we are actually okay when let's say you have a bunch of witnesses you have a w has a bunch of witnesses like that and then you can put uh your witness using a linear combination to this left input or to the right input that was R1 CS actually what we have So R1C has CS actually has some design rules like we have a multiplication gate it always outputs witness and actually multiplication gates actually can accept two inputs to fan in and each fan in is actually a linear combination and this is actually what we have done using R1 CS.

So using RNCs uh we can express some program to act QAP but it's still not enough actually what's the next step hiding actually uh it doesn't hide value exactly it it's hiding value a little bit in a group form but actually we can uh brute force some tag or uh we can get some hint from there. So to completely hide the value the basic approach that we are doing is adding salt just like Peter commitment and actually what we have done in the shor signature on the first day. So using that okay uh we're going to add some random thing and let's use that in the growth 16 protocol. What's the growth 16? So run this is kind of a very simple thing we just doing QAP but it's not hiding information completely.

So we are adding some salt that's gross 360 and after that recently uh some some people like Ariel and actually they invented a new protocol I mean how to define the arithmet arithmetizations how to define the circuits. Okay. So rather than just uh stopped by the QAP and RNCs uh we know how to design this relation between polomials. So okay what about if we design the uh operation gate in a much more clear way that is the problem. So how can we do that?

For example, let's say okay we have some value three and five and actually this is the gate is multiplication and in this case we have a two and four the actually plus let's let's use a multiplication addition right now and four * 4 is actually 8 15 6 and 16. Okay. Then uh how can we interpret this into a polomial relations? Okay. So we going to have a yeah we're going to we're going to interpolate this anyway into L polomial.

We're going to interpolate this anyway to the all polomial and all pol. And then L time minus O only for these selectors. So we're going to have another selector polomial and selector. This selector will uh actually returns one if the gate is multiplication and it will return zero if the if the game is addition. So plus l + r - o * 1 - s it make sense right?

as for yeah this is actually one zero one. So we can actually define a new polomial relation but actually uh sometimes not sometimes uh we would love to actually use this value to here because we need to able to actually use some values as a value from something out. So to connect those values we need wiring. We need some wiring like this. So in this case it should be like 3 * 5 15 goes here and it will be like 16 and we're going to use the 2 + 3 becomes five and this as a fanning for the first gate and etc.

Let's try to label them. W1, W2, W3, W4, W5, W6, W7, W8, and W9. In this case, we can see that W2 should equal to W6 and W3 should equal to W7. How to make sure? another pol.

Yeah, we need to define another polomial that make sure that uh w a vector of w1 to w9 and w1 and w 2 6 w3 w Oh no, not W3. W7 W7 W4 W5 W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W 2 W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W 3 W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W 8 W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W W 9 Actually these two polomial do two vectors are equal to each other which means that they are permutation of each other. to make sure that we need to know which index to switch to each other. Okay, to do that we did the check permutation check and to do that we needed to the product check but product check doesn't make sure us that it's exactly the permutation. For example, when we do the product check, when we do the product check, three four six actually the uh trend product of these three values will give us 48.

No, 72 72. uh and its permutation definitely will give us the same value definitely but actually we can make the same value with different numbers like uh three 8 three will give us the same value 72. So to prevent this actually doing a product check is not enough for permutation check rather than that we're going to add + 1 + 2 + 3 + 1 no not like this plus random plus r right I'm sorry random for example let's say we are adding a random let's pick a random number Yeah. What about four? 12 two.

Thank you so much. Okay. Then we're going to have five six eight and the value becomes uh 13 times 240. Okay. Yeah.

That's 6 five definitely will become 240 in this case four I five 10 five it's 250 yes oh different oh they are not permutation of each other okay to do that okay if f of x the evaluation of this polomial over The multiplicated subgroup which means the rate of unities is a permutation of G of X then the grand product over the multiplicate subgroup of F of X plus some random number should equal to product of G of X plus some random number. That's the permutation check that we're going to do. So we're going to we're going to say this is F prime. We're going to say this is a G prime. Which means that uh FP prime over G prime.

The grand pro of F prime over G prime will equal to one. So we know how to do that for unar polomial. How to do that? Yeah, let's see how to do that. For unary polomial, first for the unary polomial we define a new auxiliary polomial t and make it actually have some values just like uh t of omega x.

actually equals to t of x times uh f of f ofx. No, am I wrong? I think you're right. Let me check. I think I think it's correct.

Yeah. Then if you make like this then it should look like one. Right. And then and we make t of one to = to 1. Right.

like this. And then at the end the t omega to the n actually equals to t1us one which means actually this is t1. So It means f of one time f of omega to the n minus one actually equals to one. So we are just examining this relation by checking the pairing. Rankan, would you please try to compute your T polomial and please give me your commitment to the T the T of R and then I would love to evaluate that on uh actually yeah I mean I would love to evaluate that t of omega r equals to t r * f there.

So yeah this is actually what we are doing for product check and then we can do the permutation check then actually we can do the pl protocol that was a univariate funk but it also has some limitation that interpolating a very big data to a polomial cost a O of N log N coast. So if we uh discovered a another approach like using a multilinear polomials instead of a interpolating those things on a unar polomial. Okay. And yeah we are almost uh getting done. So for for the unary polomial I mean the for the for the multivariate polomial uh we define a some hybrid cube using a boolean values and it means like we going to have some vertex vertex vertexes on some space hypers space and we should be able to assign some values into them.

Is actually the how the integrated polomial looks like x1 x2 and x3 and we should be able to assign some values over there three four four three like this. Okay. So we can encode some data some vector into inverary polomial or in this like this into a multivariate polomial and if we interpolate this to the multivariate polomial then how we can check the L * R - O true = to 0 true for a given range. How to do that in the univer polomial? Actually we use the range using a multiplicated subgroup and we use the quotient polomial there and in multivariate setup actually we are using hyper cube instead of this multiplicative subgroup and we are checking that if this holds true if you multiply some which polomial eq AQ polomial actually uh an x and some random vector yeah with a x and some random vector actually it will give us the same value if we think about it's a polomial regarding to y and actually it becomes a multilinear polomial to us but actually if we just put the random order here it's putting actually multiplied by some random evaluations by the equal polomials.

So it means that oh L * R minus O is always zero pull over the B hyper cube. That was a zero check that we are doing and then okay we know now how to do the zero check and this is the actually uh product check in the universe polomial is al actually doing the zero check at the end. The zero is the final step checking the polomial identities and then in multivariate setup product check. Okay. Okay.

Yeah. We have a just like we defined t in the universe polomial. Now we define a multilinear polomials v tilda v and actually v tilda will actually uh satisfy a condition and I'm going to I'm going to assign some values. Let's say we are defining that in a two-dimensional boo hyper cube and the three is actually 2 + one dimensional hyper cube in in this case. So I want to assign value in this binary tree first.

So this is V1, V2, V3, V4, V5, V6, and this is 37. And I'm going to label that with the position of vector 2 starts from 0 0 and 0 0 1 0 1 0 0 1 1. And now it starts from one. 1 0 0 1 0 1 1 Now it becomes 1 1 0 then 38 will be 111. It's not here.

Now let's try to define that. Oh, I hope 35 = to V1 * V2. I hope V6 = to V3 * V4. And I hope V7 equals to V5 * V6. This is what I hope.

And I hope V8 equals to 37 * V8. Uh so therefore actually 37 equal to one and which means that 31 * 3 2 * 3 3 * 3 4 equals to 1. So if I could uh define a polomial v to satisfy this equation and plus what if the v1 equals to f_sub_1 v_2 = to f_sub_2 v3 = to f_sub_3 and v4 = to f_sub_4. If I make some two relation pull this one and for this one then actually I can make sure that the evaluation of f and the grand product of the all the values of f will equal to one. Yeah.

And okay, let's try to write down like this. V1 is a V1 V 0 0 times 0 0 1 actually is actually 35 is 3 1 0 0 and 3 0 1 1 0 1 1 3 6 1 0 1 3 1 0 0 3 1 0 1 = 3 1 1 1 zero Okay. So uh let's let's three uh seven one one zero one one one = 3 1 1 Okay now we have some pattern which pattern uh we have a one here okay have 0 1 0 1 0 one actually it looks like oh There is a sub pattern. This one is actually this one and zero and one. This one is actually this one and 0 and one.

This one is actually this one and zero and one and zero and one. So using this okay great. So we can say that uh first how to make this relation it starts from zero x1 is zero. So we zero comma x = to this is the first relation. The second relation we let's say this is a x x comma 0 * v xa 1 = to 1 comma x.

So we define two relation and we're going to check this holds true all over the boolean hyper cube doing a balation then we can make sure that oh f_sub_1 * f_sub_2 * f_sub_3 * f_sub_4 equals to one. So we know how to do the product check on the multivariate polomial too.