# Elliptic Curves and ZK Proofs - Özgür Armanc Yiğit | Ethereum Fondation

- Speakers: Özgür Armanc Yiğit
- Channel: [ETH Belgrade Community](https://streameth.org/eth-belgrade-community)
- Date: 2024-10-07
- Duration: 23:54
- Topics: People & Blogs
- Watch: https://streameth.org/watch/yt-lueaV76z9Kg
- YouTube: https://www.youtube.com/watch?v=lueaV76z9Kg

## Transcript

uh always like inviting people to our join to our Discord you can scan it and just join uh to ask some questions and say hi to everyone like it's a good place to ask some questions about ZK as well um and you can find my git up here so yeah elliptic curves I will pass this immediately um yeah so uh as you can see here um we have different images of elliptic curves and um the the elliptic curves constructed over finite fields are best friend as I told you uh because they provide us a crypt uh Group which uh the discrete discri logarithm is pretty hard and we want this because we don't want people to solve our uh you know calculations uh easily with you know like um I think it's like with for trying so um yeah tic Cur pretty pretty good about it and we the the most common form is uh we I don't know how to you know read it correctly but I guess we stress form and you can see the formula here uh we are using this formula and if you change the A and B here you will get different shape of tic curves um so yeah um these are some examples as you saw and um the the the case we have to be careful about um is the the the the singulari is uh when you change a and b you can get different uh results right so um if your a is zero and um your um you you satisfy this equation which is 4 a cub minus 27 b² like uh you will get curp um so sorry for that so you will get the the the curp and which is which has two uh same lines they both have the same tangent uh they they have the same slope so we don't want this and the the other one is not and if your a is not zero and you get the uh Singularity which you will have a the a single point that has two uh Solutions right it will give you ambiguity so the both are like uh security flows we don't want these so we have to be careful about this U formula and uh like we always exclude this in our elliptic curve choices so yeah so yeah uh let's talk about the fields uh finite Fields uh it's a fundamental crypto um component as well uh it's a set of elements uh that has um two uh binary operations which is um addition and multiplication um like good example of fields are real numbers uh they have uh it's a uncountably many it has uncountably many elements that's why we call call it a field but if we strict it we we can say that it's a finite field right so um yeah the the let me show the next one so when we yeah when we uh at at the first page I told that we construct our elliptic curves over finite fields so the the first one we have to do is choosing a prime number which will be our like uh big prime number which will be our base field then we will choose the this uh elliptic curves and we will uh use both of them to to satisfy these all you know like security things the easy calculations a lot of things going on back there but yeah we have to choose these two very carefully and uh the when we choose this elliptic curve and the base field uh the B base field is our finite field uh you can see that like in the these four Images they have uh they have the same elliptic curves but different um finite field right uh the different base field so the first one for example is 19 you can see that it's the maximum number is 18 so you can't pass 18 it will rep up to zero um you have different results each result is our um you know eptic curve when you use that equation you will get different results and each point is your X and Y coordinates so you will get I don't know like maybe 15 results and if you increase your uh finite field size like mod uh you will get for example in the second one is 97 you will get more results if you increase it to I think this one was one one 127 let me yeah 127 you will get more and more results and 487 so they are all primes and if you increase it you will get more results so I will talk about um private K public K calculations a little bit and uh this is very important because these uh points will be your uh for example uh your um public K in a point and you don't want people to calculate backwards and find your private C right so that's why if you increase your size you will get more results that's why we are choosing I don't know like two two over something crazy like 256 54 like a lot of bits um and it will be huge like it's very big number and you cannot NE you cannot calculate uh the backwards right uh you can you cannot try Force try uh so yeah uh why we are choosing Prime uh number is another thing uh this space field has to be uh Prime because um if it's not you won't have uh multiplicative in inverse for some numbers for example um if you have um if you have mode four which is not prime uh two has no multiplicative inverse right you cannot get one NE never because uh it will be always even number and you cannot get one that's why we want it's like if it was five for example you can just say Okay 3 * 2 is six and it's like equal to one so multiplicative inverse is three uh yeah that's why we have to be careful about it as well uh when we are choosing base field so yeah we will uh use this two to get these results each dot here is our um uh the the they will form a group I will explain it in here let me be perfect like this okay so a group is U also a good uh like we we have to uh have this property as well and when we calculate this like fin and field elliptic curve we will get this result each dot are set these sets will uh form a group in our eptic curve and they have only one uh operation which is addition and they have to the group um if we want to call a set a group we we have to be careful about these uh five properties uh it has to respect like uh yeah it it should be respecting all of this and um you can see like for in closure we say that if a and b inside the set the result should be inside the set so you have two dots your uh the the other dot your result should be inside uh your set as well um on your adaptic curve result actually like um equation so associativity says that in parentheses a plus b plus C should be equal to a plus b plus C identity says that we have an element and which doesn't affect your result we say um point at infinity or zero um inverse is basically if you add you will get zero uh your negated number your inverse uh commuity says that a plus b should be equal to B plus say so if you satisfy all of this you will get a group and these are all our basic things that we we we are using in elliptic curve so I will now show you how we calculate Point addition so yeah this is the most basic one right you want to add P to Q so you draw a line the third intersection point is your result but you have to negate it on y- axis so yeah the the opposite side of it will be your result so this is how we calculate addition on elliptic curves so yeah when we say addition it's like maybe you can imagine like 3 + 2 no it's like little bit different you have to do some tangent operations that's why we are uh in the the second Singularity one I told that the the tangent line is pretty important right yeah because you are using on the calculations I will show you like here um as you can see like directly we are using tangent here um if you want to add Q to itself which you know AKA uh doubling um you have to take the tangent L of it um the the and the the other intersection point will be your result and of course you have to negate it on y- axis um so you will get yeah the minus p is your result this is what we call D doubling um yeah I'm going pretty fast though um yeah let's talk about negate um so if your Q is your um you know negate like if you add three to minus three you will get zero right it's same on elliptic curves as well um this means you have to draw a line and it won't intersect any any point uh you know and and we call this a zero uh as I told zero is our point at Infinity in elliptic curves so yeah um a p here p is uh point at Infinity the only point that on the the the left side like the on the edge um it's our point at infinity and if you add zero to zero which will never intersect any you know third point so it's also point at Infinity so if you add Z to zero you will get zero basic the same on the the real numbers so um yeah so yeah scolar multiplication um this is a good algorithm uh actually as I told you like on private K to public k for example when we calculate this we use scolar multiplication actually um so if you if you add P to P you will get 2 p and at another P you will get 3 p another 5 P you will get 8p right like 8 p we have this eight number on the like uh near RP or 11 for example here um in this example like 11 P what we mean with 11 P it means that you have to add p 11 times to the uh the result right you have a sum and you have to add P so it's a lot of job you have to do this um like 11 times and in instead of doing this this addition we have this uh algorithm double and add uh which is way easier and uh it's cheaper than the the the original method you know um what it says that if you have like 11 in front of your number you can just convert it to bits and the the the if the right side like the first bit uh is one it means that take the P put inside the bag uh the the sum the bag is your sum right and keep it there and look the second one if it's one take uh double your p and add inside the bag so you got three p in your bag and if the next one is zero just double it you get 4p but don't don't put inside your bag and the the the last one is one and double this 4p it's 8p and put inside your back so you will get 11p this is the uh the basic algorithm and is it's way cheaper to uh calculate like one by one uh you can use this double double is way cheaper so um uh you can just calculate any number like this um so this will give us something new and which is our scholar field um scholar field this scholar numbers in um in front of our P 1 2 3 4 5 these are new numbers right and we if they are prime number Prime Q we call this fq this will be your uh scolar field in this will be your scolar field and in some elliptic curves scolar field is bigger than base field in some it's smaller it depends changed um this is yeah this is another thing and most of the time for example your private case in uh private case are inside this scolar field which is a random point it's very big field as well and you you are just taking this number and multiply it with your generator generator is a u specific uh point on elliptic curve and everyone multiplies their private K with this generator and gets the result and it will be your public public right so this scholar field is where we keep our uh private case so yeah this is basically how we calculate this uh big public how people cannot find right this is because this multiplication this scolar multiplication is pretty hard to like discret logarithm is pretty hard because these numbers these numbers are very big like uh two 2 over 256 uh I Googled it I guess like um um estimated uh atom num like uh number of atoms inside our universe is like 10 to the 8 T something like this and I guess 2 over 256 is like 10 to 82 something like this so it's more than that you can just pick random atom inside the universe it will be your private number no one can find it so that's that hard um yeah let's um let's talk little bit about ZK proofs as well uh I will just show some properties of it um I guess most of you guys heard about uh zero knowledge proofs before and yeah it's a proof that you can um prove something without revealing any data uh to the verifier uh they will just say okay I believe you you like okay you you Prov that it's not believing but yeah you prove that uh you know the the result of this equation uh but they don't know your um vness values your secret values so this is what we call ZK proofs okay how do they work uh we have um we have to satisfy these three um properties to call proof zero knowledge proof um yeah it has to satisfy completeness which says that um if your input is valid you cannot like your result always will be will valid right you cannot create some invalid uh it's nonsense but you cannot create something false with correct values and the sness is the opposite of it which says that um it's theoretically impossible to return true with using wrong inputs I say theoretically because yeah you can do it but as I told you it's like very hard like that's why theoretically impossible but there's a still you know very low chance very low um so the zero knowledge part is why we call this proof zero knowledge uh which says that uh which states that verifier they don't learn anything about your secret values that means you have zero knowledge proof um yeah we have three different element three different elements uh in zero knowledge actually like all proofs um the the first one is our witness witness values are your secret values which you don't want to share with uh the the verifier uh you don't want them to know this this is are your uh this is your solution challenge is the challenge that in most of the proof uh schemes like uh verifier gives random you know challenge to the prover so it verifier says that okay this guy has uh the the correct witness values because they can solve my challenges and the response is the response that prover uh approver accepts this Challenge and gives back the the the solution to verify it which we call this response in snarks we don't have this challenge is the the challenge you is the is inside the provs calculations so they don't have to you know in uh intera interact with each other so they can just create them their challenges and they can calculate the response verifier will accept that that's why they don't have to you know talk each other and a verifier just takes the proof just calculates and says okay you are good to go they we don't have to interact so yeah this is what we call snark but yeah it's not the topic so yeah thanks for listening I hope it was good sorry yeah sliding a [Applause] lot uh anyone question I guess no one here I can do it by myself yeah let me bring the microphone [Music] okay thank you uh first thing you talk about groups okay and uh you mention then generator and you multiply your private key with generator points so I think that is important hint to mention cyc groups okay yeah okay can you explain this and of course you mention end and double algorithm and this algorithm is on not efficient and maybe you can explain how when we are using ZK provs use different algorithms MSM and so on in order to obtain efficiency of the pr thank you yeah um so I don't want to uh yeah I can talk let's uh let me explain the MSM part so uh yeah multis scholar multiplication uh is more efficient uh I didn't want to say that it's the best efficient one like it's better than the calculation you know like one by one like P plus P plus P like it's 3p instead of this you can use double and add algorithm which will give you some efficiency but it's not the efficient the the most efficient one uh you can use multiscalar multiplication um actually um yeah I coded that but I I I want I'm not remembering the details let me think um so yeah that's why that's why I am having some hard hard time but um you you have some table Yeah I have I have to look into it and I can explain it to you because like I'm not that prepared right now for it but I don't want to give some false information to people but yeah I have some I have some um uh coding I can show uh I did this before I guess onor uh he's also Turkish uh he he's inside PC as well he has a he has some good paper about this um MSM uh you can check out like batch multiplication as well these are good uh methods these are good algorithms that you can use in real life cases like I think these are the uh most efficient now I am not sure that's why I don't want to talk too much but they are better than this uh double and Ed algori uh also for cyclic groups uh I would like to you know um I can I can expl expl to I can explain to you uh one by like face to face because I don't want to give some F I am not a mathematician and if I say something wrong it will be bad I guess in this case uh as a developer you know um we use these papers mathematicians wrote this and we are just using them to code so um yeah yeah I was thank you thank you for the questions um yeah I will explain to you yeah oh okay then yeah you explain I code so we can we can do that um um but yeah any other questions I'm always happy to try to answer at least oh the what why I am doing this is that uh if someone wants to be I don't know ZK developer um this is this is what what happens right you don't have to know the all the mathematics part like uh you don't have to know all the details you can just um code these by asking mathematicians you can just open papers you can use them and you can code your stuff and it will work and you will say okay this is uh and you can do your own research of course like okay the B multiplication or MSM I don't know like double end that algorithm which one is like more efficient you can use your um like I don't know vssc to uh vssc to just see the results and you can just compare it I think this is why I I'm trying to do this uh if you want to be a ZK engineer you can just learn these uh fundamental parts and you can just uh go step by step and ask mathematicians so I will ask her and she will explain I guess uh we can talk it later yeah thank you [Applause]