Zero Knowledge Scholars Assembly 2024 (Day 2)

uh so to go to the polomial oracles uh let's try to recall some concepts here okay so uh what was the pairing so let's we actually uh would love to use the multiplicative notation as much as possible and actually parent function uh we have a sum or two values in a group and then if we uh put them in a pairing function they're going to output a uh target uh element which is which satisfies this one right actually it also has uh the distributed load Right. For example, a b a actually it should equal to uh a b + c. Actually, if you do that multiple times, then you can easily uh discover that um this is actually saying does it make sense because it's scaling? Yeah. So basically this can be hop over here or here anywhere actually it has some distributed load.

This is how the pairing works. Uh and using this uh property we designed a some uh polomial oracle yesterday. Actually we uh requested ZK to commit uh to his polomial and for actually ZK gave us some commitment which was a g of f of r and actually it was not revealing uh the coefficients or the details of the polomial what they had yesterday and to let him commit to this to his polomial actually we uh let come actually pick any random number there this one and then what did it do yesterday we asked uh ZK to create two different polomials two different pol because uh ZK's argument last uh yesterday was that he has a polomial and its evaluation at nine is something a private keys right and actually what we are going to do is that we want to prove that actually this is correct. So um we requested uh ZK to create two different polomial. One is that okay if you have your polomial f of x then we're going to subtract this with a your with with the uh private key y1 and then if you subtract your polomial with the given uh opening.

Actually, this is also called opening. Uh then it should be uh it should have a factor. Yeah. With x - x of one and and then you're going to uh have a quotient polomial. Does that make sense?

So we have a left hand side polomial and we have a right hand side polomial and then uh we are asking indicated okay we have these two different polomials now so we're going to ask you evaluate this left hand side polomial at a random number r and this one at a random number r and actually we are not going to share the exact value of random number r but we're going share the random number with the form of the powers uh of r right so using those things just doing a linear combination actually zk can compute actually the q of r here because we don't need to let zk compute the other things because we already know uh f of r because zk share that and we We can also compute uh g of g2 y1 easily and we can also compute g2 g2 r minus x1 easily and then what we need to do is check that okay evaluation of the p1 equals to evaluation of p2 at random number r but actually we don't know the exact number we know these three different part as a element of the group. So using that we are using pairing here. Using that we going to send this to target group. And using these two uh different element we also uh run a pairing function and compute and actually send them to target group and compare. Then if that's correct okay your operating is correct without revealing the exact polomial is this is actually what you have done yesterday you remember all right and then in this we actually visited a pretty many concepts so what mankcom did was is called public so because flipping coins 200 254 bits times I mean 254 times to make a 254 bit uh value and then using this public protocol we're going to pick a random number and retesting uh zk to evaluate that a rand random number and then what is the soundness of this evaluation the verification it was actually um related to the degree of this left hand side polomial and right hand side polomial.

What we want to do is actually we have this two polomial and our assumption is that if p1 equals to p2 at any point at any value actually they should be evaluated at uh to a same value right actually there exist some possibility uh even these two polomials are different but actually uh evaluates uh to a same What's the possibility actually? It's how many intersections those two polomials can have. This one or this one and then actually these two polomials are different but for this intersection actually uh they evaluate to a same value. So because of that actually when actually choosing a random value in this field this actually this kind of a uh in the field prior field and the possibility to pick uh those root uh value is kind of a d the degree uh of this polomial and the size of it is final. Yeah.

Does it make sense? Okay. So this is called spar zippel. Yeah. So many of the soundness problem when we are trying to design this kind of this is called polomial interactive oracle uh protocol because we let zk commit and create an oracle which is g2 f this will act as an oracle and also as an as a reference and then we are quering interactively with ZK that a could you please evaluate that random arc.

So this is called polomial interactive oracle protocol. Um okay. Uh and one more thing here was actually we have a some uh pretty good method to make this in a non-interactive setup. What was interactive here? Mhm.

Actually it was it wasn't pretty inactive because actually ZK actually should have commit uh to a random value but actually when come pick that random value. So verifier picks one and send it to the prover and prover sends the commitment and also prover after that prover actually argues that uh the opening of the polomial error and some value in this case nine is something it's an argument and then uh prover gives us a proof that the with the quotient polomial as its proof so it's a pretty interactive process but actually we can make this non interactive how how did I do that yesterday Yeah, choice is set up. So rather than actually uh when kind of making the randomness art actually we all together create the randomness and letting anyone no one knows the exact random R1, R2, R3 by doing a multi-arty computation together creating a uh trusty set of structured uh reference string. So in just in academic term it's called reference string the the result of the transit setup the powers and also we call that also powers of toao I think you might have heard of the powers of toao when you like deal with some 16 etc. So in this case to is a mysterious value which is a multiplies of the R1 R2 and RN this is called toao.

So we are sharing the powers of toao in the group elements for yeah this is polomial. Yes. So yesterday the verifier would generate the R, right? That's the interactive version of it. Right.

Right. The non-interactive version would be everyone contributing in R and then it creates some sort of towel. The towel will be the equivalent to that version of R. Right. Yeah.

Okay. But no one knows the exact detail towel there. Oh, they don't even know what to right. Yeah. Okay.

So when we actually doing this trust setup, I actually create R1 first and then I should throw away and should not share this with anyone. So it is called toxic waste. If I share that and every participants share the the intermediate values and actually we can construct what the top is there. So I'm just introducing some academic terms and this is transforming this interactive protocol to a non-interactive protocol is called fiat heristics. So we we say fiat transformation from a interactive setup to a non-interactive setup.

So you may heard of oh people say about people say about the shame people say about trust setup powers of tile public protocol polomial IOPS if you just heard of these terms and actually it seems difficult but actually uh this is exactly what we have done yesterday and yeah so uh we already touched the basic of the polomial yesterday and today we're going to visit a little bit uh some complex other concepts which is called IPA inner argument. This is actually kind of a very interactive polomial if and then some actually IPA introduces a lot of some interesting concepts in this virus for us uh which is also related to the another polomial protocol which is called some check or kind of holding schemes or but uh yeah we're going to we're going to see actually uh how what what the core concept is in the uh inner argument but before we go to the inpro argument we're going to actually see the variance of the K2J and what we can do uh in more detail using this page. Okay. Um okay before we go to the KG the details um actually we need we need the reason why we are using KJ. All right.

In this case uh actually let's say that actually I just distributed the QR codes but actually uh what if I just creates a different random pol uh able to solve the polomial forever because it's random pol right and you're just wasting Or for example, let's say that uh we have a different colors of QR codes, but actually some of the QR codes kind of work fake then actually uh how do you trust the codes correctly? Because let's say that the Labopolation takes a enormously large amount of resources for example and it's a huge and waste then before we run the interpolation we can request some proof that okay they are all on the same poly. This is something a use case that we can imagine in our uh yesterday's scenario. Then um what about uh actually isn't isn't there any some way to open some points at once? Can you imagine how you can do that?

This actually this is called batch and to give a yeah take the question all at all all would you please uh come out and explain let's Say let's say we have how many I mean how many that we want to do. So like we have a bunch of opening that right then taking the quot instead of opening instead of taking the quotion once we can do this We have a bunch of them. So should we add or should we? I think on the left side probably it's minus but on the right side it's multiplication. So it's um x - y y2 - y1 = to x - x1 * x - x2 qx cuz you're taking Oh yeah.

So you then do Yeah. Right. So let's say this is the first one. Y but then you can also then do the same thing again and have fxus let's say yus y1. No but that's still that's another vector.

I think it's easier. No, but that's a subtraction, right? So, you cannot move. That's not going to be a problem on the other side. What did you just now?

Yeah. But how do we aggregate multiple No, it doesn't make sense. Minus the sum of I'm speculating. Um you can you I don't I don't know if you can can we move quick to the or cuz cuz right now we are we are basically the quotient is actually what's left of the colonial right and given that fx is equal to y that's evaluation of a point that is known to public if you're opening more is it that we want to just show more stuff Yeah, let me give you some hints. Let me give you some hints.

So let's think about only the left hand side, right? And then in this case, what happens if we evaluate this left hand side at x i zero. For example, what we want is that left hand side evaluates to zero. If we evaluate that at x1, and and x2 x2 and oh okay okay this is actually why we want then let's think about the right hand side too oh power let's think about the right hand side too yes if the left hand side should be evaluated to zero at x1 and x2 and x3 what about the right hand side should be evaluated to so it's the product okay let's let's try again so it's No actually uh going this will be I actually [Music] pol the root no there is different Q because You dividing by different x minus x i. Oh, we can just you want to show one and then just inside.

Exactly. That's a good sense because we are aggregating. So zk will give us only one. Oh okay. So like And it's like a big X where this is actually like all the small like the individual ones, right?

But so then there is a different app. We know treat. We only know the treatment. So it's also a product of all yus I suppose to we are almost to the answer then uh because think about that um we only know the f g to the bar right then so we put in [Music] instead of uh this one instead of this uh product then maybe we can try to change this a little bit. What what what does this second term uh work here?

Let's think about the right hand side is evaluated to zero when we evaluate that at x1 x2 and x3 x4 which means left hand side should be zero too right if you put x1 the second term should be y1 y1 if you put x2 here second thing should be y2 It's three. And what should be this the second turn? Another pol. Another polomial that satisfies that satisfy uh it's kind of like how how it works for the 3D but you basically take G and then takes a value and then takes the i as the input and gives you the y of that specific x. Oh, so you basically find a polomial that isn't it won't it be the same as the original polomial you all the it's a different poly by computing the because the proven knows the values right so the prover computes like from X all the X I's and make make that interpolate into a polom.

Yes, that's the Oh, so the I get it. So it's a lower degree. I get it. So basically you're trying to then you just do like X - X I all together, right? No, just call it G.

I think you just call it Yeah. Yeah. Just like we are doing some another lab interpolation there. All right. Yeah.

So, okay. So, let's just say GX G of X is G of X1 is G of X I is Y. Yes, correct. That's what you want to do. Okay.

[Applause] Done. So, to substitute the lower Actually we notate that in like this f of x actually can be um written like um z of x times q of x plus r x. to the remainder. Yeah. Zero polomials and quotient polomial and the remainder polomial is a basic form of the division.

