Session 3 - ZKP Basics

Transcript

Okay. >> Um, whenever you feel free like you feel for it, we can start. Actually, >> I'm recording right now. Yes, perfect. Okay, who's ready for more ZK ZKGM? Everyone, my name is Militita. I'm

de engineer for ZK verify and also doing PhD in zero knowledge proofs. Uh let me try share my humble presentation. Okay, today is not going to be easy, but I believe in you guys. Uh, we have been through um quite some rides with cryptography and um everything we had, right? And uh the hashes like and the ciphers and all the games we had.

So I trust we're going to have um we're we're going to have some ample understanding with uh with further math. Uh but yeah, today is going to be the day where we're going to dive in um KCG commitments. Uh but also we're going to show how to work with multiparity computations. what are actually zero knowledge proofs now that we had um uh now that we had uh all the parts from the cryptography that we have covered. One thing that came to my mind that we can cover and uh I can send you um some links about it is

elliptic curve cryptography uh which um which is uh which could be the crown of everything we had here. uh but uh maybe we can cover it in the next class as um as intro to snarks but yeah let's um let's start with the properties and who are actually the actors in all of the these zks you know like let's see that where's their zero knowledgeness and all of these things right because we're constantly talking about how to trick uh hackers into not be able to read uh what we're trying to hide. So it's always some kind of with cryptography and zero knowledge proof is

always some kind of you know hide and seek game in a way. Um so yeah let's um let's see who are the actors are uh who what do they do? How does it look like? And I'll try to explain uh KCG um which uh which will help you understand and see the the zero knowledge in this part. Okay, before we dive into it, why ZKPS?

Why? Uh it's um it's been shown to to I mean like before blockchain we didn't really use ZKPS. The blockchain was the uh the the machine that pushed uh ZKPS forward. Uh before that it was sitting in a dark um on a paper that uh uh people in the 80s have um um have created. it's uh it's that old uh older than most of us here in the call I think uh but uh you know sometimes if the industry does not pick up certain things uh it's not we're not going to see the

development of it um so how did it come that we have ZKPs in in the blockchain so one of the first things that uh most of the people heard about are ZK rollups where we're trying to see like you know how can we just put like thousands of transactions into one as in a way to reduce the cost of uh one transaction. So instead of paying for one transaction you will pay for a thousand part of it uh by having a rollup. And uh for that to be um possible we need to um with all the

thousand transactions uh being run on some layer two we need to enclose a proof that we did all of these uh transactions correctly. Right? So that's where zero knowledge proofs come to light and um and we have a spotlight on them um for for a couple of years due to that. Uh another thing is uh privacy. So you can have uh um it's not only that you're proving that for example you um you calculated all of the transactions correctly. it's uh also for uh hiding um certain data. So it has that uh nice

property but usually when people say like oh it's using ZKP doesn't doesn't mean that you're going to have the the privacy property. It could be it's it's a very common misunderstanding with ZK that um uh the the zero knowledge in terms of privacy is always included. Uh but uh yeah you can use it for that way as well. Um so how does it look like? Um so you see this uh nice save box and like I can tell you like hello you know I know um the the secret code to this safe box and um you try to unlock it you cannot

because uh you don't know the the secret password the secret phrase right uh but I tell you like hey you know I know that that uh combination and um you would tell me like prove it and I would say like okay but I will not show you my secret combination because then it's not secret anymore, right? Uh but what I will tell you is like you can you know write something on a paper that only you know what it is about and you can slide it through this um small opening and if I can read it uh that means that I was able to open this safe box right and uh read it out for for

you. Um so that's something that we usually call interactive proof because you can you can say like oh you were so lucky that you just guessed uh the combination which might be true. Uh but if we increase um the possibilities um that uh the possibility that I was able to just guess it it's um it's diminishing. Right? So that's um that's one of the examples that you can use and um explain um what is actually zero knowledge proof. So in this case that would be the combination to a boxh what do we use in zk uh who are the

actors right whenever you have a story you should know the actors like the main actors are prover and verifier. Um so prover wants to actually prove um some statement that would be a subject and the verifier would be like hey like um you know I need I need something to to support it. So with that uh approver will have a witness and there will be relation between uh witnesses statement that uh the verifier will get.

We'll see it in in a bit. So yes um uh if we have uh we just come back u s uh would be a statement. W is usually witness. Uh that's how it's marked usually in Z case. Uh witness is a secret part. Statement is something as in hello I know the combination of the say box. Uh so yes this is uh actually uh the yeah the basis basically uh basis uh in in a way that um hey I want to prove that I have a statement uh and I'll and

I close the and close the witness as well uh but I will prove the relation between the two without revealing my secret my witness is so yeah um we have learned hashes uh a couple of classes ago. So one of the examples we can use is hash pre-image where uh we can say okay you know um I I can tell you like hey I know uh such number that um when we hash it we do the the the modulus 7 it will end up in four

and uh and uh that will be um that will be the the statement Right? And the proer would say okay sure I will um I will ask you to prove it. So sometimes it's uh um sometimes it's uh difficult to do it in in uh in a way to um let's say like you you can say like okay I I know um I know a hash um of modulus 7 such that it ends in four but um it's easy uh to just add on numbers in this case but when you have to do it on a bigger scale. It becomes

really difficult uh for a for a for a um prover to do that if they do not really know the answer or they do not possess a group uh that uh has the answer to it. Um so for example how does how does verifier satisfies uh how is verifier satisfied with answer. Now uh there is um something that um uh the the verifier can do is uh they can add um certain numbers up to um in a such a way that it satisies that modulus

