Additional session - KZG

Transcript

after. Okay. >> I sent a message two minutes ago. >> Okay. Okay. >> All right. Whoa. >> How are you? You look like you're hangovered. >> Yeah. >> Partying. Huh? >> No. I don't know. Yeah, >> like I was at the station just before Rhino Zim and then just after I have to do my uh ambassador duty.

>> Oh god, a lot of >> by running a session in French for days. >> Um >> I see. And after that >> you look like you you look so tired. I'm sorry. >> I'm tired. >> You should listen just a bit. Oh yeah. >> In fact um is is more about dealing with all the things not only just session like session is just like 10% of my time.

>> Hello. The rest is all about logistic and stuff. I mean um yeah, so all right. Um I think I will let you leave. [laughter] >> Yeah, >> I know we we don't have a lot of people here, but I believe they're gonna watch it because um this is not the, you know, usual date for them, but thank you for this session, Lisa. >> Seriously, we really appreciate it. [laughter] they ask for the recording um because in fact a couple of them can't can't attend um as it's Friday etc. Oh, yeah.

[clears throat] All right. >> Okay. Um, yeah, it's a pity. Uh, maybe we can wait for a couple of more minutes for everyone else to join. I want this >> remind them also. >> Yeah, we have this. So, the session will be remarkable, right? [laughter] Yeah. Let's let's try it with with remarkable because of the calculations and everything that we have. So, yep.

I'm not in Milan anymore, so I have this equipment with me now. >> Yes. You your background seems more gray right now. >> Yes. You were living in Serbia, right? >> Yeah, for most of the time now. Yeah. >> But I see you travel a lot, so it's really hard to keep up. Where are you? [laughter] >> Nobody knows. Um maybe just one minute too so then we

can start. >> Mhm. Um yeah. Um are you traveling for the connect me stuff? >> Yes. >> Or are you planning to like No, it's all the time. It's something right? >> Oh, it's um when I was um like 20, I wanted to be a digital nomad, but now I realize I need some, you know, home environment.

Uh for me, it's really hard for me. I tried a bit to travel through the events. Right now, I just say no because it's too I get too tired, I think. So I appreciate whenever I see people just travel all over the world. >> Don't be a devil. Then [laughter] >> I see where I live is like like different, right? Because you're traveling for for job like hey I have eat global next week for example. But it's not like, okay, I'm living right now in Milan and I want to go Mexico City next month or I want to go to Buenosiris in two weeks or things like that. You You have a place to crush.

>> Yes, I have two places to crush and it's fantastic. [laughter] >> Uh, it's really hard for me. By the way, I have Turkish passport and we literally don't have any privileges. So, I need to get visa for everywhere. So, >> no for me. >> I see. I see. What can we try is I'll try to share my remarkable input.

Let's see uh how to do that. screens documents. No advanced. Okay. Do you see this guys? >> Yeah. >> Oh, super cool. Let me try writing something. Yeah perfect.

Okay. Okay. Um so yeah, let's uh open the session if we think everyone who has um has planned to come is is here. So hi everyone, my name is Milita. I'm a deval engineer for ZK verify. I'm also doing PhD and um zero knowledge proofs. Today we're going to you know go through the KZG commitment scheme. Um the thing with uh the example we're going to go through is that you need to have a pen and paper. Once again,

um, we will not do the pairing on the elliptic curve that the original KZG has. But what we will do is uh we're going to use the power of algebra and um see how that um how the algebraic backbone is uh played with the KCG. So that's what we are going to show. Um so um yeah let's um let's start with um the trusted setup that we had last time. Let me just organize things here because it's I just arrived home so it's I don't

know where things are. [laughter] I'm maybe I'm in a fact no. In fact, one person um approached me some time ago and said like, "How is it to be a nomad?" And I'm just like, "What do you mean?" He's like, "Oh, every week you're somewhere." I'm just like, "Oh, yeah. Okay, I hit that mark." [laughter] So, yeah, let's um let's do case G. Uh Arrow has pen and paper. Yeah. Yeah. Yeah. Uh that's perfect. Let me check if I can see also the the chat here if anyone asks something.