Right? Then actually if we put actually move this to the left hand side and we're going to see like f of x minus r of x will equal to g of x * q of x where z of x will be zero at x i uh And R of X will be will return Y I right X is a much lower degree. Okay. Then three or four like we are opening three values. Yeah.

Yeah. The degree should be two. Mhm. And yeah, and actually this can be computed uh by the verifier. Mhm.

Because we can just simply interpolate. Okay. X1, Y1, Y2, Y2, X3, Y3. We have those values. We interpolate polomial.

That's all. So we can compute this R of X. We know the coefficients. So because of that we should be able to compute the due to the R of to this is uh the batch opening uh using K equipment. Do you see some actually um actually this is pretty important concept here for the all of the polomial IPS because this is pretty simple like we are opening some values at given range.

So actually we are finding the range. We are finding the range. So let's see what's zero and quotient and remainder. So the cx is essentially the And the binding point Z of X Z Z of X actually binding this relation actually to the X1 and X2 and X3. Uh it will actually it will uh holds true uh only for the given range x1, x2 and x3.

I mean actually yeah we're going to see how how to use this binding polomial uh for the other cases but yeah for right now let's just think about that uh this is the basic form and sometimes actually we also say uh accumulator polomial instead of zero polomial so you can also say uh a of x and g of x plus r It does make sense, right? So you can also so maybe uh imagine actually what the main challenge here is. What do you see the main challenge is? And uh for ZK maybe is there anyone who can simply explain what you have done today what I've done for the last 10 minutes volunteer please what we have done in the last few minutes yeah I can go y so um so we started off with the prover showing the polomials and the prover is going to give them some points x1 x2 x3 to the verifier And what the verifier would do is they would try to interpolate based on the points that's given by the prover and that's how they got R of X and then they send that to the prover and then the prover use that to compute Q of X uh verifier you mean but how would the verifier comput Q of X without knowing the prover no RX can be computed by the verifier yes because verifier also have X X. Yes.

And Q of X is something that can that should be computed by the program. Yeah, it's computed by the prover. I get that. And that's where I'm lost. So here actually uh what we were doing is that we would love to uh verify that your openings and the all the shortcuts are exactly on the same poly at once.

Because if you think about the long run of the place and it's a really computational heavy and expensive work then we can do that I mean we can we can do that one time for example so we need a proof that every point on the same polomial and for that uh this is actually how we are doing the batch opening of the polomial at once because we are designing that actually yesterday We also designed a left hand side polomial, right hand side polomial and left hand side polomial was just kind of f of x - y1 yesterday. In this case we are defining the left hand side polomial with f of x minus another polomial r of x which is validated to y1 y2 y3 and x1 x2 then it will evaluated to zero for the given x values left hand side and then the right hand side will also look like should have the roots the with the vectors with x -1 x - 2 x - 3 and then a quotient polomial there. So this is the how we do the batch uh opening and the challenging point here is that what looks like the most difficult part. Yeah. In this in this logic, what is the most challenging part in terms of population or in terms of computation?

Computation. Yeah. We need to divide the polomial large polomial with this one. You know the large. Yeah.

So computing the quotient polomial is always a computational overhead when we actually create some change polomial happening. So in our example, is it worth it to do that or like right we're proving a um small number of openings I think it's still worried because we have a lot of combinations so we really don't know that actually which points are exactly the same point same point we really need to know that. Okay, great. Uh so actually we have covered uh the uh bad application component. So this is a base for and also we can define the remainder polomial with a simple interpolation.

Okay. Uh and finally the CT should actually share the quotient polomial. Okay. computing the coal polomial and then going to share the two of in another form and then finally we're going to check uh that okay if you have the polomial we have a this is a zero polomial so actually we are just checking this pairing Um okay and then I'm I would love to share the second example of how to use K2J that um let's recall yesterday's uh exercise we have done I mean to reconstruct a six degree polomial how many information did we need yesterday? Seven data, right?

So you can think like okay if you have a 10 degree polomial how many points do we need right? Then the tender polomial let's try to evaluate that at 1 2 3 4 5 6 7 9 and 10. and 11. And actually yeah it has some uh 11 information which means that polomial it actually has an information inside of it and the size of the polomial actually is corresponding to the size of the I mean the degree of the polomial. For example, um let's say that we are using a really uh large prime field.

Then I'm going to write the one degree polomial here. Okay. Right. This is a onederee pol. And let's see the twoderee polomial.

What about the 3D polomial? Actually, we need more space to write terms, right? So, this is the size of the polomial, size of the coefficients, size of the data. So if we have a many terms then actually it's including many information inside of it. So we can think about polomial is a way to some data.

So vice versa data can be encoded to polomials and polomial can be interpreted into some data. Right? So let's try to express some data uh in the form of polomial. Okay. Uh rank would you please give me some numbers?

5 to one. 5 to one it's a data 5 to one is a data and let's try to encode this to a polomial. It's also it's also some way to encode the data. And there is another way to x. Yeah, the right side [Music] actually I think uh the five degree polomial can express more information.

Maybe x= x and when x = 1 to two just like in array just like array but it's index index can be the x i what's the value of that array can be the y i this RCS here using X index. Yeah. Yeah. Right. X index using index for the X.

Yeah. That is how we code the values. Is this the most important is that is there a name for name uh this um name. So this is called this data usually is called as vector and then we encode this data into this form. Actually we can always express some d some polomial into two different form.

This is a coefficient form and this is called evaluation form. So in this case we're going to have a extra 0 five. Uh please interplay this thing. No. Yeah.

Anyway. Yeah. Let's say A and B. Good. We don't know what the A and B is.

This is called coefficient form. And this is called evaluation form. And anyway actually they are expressing a unique same polomial. So we can encode this vector into polomial into two different form equation form or evaluation form and then we're going to let you commit to your polomial and we're going to get the g to the f of f of power here and this is called vector commitment. Yeah, vector commment is just simply letting you actually transforming your vector encode your vector into a polomial form and then letting you commit to that polomial actually.

Yeah, maybe vector commment also can be kind of a local root commitment etc because local tree is basically an array how to express an array right and we can also express this array into polomial. So in terms of the kg command scheme factor commment means that okay we're going to say we're going to this here uh there exists some efficient way to include this vector into polomial. Maybe using zero 1 2 3 4 might be the one of the easiest way definitely. But actually there is a one more uh pretty efficient way that we can do which is called the root of unity. You have heard of it right?

Root of unity which is 30 days a omega. Okay. The root of unity means that uh omega omega 2 3 for example like this and actually in this case omega to the 3 will be one. Which means in this case we say that uh an element which satisfy uh the n exponentiation of the element becomes one is called the root of unity. So if we see the complex plane for example then let's say we have a some unit circle in this case uh let's say we have a one element here uh which angle is like 45 and we have a point here P and in this case P can be a root of unity of uh in this circle U it's uh which says it's a order to eight here.

Okay. The reason why we are using the unity is that uh what we're going to do is that actually we're going to use zero and one and two instead 0 and one and two for the x i right and actually we create the zero polomial z of x and the z of x actually uh it look like can you see x - x i x - like this. Then rather than putting 012, if we put the root of unity here, omega to the omega to the zero, omega to the one, omega to the omega to the two, then actually it can be equal Well, actually this can be interpreted to a different form pretty easily. Which form is that actually because you know omega to the 3 should be one which means actually this z of x is x to the 3 - 1. Z of x should be the x 3 - 1.

because it has three uh roots inside of that. So it should be the factor of x - omega to the 0x - omega x - omega omega omega x. So because of that you know it looks like this uh right? So one we have only one intersection which means that we have a three roots there and actually they becomes the root of unity right since you can convert that 3 x^ 3 the value of omega isn't it you will still use the roots in other cases of other pol because you encoding the coefficients into so the population of rx and calculation of let's QX still also uses root of unity in this case, right? Uh in this case um yeah Q of X actually depends on the root of unity because it the Q of X actually we are dividing that with a zero polomial and zero polomial we are using X I with omegas.

So yeah it affects the quotion polomial too. So you're replacing um instead of interpolating 0 1 2 3 4 or random number we just use. Yeah. So in our case x i becomes the omega to the i minus one case rather than just using i minus one. Yeah.

You still have to calculate first the root of from the right. For example, let's uh think about our prime field. The prime is seven. And what happens to two? Let's calculate two or one.

So two is a uh root of unity. the third root of unity in the prime root of seven because 2 to the three becomes one seven. So two is the n I mean third uh root of unity in of the five field seven of seven. What about if the p field is 11 and then if we choose three three nine uh six no five four 3 * 3 is 9. 9 * 3 27 - 8 is not 5.

5 * 3 15 - 11 4 * 3 12 - 11 is 1. Okay, great. So it's say uh 3 to 1 2 3 4 5 1 11. So in this case three is the fifth root of unity of prime field 11. This is actually how we calculate the unity.

So this is the rule of unity is used like in the first one we use the represent values that the initial values before we that's set up easy is that the reason or like I was also thinking that it's hard to compute a group we mentioned yesterday you only needed like G2 if it's one opening that's a pol that means you have many terms in. So if we're using does that mean we can compute less as long as we know how many? Yeah, actually that's also true because root of unity will make the zero polomial to the uh to the kind of five minus one and then we don't have any some additional terms if if you actually calculated this vector to zero and one and two and actually the zero polomial will look like a little bit different like 0 0 2 minus uh like 3x + 2 right I'm not sure but but so we still need like something but so then we still need that We still need to comput or like we need to in advance know the max batch size that we're going to um I actually I don't think so. Um the reason we are using the root of unity is that uh actually it gives us the the zero polomial in a simpler form and also it actually let us use the lron interpolation in a much simpler form. So if you use the root of unity especially when we interpolate these three polomial it becomes very easy to use the root of unity when we do the lab interpolations that's the kind of main reason so for example if you're actually uh having a pretty long array and data Let's say that we have a million uh data in an array which means that we need to interolate the polomial which degrees million and it's kind of a pretty difficult work uh if we use just a random number because we need to compute everything but if we use the root of unity then actually we can compute the logarithic basis polomial very quickly.

And then we just do the linear combination with the LR space polomial and the and the and the value and the back value is in the vector. So I guess my question is yesterday we said G2 computation is going to be expensive and that's why we when we comput the power of like when we did the trans we don't want to comput that many terms in G2 but in this case since the degree of the zero polomial will change depends on where we want to degree of pol depend also all the degrees in there escaping. Yeah. Um the polomial actually will be computed in G1. Um Actually I think I need to revisit that a bit that how the computational overhead comparing either G1 and G2.