ends up in zero and they can say like okay I added this and it ended up with modulus zero. uh but uh there is uh a weakness in this that um that we have uh that it can be revealed and uh that prover can learn about the original number. Uh but uh yeah it's um this is how it goes. It says like I know a secret number that hash four where if it says prove it but don't tell me the number then prover can show some alternative valid number. um it just can add the modulus to it and verify can say like okay I I trust you that you know

these answers uh without showing me the the the one that u you actually um you you want to hide uh because basically what uh we proving here is that we can um we can make such calculations that satisfies our uh um our statement Uh so yeah, let's um let's try it out like we did before with Paris. Um so how many people are here?

Let's see. Um there are like bar me and I guess some AI. um that there are 31 people uh if we do not count me. So let's make some pairs and uh let's make some calculations. You guys can say like um yeah let's uh uh I'll tell you that I know modulus such as uh we can use uh modulus 7 or modulus let's say 13 uh but let's divide in pairs um I don't

know hatton do you want to uh do you want to write pair couples or >> yeah sure um let me just check who wants to be with Okay. No one. >> Yeah, I'll be there. >> Okay, perfect. >> Okay, let's let's write down because it's going to be difficult. >> Yeah, it's >> okay. Let's say Hon and uh who's there? Elas that's one Ariel Ros you know guys how to send um private messages in this chat so far you know super cool

okay Okay. Uh we are working with module seven, right? Seven. >> Uh you can you can choose whatever you agree on. >> Okay. >> It can be between you guys. just um just use a prime number.

Oh, hello Laura. Is there something who is not named for

Paris? No one. No one came right now.

Um, can you show again the previous slides with the example, please? That's it. >> Yes. Thank you. Okay. I suppose that uh most of the

people have communicated and um tried. Why did Ariel scared Rosia with the secret number? You just left the the meeting. >> No. Okay. How many of you have uh tried this

um successfully with your partner? >> I think we did. >> Sorry. >> I think we did like >> Okay. She gave me a number I gave her and like we try to um um prove that it's satisfied. >> Mhm. Okay. So, uh question uh from Karolina. Um so the the verifier is supposed to prove that they know um such groupation of numbers uh that satisfies that um let's say modulus um uh of seven is four

like in our example uh like uh what we have um here that is the the idea okay uh that was One easy exercise for a for a plane prover and a verifier. Um this is what we had here is interactive proof where um the the brick can ask all the time the verifier like hey can you um can you prove uh that you know that you know a number that is uh member of this group. uh just excuse me I don't know

but I I didn't understood even if it seems uh logical but u can we do it with an example that I pick so that I understand what we have to done >> so yeah let's try >> if I give you 15 what are you supposed to say to me or to verify your >> uh let's say that uh for example you have um um let Let's let's see this one. Uh let's say that hash of something. >> Yes, >> modulus seven ends up with four because for a for a 15 you would need to find something that's bigger than uh than uh

than seven otherwise you didn't do a modulus properly, right? Because uh 15 modulus 7 would end up in what? One. Uh so for this example um the the the main idea is to prove that you know such number that when you apply modulus of seven you will end up with four that is the the whole idea >> but what was supposed to say to me the other person like uh I don't understood the exercise >> uh yeah I'm not sure uh which part uh let's Can you and Hatton do one example so

that it is clarified? >> Okay, Hatu has hands up. I was just going to like >> ask it. So I have a magical number and in this example, let's call it X and X mode 7 is three. So I will send Melissa not the number but I will send her that 52 for example so that she can check whether my um like am I you know correct or not but my number is not 52 right this is the right approach like did I understand wrong too

>> uh okay uh it's uh it should be that um whatever Whatever you send, if you're not doing the padding, it will be it would it would satisfy the statement. The statement is that uh the hash is four. >> Uh yeah, like I said hash is like three and I send you 52. But it is not my number. I just add multiple seven. >> Yes. Yes. Yes. Yes. >> Not understand my number. Like >> I'm I'm just saying that I pick three. Okay. Okay, I'm revealing my secret right now. Okay, I three, but in order to send to Melissa, I don't want to send three. But I'm saying that, okay, if I

add multiple seven, um, you end up seven. You you added up seven times seven, which is 49. >> Yeah. And I end up with 52. And I say, Melissa, this is not my number, but if you satisfy this one, you will satisfy my number two. So it is like that, right? Yes, that's it. Ariel, >> yes, I I have I was having like the same question because I was expecting a kind of response from my partner, but then I just realized that you are sharing like a proof that you know a number in the cure. So for example the cure is made by these three numbers 108 350

482 and and I sharing like hey I have this cure this secret number that is part of this cure that module 11 is equal to 9 but I'm not sharing what is my number it could be like for example 31 that it's also modulus 11 equals 9 or even a graded number >> yeah that's it you um you you're not necessarily sharing your secret number. You're sharing you're revealing some part of the group um where like it's like hey for this one I know I know the solution and uh you know that this group can be um

insanely huge. It doesn't doesn't mean that uh you know by this repetition you will end up actually showing the that number but uh you're showing that you you know the answer to something. It's um it's maybe not as intuitive in uh in um in a way that you know like yeah but in the end someone will find out find out the answer right uh because uh in the small group it's uh that's why it's um we're using uh some more complicated u maths for z case uh but this is how it's done um usually the prover is asking like hey verifier you know If you

really know the answer to um to this, you will show me something like prove me and like there are challenges because in this example for example what Hatton said um I could say like yeah 52 modulus 7 um yes it will end up u let's say in three that that you um said it's going to be your hash. Uh but I can say like okay Hatutton was just lucky and like next time she can provide 59 or next time she can provide uh 66. Uh but I can say like you know Hatton is just lucky and like by repeating um by repeating this I'm

