ZK Hack Study Group – MoonMath Manual 2024 – Week 4 Part 1

Transcript

okay you guys can see the screen yes yes okay my talk is going to be fairly quick okay so I think about 25 minutes um so this week I did not follow the book okay I follow some uh uh articles on the internet also the rare skill cbook I found the the E part there is easier to understand okay um so let's start with the definition uh we have where stress curve right so the format

is the equation Y2 = X Cub + a x + B but you have to make sure the discriminant is non zero so all the points on this curve form a set and we we are working with the set full of points on on curve uh and each of the curve so the XY pair they follow the equation so this equation okay so this discriminant nonzero requirement is to ex exclude the the singular curve situation okay so uh if you have this uh zero discriminant

then is hard to Define like addition the the addition group law okay so we are excluding this zero determinant situation and the graph General like looks like this and also to make it a group we have to Define an identity element right so we Define the point at Infinity as capital O So this point is just imaginary it uh so it comes from nowhere uh we are just defining it for making this a group okay so we are making elliptic curve a group so that

our group Theory can apply to it and so how do we defined group flaw on EC is pretty intuitive we are just connecting two points for example we are doing P plus Q so we are just connecting p and Q with this St line it's going to have an intersection with the with a curve somewhere at R but um we can say p+ qals R because that's going to create some contradiction you can try that on your own okay so if you define p+ qal r then you have like a circular addition

like P plus qal r p+ Ral q and q+ Ral P there is some contradiction there so there is no way to define like group plw if you just work with this stre line we have to flip this uh R across the x axis okay so we are defining p+ Q equal negative R so this is just like a reflection over the axis of R so we are connecting two dots and intersect uh the curve with some other point and then flip it over the x axis okay so this is the the definition so this pretty

artificial it's not like a natural thing you find in in nature okay just like artificially we Define addition on you see like this okay so it's just like a definition we we just made it up somehow okay and yeah elements in the group is just points okay identity is the capital O which is a like an imaginary Point okay so P plus negative P equals capital O so this is yeah some uh something like zero but yeah it's like a

point okay so one thing uh that you should remember is with this addition definition uh this group is a is an a building group so how do you prove it the intuition is pretty easy so you can see from the graph that P plus Q equals Q + P yeah this is the geometric interpretation so they are generally just like a building you can see because P plus Q the intersection is r q plus P intersection is R again so they are the same

okay so there are a few special cases uh the first one is what if you have P equals to zero so this zero is it's just capital O I'm using this notation like randomly okay so so this zero is just a capital O the imaginary Point um so in this case it just identity so so like for some nonzero point R so r + P or r + Q in this case is just R so r + p = r this is identity so after you add P or add Q you don't really change the value

of the original Point okay so second special case is what if p is the inverse of Q so geometrically what I mean is they are just symmetric across the xaxis like this okay and in this special case if you do p plus K you get that imaginary Point O capital O somewhere I just visualize it as like some point way way up until here okay so you don't have to think like where this point is you just imaginary so this is uh just like the the identity element in in in addition

okay so p+ Q equals o uh the Third special case is really interesting this one is is really bad in some sense because we are saying um P plus Q we want to have an intersection r on the curve somewhere right but if you have P equals Q then [Music] you I mean like geometrically is pretty hard to think of but what I think of this is imagine you have like two points really really close to each other for

example p is here and Q is somewhere here for example and you have some like calculus thing right you just push this Q to P little by little right so until somewhere that P and Q somehow overlap then the line you draw is the tangent line yeah so for this one I think rigorously you have to prove it but I just don't want to do too much formal proof on this you know so uh the thing is there's a theorem saying if you have

this uh if you draw a line between p and Q in this case then you must have an intersection somewhere okay so if you don't so in this case if you draw a tangent line then you only have two intersections this one this one so in the other case you have three intersections so so there's a theorem saying the only possible cases are either two intersection or three intersection there's no other special cases anymore okay so so yeah if you want to prove it yeah just prove it on yourself I don't