52, right? How do I know where what is the field that I want to evaluate this pol in to get the root of unity from? Like how do I know what field to operate this in to get this to like W= 1 W = 5 = 2 W1 = 2 Yeah, basically 51= 2= 1. How do I find the root of unity in a in a given prime field? How do I know what fields operate?

Is it the field? Is it the field or the group that I want to use for the KG commitment? Yeah, actually in this case the field is where the uh this case field is where the where this kg polomial is defined on. So this polomial actually might be defined on a triump field. So we usually uh note that like f of x is a polomial define a prime field with uh degree n.

X nus one if we are actually including n data. Yeah. How do I understand how the first and second one in this one in this case actually uh let's say we are using the prime field with prime 7 and we found the third root of unity here and two is the third root of unity in this case actually we're going to the zero polomial will look like x -1 because 2 to the 0, x - 2, and x - 4. And actually, it should equal to the x to the 3 - 1 7 because we are doing the modularization. application let's say you know what you're operating on comput right right the space basis polomial of this right exactly so because of that if we actually use a fixed length to encode some data.

We can use the same logic basis. For example, if you want to encode some data, for example, uh we going to just like solidity, we're going to have a fixed length of array. If you have a fixed length of array then actually we can premp compute the long run basis polomial and cach them use them actually repeatively so in this case we know already so we don't need to compute the information we can just reuse the values in Yeah. Yeah. And when we compute the L interpolation and if we use this retribution then actually all of the terms is actually decided by the kind of FIA first transformation.

So we can compute the reference bases polomial correctly if you use the root of. So is it easy to find the like order it is from the original from the from the time field right given the size of like even the 11 is it easy to find the fifth order is three I actually uh don't exactly remember the algorithm but there is an algorithm to find the community Um, Do you want to have a breakout group session or do you want to go to the PS commment and in argument breakout session first? Great. Okay. Uh then in the break up session let's try to visit the concepts again by ourselves.

Okay. First of all, let's try to recall the first recall the concepts. carrying uh agreements. Uh shade public. Uh and we the polomial IO of P and B opening and the root of Yeah, let's go.

Oh boy. Um now we're going to talk about Zc. [Music] So now to try to utilize actually what I've learned and studied um yeah so we actually visited the one polomial scheme and um what is interactive or pro and also we have visited the polomic schemes. Okay, let's see uh in this case actually how to prove uh f of x1 = y1 and f of x2 = to y2 um we left actually uh make the polom schemes by evaluating that at the towel and actually we get we got the b to the f of toao force and then actually we did some uh query we actually made some two different polomial and then query that the random mysterious point mysterious value to this case actually uh [Music] This is actually what I've done. Then actually we can add more constraints.

Uh in this case actually what are our constraints? The constraints was they will be evaluated to zero for a given uh x values x1 and z. There are some constraints that we we have given there. And actually what about uh if we think about various system three pol. So in this case there is system left polomial, right pol and output polomial.

What does that mean? Maybe shall we try to um encode uh some values into a polomial. So let's say that okay I let's say in= 3 by 4 these three values into a one polomial let's say this l of x so this is a l x1 l x2 l x3 and we have a another value uh that two three four and let's say this is a right polomial okay we are actually saying that we have a two vectors this is a vector a and actually this is the vector b okay uh what happens if we do some hot product between these two vectors let's say Here we're going to have a another new vector C doing a hardware product between these two vectors. Then it becomes like six, right? It'll become like 15 18.

Okay, we have a three vectors now and these three vectors actually have some relationship between each other. The hotwork product here. So 6 is actually 3 * 2 15 is 5 * 3 sorry should be 16 should be four * 4 and then let's try to also encode this data to as an output polomial okay then okay uh what will happen to these three different polomials Can we actually uh some define some relationship between this polomial? Um I think yes. I think yes.

And what happens is that uh let's try to multiply these two polomial definitely this is not exactly same with this because the the degree of this left hand side I mean degree of the L of X times R of X will like four degree two degree two and multiplication of these two polomials will have a degree And this all polomial will have a degree two. But actually we have a method to define some relationship of that. How? Using the zero polomial. Let me show you how to do that.

L of X and O of X will equal to O of X at X1 and Y X2 and X3. Which means that if we subtract this value then they will evaluate to zero at X1 and X2 and X3. Does it make sense? So let's say that this is a actually auxiliary polomial P of X. We define a new polomial and this P of X will evaluate it to zero at XY if L of X and R of X O of X uh encoded correctly and satisfying this hot product relationship then this will evaluate it to zero.

Does it make sense? X and RX have the same. Uh yeah, let's say they have a same degree. So the we have a the size of vector is here three and the degree of L R O it's two. So it must be the same.

Uh the degree must be the uh same to actually They don't the only condition here L of X is that L of X will evaluate it to L1 L2 L3 at these three points. This is the only constraint. The first constraints that okay L of X is interpolating these vectors correctly at X1 X3 and for the R polomial the constraints symbol it interpolating it's interpolating 2 3 4 correctly X1 X3 all of X should have the same constraint and then we can actually define a new auxiliary polomial P of X by multiplying Find L and R polomial and subtract with O polomial and then the result it should be evaluated to zero and do three values. What does that mean? We can express this equation into a a little bit different form with a factored form with zero polomial and Quan polomial which zero polomials actually will be evaluated to zero and then we should be able to define this quot polomial from this by dividing this polomial p of x by z of x.

Okay. Uh so it's it is something like this. uh Wong has a vector has a data a vector a and also wong has a data vector b and rong also has a data vector c and then he's arguing that I have three vectors that satisfies C is an result of the hot product of these two vectors this is actually But when is not arg and then to verify that okay would you please give me your commitment for each vectors please give me your vector commitments for the first vector a vector b and vector c thank you so much we're going to have a l of toao r of toa of toao right thank you and then uh would you please multiply your encoded version of polomials of the l of x and r of x and then subtract them using the o of x and then actually they should be evaluated to zero at this x1 x3 33 values. So it should be able to be divided by zero polomial and it will have a co polomial. You should be able to compute that.

Would you please give me your quotient polomial with evaluating that at toao? Okay, thank you so much. So I have L of toao. I have to r of toao actually you also shared of toao but actually in form of the group element and we know z of toao and when can share the proof q of toao. Okay, let's try to do the pairing check.

Oh, it's we can do a pair check. If we do the pairing check, then oh great. We call it three vectors and they are actually have some relationship between them. And vector A product vector vector B is vector C. This is the same.

This looks the same as the KG. Yeah, that's RX. So it's actually fus y = y z y i the whole total. So it actually uh for for that it was for opening of values on the polomial. In this case we are not trying to open the values inside of the polomial rather than actually we are just still hiding the values but we are trying to define the relationship between polomials.

So we have a three different polomials which is an encoded version encoded form of these existing vectors. So we now have L polomial, R polomial and O polomial and actually the relationship between these three polomials is a polar product here of say a vector values and we are checking that is this correct is this correct polymer product thing we can also define a different thing definitely the addition so simple isn't it so simple That is so simple. So all of the thing is that we are designing the relationship between vectors in terms of a polomial. So we include vector into polomial and try to okay do they have some multiplication relation between each element then yeah they should yeah satisfy that in this range in so this zero polomial works as a binding the range of this relation here which means is that you know actually if we we when we product it's a multiplication which means that it's a degree four right degree four which means uh actually it'll uh it will satisfy L of X time R of X - O X uh value says zero only for X1 X2 and X3 it will not be zero at a random other values. So this is uh actually how uh we can bind the range of this relation.

We can do more. For example, let's say uh L of X and R of X. Okay. They are encoding some values three values but actually we have a relationship that this is plus so actually it's kind of a eight but they are multiplication then we're going to make a two different we're going to make a new polomial that L of X * R of X - O of X will evaluate to zero at Z X - X1 X - X2 only times Q of X on the other hand it will also evaluates to zero for X - X3 I mean L of X + R of X minus O of X will evaluate to zero only for X3. So we can divide actually some uh relation here.

So the zero polomial actually works as a way to buy the range of the relation. If we can actually if we uh use this kind of some how to define the relation um we can actually uh write a program using that. Let's see how we do that. Okay. Actually as I shared uh when we find the range using the root of unity is the most efficient way.

So now we're going to uh define uh the rank one constraint system. Okay. So we're going to have a three note. The first one is a witness. The first one is called witness and the second is called addition gate and the third one is called multiplication gate.

And we have some rule. First uh we also have a input wire. Input wire actually can uh send some values to other node. And in this case input wire comes from a witness or only from the addition gate which means multiplication gate cannot output a an input wire there. An input wire actually also has its own scalar value.

So when the input wire is connected to other node for example let's say a witness value was three but we have a input wire with scaler four then the value will be actually go go to the another node by the scale and the rule for the addition gate simply it has two input wires and up to one input wire simple and we can also make some combination linear combinations with uh addition gates and witness nodes. So if you have a three witness values here W1, W2, W3 and then using the input wire and the addition gate we can express some linear combination of the witness values. Okay. And the rule for the multiplication gate, multiplication gate will also accept two input wires. But actually it will output a new witness.

It doesn't output an input wire. And multiplication gate has a constraint with the output witness. This is actually where we are trying to use the pairing checking the constraint and checking the relation. Okay. So one constraint actually is a only a combination of the left input and right input and each input actually is a linear combination of witnesses.

This is a rank one constraint system. So one constraint actually has two inputs and each left input and right input is actually a linear combination of witness using the scalar values. So um Um okay now we are trying to make a real example how to write I'm sorry okay uh so when a multiplication gate uh exists it accepts input wires from left or Right? So it accept two input wires but the order of the input wire is a degree one which means the output constraints will not have a degree more than degree two. I mean it means like uh there will be some output okay there is a output and let's say here's a input the first input second input and maybe the result will be something like W1 * W2 this is okay But actually if this also a multiplication of two witnesses then the degree of this input is two.

It's not okay. Yeah. So each linear combination will have only degree one because it's a linear combination. Okay. So it's something that actually uh if we try to write a sub program uh using this uh R1 CS system in this case actually we have a three multiplicative gates.