diminishing chances that she is lucky and that she can actually calculate that. Um okay so the verifier has to keep providing different values until the prover and verify is like uh find the same number. So the prover can the prover has to check uh it will not just accept per se it needs to check does it satisfy uh the equation. So in this case it's 25 modulus 7 that ends up in four.

So the the the thing is that prover has much lighter work than verifier is the verifier does. So in this case that the prover is just um checking one equation while uh the verifier needs to um sorry the prover needs to um has this hard work where a verifier is just like checking um at the end. Okay. uh does this satisfy the equation what the prover and uh the verifier would be like okay. Um until the verifier is convinced that the prover actually knows

something. Okay. Okay. Uh we're going to go through more examples. Um so we'll open questions later to see if uh we have actually covered this or we need more examples or or explanations. Uh yeah. So one of the things that like sometimes you want to add some padding u as in that modulus of whatever the proer sends ends up in zero and uh in this example is like if we just say okay

we're going to send you 25 um you know the the verifier would know like okay so you know I will reveal part by part but if we you know add some uh some padding to it for example uh 10 35 modulus 7 will end up in zero because it's perfect division in this case so nothing is um left after modulus uh but um yeah if we say like okay our r is 10 it's easy uh for um the verifier to um calculate the the the secret number and uh that's why we'll see in in some of the examples how to use

commitments. >> Oh wow. >> Okay. Um >> yeah we have uh we have tried this. So um uh as uh as we had like um yeah let's uh find the secret number that hashes to four verify would say approve it but don't tell me the number prover can show alternative valid number um so let's say not 25 it can send 32 or or 39 and uh then the verifier will be convinced without learning the witness or the witness or the secret number.

>> Okay. Um so you can uh play with that like for infinite number of times and um the the weight of the calculation is uh on the prover that prover constantly needs to prove itself pun intended. Uh and yeah it's uh it's uh constant rounds like hey prove me you know something and like it can go. it's really not that efficient. So, we needed to to um to go to work with other stuff. Uh but um that are non uh non uh interactive uh proofs which we're going to see later. uh but yeah one of the nice examples is the

graph isorphism that you can see in this u picture where we uh were let's say proving the part that um n2 is between n1 and n3 and all these relations and all these graphs are true so yeah we have seen the noninteractive >> sorry can you go back to the isomorphism I didn't really understand why it was uh important for the prevent the vifier. >> Okay. Um so um I can tell you that I know such uh graph uh that satisfies uh the relations and I can present it in

in different ways and uh every time um it will be uh the truth that you will find a path through from one uh point to another and uh all of these are um practically the same picture. Um they are proving the same thing uh but uh they are like uh presented differently if uh that uh makes any sense. >> Okay. And this is to reduce the the like the number of time the prover has to prove.

So it's um it's not um uh it's not uh uh I wouldn't say it uh it would it would decrease uh the the interaction but it's um just one of the the examples that uh we can see for the interactives. Okay. Okay. Super cool. Um yeah, so we're going to see uh something that's more exciting than um than interactive proofs because with interactive proofs you can um you know you can query many times

um the the proverify can do that. uh for example there are even 3D maps that's something that's similar with the previous example where I can say like okay I know um I know such place in the map like that it's like three coloring uh uh three coloring map and I can always say like yeah I know such a color that um that that doesn't repeat around itself And it's uh and it's provable by by math. And then you can always say like okay but reveal it to me and reveal your

neighbors and you will just see always one one part of the map but the map can change but my statement will not change. So I can always say like yeah but the map is true but and you always query it and like if we have the same map eventually you can learn all the fields but if the map changes constantly like uh in the previous example the hash could change let's say like yeah I know how to calculate modulus and uh you can say like okay pro me with modulus 4 pro me with modulus 7 13 11 whatever and I if I always give you the uh the correct numbers or the correct coloring on the

map. you will be you will say like okay this um this uh prover knows how to calculate um these uh values right uh but um it's uh quite inefficient because there's always back and forth communication and someone needs to check it um so that's why we have uh fat shamir transformation and uh it's um this part uh that we're going to see later is used for for blockchain.

Uh yeah, let's um do another exercise. We're going to we're going to do it uh with um multi-party computation. You will see it um often in documentations especially if you're uh reading some white papers that people are using multi-party computation. So what does that mean? And that means that uh for example we can even there is even a se uh secret sharing uh part but it means that actually like everyone who's uh who joined uh everyone who joined uh computation will take some part of it

and in the end no one would be able to determine uh a secret part. uh why is it uh um interesting? It's interesting because for example you can um calculate you know how you know usually companies are saying like okay the salaries we have in the company are uh kept secret and for example you want to know what's the average uh salary in your team but you do not want to reveal your own data you just want to find uh what the the average is as a team and uh what you can do is um because you want your inputs to stay private, everyone can just learn

the result. Let's say there are five of us and all five of us were um we're adding up our data and um the the public result uh can be divided. We're going to look at it how it's calculated. Uh yes. Um okay for this exercise we need all the participants. We can because we had a birthday attack u last time we can uh calculate um our ages uh we can calculate uh the average age of all of us. So, uh how does it look like is that um I would

need a couple of um I would need a couple of uh uh volunteers to do this because I don't think uh we can do it as efficiently with uh 32 participants on the call. Uh so let's say um we have um 10 uh of participants. Uh okay. Uh I will um I will start. Okay. Oh, there's some questions. Sorry.

Okay. Aha. So Rosio didn't just leave Ariel. It's Ariel, you see your number was not that scary. Nothing is scary for a sea. Hey, okay. So, okay. So, there is um Okay, we need 10 participants. Who's in? Write in chat.