Uh do not get burned please. Yes. [sighs] Okay. Super cool. Super cool. Um I don't I don't if I'm sharing screen I don't see comments. So if there is something just like raise your hand and I'll I'll see it in in the bar with uh the camera. Okay. So we have for um KC3 we're going to have a trusted setup. Trusted setup is uh done through something that we have shown in in these classes in this lectures of ours. It's called multi-arty computation. So you

remember when we were um trying to uh calculate the the average of our age of the group age we did MPC. So in fact that's how we are having a setup in in KCG as well. Um so we're going to start by calculating the the setup. Okay. So it's cool that you see this. Well, let me just Okay, it's going to be black.

That's it. Everyone sees it. Well, I'm not sure about the size. Okay. >> Yeah, it looks good. >> Perfect. So, what are we going to go through is setup commitment evaluation verification, the four steps. Okay. Um let's start with setup. Nice.

So for setup we need to form a certain group um that and end the generator. So it's going to look like this. Five, six. So this is our starting point where we can say that the G or the generator is one and the order of the group is seven.

What does it mean the order of the group? Uh okay, I can see the red dot now. Super cool. Uh so the order here means that uh you can have only as many uh participants in this uh in in this group um as how many um how big this order is. So if we have seven the maximum number of element the exact number of element will be seven. Right. Uh, okay. Let me just check. Let me think. Is everyone following?

>> Yeah, I think sport is a good idea. I love the writing like >> Yeah, I I was uh uh I was uh hoping I will use it uh in the previous ones, but uh I didn't expect that my trip in Milan would prolong. So um then we had to do like actual pen on paper with my side. [laughter and gasps] So here what we see is the G. The G is a multiplicative group and um and yes we're going to also define the field um which is the finite uh um we call it the finite field of prime order P. So

what does that mean? The finite field means that the field can uh can have as it needs to it needs to be of the order p to say so. So it can have like 1 2 3 4 5 up until to p minus one. Let's write that too. finite finite field of okay

the group chief so I'm using all this so that you know whoever is taking recording they can also see it on the Okay. Can you all read my writing? >> Okay. Okay. Uh

if we have um everything written down now we have to calculate the global parameters or where we see it as GP and someone also um is calling it the structured reference string or SRS. So you will see both uh versions. Okay. So what we're going to do, we're going to do it like this. Sample random towel. That's our secret, right?

From FP field. Okay. So how big is our field? Our field is see we have the G right. >> Um are you writing right now? >> Oh >> okay.

It's not connected right now. >> Oh, okay. Sorry. >> Okay. Yeah. Yeah. Yeah. Let me uh see where it stopped. Sample the towel from from the P. Okay. Uh All right. So, let's see whether if something else is missed. Okay. So uh we need >> the GP. All right. So these are the uh the the parameters the global parameters that we have

and we're calculated in this way. We're going to have H0 is G. H1 is to * G. H2 is to square * right [clears throat] and we can go to hd t to the power of d g if we are within the field of gd + one um this d that we have it's a height of a polomial

and in the end we need to delete toao. So the the the the MPC should delete towel after this step. So when we calculate hes the global parameters we should delete toao we should not use it later. uh the fact that we're going to use uh um toao for checking is just for the algebraic checking later in in the lecture. Okay. So let's um let's calculate GP for our example using this one right

and saying that um okay so first of all we need to sample towel right [gasps] let's say that our towel is five so we're going to use this one Okay. Yes. And we're going to use this top part. So GP is H0 is what? If we said that g here is one,

it will be one, right? H1 will be to * g. In our case, it will be 5. H2 will be toao to the power of two. time g and because we have modulus 7 it will end up as what 25 modulus 7 it will end up as four.

So our global parameters are 1 54 respectively. Okay. And uh yeah why do we have only three of them? Because the the height of our polomial that we have elected as this one. Let me just share it. Maybe I should have shared it before because otherwise why would we stop at three elements right?