Uh let's see. This is the first multiplication gate and this is the second multiplication gate and this is the third multiplication gate. In this case actually this is for the first multiplication unit. This is for the second multiplication. This is for the third multi multiplication gate.

Does it make sense? Um and you can see that Each of these multiplication gates affects a input wire and its order is a only one. It actually it it gives a two W 8 and linear combination of a W7 [Music] plus 2 W like this. So it's accepting two W8 instead of just one in the in the case of X the M1 passing through. Can you repeat your question again?

I think I think uh we we have a uh more intuitive uh example next. Let's see here. First of all, we going to uh we have a in in this case we have a uh nine witness values right from W1 to W9. So we can say that we have a witness vector W there yeah and then uh okay let's say we have a three multiplication gate. What we're going to do is that we're going to find the left input for each gate and also the right input for each gate and also the output for each gate.

How to make that? because each thing each left and right is a linear combination of. So it can be uh actually written a form as a inner product between two vectors. In this case uh uh okay this you can say that h1 is just like x1 x2 x3. So the left polomial will return uh the linear combination combination value at x1.

Let's see here the first multiplication. What should be the left polomial should evaluate to for the first most indicated gate? It should be evaluated to a 36. Right? And what should be what it should be valued to the second?

It should be valated to 2 W8 and it should be evaluated to at the 38 uh 8 W2 + 40 W1 right so the left polomial will have will will have its own evaluation values for uh for x1 x3 and each value will be expressed in a form of inner product between two vectors because it's just a linear combination. So in this case the first vector is a 0000 03 0 0 0 uh inner product the witness vector will return you 3 w uh 6 there in this case it will return two W8 exactly and in this case 4W1 + 8 W2 so it exactly outputs The uh left in is okay because it's a feed group. most between L and um Our mission is actually anyway uh getting the left pol computing the left pol and the efficient way to compute the left polomial is using inner product with the witness vector and uh the logic basis polomials uh which can express the left vector make sense. So we have a vector and we can pre compute the lo basis polomials with the same size of the witness vector and if you do argument then actually it's just computing how to compute the uh yeah the left pol Okay. Uh this one.

Yeah. Okay. Uh this one will L1 X will return will evaluate it to 0 and x1 zero at x2 but 40 and x3. This is L1 of X. L2 of X will be value to zero at X1, zero at X2 but a X3 like that.

So we are actually interpolating each column here exactly saying is wrong in the back. So we are computing nine uh nine polomial using interpolations and we are actually uh saying that as a l In this case, what exactly is actually this does not uh relate to the witness. It also it's only depend on the how the program looks like. So this is the information of the input wire. how how the scaler uh is actually uh sending the values to the multiplication unit.

So this basis is of course dependent on this and like naively we can just do it as like the input signals going in but is there like would there be a more efficient basis? Um I'm sorry actually this is not a basis. Uh it's a it's a we we have a L basis polomial but L1 of X is a combinations of the L basin actually the matrix. Yeah. So because the L1 of X is a definitely a linear combination of L based polomials with those values.

So we can easily compute the result using a uh matrix uh multiplications doing a linear combination. Yeah. So actually this is called a uh quadratic arithmetic program. So we are converting a uh circuit which can be inter actually interpreted as a program into a uh arithmetic form uh using these polomials. So we we we could actually compute L polomial or polomial O polomial uh separately and we can examine that examine three different polomials at x1 and x2 x3 just like what we did over there.

So in this case we define a uh new polomial and actually it will be evaluated to zero at x1 and x definitely we we're going to use the uh root of units here for x1 x That's all that's all about the uh QAP and R1Cs. So why do we need to break it down into left and right? Left and right. Okay. So we write a actually we wrote a circuit like this.

So we just wrote a program and the program can be interpreted into a a binary uh circuit uh which has a multiple orientation. And then we can also add some uh interesting properties like scaling or efficiencies. And then if you write a circuit like this, we're going to actually have a uh witness with this vector to assign values to this witness node. So we have a nine Japanese and we We are actually proving that oh I have nine values which satisfy these circuits condition and for example like we are uh opening the output W9 here for example if you open the output then actually oh it's actually these witness values are satisfying this circuit Then how actually you can prove that uh your witnesses are exactly satisfying the condition. Okay.

To the to make the witness satisfying this condition in our CS system we need to figure out how many multiplication gates this circuit have. In in our case we have a three multiplication gate and each multiplication gate will actually receive two inputs and each input is a linear combination of this witness. So for each multiplication gate we're going to have a left input we're going to have right input we're going to have a output node. So we're going to encode the result into a left polomial for three uh values x1 x3 also for the right polomial also for the h polomial. Yeah.

And when we compute the uh left polomial actually it's a linear combination of the just a linear combination of the circuit information and the witness. Actually we have visited we we we should have to vis visit the uh inner argument before we go to QAP but yeah anyway please explain why is it because want to satisfy that formula that the reason why we want to find the value uh actually witness value is your own Secret of Windy vector. The vector. Yeah. Wind vector is your own secret.

For example, you say your private keys that satisfy some certain conditions. So we need left right because it goes up to quadratic right but why can't we go up more why can't we like middle right that we can have like for example um like just unnecessary because we don't have a uh proper way for try pairing function. One one question regarding the last slide. Um so looking at the last slide you are creating you're interpolating the uh function L into uh basically based on the column and you're getting uh the current LX right in regards to the witness. Um so um the yeah sorry um the last slide so um you are you are interpolating here you're interpolating based on the weight on the wires right or But not the witness necessarily, right?

Cuz you know, or is it based on the witness? Cuz you Sorry. Yeah. So, no problem. Yes.

Uh so here you are interpolating based is it interpolating based on like no not on this side I think the next slide where you are interpolating you're showing that yeah here so you are interpolating based on the witness here right for the L um polomial interpolating you mean the L sub one L sub 2 they're interpolating the scalar values of the input wires Okay. So, but why do you have to uh do a inner product do a product argument with do a product of that um vector of polomials with the uh witness. Okay. Uh let me visit here again. Oh, okay.

Sorry, I got it. Um it's because LW is getting the Yeah, I got it. Okay. Sorry. Because actually it should um output um yeah the left linear combination.

Yes. Yes. And then if you put x1 here it it will give you a kind of a 0000 40 etc. Got it. If you do an inner product argument inner product you're going to get some 40 x1 and 40 w1 plus a w2.

That's why you are multiplying. Yeah. Yeah. Okay. Got it.

Just got it. Just needed to take a second. Okay. This is actually how we exactly um do a zc here because we actually uh inner product argument actually introduces uh how to do this uh inner product between these two vectors. So actually it's a really intuitive concept also to understand pro 162 and JB2 but uh let's go to the right Um okay in this case uh the circuit information is given right and the uh this L polomial this one the L sub W means that actually it's related to the weakness so it should be kind of some um including some hidden W's but this uh large L or O polomials actually they are just a interpolating the circuit information the scaler in widers.

So we can consider that as a kind of a publicly shared building, right? I mean uh is it it's a yeah that's why it's public here. Yeah, we just values the wire values. So they is a public uh which is shared between the prover and the verifier all together. Uh then uh when come actually has come with this.

So using the witness when does a some inner product uh using the circuit information and when comes with this. So when should be able to create three different polomials here L subw W X and L sub W of X R X and the output three different polomials here and they are just say inner product of the circuit information and W cons yeah then if con actually satisfies the circuit information correctly then it should satisfy this condition too. This is what actually what you have done there. If we put the x1 here then left value of the multiplication right value of the multiplication gate should equal to the output value of the multiplication gate for a given uh elements x1 x3. Yeah.

So we are uh learning term. Okay. could you please uh create a a polomial p / x and then uh let's try to examine that together with the zero polomials we use omega for x right we are using x1 omega to the 0 to the 1 omega to the instead of x1 x3. uh to examine that. Okay.

Uh let's visit the exact definition of the uh QAP here. Then QAP is just uh we we made the R1 system and we wrote circuit there and then If the witnesses actually satisfy the RCS condition then we can define a polomial uh relations between the LR O and the witness and actually this is the uh this is called the Q. So for the uh given x values x1, x3 the auxiliary polomial q of x will evaluate to zero. It means that it will be able to be get divided by zero polomial and have a quotion polomial and should be able to give me a quotion polomial that satisfy this all these conditions and then checking that just using the public protocol and uh And for lambda we are evaluating that at random ru what's h um referring to here h and h sub m okay so um h is uh technically means the multiplicative subgroup which is the set of the root of unity. Okay.

And hm is the set of root of unity used by this. So there's a h sub m there. Is there a difference between that set? Yeah. Ah okay.

I am actually uh denoting here m for the sub multiplicative subgroup for the multiplication gate. So in this case uh the h sub n is one and omega one and the two with the third root of unity. Let's try a little more. Um, okay. I am regretting that we skipped the Peter's commitment in the inro argument.

We can go back. We can go back. We can go back. I don't mind. I I think it's okay.

We can go back. Um actually it seem it seems like we already actually achieved our goal what you want to do isn't it because Bangkok has a witness values nine values and then okay if you have the nine values please make a three different polomials using a linear combinations with your with this vector test. So when should be able to output L w of x r w of x o w of x these three polomials and yeah please try to make the auxiliary polomial l * r minus o then it should be able to be get divided by zero polomials and please give me your co polomial and let's check at a random one then it's done actually we have examined the exact uh relation between those vectors we already actually have achieved what we want to do but it's not enough in what point what we are missing here what we are missing it seems like when has a witness all of to seems like it's hiding informations or of to seems like adding informations. Is that exactly hiding the information correctly? We can't we can't put a value in and check this.

But we can can we do? No, we will know what power is, right? We don't know what power is. But you know what? It's in the reference, right?

What about what about like this? Uh when it comes with this is actually a very small number one or two or zero or one. All the witnesses are just say zero or two. Actually we know some values. It doesn't what does that mean?

It it commits to the polomial but it like if it because it will make some of the bases. Yeah. So WA actually already shared that his value is kind of three to five. Yes. And then WA actually another witness and actually share me shared uh with me the uh G to the F of towel again to me but the value seems same then actually wanka is using the same value yes that's so this is the reason why we are using Peterson commitment when we hiding a value To hide the value completely, we should always put some salt just like we have done in the signature line.