Everyone wants to join. Okay. So, this is how we're going to do. Um I will write down uh uh so I will give my number uh to uh one person that person should calculate and add their number etc etc let's see uh but uh how to send it privately I will send u messageages messages.

Yeah, someone just revealed their age. Fine. Uh I will send private message to that one uh person and that person will will send message um to others. Let's make a kind of a chain. So I will send my uh number to she will send it to read. Okay. you something uh that random offset is going to be different for all of us or the same >> I'm I will be adding the random offset the first one >> okay but in my turn should I add my own random offset too

>> no you just you just add your age >> okay >> the first person will add the offset uh but because I'm not tracking the computation I will not be able to know each of your private inputs because the person you're sending uh let's say that you are the first person that um uh is uh having input from me uh you will not be able to find anything about uh my secret input because I have the secret offset and you add your age but because you're not sending that back to me I cannot read it and the next person will not be able to read what's in because we got like the mixture of two sacred

inputs and one random offset. Okay. Uh I will I will just make so like what we will do is um I will send my secret input to Hatun. Hatun will send it to Hatun will add her age and send it to Reit. Reit will add his age and send it to Ma Malu etc etc. Okay, let's see if we're going to have something.

Okay. Um, >> so Mir tell me one thing. So the last number will come up to you only. >> Uh, you uh whoever is the last in chain. Oh >> uh send hands it back to me.

>> Okay fine. >> So then you'll be subtracting the offset that you have earlier added. >> That's how uh not average but the number will be removed. >> Yes. So, Lu Aka will send um will send it uh

will send the number back to me because if uh if the last number is public and uh the the offset is not subtracted um Then uh Hatton will be able to compare the two inputs and find out my secret input here. So Hatton I will send you my secret input. Let the games begin.

Any else you just ask? So only the the last person we know the offset right? >> Yes. I mean the first one and the last one with the chain. Okay, while we wait for the other

participants, uh, may I just say how vibrant is Milan office here? That's awesome. The office is also looks perfect. >> Yeah. I love it here. Is it Is it a we?

>> Yes, it's a we thought so. Where are you right now? In Milan. >> Yes, where our engineering team works tirelessly. Okay. I have received um a number from Daka. Okay. Yes, it is a beautiful place and we have

really nice sunsets. I love it. So um we have 296. Yeah 296 as our uh number in the end and uh we have to divide it by 12 because there are 12 participants. So what is that in the end? What's our average age?

Almost 25 24.666. You guys think it's right? Everyone who participated, do you feel like you're around that age that we got it right? the final round. >> Okay, super cool.

We got it. That's MPC, guys. That's multi-arty computation. So interesting because it is so easy, but it works really fine. Like it's so interesting. >> Yeah. Right. It's like people are like using it all the time and people are like okay uh does everyone knows what is the offset? Uh who would know what's the offset? Uh maybe yeah the la the last person who was um who's getting it? Uh first and last only if um only if the last person is uh is publishing. Yeah,

because I would uh I would say uh I would say like okay this is the the the result because if I subtract uh my offset and divide it um that's um that's um the the secret is retained. Super cool. Yay. Nothing got leaked except that John published uh before we started.

Super cool. Okay. >> Yes. So, uh the group is hiding the inputs. uh only reveals the the results and uh the the witness is also hidden with ZKP uh it's revealing only the statement true and yes we have a privacy preserving computation let's look at properties of zero knowledge proofs does anyone have strengths for it now that we had a couple of computations

and waiting times. Uh okay. Uh so there are three things that we need to satisfy in order to be able to call something a zero knowledge proof. It's completeness, soundness and zero knowledgeness to say so and it means that we do not know anything about the the input. Um so with completeness it means that if the statement is true uh an honest prover can always convince the verifier. So if we know how to calculate the modulus we'll always be able to calculate it and

uh convince the verifier that we know how to um use that function. When the sound with the sound that says that if the statement is false, there's no way that uh uh we as uh someone if someone wants to cheat, right? a cheating prover. Um there's no way for a cheating prover to uh prove um and and trick in the end uh the verifier into accepting uh the proof because uh the the verifier will be always um checking it. Right? So there is no way um with interactive proofs there is always like a diminishing

chance that um this can be done. Uh but with multiple rounds it's um that chances are like um let's say like um if we have the result it's like zero or or one and the in the first round it's um if it's like zero or one it could be the result and let's say the correct result is one. uh in the first round it will be uh 50%, in next round it will be 25%, then 12.5 etc etc where it's um one through uh two to the power of rounds uh will be uh the chance that actually um the person is just being lucky and is

able to trick it. uh with uh the the third property the zero knowledge NAS it's uh it says that verifier cannot learn anything uh beyond the fact that the statement is true uh with that uh uh thus protecting uh the prover's secret um information and uh the provers's um information is not leaked and uh no one can um say anything about it. Uh that's one of the I suppose that many people here in this group uh when they hear about ZK usually the first um realw

world use case would be like oh you can prove you are of certain age without um actually showing uh all the data from uh your uh from your ID right uh or from your passport but you can just say like hey I have this passport But I'll enclose the zero knowledge proof that uh says like okay I'm over a certain age and I can enter this club or I can uh buy certain drinks or something like that.

Why do we have polomial commitments? Um we're going to see how it looks like uh to um uh uh to to calculate them. It's um in the beginning it looks a bit scary but actually it's not. Uh if you go through it a couple of times you will see uh why is that? Because you are uh practically just repeating the same order of things and we can try it with uh uh some equations that are quite um simple. uh but let's say that u you know uh the the prover can learn something