Okay this is our polomial minus one. Only provers this polomial, no one else. And the prover should prove to the verifier they actually know the the polomial. And they will do it by making valuations of the polomial. um when uh a verifier sent a value um we'll show it uh later.

Okay. So now we have our Okay. Yes. Hatton. Um so if my polinomial would have been xq I should continue till 3 right like um not x² but if it would be like x3 x over 3 um we should calculate one more ash right like the order should have been three in this case. Yes, this is why because with uh with the polomial you will have let's say that in your case you would have

okay I'm going to delete this but let's let's write it. Let's say you would have like 3 to the power 3x ^ 3 plus maybe nothing combined with uh x2 or like 7 x + 14 let's say. So for you to be able to properly calculate this, you would need to have h for every of those even if we have zero here. >> Okay. This is why we stop at two in our example. Okay. >> Yes. Yes. So even if we had like uh I mean that polomial wouldn't be uh used but let's say that we only had like uh uh one um height uh we will one uh one

um member but it's um then it's then it's not a polomial right but um you know even in that cases like because you need to um you need to have um uh you need to have a a parameter for all the coefficients. that are there. Okay. Okay. Mhm. Delete this. Yes. Vanished like that. Nice. Perfect. Okay. Any questions regarding the setup?

>> Yeah. Can you explain again where do we get the G equals one? Uh that is something that the group that produces uh that produces age values they have um elected that >> got it. >> Mhm. Mhm. So they're um they're uh responsible for having u GP like um of course you would need you would need to know um the order later because you need to calculate the modulus but you shouldn't know toao um so these secrets there um the the where wherever you have towel and you need uh global parameters

that's what they calculate. So they need to know uh the the the height of the polomial to be able to do that. Okay, let me move. Yes. So nice. So much easier right? Okay let's do the commitments. I hope we'll have enough time. Yes, we will.

So, what is commitment? Um, that is our polomial evaluated at secret toao. But because we do not know secret tower, we're using h values the global parameters um that uh the the group sent that the multi-arty computation sent us. I don't like that we do not have nice brackets. Let's make it like this. Okay. So we said this is our polomial, right?

So let's uh write it from the lowest of the orders to the highest. So this is our effort x - 1 + 2x + x to the power of two and we want to do uh to make a commitment so that we can send it to the prover. Is everyone following? So far as I am writing down super cool let me check just the the the okay nothing in the comment section all right so let's calculate commitment f

that is per formula f0 * h0 + f1 * h1 plus f_sub_2 * h2. In our cases, uh we're looking here at [clears throat] the constants that are let's say like uh if it's like a f zero that we see that's uh the constant next to the x of power to the power of zero. So that's one and uh our constant is minus one. So it says minus1 times h0 that we had

here is uh okay it's still on the paper it's it's here. So it's going to times 1 plus um x to the power of 1 in our polomial has a coefficient of 2. So it's 2 * h1. H1 is here. It's five plus with the same logic we have one here times H2 which is 4.

So that ends up in uh -1 + 10 uh it's it's 13 modulus 7 is six. This is what the prover calculates. Okay. Here for us to check it, we can do evaluation at secret D I mean secret tower. Sorry.

So this is not what the prover would calculate but it's for us to confirm um these two uh are equal and the equation stands. So we're going to do the evaluation of function in toao and we said uh it's it's times g it needs to fall into g field.

So it's function of five times g which is 1. It's modulus 7 because of this. What is it? It's because of modulus. So I'll put it like - 1 uh + 10 + 25 is six. So this is something what we do as as an internal check. Okay.

Now what we will do is do the evaluation. Uh by the way I'll ask all of you to try this at home with um your own G's your own um U values from uh the verifier that's been sent to the the prover with um with your own towels um and uh and everything combined. So um and you know you you can post it. So why not make your own toy KZG.

So for the evaluation we need to include the verifier too. So the verifier would say like okay let me send you something to see if um you can you can uh do the evaluation for the commitment that you have. So here we would say suppose the the verifier sets U is four that is chosen by the verifier and we need to calculate the function function in u S is V. We're going to use this later for finding zeros of the