want to do it and so I said this special case is very interesting why because we can Define scalar multiplication based on this case Okay so uh if P equals Q think of this as p+ Q equals p+ P equal 2 p so uh so this special case just leads to to the definition of scalar multiplication you know so like the code and code multiplication on on EC is just you do addition for for n times so basically n * P equals P plus P plus P

for n times okay and so some of you may ask like this is pretty hard to compute uh if you just want to Pro Force the the addition like you do everything here then it is going to be pretty pretty expensive but there's an efficient algorithm called double and add so that you can compute the scaler multiplication uh effectively so how it works for example um if we take Nal 151 so we are Computing 151 P so the the way uh how it works is like uh in DSA this

is called M mization right so you just break everything into two to the something power uh you can always do this because you can you can decompose a decimal into binaries right so so if you have uh like you just break it down into zero and ones and uh uh you can just say like this is 1 p 2 p+ 4 p + 16 p+ 128 P right so so in this process you are doubling it but in only one Tri uh like you only Traverse the the list once

so you are Computing this if this P exists in the formula then you do add otherwise you you just skip it for example in AP case we don't have AP here so we just skip it right so if you have it you double it and add the original value and and double and add double and add if the thing does not exist in the formula you just skip it okay so this is called double and add uh so the in theory we are reducing the time complex uh complexity into all whole login because we uh for each

double we are read like we are how to say that I mean for each double we are skipping like half of the possibilities right so so the total computation it takes is just all login so this is pretty fast okay this is double and add so what we did is defining addition and scalar multiplication on EC but remember that scalar multiplication is just a special case of addition so uh when I first learned e somehow I thought is a ring

because it has two operations that is wrong okay so e is a group I mean you see over R is a group and uh this scalar multiplication is just to make things easier so this is a special case of addition the only the only operator you you define in the definition is addition okay and we have those and uh yeah P comment here just remember this is Building Group therefore the group Theory we cover in previous weeks they also apply to to EC right so the big theorems everything as long as it works

for a buing group it works for E okay so learning group Theory only simplifies your learning you don't have to worry too much details about e just think of it as a Building Group okay do we have questions so far oh I see the comment in in the in the common area saying what does fields of characteristic mean that means you just add this uh for example P plus P plus P

equals capital O then the characteristic is three so it means like how many times you add to yourself you you get the identity that's a characteristic so if no oh wait if no question let's go to the next page EC over finite field so we just cover EC over R uh in a notation wise uh we can say you see over R is a collection of XY points in R2 right because both X X and Y are from

R they must follow this equation and they also have nonzero uh discriminant and un need capital O because capital O comes from nowhere this is artificially added into the into a definition okay so the graph looks like this uh why do we Define EC over a finite field because if we are working with r you can see uh for finding a point you have to try like a some value some random value for x and then you

take square root right so in the process you're creating probably you're creating decimal numbers so in general in crypto and ZK we we are only working with integers right is pretty hard to work with with a decimal value so we are we choose to Define this structure over finite field it turns out over a finite field uh the computation is a lot uh is much easier than than over R think of this uh so for a finite field we are limiting the addition we are limiting the result in a

finite set right so the maximum value we can get is p minus one so the computation is pretty efficient and also there's one interesting property over over a group with prime order is that any group with prime order is a cyclic group that is the one of the coral are of L rench right so so cly group is generally more interesting than a Building Group because we have many big theorum theorems on on cylic groups so you can see the the notation is pretty similar

it's just m p right so everything works M and others are just the same so after we put the M restriction on this group the result we get is no more a curve because uh now like like in the old over our scenario we have like continuous set of points right so in this uh case we just have this great points so for example uh this one is p equals 18 P equals 96 P just grows larger and you can see