out of it with time uh we'll see about it uh but yeah so the properties to commitments is like yeah I'm committing to uh let's say some equation and I will tell you like okay like every every time you ask me about it I will tell you like for the value on um uh on on x's I will be able to tell you like the the exact value of that function uh the exact point in in the in the system. So the properties are binding, hiding and succinct verification. Why all of that?

Um so binding is like you you are like um always you're com you're committed to that function and um that's the property of binding because uh you are um using that um as to stay uh uh true to to that one function like that's the the the binding. It's like always that one input that you have will always uh end up at the at this at the same um at the same point let's say in the x um xy uh uh system and um and hiding is of course that you do not reveal the whole function success this is that you can uh

check it easily. So yeah let's uh let's go through what another example like who's excited for this >> m before we could proceed ahead I still didn't got the binding part what exactly so what what do we do exactly in binding >> uh you you'll see it through the example um so we can uh we can say like uh um I don't know uh how do you want to to make couples here to let's say like okay like anytime I mean like Maybe uh maybe we don't have that much time or like let's see uh what else is there.

>> Uh person can do it as a theatrical way like not all of us but maybe we can you know something like that so that won't take a lot of time. >> Oh yeah yeah yeah we don't have to do it together. Um you guys do you see guys uh the chat before we started MPC there were pairs. >> Okay. >> We can use the same pairs so I don't have to write them.

>> Okay. Yeah. >> So there is hatum alasio. Um so the idea is um to uh pick your polomial uh polomial meaning like um you have uh one uh function and uh that verifier can ask the value let's say something on x axis it can be minus one or something like that and the pro will just reel it uh by the end of um let's say a 10th uh challenge you will be able to see the function but you will not be able to completely reconstruct it if it's something much

more complicated right that easy so let's try it you know you can use uh polomials 3x + 2 u minus x minus one uh u you know be creative with it and um then uh the verifier can ask and prover will reveal uh certain dots on um on the grid coordinate system. In these cases, x is always prime

number right? you are mute. >> Sorry, it doesn't have to be. It needs to be something. Um, so it's like the equation in coordinated system. So X can be whatever number. Um, so uh a verifier can ask approval like give me um your result in this point. It can be any point on x axis.

>> Can I ask you something? >> Sure. >> Like whenever um like I reveal something for example um it says it ask three and I say it is 30. What does that mean? like they don't understand my function and what the value that I real means like how they can check whether you know I'm telling the truth or not did I did I ask correctly or not but I don't know um like I don't understand the reason like right now in this example prover reveals 11 so like what what happened

like with 11 >> it's the it's the result in in the 04. >> Yeah. But like um you know >> here the equation is already there. So we calculate that is okay what Hatun and I or or we are trying to understand like suppose I give X as a value and Hun is revealing the final output number something as 30. Now that equation so do we need to crack how we can crack that equation part or what exactly we are expected here we are confused about that that aspect the process what we are expected of because we are not revealing

the exact we can say equation just sharing the numbers so do we need to come to a point to an equation or something else hope I clarified that >> uh only like asking uh values and uh the results, right? That's it. >> Yeah. Yeah. Yeah. Yeah. That's it. That's it. >> Okay. Okay. Uh so I see the questions in in

the box and um uh what uh would be the answer is that you binded to the polomial um committed to a polomial. So you cannot find you cannot trick uh the the verifier finding another polomial that satisfies the result. >> Yeah.

So we did the exercise to show how it goes but basically you are binding with the polomial that you cannot just abandon it and say uh we will not uh we're we just decided not to use this anymore and we're binding with something else or like we're um we are uh leaving uh this uh polomial in in a way that you know I'll just find Another equation that satisfies the result. Okay, I see the questions. So, how to

bind the polomial uh where they where they are. Um uh we we can um we'll see how one of the famous commitment schemes look like uh case over Col Goldberg and uh we'll see how they do the calculations um how do we uh use the the binding mechanism uh where is that polomial who has it right and all of the rest of it. Um, so far I just wanted to uh show you how the calculations look like behind the

scenes. Um, how does the mechanism work uh back and forth uh with uh the the proving with the numbers right and calculating some function. Um so I hope that everyone did it in the pairs already. Um so yeah the the polomial is um is is binded with the prover and uh we're going to see how does trusted setup look like. There is there are zero knowledge proofs without trusted setup and uh that's why they say they are quantum resistant and uh that those with the trusted setup are not

quantum resistant. Uh we'll see all of it um in a bit. Just uh let me share it. >> Okay. I hope uh you can see uh the okay see people not in so cool. Uh so KCG is something that's the backbone of um of their knowledge proofs so far. It's a commitment scheme um named after Kate Zusha and Goldberg and um that's um yeah we have we will

see pairing in it. Um how does polomial commitment look like? Um how does binding work behind the scenes? Uh what is commitment and and how to prove you um know know certain uh value without revealing uh uh full uh without revealing your your um uh your secret in the beginning. Right? Okay. Uh the key properties of it are that it's compact, efficient, and that it has trusted setup. Uh why do we have all of this? Um it it needs to have

structured reference string. We we'll see in a bit how does it look like. Uh the verification is very fast. uh you will see that it's uh constant size commitments and proofs which is a very nice property when you look at the trace of the proof in the end and uh it's uh not um increasing by um it's it's not increasing with uh um the inputs it's uh rather a constant size and let's let's see how it look like looks like and how does pol polomial setup look like? So first of all to have

a polomial you need to have um a structure that looks like this one like p of x and then you need to have um x to the power of um uh it depends on the order of your polomial uh in this case it's order of uh n so you will have h at certain place you will see like a z it's um it's binded put um x0. So because it's anything to the power of zero means one. We just have uh we just have the uh the constant here and with the polomial um the coefficients are