polomial. U is a root of F while F is calculated like like this. X - U divides F prime at the same time. No, the proverifier should not towel. It should be deleted after the trusted setup and we should only work with the global parameters.

Uh what we have here is um also like how are we going to find the zeros? Sweet. That's q of x * x - u because of zeros something. Um, okay. I'll I'll mention the the theorem later. It's not to forget it.

F and the point of u should be minus one. If we are following um okay we still have the function here -1 + 2 * u + u to the to the square the power of 2 it should be -1 + 8 + 16 okay of course modulus 7 should be 23 modulus seven that should be two.

What does that mean? Because we said that okay that the end result um the the result of the function um at the point u should be v. That means our v is two. Okay. So the f prime function that we're going to have is f minus v which is just shifted

our our function - 3 + 2x + x to the square. Okay. [sighs and gasps] Now um we need to find the quotient polomial which is not going to be sent by the proverifier but the evaluation of the quotient polomial will be sent and this is how this is uh that's called witness

And the Vness uh this is the Vness polomial that we're going to see where the quotient polomial because we had this part just here where it be much easier. Q out of X [clears throat] is F of X - 3 2 X - U.

This is the witness polomial. If we do the calculations, it will be uh - 3. Where is it? Uh + 2x + x ^ 2 through x - 4. And once we apply uh the modulus, we're going to end up with x + 6.

Okay. Witness this value is the value of um of witness polomial looks like this because our quotient polomial is x + 6. We want to calculate the commitment and that's what we call the evaluation, right?

We'll calculate it by Q 0 * H 0 + Q1 * H1 + Q2 * H2. Oh sorry. There's uh because we have the height is now uh uh two, right? because we have only uh x and there's no x or two or something with a higher order, we're going to have only um two um coefficients to be calculated.

So in our case, q0 is this one. >> [clears throat] >> x * h0 was uh 1 plus q1 is 1 because the coefficient of x is 1 time h1 was five and we have to do modulus of 7. So here it's 11 modulus not modulus modulus

7 is 4. This is [sighs] commitment Q is four. This is the witness value. And only this is sent to the world. Okay.

Check if there are any questions so far. Okay. people. Some people join. Super cool. All right. So um we have seen that we're doing commitments and uh those are the evaluations at the secret values. That's what commitments are. Um also uh the witness we calculated here the witness value um that is per definition the object that con uh that convinces the verifier that the claimed

evaluation that v is the result of uh function with the value of u is consistent with the commitment um q of x. Um I don't know if someone needs to do we need to go through the factor theorem of the algebra for dividing the polomial or not please let me know. >> Um I'm having hard time to understand like what is doing verifier prover and who is setting the um u value like sorry I think I missed that point.

Okay, let's put it on paper. >> It's better than >> Yes. So, how this dynamic works? So, we have global parameters and the trusted setup has been done by a multi-party computation. none um neither the prover or the verifier um has any uh knowledge of that. They know only the global parameters.

Then uh the prover says like okay I will tell you that I have a secret um function that I will prove to you that I know it and I'm going to do commitment um and the prover calculates the the commitment and uh the the the verifier is sending um what's what's called like the challenge just said like, "Okay, um I'll send you some U." So, we're going to see if uh what you send back is falling within uh the the zeros of the polomial

because otherwise if um if the prover does not know the the the the evaluation, it will end up in in fractions. And because uh it will not be like round number what we what we have um like 11 or something else it will end up in in fractions uh if uh we do not have a zero at that point of the polomial and uh because we're working the kg is meant to be within the the elliptic curve then we will not be able to convince the the prover that uh we have that polomial.

Um so in um in other words if the polomial evaluates um to zero at some point then x minus that point divides it exactly. Okay, that's what the fact theorem um says. And if um the vi that we got the the root that is wrong um the division is going to fail um it would um set this uh remainder it will leave the remainder and um yeah the verifier will catch it um if the if the pairing check and that's being done on the on the on the