thear larger p is the more points you have okay so you see over over a finite field is pretty hard to visualize because it just a set of points but for Simplicity you can you can also just imagine is over over fin field yeah you still think of this graph it's pretty easier easier to memorize okay but in reality you are just working a set of points like this yeah the the good thing is you see uh over R you see has some symmetry over the x- axis actually over finite field you have the

same property you see symmetry here this one this one this one this one you're not going to prove it but but yeah yeah you could you can play around it yeah see this like the the reflection line is like here so you have symmetry same same for this one but it's hard to see okay here I'm making a claim uh you see over finite field is a building group and even better is a cly group as recall that why is a cly group because we cover L range last time um

a c are of L range saying any any group with order P where p is a prime then it is cyclic and uh anything other than the other than the identity is a generator okay so so for for example we pick a like a random point on a litic curve over final field then it is the generator and we can generate all other uh points here in the form of NG so this n is like from from one to to P minus one from zero or no no no from one to to

P yeah like you can you can just Traverse the like every points on the curve by keep adding G to itself okay so in in reality we are using uh BN 128 we are using BN 128 uh this is a the name of the curve so sometimes is called BN 254 uh the difference is this naming convention means this curve has 128 bits of security and this naming convention means it has the prime P has a 250 uh 2 50 before bit so they they are just like

different name for the same curve so this curve has two 254 bit of prime p and uh um the security is 128 okay so here's a great article if you want to read more about this curve so this one is called like BN 254 for the rest of us okay so this is the article you can read it and the field modulus is this huge number so we are defining a curve that has the form Y2 = iq+ 3 a module of the field

modulus so this is a field modulus so everything the computation Happening Here the result is is always bounded by this number okay uh so field modulus is just it yeah is a prime P I just mentioned so the for uh if you have a curve with the form y sare = uh xqb plus b where B is a constant this is called a BN curve this is used by ethereum precompilers okay so so therefore it is the most practical thing you can you can work with and uh in fact I I constantly work with a the library PCC right this

library is written by ethereum Foundation I believe this is I the official python library for for the curve okay so uh the G1 here is pretty hard to explain right now because it works in bilinear pairing but you can think of this as some generator of the curve for now okay and you can add it like this add means G1 plus G1 G1 plus G1 is this uh huge number here and uh you can assert that uh G1 plus G1 equals 2 * G1 so here's a gotcha

here like you have to to put G1 before before two because it's pretty tempting to say multiply 2 comma G1 but yeah that's wrong and it took me some time to debug right so you had to put G1 first and comea two yeah this is just some implementation stuff in the in the library pretty stupid uh one thing to remember is that field modulus is not curved water so in my experience usually you want to work with curve order right because in ZK you are doing bilinear pairing for hiding the information right

so you are working with G1 G2 and g12 so when you do operation on the EC over final you had to worry about this curve order not field modulus yeah right I constantly use this one I never use field modul somehow okay so I have to remember that there are not the same concept so field modulus means we are doing uh integer operations m p and this field modulus is that P that P Prime okay in curve order means how many points on the on the EC so for example you have

um let's say you have an example say there are let's say 20 points on the curve okay so you are reaching 19 G where G is a generator then you plus G to it you got 20 G 20 G is just capital o is that yeah capital o is that imaginary point the identity okay so curve order means once you reach curve order you just wrap around one Circle and you go back to zero and then you do the do the

operations again okay um one interesting property here is you can actually encode rational numbers yeah this property is pretty interesting because think of a field by definition of a field everything other than zero has inverse so you can always find inverse to three so if you want to include rational number you can say oh so two uh 2 over three is um 2 * 3 inverse and 4 over 3 is 4 * 3 inverse and they always always exist

because this is a non-zero element in the in the field and by definition the inverse always exists and and how much is the the inverse don't have to worry you can do do it in a using the python function power power p w okay and so this means the base is three exponent is negative one and we do that in modular curve order okay so to encode 2 over three you can just say oh two plus uh two times power of three three inverse and then you had to mod