secret. So in our in our case that we had uh we were supposed to have um secret coefficients but because we do not have a commitment scheme we cannot do it as um as efficiently as uh KZG commitment scheme does. Um so you want to commence to some polomial and you want to later prove that whatever is given to you you know the result as we did in the previous example because we were able let's say hat was able to tell Ariel okay um I'm um I'm committing to this polomial and I'll prove you that I know it by providing you the results uh to it uh with uh the

uh with uh the challenges you give to me. The trusted setup um the trusted setup is made uh by a group uh of certain order. Uh usually it's uh group G uh or for order P. And uh we'll see in a bit um how to generate one of those uh how do do they look like? How do we uh choose them? And um the G's that we have are generators of the group. So you can think of them as um a value in the beginning that we're using

to construct the whole group that will be used to um calculate um points in our functions. Right? you we will see it in a bit how everything looks like because we have uh an example uh yes if we have um um trusted setup uh leaked right if we have the ass leaked which is um uh which is a part of uh uh structured reference string that we h that we see here then uh the security will diminish uh which we cannot um we

cannot uh allow. And um yeah, these structural effort strings they can be universal, they can be per circuit. Uh but um yeah, wherever you can um you should have one per circuit. It will increase the security. Let's go to the procedure. All right. Um so the KZG uh consists of a couple of steps. Uh we will see how does uh setup look like. Uh how does commitment look like evaluation and verification.

Um so first of all you need to create um this secret group of yours this um trusted setup. you need to do the commitment uh to uh a certain polomial right um using your setup and later on we will evaluate uh the result and later on verify it so the let's say that uh this is our group um of order p what does it mean that the the the number of uh um the number of participants and number of elements in

the group um can be a maximum of P. Let's say it's seven. It will end up in in seven uh members of the group. Right? This is how the the setup is done. uh this GP that you see it's uh the the calculated group and then once we have uh TOAO which is uh that uh secret it needs to be deleted uh but so far you see that we have um G uh G is a member of uh one of the

elements of group uh G. So it can be anything from 0 to p minus1 * g. Okay. And uh then uh whatever we picked for trusted setup we will multiply it till the order of d which we'll see it's the order of our equation. uh till then we will calculate the GP because um we can even calculate more of it but it doesn't really u make sense for us to go over and have uh um and have ages for bigger order than our a polomial is.

This is how commitment looks like. Uh so we are committing this um GP this group that we have HO H1 H2 etc till HD uh with the function uh where whenever we uh calculate the function in in these um um in this areas with tow we'll get uh something that well uh sorry this is okay I'm trying to to to uh to to read to be able to read everything and still have have the camera set up.

So this is this is how it ends up in in uh in the commitment because we're going to do calculations with uh secret numbers. Okay. Um so every part of our polomial uh every uh degree of our polomial will have enclosed um enclosed h. So for the the constant in our in our formula in our uh polomial we'll enclose h0 zero to the order of one will have h1 uh all all up

to the order of d. Let's go through an example. Let's say we have um group uh from 0 to six uh meaning that the order is seven and we will say that uh the G is a generator of the group and uh we will pick one because it's uh much easier for us to calculate right um f uh p that we have seen it's a field uh of the um uh it's it's a field of order of b

uh this is our polomial x ^ 2 + 2x - 1 and let's say that we are picking toao uh the secret number uh we're picking up as five and because our d the order of our polomial is two we will be able to calculate the GP and we will uh remind ourselves how just let me check if there is anything that is unclear check.

Okay. Okay. So let's remind ourselves how do we um calculate uh our our polomial um the commitment of our polomial uh we can uh we can do it like this but first of all how do we calculate the group right this is how so first of all um h0 will become g What we see uh from from the top part is that g is 1. Um h1 will be toao * g because

uh toao is five. Um we will end up with the number five in h2 we will see uh toao to the power of 2 u* g which is 25 * 1. Uh but because we have the order of seven, it will end up in four. I don't see it right now. Is it? Yeah, it's written four. Any questions so far? Okay.

So this is the commitment. This is how we actually um commit to a polomial. We're using the previous values that we got H0, H1, H2 that we calculated using toao um and uh and G and we're um we're calculating all the points within our polomial. Can someone uh jump in for this exercise? Would like to volunteer.

In the last in the last example, H2 was 25. So how come the H2 is written as four? >> Uh because uh because Yeah. Yeah. Yeah. Because our uh group order is seven. So we need to do modulus. >> Okay. Fine. >> Mhm. >> Okay. >> Because when once you have the order everything needs to be all the results need to be within that group.

Hatton, do you want to do the first example which with uh F0? >> Um yeah, I can try. Um so here uh >> Mhm. >> I don't know how to uh like I don't know my steps. I think it's >> okay. >> Let's go through it together. So we have f0 * h0. Let's see if there is uh something that we can use uh for us to help us. Let's go back to definitions.

Where did we define it? Okay. So, um we will use um age zero, right? Which in our example before was one. >> Oh, I see now. Okay. >> Yeah. >> You okay? So um in the first one uh the h0 was uh the second >> one >> was one in the second one it was five

and it the third one it was 25 but since we get the modulo it is four. >> Mhm. >> Um the f values we are putting one uh for example we are putting zero at the beginning. So it is minus one. >> Yes. Because that is the the order that we start with. Yes. >> Okay. In the second one we are giving one and it becomes one two and >> it is 2 * x >> that way and when we calculate the result it is 13 um we are getting modulo.