leptic curve um is done. If we is correct then uh division works perfectly and um q out of x is a proper polomial. >> Can I ask one more question and this may be stupid? >> No there are no such questions. Few years ago, I remember there was a KCG something in Ethereum like um I don't know you need to go to their websites and I um word and send them. Do you guys remember it? I don't know like I don't know send >> um what

what is the reason like why they used it? Like for example, I >> I believe Ethereum used this. I don't know by the way. >> I just thought that okay, I remember something like KG but yeah. Ah >> yeah that's um in the comment se session um Russio right some of the KVG trust set up like why this >> uh so what I uh what I've seen and and probably that's uh that's it's I think it's um the ceremony of the trusted setup I think I even took part of it so this is like the the beginning that

everyone is uh calculating one part and then everyone is generating the global parameters. I think it's used for that one that as many people that can join. So it's more um deemed as more secure. I see now yeah check uh oh okay uh so yeah we need to do the verification as well. Uh but yeah before we before we go there as um yeah did I forget something to shareh okay

yeah let's do the notification just wanted to check if I have something that because we have a couple more minutes Uh yeah [sighs] now we're going to do the verification part. We're going to pretend we're um the verifier, right? Okay. Uh um how do we do verification? So in this example because it's a toy kg like the the real KZG is done with the elliptic curves and points on elliptic curves and uh the pqr are prim uh points but um here because um we do not know the the

pairings and uh the elliptic curve as as a technology we're going to show it as some more like practical example to the um how does evaluation and algebraic check works because that is the backbone of KCG. Um once we go through example like this one you'll be able to go and um and try um understanding how it's working with pairings etc. um in the paper um I'll send it to you uh the KCG uh uh paper you will see that um they're doing the multiplication

that is due to the cyclical groups that there are we have um um additive cyclical groups but there are also multiplicative cyclic groups that means that what we're using here with um the the constants in front of every X um we are adding them and that's how we do the the commitments but uh you will see that if you if you want to dive deeper you will see that doing multiplications okay the verification should be always um

so usually the the weight of the calculation is on uh the prover and much less on the verifier. So the verifier should have um easy task and the prover should bear the the weight of the calculations. So let's write that down and be done with the Friday.

Okay. So to do verification I mean like again like the verifier know the prover they do not know to um we um calculated we checked uh the commitment using um using toao just for our own sake to see that the the math is mapping right. But uh but yeah like none of them they know it and um in real world a verifier would use uh pairings to check but for our case the verification that we can check is oh why we have this to minus u

times commitment of Q should the commitment of F minus V G. Okay, let's check for numbers. So, TA was five. G was 1, U is uh what was U? U is four. Check. Yes, U is four, V is 2 and we got almost everything. Bar commitment of F.

Uh commitment of Q is here. Commitment on F. What is commitment to F? Does anyone has anyone wrote that down? >> It was six, I believe. >> Okay. So the verification should match. So we have 5 - 4 * commitment of Q is 4 should be the same as 6 - time 2 * 1 and

it ends up it ends up as checking This is the the algebraic check and uh let me check if we have something else to mention if we have skipped something. Yeah. So the only thing is that uh that the the prover should not know the verifier should not know to he will um to would be hidden in the real KCG

scheme. But this is the toy KCG example and the verifier we use uh pairings on the lipic curve instead to check the relation between the commitments. Um so that that is that is all that we uh have for today. Um I would ask you to check it with your own examples, check it with your own um small um commitment scheme, with your own trusted setup, with your own modulus.

Um yeah that's all folks for today. Um thank you. It was really cool to see the map behind. Um I was just uh so verifier define the U and everything. Um the prover is actually doing all the job. Verifier just check it is correct or not. >> Yes. >> Yes. >> Okay. It's really cool. It was really cool.

>> Okay, super cool. Guys, are there any questions? [laughter] It is. It is. All right, then we're going to wrap up the the session and uh yeah, that will be all.

>> Um today I will try my own version like to check I learn or not and share it to the group. >> Thank you very much for additional session. Really we take a lot of of your time and thank you very much. >> Thank you for being there. See you soon. >> See you soon. Byebye. >> Bye-bye.