Yes, if you put some salt actually we can prevent people uh getting some exploit some information there. So Peter commment is a kind of a very uh essential and foundational actually it's it's doing a really foundational role to hide information to hide information you need to add a non putting some salt there is just the same as but with salt is a commitment scheme. Peterson is a hash. Um Peterson is also commment is uh something like time to use slides. Yay.

You have a value. But actually if you share your values with this maybe it has some vulnerability because if it's a already a known value then we can see that oh you're using the same value. So to prevent that we actually adding another stuff here a new generator and this new generator actually has a unknown relation between this generator which means the h will be a something kind of a a this value but no one knows this value what what this value is and using this new generator you are adding a salt here and then you're sharing that instead of a actually it can be also used as a commitment but if you use that multiple times then actually it might be a problem. So using that using this uh instead of using this only this one if you add a the first bolt and then if you also actually share that multiple time for different. So this is actually how the comm gives a complete um hiding when you share some value but you should be able to uh open this value later even though the secret value is but because we added salt it's going to be different every Sorry question.

My understanding is that what we trying to do here is to hide the fact that the same thing. Yeah. But uh even without the salt, the secret is never going to be revealed. So that's not what we are concerned with. But the secret if the secret is a small value one or two that it can be revealed.

Can be it can be revealed. I mean by brute force attack because we can just try a small scaling of some generators easily. We know G, 2G, 3G, 4G, 5G in the generator. The power of the secret to generate the secret is where comes from. Um, actually X1.

Yeah. For the Yeah. Because you can see that uh if you have this actually unknown R uh it will be uh it can be uh written like V + R S. actually more plus RS. It's a S is a known value.

It's a is a chosen S is chosen by the proverb and R is a just a mysterious value. So no one knows actually what the RX here is. Um so actually we are using a pretty similar technique that we are using the Peter commitment in two. So uh instead of actually using the uh values directly uh we're going to say that small p1 uh is actually alpha plus uh the evaluation of the left polomial. All right.

And p2 is a beta plus uh and let's say no one knows alpha and beta here. No one knows alpha and beta. And then uh let's say that p3 alpha * r beta * l + o + a * q and if you actually try to multiply p1 and p2 and subtract that with p3 it it will return all uh so yeah so we let the prover share the G to the P1 P2 P3 rather than that it's a uh rather than actually it's a L of R of R or O as we are hiding a value with the mysterious alpha and beta. In this case, making the making the alpha and beta value being mysterious is pretty important. And actually we can just do a pairing check.

Yeah. Say p1 * p2us p3 should be equal to alpha beta. In the prom we can we can just say check it using parent function. L actually L sub W actually means a witness related polomial. So it should not be You need to make the LR from the circuit is public but linear combination of the witness and the circuit polomial will return you the L subw R sub W and O subW polomials actually because it's a including the linear combination information so because of that they should be private So the result should be yeah so a sub w r sub w o sub w the polomial should be private and we do that uh and we we can examine the relation just like this just like this actually we already achieved what we want to do the relation checking the rel examine the relation actually if we do not use the Peterson commitments style hiding scheme there is exist some potential to leak some information from there.

So because of that we are adding a mysterious value earthqu mysterious value beta just like we are doing in the previous moment. So instead of examine examine that with the L sub W of R we define a U P1 by adding mysterious alpha and define UP2 and define UP3. Then if you multiply Q2 minus and subtract with B3 it will be alpha time beta and we should be able to test that using pars. [Music] So basically just uh yeah plus this one we are just adding some offline two left polomial and two right polic represent the circuit. Yeah.

LR1, P2, P3. This is just basically How do you think is it easily reversible? So what how is it possible? chosen by our chosen by the chosen by the trust no one knows but people knows the alpha alpha and beta is trusted Then how can P1 G this is G. So my own question my question was if you don't know how you comput but you don't need to comput Oh So, how does the verifier know that the prover correctly compute all these?

How does the verifier know that the prover correctly computed the L of let's say P1, P2, P2? Um, car. So, okay. So, during so everyone's just like three. There exist a some terms which is a multiplication.

Yep. Ah, because you get you will you know G to the R to G to the alpha and you can do a pairing. uh not sure actually um to compute that correctly we cannot compute that using pairing okay we should give the group element because of that uh when the prover computes P3 during the trust setup we should provide values with alpha in power g to the alpha g to the alpha square alpha alpha Q. Ah, I see. The basing of the R1 CS and QAP is pretty simple and this is a basic formation of the GR 16 with a non-interactive with a non with an interactive setup.

But actually if we do a nonractive setup, it becomes a little bit uh complex, a little bit more Actually this is actually what the uh proc transformation. So this is the cell. So when you think about that actually you should actually See this point L sub W of T to due to the L of towel actually can be interpreted to a G to the inner part of a L pol which was a interpolate interpolated values of to times like this and R to O to which means that they are the circuit information. So actually this is where the uh trust is setup for a circuit comes out. This is the reason why we need to do the transit setup for each circuit because we need the those value L of to R of O of trust setup you additionally compute all this you additionally compute all these values.

Okay. We should actually we should provide those values to provers and prover actually just does a linear combination with those given trust set of values uh by for given circuit you know it's a circuit circuit polomial and you have your own witness you do a linear combination I mean inner product with those values and compute It going to give the give us the first pi 1 pi 2 uh this is a addition of the to the alpha the uh value evaluated the to your left foot right input and output polomial so I'm trying to explain like why uh in general because actually in this case uh you can see that uh actually many other explanation doesn't explain this as a inner product between two vectors right we can do the same thing using the vectors inner product using the inner product argument I mean we can make this one. We are doing this using a uh electron scale multiplications but we can do that using inner pro argument together. Also we can make commitment using this one this one using inner prog. in argument means that if you're having two vectors and then the result actually equals to the satisfies in between the two vectors.

Yeah. And then you can share your vectors in a form of a group form too. So this is something where we can do the we can achieve the uh same result in the same call. transformation. Okay.

So PS transformation is letting when come no choose a random number anymore. Yeah. So what is happening to do that? What is happening to do that? It's just assuming that some trust setup is generating and this is sort of like then writing it out then what pairing is required or what element is required to create during that.

So when we say phase one and phase two stresses phase one is essentially computing all the power right? Yeah because tiles can be used multiple times. So and then phase two is and then phase two you pick out all the ones that you need to combine them into like lal actually I I should say it's not regarding to the tow I think um space one uh it's creating the alpha and beta alpha and beta and for the circuit we are creating the uh yeah we're creating the towel for the second phase. So you might not be correct. So the alpha they are they're separated.

Okay. But the during trusted setup at least the first phase of trust set up where you is it the first way or second phase that collects your all randomness I forgot but the alpha and beta here after the trusted setup you generate g to the power of alpha right to the alpha in the group right not the alpha and beta to be used right alpha and beta here is it public public because if it's public then everyone can calculate alpha beta is not You need because you need G2 towel as well. So towel must be in the first phase two. So it's all the combinations, right? Cuz you can finish phase one and take it away and now you lost Alpha and Beta and there's no way you can do phase two.

Yes. I I so that must mean that it's already like g all the powers of like g of cal all the powers of g alert and all the powers of uh it's okay it's okay because using the gtd alpha we are just exponentiate that with toao because it's the same we're going to be gd alpha to the secret it's the same it's the same yes Y have size. True, true, true. Yeah. Uh let let's Yeah, let's think about the on the difference between face and face two during our breakout group session.

Yeah, having a breakout group is pretty good. Yeah, I mean I I hope to give you more some concrete uh understanding for about the US information in the trust sets. So it's something like a uh Ellis Bob Carl was participate in actually came from was choosing the random number R here. But we're going to replace this random number R with a very mysterious value to and how we make this towel is actually okay. Let's pick your number A and then would you please share your uh secrets in the form of group then?

Okay, thank you. At least Bob comes in and using value. Okay, I'm going to uh multiply them times like this like this. Okay. Then you say it becomes like a AB square like this and we do this call does the same thing and actually all B call doesn't actually they share small A is more exposive with each other then becomes small A and we have a actually G and G to the power and to the top square this is How we can transform it?

How to pick the random number? Right. Get some transformation here. Actually, here's some more details, but I think it's good time to go to the breakout group session. What do you think?

in the breakout group session actually we can just revisit about the how to define the rules for the RNCs and yeah we can just try to define the why that the form of QAP and then we're going to add some salt so we're going to make a very some basic version of a code 16 but actually this uh slides include is including more information about how to change the Vary transformation plus actually uh you can also expose some of your witnesses there. You can also expose some of your witnesses there. So actually it is introducing how to expose some of your witness into public input and actually keeping some inputs as in private some witnesses in private. So maybe uh let's visit this again and then after the breakout partition uh let's visit the uh another polomial IO piece and then we might be able to visit plum using this how to define the relation in this case we only need to find the QAP relation using polomials L polomial time R polomials will result the output polomials for a given range actually we can do many things using this the relationship between point and okay let's go to the breakout position okay This is actually what we have done and we can visit the Z. Maybe I'm a fan of that side.

Maybe try a little bit. Yeah. If you have computer then let's try to go to the zko.ndev then uh if you don't have maybe uh it's accessible as well. Okay.

So we going to write a source code using the R1 CS circuit that we had as an example in our question. So here uh maybe [Music] It's okay. It's okay. So let's try to write a program using this circuit. So in uh circle you can think signal means the witness.

In this case, we're going to say the signal input W1 2 3 4 5 6 7 8 9. Then uh let's try to define the uh first okay before we go to that uh W1 is actually one it's a constant. Okay. So if you just do some scalar to W1 it can be any number in this prime field, right? So it can be kind of a 37 or 38.

So it can it can it will work as kind of a base uh number system there. So we usually don't uh express the constant in in person as a as a signal in circle. Okay. Yeah. So we don't need to declare the consent and uh okay W2 is here W3 4 5 6 and you can see that W7 8 9 are kind of a some outputs of the multip so we're going to say that okay there are not inputs they are kind of a some intermediate values that we can compute from real inputs.

So actually we are putting exactly as five parameters exactly five parameters to this program and W7 and W9 and W8 and W9 are something kind of a computed value during the program but in our case we are actually declaring that W9 as an output in this case output is a And these W7 and W8 they can be inter [Music] computed from uh when you're just running the program like this and then we're going to uh define the each of multiplication gate. So the multiplication gate one. Yeah, actually you can uh when you write this diagram uh the constraint is actually expressed exactly same way in circle. So W9 I mean where is the first multiplication W8 is the output right I'll put equal to 3* W6 yeah this is a linear combination Yeah. And then we're going to add a scaler here.