So I don't understand why we're like I don't understand why we're calculating these stuff. I'm sorry if it is too fundamental. Uh no worries. Uh because uh we want to show uh in the end uh what uh how can you know we hide uh uh our um uh our our um trusted setup. Because once we calculate everything within our function and uh give it to the the verifier, they will not be able to deconstruct the towel but they will

be able to um they will be able to to say that uh we uh have the right uh polomial. They will they will come to the same result basically. Oh, say they will have ash values but they don't have the towel, right? >> Uh yeah, we can we can look at that way. Yeah. >> Uh maybe this is uh a bit um too advanced uh for the group. Um yeah, maybe we can uh wrap it up soon due to uh yeah well let's uh maybe I have maybe we haven't planned this that much right uh because it seems like it's

too advanced a bit uh but um yeah if uh if nothing I will uh give you the whole calculation that everyone can sit down and calculate and um yeah I don't expect it's um going to be in one setting that everyone can understand KZG uh but um I'll just show you how to calculate it right now and uh then um I'll just enclose the the whole calculation with the commitment and verification evaluation so that uh you can check it and compare

It's a bit um it can be complicated. >> I have a question. >> Yes. >> Um to calculate H2 times H >> or it's written H3 but it's H2 or it's H3. >> Uh let me check. I don't see it. Yeah, it's actually should be it should be uh H2. It's my mistake. And so f_sub_2 * h2. So f f_sub_2 would be 2 uh * 2 + 2 * 2 - 1.

So we get 7 and then we multiply by h2 which is 4. So here we um >> no I think must multiply with one not two like minus one two * 1 + 1 >> but how do we calculate f_sub_2 basically is my question. Uh yes. So what we have here is we're using the coefficients uh with f0 f_sub_1 f_sub_2. We're using coefficients. That's why we have um respectively minus1 2 and one. And we're multiplying them which with h0 h1 and

h2. >> And how do we get one for f_sub_2? uh one for f_sub_2 because in front of x to the power of two uh there is uh there are no coefficients so we're implying that coefficient is one. >> Okay. Uh okay. So f_sub_2 is the coefficient be um in front of the power of two is it? >> Yes.

Oh, that makes sense. So right now um we don't have to reveal to but um since they have the coffee and they have the ash values they can calculate any values and we can check like um I don't need to reveal that value but we can agree on the value actually is correct. Okay, >> this is this is what the the commitment part is. >> Uh but uh yeah, for for it to be calculated, it needs to well um we'll use uh the what we have made with generator and trusted setup later.

Just check here we can uh use uh commitment uh with f um with the point in towel meaning five uh times g the generator which is one and it because it needs to belong to the field of g where we got the generator from we need always to be at the same um in the same field in the same modulus and we need to do um we need to do modulus seven because uh our p the order of the field is seven.

Uh so what we can do is we can calculate um the the polomial in.5 that means -1 + 2 * 5 + 5 ^ 2 that will end up 34 with modulus 7 it will in Yes. This is how we do the the check >> and the check is done by the verifier or

by by who? Uh this is uh so far because we have uh in this part wherever you see toao um this this it cannot be done by a verifier. So verifier should not know anything about uh the the secret value. Um it's it's just for us to check. This part is for us to um check if we did everything well. uh but uh if we did everything well with the the from starting from H1 and H2 values we should have the same result. It's done just for the internal check. It's uh >> okay

>> done usually right. >> Yeah. Yeah, it's it's uh it's a bit uh advanced. It looks a bit complicated. I'm trying to make it um as simple but still it's like you know there are fields, there are new terms that we have what is uh how to react it with the chicken in a shell. Oh,

but yeah, it's um this uh this is uh deemed as a foundation of zero knowledge proofs because it's uh you know you will see the the secret value uh what actual binding is how can you check it because you see that we have used our polomial with calculated H0 H1 1 and H2 and got the same exact number as if we had used uh just towel uh the secret one that we were supposed to delete in the beginning but we were just like we're going to keep it just to check it later. This is just for the example. Uh but uh but yeah, you know, it's it's a lot of new

um it's a lot of new terms that we have and uh and yeah, then the order of the group, the the group itself, how do we use it and like thousands of questions and like why do we need to be within the same order? Uh but yeah that's uh that's uh you know that's uh what we have with the KCG which will see that there are foundation for snarks like uh GR 16 etc. But um yeah, I will um I will send you guys the the check uh the the the verifying and evaluating part of um this exercise

because we sly do not have that much time and I would like uh for you guys to repeat the process. uh I'll just put it uh the complete um calculation in the chat uh so that you can repeat the process and um please if you have time please do it. I'll be there to answer all the questions because doing this uh on the class uh with uh the uh with this advanced topic uh we wouldn't we will not get this far but uh we need more time than we had.

Um so uh let's um let's then um stop here and yeah the prover will never never be able to know to uh and yeah is it math or magic who knows Mr. been uh has definitely um you know uh provide gave some uh bigger answer to um contributed to the age in MPC computation.

Uh so where we use KZGs um is uh mostly with um yeah with the Ziki circuits the work trees uh and with rollups and um yeah let's go with the summary for now we're going to stop here. Uh later on we can we can work through verification evaluation. Uh we have uh seen the witness, the statement, the relations, the prover, the verifier. How do they work? How does how do interactive and non-interactive uh proofs work with multi-party computation?

the key properties of zero knowledge proofs which are completeness soundness and zero knowledge ness and uh how the commitments look like and KCG which are the zero knowledge proof foundations and then for the next class uh you can uh uh you you will look at um the the calculations and polomial commitments that uh I'm going to send in the chat for you guys And then if needed we can have one shorter session just to just to try and calculate once again uh everything that we have but I think it's it's a bit too much for for one sitting