the curve order once again because in Python this um this multiplication is oblivious of your your curve order that you want to work with like this multiplication is over R right so you have to modul the curve order once again outside yeah this is pretty uh pretty sneaky bug you probably make if you don't put this mod curve order here okay so we can incode 2 over3 in this way uh we can incode four over

three in a similar way if you want to try to assert that uh 2 over3 * G1 plus 4 over3 * G1 you got 2 G1 this return true okay so in some S I just want to show that you can do rational number operation in like a encrypted setting because once we we multiply G1 somehow we are quote unquote encrypt this number because if I send you this

number you are not able to recover this number number right yeah this is the the EC DLP hardness assumption we are going to cover next okay so yeah just remember like somehow easy operation like like this you multiply something with G1 is kind of like encrypt the data but uh encryption I have to P put like double code around it because we are not really encrypting anything because encryption requires a secret key we are now using secret key here okay but yeah you got my idea like this is already pretty close

to the idea of zero knowledge pretty co uh pretty close but not quite okay question so far is an E Group over finite field always sickly yes uh the answer is yes actually I Tred to prove it but it's pretty hard to find like a literature like some easier proof for it you know uh I think is Cy uh it should be pretty involved to to prove this fact but you can just memorize it over yeah yeah I claim that EC over fin I field is always CLI so the property uh property is

pretty nice pretty nice okay and so let's continue oh wait I see another question asking is because the computer having issue with floating point or some more fundamental [Music] thing loading point you know I don't think the problem is a

computer I think the problem is ethereum actually you know uh because I know that uh you know there's a a bug class called like Precision loss right like compound empty Market bucks like 100 Finance hacks that type of stuff um ethereum is using fix point because it's easier to represent uh floating point I heard it it is pretty hard to do floating Point arithmetic in like a

blockchain setup because you have to reach consensus between different nodes and you want that uh computation to give you a deterministic result over different computer computers you know there's something wrong in the floting point computation uh in ethereum so the standard is using fix Point uh fix point is just like you record like how many decimals are there and you uh you record the number as as integer for example uh the integer I record is one 02 and I say decimal is one then the

actual number I represent is 100.2 that's just easier to work with so it's easier to reach a consensus over over the blockchain okay yeah we are we are way off from DK we are talking about some sneaky bugs yeah that thing is pretty deep you know the Precision loss uh let's continue uh oh this is pretty easy I think I almost finished with my talk uh we just said uh like we are using e to encrypt data okay so this is an

application of it recall that last time we covered uh traditional D Helman protocol in traditional D Helman and and we were using the DLP problem so DLP means I give you h g to the X not P for example this uh this value is what I distribute on the internet okay I just send out this I publish this information on my website and then if some malicious Eve comes here and got this information she want to recover my my secret X okay so my secret is the exponent and she

wants to to to recover that the RP says it is impossible to compute it okay uh so so that was the harness assumption for Dy Helman so right now we are working with easy Dy Helman so if see def Helman just we are replacing this harness like this difficult problem proper y uh with uh the uh the elliptic curve uh so how it works you just regenerate a secret key this is just some random integer okay so Random integer secret key for Alis Bob generates a random secret key for

himself still a random integer and then I I compute the public key uh oh forgot to mention that we had to agree on a generator G that Alice and Bob must agree okay this usually is publish in a standard or something like n standard okay uh we we have generator we generate a secret uh integer for for each person and then for each of them they just compute uh the random number times G so this was the scalar multiplication V just talk about okay so everything of course Works in a finite field so so they have to Define like a

common shared uh field modulus as well okay uh no I mean I mean curve order yeah like a share curve order uh so they exchange a public key and then in the end Alice has pkb Bob has PKA and what they do is they just multiply their secret ke he on the the the encrypted data they got from the internet okay just just multiply like this information what comes from Bob and this information PKA comes from Alice and then they just multiply this secret number to this info