Perfect. We made a linear combination for the left hand side left and right. And let's do the same thing for the two. Volume three, volume two. Everything up is W9.

[Music] Oh yeah, right. We string 22 + 5. Yeah. Uh that's all and we're going to open the public uh for example here can W7 needs to be in front of because depends on the value of W7. Um if you want 23.

0. And what about actually uh it does not give us some uh sense for the linear combination that much. Right. So, we're going to write another circuit that okay, we're going to express this thing in a little bit a little bit differently. We would love to express the uh linear combinations in a better way.

I'm going to uh declare a some new intermediate uh intermediate signal. So uh left input one and Why is it left in like this? It's actually Can you see the the design here? I mean how it appears. I mean actually it means I mean uh this symbol actually means wire so it does not introduce any constraints because wire can go into addition easily.

Yeah, you know here that we are just a doing a scalar multiplication over witnesses. We are not doing any kind of a multiplication between. So this is why any point in time we can only do single Then you need to introduce a new conraint. So here is we have a and actually you can do the same thing for the another case too and maybe let's skip that. Don't need to do that right understand what what does this uh input wire does here and also we can actually make it a much simpler what about this okay uh let's separate each multiplication like this multiplication gate So definitely have the first input and second input and it's output and then um I mean I'm sorry let's say the uh the uh for the first multiplication gauge actually we are using W6 W3 and W4.

We're going to have a three inputs. In this case, this is the W uh six. It will be a W3 and it will be a W4. Then we can make constraint here by uh 3 * W1 uh times 4 * 3 * 2 + 2 And then we gently replace these hands. We can define this as a component component.

Component one is like this like this. And for input value we are wiring and second input we are wiring. W4 and uh yeah, that's all. Yeah. So that That should actually W= W8 and actually W8 is not uh does not have an assigned value.

So we are assigning and constraining like this. For example, actually if W8 already have an has an assigned value like this for example then we can uh make conraints like so you can name like um you say double arrow is a combination of the single arrow plus makes it comfortable. [Music] So yeah, so our writing on RNC circuit starts from how the RCS system works. So we need to understand what's the wiring, what is the scalar of the signal and what's multiplication and why it is making the constraints without understanding that maybe we may sometimes miss some constraints inside of the system. But if you understand how it works actually uh we may able you may be able to write a certain in a safer way.

Okay. Um actually there is some real world examples. This is about where we are using the circuit uh in the real world. We can actually uh write a program uh that proves the mer in this case. Uh let's try to see how it So basically you can think like we're actually parent node actually get a two input from left and from from right.

So we can definitely define a component there right and put some value into left and some value into right and then we are making constraints repeatedly and then the publicly open value is the mult. So if you actually provide your multiple proof with a leaf and its sibling values then we can actually uh repeatedly compute its parent node and checking the constraints constraints constraints for by each uh layers. Then we will be able to finally approve that okay your leaf is inside of the MLE tree just exposing your buckle root without rebuilding the detail leaf and the sibling data. This is actually the real example and we are using that in many applications for the to add anonymity. Um for the next step we are going to visit uh other polomial uh IOPS and uh PL protocol IP IP okay I think IP is a little bit complex to uh visit Um okay in this uh part we're going to actually cover the different types of a polomial IFPS.

What is the first polomial if uh we have learned KG with putting some value or putting some evaluation of the polomial there was our first uh polomial IOP and actually we also uh followed that batch opening of KJ polin. Then after that we visited the Q8 encoding vector values into left polomial, right polomial and upper polomial and then checking that they are satisfying uh the equivalence relation for a given range. It's pretty important for the given range is really important because for the other uh values actually it will not get evaluated to zero. L * R - O will not get evaluated to zero uh in the actually outside of the range. Uh yeah let's visit the concepts again.

So is that uh the first is about simply ping the two polomials are identical to each other. We just we just did it pretty many times P1 and P2 evaluating them at a random number RX and then checking that uh the value the evaluations are same or not. If theations are same then we can consider the two different polomials are actually the identical. This is a calling the polomial identity and we use the we use the public part and the softness depends on the super volume here. Yeah, maybe just see uh let me introduce the detailed notations here.

Here uh we are defining a polomial f of x and v of x and we are checking that those two polomials are identical and then this is actually is a notation for public. So it's something we are taking some random number R in this field. So we pick a random number R from the field and then checking that f of bar = to bar. uh and this definition is that these two polomials are a element of the set of the all potential polomials which is defined on this field and it's uh which has a degree less than less than or equal to d uh the example is that let's say that the the d is one And let's say the uh prime that we are using is three. So p is three and d is one.

And then it will have a form like this. Shall we try to make a set? 0 uh 0 1 0 0 1 0 2 1 0 1 1 2 2 0 2 1 22 2. Z look like zero and two and x and x + one x + 2 uh 2x 2x + 1 2x + 2. Actually this is the set of prime field of three and uh less than degree one.

So in this case you're saying that f and g is a an element of that set. So it means basically means that it's a okay it's a polomial mean less than d or or equal to d and actually it's defined on this prime field. Uh and this means that probability that uh we are actually the equivalence of these two polomial by evaluating them at a random number R that is called a polar and accidentally actually there exist some potential possibilities that it the same value with this with this probability it's not one uh yeah say yeah the pro the The probability that they're not high. Yeah. The sound is error probability is this one.

Yeah. And the total sound is should be one over the size of field. So it sound for uh almost cases. Okay. So we can actually define the polomial identities in a pretty different ways.

So you can just design your left hand side polomial and right hand side polomial and we can just check it. If you just evaluate that a random number then we can just check that oh this left hand side polomial is actually equal to the right hand side polomial. This is actually what we doing. And in this case the sparse polomial also works. And uh the sum is uh actually depends on the total degree of the left hand side polomial or the right hand side.

And actually we also introduced uh the binding already when we are doing the QAP because we tested them only on the X1 X3 not on the all all the field. Um so actually if the it means that if f and g these two polomials are identical actually they will uh evaluated they will be evaluated to the same value uh for all x in the prime field but there might be some that okay SMG are actually not identical but they will be validated to a same value for a given range. This is the range that we want to set. So we are saying that we are binding the range to x1 x2 x3. So f and g can be different with each other but at least at x1 x2 and x3 should you guess that right now [Music] for at least for x163 uh fng at least they are giving same even even though they are different and the uh method to find the range is using the vanishing polomial the zero polomial.

So if we use zero polomial then uh actually we can uh yeah I mean we can define a sub auxiliary polomial like f for example f minus g as a new polomial and then uh let them banishes to zero for the given range. Actually, we did it pretty many times already. Yeah. So, this is how how we bind the range. Um and then the first uh method that we have used is actually we already uh we already found the range when we are doing the opening for the cage commment.

which means we try to open your polomial at x1. So we actually we already bound the range with x1 and after that we try to open the polomial at multiple multiple values x1 x3. So for that we have to find the range by creating a zero polomial x - x1 * x -2 * x -3 because it will vanishes to zero at x1 x3. So we already actually found the weight 63. Um so this is actually how we can do the opening.

We already covered the multiple opening too. So we we I've seen the basic word and how for example uh the next question is that uh we did multiple opening but can we evaluate the uh polomial identity checks uh multiple polomial identity Do you think that we can do that? A= like uh no actually we are having a uh some multiple constraints like F1. Do you see that? Yeah.

Okay. I'm thank you for sharing your sum of your data. Thank you so much. And actually I would love to check that. Oh then oh before you share your sum would you please uh make some commitments to your polomial.

Okay. Yeah. Let's say that we actually when interplay polomial and yeah interpolated polomial, right? It plays a polomial. Okay.

Uh and yeah, please give me your comment. Okay. Here's my R. My R is okay. My like seven seven.

Yeah. So you give me some your commitment. Okay. I say just G to the F of bar F7. Yeah.

Yeah. Actually yeah I know Wan know F7 and I know G2D F7. I know that. Yeah. Okay.

Oh man, thank you for sharing your commitment. Oh, you actually shared your sum. Great. Thank you so much. And then let's try actually you are saying true or false.

False. I need to give you Q7. I need to give you Q7. Q7. No, actually you don't need to give the Q7.

Yeah. Let's see how we can do that. Yeah. This is the kind of cing the grand sum. Yeah, cing the grand sum.

And actually I'm going to request you the give me a proof of the grand sum here. So actually we can call that as a uh univariate sum. We are letting compute the grand sum and then um just checking the sum is correct or not. This is actually how we do the grand sum uh checking checking the grand sum of your polomial. Um yeah.

So you're um That's Y I Y I is a value 435 there. Oh yeah. So um basically uh the evaluation of f at omega to the zero and one to the two will be valid to four and three and five. Um and actually this is just a log interpolations and doing a linear combination with the L base polomial with the with this 435 values. Uh just one let's go here.

Actually if we do a uh grand sum of the evaluations of your polomial uh at the multiplicated subgroup I mean the using the root of unities then actually uh it will be expressed like in a form with this vanishing polomial plus Say here like this the banishing polomial times q of x plus r of x and actually r of x will return uh the the lang stops there and then let's try to Uh write them all down there. Actually, do you see the some pattern there? I need to introduce a very uh important characteristics of a root of unity that if you have a root of unity then if you have the n root of unity then 1 + omega + omega² + omega to the nus one actually it becomes which value you want. Just take a look at this. And actually what might be the optimal number for us?

One. One. One. One. I think there's another better number.

10. N T. [Music] Yeah. Actually becomes zero. Yeah.

Just think about like this. Oh, because they cancel out. everything. Yeah. Okay.

Uh what is the best way to explain this? Because omega to the n is one. Omega to the n -1 = z. and omega - one omega to the n - one plus actually it'll give you omega to the nus omega to the n minus one and then if we add omega to the n minus 2 it will give you omega to the n minus oneus omega nus 2 right so they cancel cancel cancel plus one will give you a minus one equals z right. So this is not zero definitely.

So this is zero. Yeah. using this fact. If we just take a look at this actually if we just uh add everything here then okay um we can move this out can switch exponent together anyway it's kind of a uh the sum of the all powers of the of a some element of the multiplication curve. Which means that it cancels to zero every terms actually exclude uh exclude is on the a.