uh after two hours I I don't think anyone has the concentration sleep. >> Melikica uh can you just put the previous slide where the use cases? >> Mhm. Yes. I had read I think it's uh EIP4844 is also one of the things right I actually wanted to know if you can put some light on that and cuz I've heard that KZ which was >> which one sorry >> EIP4844 >> foundations >> uh yeah I will I will send uh if you can

just write in in a in a telegram group and tag me. I will send uh all the details about that. >> Okay, sure. I'll do that. >> Okay, perfect. Today was really intense by the way. Like I'm sorry, but >> this is amazing. Like I can feel my brain is growing. So I I'm I'm sorry. I know it's um sometimes this is too much uh um but um yeah if you guys want to understand ZK's in in depth yeah like um Hatton we can organize um some um session between

today and Wednesday just for uh wrapping up the KCG because uh for KCG I think we would we would need uh another 45 minutes for everything to to go through. Uh but yeah, first of all, I would like uh you guys to work uh through the examples I I sent and also for what Saav asked, I will uh provide um answers for that as well. uh but for uh after the KCG you will see the GRO 16 and plunk and starks and uh yeah for the uh for the building

together you can always join our telegram group for ZQ verified dev uh follow us on Twitter or X visit our docs this is me on Twitter Zeraxa and yeah like stay building stay curious with ZK and yeah honestly on if we if you want we can organize um some session tomorrow or Wednesday uh where we can go through uh more details on KCG. >> Yeah, sure. Uh I'm I'm going to text you and we can arrange maybe.

>> Yeah. Yeah. Yeah. Yeah. Tomorrow I think I'll be at Polytechnic Milano. I'll know by the end of the day uh which day exactly with the professor. uh that yeah it's um um I see that people are interested but then the the attention is not here anymore. By the way, I try with different polinomial and I get the correct results like the commitment and like yeah like trying another example with myself helped me a lot like I got it. I got >> Yeah. Yeah. You see it's like it needs to start somewhere so that people can try it out on their own and they see like okay every time I check it with towel whatever my tow is and my

generator uh it will end up in in the same result. So it's >> Yeah. So it's it's a good start >> moment for me like Yeah, it's working. So yeah. Um let's just >> Yeah. Eureka, right? >> Yeah. People going to love it. >> Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. We need definitely one one additional class for this so that we can see like oh you know what is actually binding uh property? How do we uh prove we know something without telling them that we know something? And uh you know what are those numbers that we're actually sending?

>> Um thank you for this session by the way. It took literally two hours and like u >> I didn't I didn't get any water. >> Yeah, by the way I just drink tea but yeah. Um >> Oh this feels good. >> Thank you very much. Seriously, >> guys. I hope you you're not too discouraged with this session. But yeah, let's uh let's continue working on um let's continue working >> I have a question. Uh I just wanted to know uh how what are the like uh real use case where you think this commitment

case I'd say will be used or is just the theory part because honestly I'm more interested in the application part or you know is it going to be useful for me as a developer as a builder. >> Uh for this it's um why do you need to know KG as a developer? Um actually like there is nothing that you actually need to know um per se like when it comes to if you just want to do application part sometimes like you don't you don't need to know um you just want to do application you just want to use zero knowledge proofs you want to verify them um you can say like okay I don't need to

know but there will be certain parts where you want to write a circuit and you don't know what private inputs are like how does everything work behind the scenes and if you want to know uh you know uh what is the the hiding property how does it work work uh um you know do you want to use some other curve do you want to use some other type of proof proof you would need to know such properties because how else can you tell like you know that uh certain uh uh that certain curve is not for you that uh certain type of proof um will not meet your standards and and your wishes and what you want because let's

say it it it uh it exponentially grows with this example you would see that it's always constant one. Um so those are the things that um if you want to learn how to um develop u applications using zero knowledge proofs um it's not mandatory but if you really want to be good at what you do you should definitely learn it >> I wanted to write tree but I couldn't uh because after the ethereum road map I saw there is something called Oracle tree and I said hey maybe I can do it it's must be another data structure uh I couldn't because I didn't know I didn't

understand commitment I think but I'm going to just check it out after this class maybe I can understand finally >> yeah yeah yeah we we need to wrap it up with the verification evaluation then you'll see but it's um it's as if you learn any kind of math you need to do repetition that's why they have one class and like couple of repetitions but um to try it out with different examples but yeah guys um I'll send you everything. Uh thank you for having me.

Thank you for staying uh by the end of the lecture. Uh hope you will hope you will read what I send you. I believe everyone going to read because it was really interesting. Okay, it will be even more interesting. >> Um, I think we don't have any additional questions. So, um, we can finish. Uh, we took Melissa's two hours and maybe we can just finish right now.

>> No worries. It's it's two hours gladly given to or ZK. Anything? >> Yeah. Yeah. >> Can we go to cry right now? >> It's okay. We were we all were in that in that spot like uh I was uh when I first saw ZK Pro I said I'm not going to touch it with the town football pole and here I am. >> Yeah. So it's it it looks frightening and that's why we started with um some smaller examples with some intros so that this you know when I throw ZK proof with as if KZG it's not that um intimidating because you went through

the helman you went through hashes you went to um some older ciphers some modern ciphers you've seen it uh as as a preparation but still Like now you are prepared but we just need more time to go through um through everything slowly that um you know that groups are not new for you um that orders are not new for you. Now that we have um come to this point then we'll um do the evaluation and verification part as well.

Can I guys um thank you for the session and um hope >> Thank you very much. Yes. Thank you so much. Bye. See you Wednesday. Thanks. Take care. Bye.