and the correctness is uh pretty easy to verify that so the multiplication here here happens in a finite field and that field is multiplication is a builing we are just multiply for example like 3 * 5 this is five time three so so yeah it's pretty easy to see that in the end they comput a Shar secret okay so the the security here is um we are publishing this two public key on the internet what if uh ious actor Eve comes in and extract this info and

try to recover my secret key uh this is the Assumption of ecdlp because why is the Assumption because we don't have efficient algorithm to compute it for now but yeah I don't think there's a formal proof saying you cdlp is hard hard but uh right now the the assumption is without quantum computer is impossible to break for example you you you give me SK plus G for e is impossible to compute SK if Eve does not have have a quantum computer okay uh so yeah I'm yeah yeah I'm promoting my my own article again so so this is my

block uh if you are interested in like a small subgroup tag on on on the EC you can read it here yeah actually I found this bug in a live oh no not live is in audit you know like a web three protocol a pretty big name but I can't reveal the name I think yes yes under NDA or something can reveal the name but I found this book in a in a like Tic curve uh Library okay this small subgroup attacke pretty interesting question so far oh you guys are dis discussing this

nasty uh floating Point thing again oh my God uh let me read it oh finest no I mean this is pretty interesting topic you uh if you are a security researcher you have to focus on this fting poin thing you know like in ethereum is fix Point have to focus on it because like this year I noticed like quite a few attacks in the real world they just exploited this prision loss comining with some other properties you know like ERC 4626 inflation attack or compound empty Market attacks something

like that yeah they always involving some prision loss pretty important topic uh so in the end of my talk today this is the last page okay uh this is very interesting uh it's like a motivation motivational DK example that for example I want to prove a really easy problem I Prov claims that I know XY such that X Plus y = 15 okay this is just a to example uh so I have aover I have a verifier verifier wants to want the prover to prove it but uh without sending X and Y because we are

trying to achieve a zero knowledge property here so uh what we can do is we can compute XG and YG this just a scaler multiplication over finite field and send it to the verifier and verifier checks XG plus YG equals 15g so so as long as this equation holds we have x + y = 15 but verifier does not know uh the value of x or y because of the hardness Assumption of ecdlp okay yeah pretty interesting you see the zero knowledge property is easy to

achieve but the problem is efficiency okay so right now we don't we don't like walk through like the real world DK protocols for now okay we're going to cover them next so for now we are getting this intuition yeah so why are we studying elliptic curve because elliptic curve is connected to the zero knowledge property but the problem is efficiency okay so yeah just remember that if you want to achieve like if you just just want to achieve zero knowledge but not ex synct yeah you can just use bilinear pairing I think

okay so another example pretty interesting is we can incode rational number we just talk about that okay so prover claims that he knows X such that 23 * X = 161 verifier says okay prove it but don't give me X because we want to make it zero knowledge okay um Pro just compute the inverse of 23 yes is always exists because we are doing in the finite field um Pro compute so this number so in Python is 161 time p uh 23 comma negative one comma curve order okay this uh he sends this um this

encrypted code uncode encrypted data to verifier verifier just multiply 23 on the left if the final result goes to 161g we can confirm that this data is correct without knowing the actual value of x okay pretty insightful but not realistic this is a basic basic ZK example okay so for further study I recommend you to check out the source code here also play with yeah pyc see pretty interesting this is the official Library implemented by by etherum Foundation

okay okay that is my talk that is my talk you are welcome I'm GNA stop sharing at the end I fix your your your screen sharing stuff yes that was the perfect time for me to fix it oh nice well great talk yeah I I think it was also good actually yeah I think it was good we switched it up because um I picked like some examples where we can actually like compute things and you gave like a very nice introduction to um tic curves so um maybe there's still questions for your talk but if you want

I can show the exercises I have with me um yeah yeah yes please go ahead sure so let's see technical difficulties aside okay I hope you guys see my screen great