Yeah. Sorry, right. So we have a the B will be kind of a B * A and the all the other values will actually be cancelled to zero. So the value is a kind of P * R of zero. Um okay then how to evaluate actually when comes argument that the sum is 12.

Okay to evaluate that actually we do the same thing using the public protocol when it comes polomial and let's say actually the polomial might be might be a little bit different but actually it's evaluations at the root of unities the third root of unities actually is four and three and five and sum is like 12 then polomial should be able to express in a way f of x is a z of z of x for the multiplicative group the third probability and some quotion polomial plus remainder and this remainder actually should give us the uh r the opening should be the uh s over d opening of this remaining the polomial should be actually uh s is that okay wan is saying true. So for the for the polomial on f side so the polinomial that you are computing uh fr is still uh very much done via like the commitment either kg or whatnot but you additionally to actually sum check this s= dr of zero. Yeah, we have to say adding some check. Is using root of unity compulsory for some check? Using root of you must use some.

Yes. Okay. For unity as some check. Okay. So we can actually evaluate I mean sum check uncheck is that I am letting you evaluate polomial uh using root of unities and summing up the all the evaluation values and then actually this is the value that you gave me.

Yes. And then I'm checking that you're saying not by opening your remainder polomial there at zero. I see. You know zero because after going through the entire thing it all cancel out except for zero. You're going to you're going to give me actually you already gave me the f award.

Yeah. Actually this is something that I know you should give me the board. You should give me the or and also you should give me your opening proof too. R is a S over D. So what's D again?

Degree degree degree of the F pol. How do you get the Z H of R in this case or the verifier? Does the verifier compute Z H of R? I actually publicly shared road to immunity multiplic. Oh yeah.

Because yeah. This is a vanishing pol. they're sharing the values together. Okay. Uh and actually we check that uh checking the grand sum and also we can check oh wan would you please try to multiply all of your elements and give me the number grand product.

Okay. Uh 60 m 60. So this is called the branding the brand product but actually uh checking the brand product itself is a little bit difficult. So we are using a trick. So we can check that your grand product equals one easily.

But it means that we can also check the grand product of a fractional polomial equals to one. This also uses uh the roots of unity as well. Yeah, it also uses the roots of uh and let's see how we can do that. So we are doing the univer uh the product trap on the one indicative subgroup. So we have a root of inity uh where the omega to the k equals to one and then we want to check that all the product of the evaluations and the multiplication subgroup becomes to one.

Let me refresh. It consumes a lot of memory. Okay. So, uh the method to uh make it sure that the product equals to one is that uh we are defining a some new polomial t there and then we are saying that uh the evaluation of t at one equals to f_sub_1 and the evaluation of t at the omega to the 1 equals to f_sub_1 * f omega. So we define the auxiliary polomial t just like that.

And then finally if we evaluate the polomial t at omega to the k minus one and actually the value will be the grand product of the evaluations of polomial f there. Okay. And then actually if that holds true, uh we're going to see that the evaluation of t at the omega to the i over evaluation of t at the omega ius one will equal to will be equal to the f of omega to the i. Does it make sense? If we define the polomial t correctly, it will hold true for uh all over the value at the multiplicate subgroup because it's just a actually just definition.

We just try to define a polinomial of t in that way. And if we define polomial t correctly then it will satisfy this condition for all element in the multiplication sub and then actually we can just uh move this uh divisor to the right hand side and then we can say like okay uh t of omega x = to t of x * f of omega x for all of the uh elements in the multiplicated subgroup. We should make sure that uh it's only for the multiplicated subgroup. It's not saying that t of omega x is a t of x * f of omega x. It is just saying that the evaluation of t of omega x equals to t of x * f of w omega x at the for all of the elements of the multiplicative subgroup.

So it's actually we are binding the range So actually if if this holds true that actually uh it says that oh the t of omega to the k minus one is is actually the grand product of the f uh for the root of unities. So we can actually can compute the grand product using that and our the the relation that we are trying to check here is that the grand product equals to one. So which means uh if t So omega t - one = 1 that actually it means that the brand form of the f equals to 1 and actually it will uh satisfy this polomial relation. T and f actually they will satisfy that relation. Does it make sense?

I don't quite get how uh Okay, so we see that TWI / TWIUS 1 is equals to F WI, right? And that's because um if we because basically if you divide them, you get T uh yeah, you get TWI, right? So if you if you divide them you get w you get the evation f and w of a certain index right so you can try to divide a two row yeah then you get one of right you want to get this one if you divide this with this one so how does that lead to um so to say the fraud check why why is it that um can we go to the next slide So here um I see that for some like the left side I understand but the right side for some t that is that is in an element of the finite field of size p less than k um for for the function x such that t w k - 1 is equals to how do we get the pw kus one is equals to 1. So how do we how do we get this one and how do we get this one and this one. Um um okay I mean actually uh this is saying that if there exist a polomial t which is defined on this prior field with degree less than k and actually if this polinomial t uh satisfies the condition that T the evaluation of T at omega k minus one equals 1 actually it mean and also actually actually it satisfy this condition too it means that the bread of fals so we need to actually there there should exist this point on the t inside yeah such that the valuation of this t at the ome= to one and also which satisfies this condition two for all of the uh element of so we need to construct a t such that right I see how how how we construct the key interpolating okay interpolating like that so to prove that the P is constructed correctly.

P is constructed correctly. Uh we don't need to actually uh we are checking that by uh polomial identity check. So wanka actually should compute wanka's own auxilary polomial t which satisfy these conditions like this and then actually that polomial will definitely satisfy uh this condition the like this condition definitely okay definitely they they may uh satisfy the condition. Then actually we can now use the public coin protocol like this. We are actually binding the range again using the zero polomial which means that it will evaluate to zero for the given range.

So if wanka gives me the polomial I mean give mean the proof uh the quotient polomial to me and also give me the proof that your polomial t evaluates to one at omega to the k minus one then actually oh your polomial I mean your polomial f the grand product of your polomial f is actually point. So, okay. So, t is interpolated from fx fx as well, right? Yeah. The pro the product uh of f fales of that.

Yeah. Of y. So you should actually compute a some new intermediate polomial t from that and then using that you get the calculation of t twx minus tx times this and then in that specific interpolation you get the property of t w k minus one uh is going to be equals to what? Yeah. Sorry remind me what k is again.

K. Yeah. K is the um the number of the multiplicative group. The number of the or the size. Yeah.

The size of the multiplication. Um because actually we can uh compute not only the grand product of a polomial but also the fractional polomial product actually we can use in a a little bit a some creative way let's see which means that if we can check the grand product of a fractional polomial that means the grand product of a polomial A and grand product of polomial B we can Check if they equal to each other. It's just not a pol. Uh fractional polomial. So fractional Oh yeah.

And checking the evaluation evaluating that relation is actually not that different with what we have done for the checking the grand product of a f of x pretty similar. And actually what do you think that the reason why we are doing this checking the grand product? We can check a lot of things at once. Yeah, we can. Yeah, we can check many things at once.

Uh yeah. Uh let's say um we have a three numbers 435 435 And we have another three numbers. Uh not yet not yet. And actually interestingly the grand product of these numbers and these numbers are same. Then what do you expect?

What do you expect? the same pretty similar. Maybe we may have a two 310 310 but the number has same but actually we are expecting a pretty similar thing right like five three etc. How do you how do you case? So actually this is a permutation of this but actually 4 3 10 is not a permutation of this.

I mean two three 10 is not actually they are showing us the same brand product. Then maybe if we tweak this brand checking the brand product a little bit then we might be able to check these two vectors uh permutations of each other. Yeah. Um what about like just adding a random number for each element and then do a product then maybe we can check the permutation decrease the chances I suppose chances because there's still possibility even after adding a random value that will result in the same right But it's a lot harder. That's why we This works.

It's a random number. It's hard. If it's a fixed number, I mean actually 4 * 5 is 20. 2 * 10 is 20. But 4 * 3 and 5 + 3 is 2 + 3 10 + 3 is actually 65.

Yep. So it will result to a different number if we add some random salt and then do a grand product. Actually if they actually if they if the brand product equals to each other uh even if we add some random value to the elements actually the possibility that they are the permutations are pretty high. This reduces the chances of uh the approver having to trick because of the random number but but it doesn't reduce the chances of it's actually colliding right because there still a chance of getting the same one just that in this case because we added a random number it makes it a lot harder to be the same values right Yeah. Okay.

Then uh let's see the reason why we are doing this grand permutation check. Actually we can yeah this is how we can check the grand permutation. So we have two let's say we have two vectors and then uh vector a is a permutation of vector b. If you pick a pop by the public protocol if you pick some random number and if you do add them and do a prime product and then if they uh results in the same value then actually they might be the permutation of each other. Then uh we can also yeah actually interpolate values into polomial and we can just add some random number there that so f is actually uh f of x plus random mark for example No one has ever wait that works actually that works but you know I have but this is something actually that we want to do because what we are trying to do is that Uh let's introduce P first.

Okay. Actually we try to write a R1 CS circuit uh today but actually we can express that in a much simpler form. L R O maybe there might be some polomial and then okay let's say we have some witnesses like this W1 W2 W3 W4 W5 W6 W7 W8 W9 like this then you're just uh saying that Okay, they should satisfy this condition. Uh but actually how can we introduce the input wiring or something else? It's just introducing the constraints.

How can we put the number to some something else? Forget boys like okay W1 W2 multiply is W7 and then actually they are separate kind of some constraint W8 W2 W5 and W9 W3 W4 So we need wiring. We need wiring which means that okay W2 equals to W5 like this we are actually putting this output as an input for this gate. Okay W8 actually will go to this left left input. So W8 equals to W1.

So in this table we can see like oh W8 equals to W1 and W2 W9 equals to W2. Actually this is the wiring in the plunk and uh if they are actually equal to each other maybe we may find some permutation relation but with an indexed system because we are actually uh let's say we have a omegas from w1 to w9 9 and W1, W2, W3, W4, W5, W6, W7, W8, W9 as a vector. This is a first vector A. And then let's try to make another vector. But in this case, we're going to switch W2 and W9.

W1, W9, W3, W4, W8, W2. We will also change once more with W1 and W8 like this. So we are doing a permutation. So we know we actually okay in this case uh wa please give your interplay your witnesses and give me the first vector to me first polomial to me okay and then okay great then I'm going to give you a another some polomial actually uh which can switch these two uh element with each that will be kind of a sigma polomial. So sigma polomial will be evaluated to omega to the zero will evaluated to omega to the zero but no will be validated to omega to be seven.

Omega sigma of omega to the 1 will be evaluated to omega to the uh omega to the 8 and sigma of omega to the 2 will be valued omega to the two and the others will be like same but omega to the 8 will be like omega to the one sigma if then okay m when I gave you this sigma polomial So you gave me your uh with this polin app then let's try to make some composite function using sigma like that. Let's say this is another fp prime. So if f prime is a permutation of f you will result in same we're going to have a same brand product. Yes. This is conraint.

Does that mean Like let's say you have more wiring right also then yeah so the sigma polom is just a wiring right I'm saying that sigma is not unique like you can sigma is unique for circuit yeah sigma is just a circuit information in this How do I? So yeah, Yeah. So if the on your app are actually they are having the index permutation uh relation and the index permutation relations defined in this sigma command. Then we can just random linear combinations. Basically we are adding random art uh to make it uh the permutation is ex exactly same but actually we would love to make sure the uh index too.

So actually the sigma function sigma polomial uh represent the indexing. So we pick another new random s and then for the left hand side we're going to add s * x and right hand side we're going to add s * sigma of x because we're going to we're going to evaluate them at the ome using the root omega and actually Sigma of X returns you another omega I another omega. So the R and S is the R is random but the S is also random G is F prime in this yeah then F and G are a permutation actually it is called the sigma permutation and the index I mean the copy constraint information is actually defined inside of the sigma pol. What is the usage? Uh actually so actually we can write the arithmetic circuit into a little bit different for so we are actually uh defining left polomial right polomial and output polomial or maybe we can add another one like c of x.

So the result that we want is something like L value times R plus C actually this is a the all about the arithmetization right equals the output. So this is just how to write circuit. Yeah in a different way. So this is called a PL style argumentization. In this case we have a it looks like table.

It looks like table and then actually we have some witness values like this. L of X should interpolate those values. R of X should interpolate those values. Ox should interpolate those values. And you're going to come into a big inter a witness polomial using those values.

And then we're going to check the permutation to see the wiring is actually connected to other gates correctly. Yeah. Correctly. Yep. So then you cannot have multiple wires from the same signal.

So in other words, you cannot represent an outs. Mhm. Well, you cannot represent any CS. We can do that. Why?

Actually, we can connect these two thing. Sigma is not still a permutation W4= W8 = to W1 but don't you have to permit two times to check that then permute two times um okay I know what you're saying right like you need to switch one and eight and uh I think you're correct. I think you're correct. Y maybe but actually we can resolve that in a different way because we are just using a same value. So maybe we can try to uh define a little bit different way or either expand the table the the wiring table.

There's also a wiring table in this. It shows what is being connected to what dates. Right. But I'm saying that for that table it needs to be expanded otherwise like it's not necessarily one to one. Yes.

Yes. If you if you add one so it's not a binary gate you have to define a custom gate to handle it because I think by default it's binary. Of course, if depending on the system you're using based on block to add a custom if you add a custom G in you basically add the CX in, right? So, and like some of them and if you add things like that in, you now need to make things bigger. So, we covered funk.

Yes. Yeah. Actually, covered funk. Uh yeah actually yeah I yeah there's a more detailed explanations of the PL startization. The inform we have gate node and we can actually define what the gate looks like and then uh this equation is about how we define the relationship of the input and and fan in and between the bend in and then out.

Um and and yeah so actually we are adding some wire information there too in this case. Yeah. So we have a three multiplic uh two multiplication gates like the first gate is plus and the second gate is multiplication third gate is multiplication. Yeah and then we are wiring uh the three with seven with six with eight like that. Uh so let's say the t uh of x is the the uh interpolation of your witnesses and then uh yeah let's say we also have this kind of a input values too input one input two input three input four uh actually I am noting this input three and input four maybe or input one or input two is a public value here in this actually input one two are the public value I think.

No. Yeah. Uh yeah, all these things are public values here. so these are public and these are private in this case. uh because in in in growth 16 uh multiplication is constraints right it represent constraint so in pl um does the addition gate itself is a constraint okay so this this constraints the wiring this constraints on the wiring that's why is that the case because it constraints the wiring that's why G also have constraints now but actually uh so we need a selector to use which con which uh constraint is it a addition constraint or a multiplication.

Yeah. So we need a selected polomial. So select it's a addition gate or a multiplication gate and the left side is about the wiring information. So this is actually there's are there is some steps for the first step. Um yep we we we check the inputs.

You need to give me the input polomial here large B and then actually we going to op do a batch optim using the zero polomial for those uh input element. So you're going to give me the uh witness polomial t and then it should satisfy the batch sharpening of the input values at the given x values and we are using the omega to the minus one minus 2 uh to the omega number of the inputs as a uh x values to evaluate them. This is the first uh IOP that we are doing. We are doing the bet. So it's a the first IOP and the second IOP is uh checking the permutation the wiring information because the sigma is a already a given thing.

So uh when come uses a polomial t we are just checking the permutation checks there if polomial t uh satisfies this pol per permutation check that actually it means that the element of the uh vector Actually they are permutations of something. So the wiring is correct. W2 equals to W5 for example. This T is not the same one as T in IOP1. Right?

Same same thing. It's the same one. And sigma is a given given value given. And then for the next step, we're going to do a gate check. Uh yeah, this is similar to how in our one CSV we it's in similar similar.

It looks a little bit similar to the R1 CS gate. I want a little bit. Yeah, a little bit. But it's focus on the gates. Yeah.

Uh okay. in in Pong actually uh you can see like uh L polomial, R polomial and O polomial actually we can uh actually divide the witnesses into a like three different groups. So we are using a scalar three there. Omega to the 3 I actually gives you the okay this is a left polomial and if you do a 3 I + 1 becomes a right polomial and if you do a omega 3 I + 2 and actually it says the output polomial. Rather than uh actually uh explicitly saying these left and right and output polomial we can just uh check the left right and output using the root of unity is the three * zero or one or two.

So the first one actually it says oh it's an addition gate and the second means oh it's a multiplication gate like that. And the result definitely should be the out. So the S here is the selected right. So because the s gives you one then actually it will it says oh this uh this this is the addition gate and actually if the s returns zero then it will cancel the addition terms but actually it gives us only the multiplication term so it becomes a mult multiplication gate. So we have a so here like in Pong there's quite a lot of polomials we have the selected polinomials the um permutation sigma the index polomials yeah sigma and then we have polomials index polinomials and also the does the circuit polinomials separate into the wiring and the gates or is it just what wiring is the selector And the I mean the circuit information uh consists of a selector and wiring.

I see. And selector polomial here is s and wiring information is included in the sigma polomial. Okay. So we only have these three. selector wiring and um wind volume.

All right. And then finally actually we are doing the output check. We already check the mode gates. We check the inputs. We check the wiring and we are checking the final outputs there.

Actually mostly the final output is uh in plunk is zero maybe. Yeah. by the start. Is the output check a special check or it's just or it's just proving it's um actually in my opinion we can just change the output but by the accept protocol uh we are just fix to zero. Just Yeah, it's just about how to write the circuit.

So, is there for interactive pairing or you're doing that in an uninteractive way using pairings. Yeah, because all of these polomial relationship checking the polomial IOPS can be done in a way in a non-interactive way by the transformation. Yeah. [Music] So in IOP one it's a it's a it's a pairing check that one I can see. Um in IOP2 which is the permutation do you still also need to do a pairing check for the for the product product check?

Actually, we can check all of these relations at once because we already cover the batch evaluations by the random linear combinations. I see. Oh, I see. So, we have four IOP checks and we are just doing the random linear combination of these four checks and doing ones. So, we are doing only one pairing check.

That's the reason why we are doing the fetch evaluation. I see checking multiple polomial identities together because we the pairing check is so uh expensive. So we need to minimize the number of a pairing checks and compared to gro 16 the existence of this permutation check in the allows you to give us a setup. Um yeah actually uh as you see in this PL actually the uh we are not having any kind of some pet styles thing which is related to this the circuit. So because they uh not related to the the trans is not depend on the circuit.

Okay. So, it's not really caused by the addition of But in batch valuation what we are essentially trying to do is to prove that the result of two poloms are equivalent. Right? So, here in PL if you do that what is the other side of the things that we are comparing it to so on one is it the proof um oh yeah because you are comparing the same thing of fx minus y is it uh you are actually continuously sharing me the growth elements okay okay so you are sharing your commitment for the your witness t of and actually we know that what the c of tal is And you you need to share me the queue of tow for the outputting for your inputs. Oh, got it.

So the batch evaluation here it's applied on um what we learned in case the uh wait batch evaluations. Yeah. The the evaluation of f(x) minus rx = to q zx xqx right is that it's just that um in our case we are batch evaluating based like we are using batch relation of both sides. Yes. So batch evaluation is something like this.

We have a a polomial plus b equals c y b + e = f and actually we can evaluate them at once by doing a random linear combination. So I know what it is what it is and then okay using this random number let's do that let's evaluate them at once then we can do only we can do the parents only once just just so that's why you can like for you can also choose to have like a wide table with less row and like how does that relate how many polomial you have, right? Because you can have like a Y table with more columns, right? Or less row or you can also justize it as a table that has many rows and less columns. I think in this case because each tables, there are two tables, right?

The wiring one and the gate one, the gate tables and the wiring table. So both of them undergo different calculations and result in different polomials. No not yeah it result in different polomials. One is a selector polomial and another wiring or the sigma polomial. So they they are calculated differently to make sure the constraints are met.

So we are doing batch eval evaluation on the combination of this and then um the batch evalation is then done on trying to verify it during during verification when you want to check both sides similar in KG at least but I'm I'm trying to figure out how I mean you can take a random linear combination But I'm trying to figure out what will be the qx, what will be the z x in this case. But it's also a polomial. So technically we can just separate them into parts by giving it rank. We finished. [Laughter] trying to make this.

I think that uh it's time to wrap up today's session and tomorrow let's revisit this via breakout session again. Yeah. So we're going to we're going to try to understand how the permutation check works from the how the understand how the grand check works and then we're going to try to uh understand the plum protocol and and then we're going to move on to the sump protocol tomorrow. Okay, great. Thank you so much everyone.