ZK Hack Study Group – MoonMath Manual 2024 – Week 5 Part 2

Transcript

okay yeah you guys can see it yes okay nice nice uh so let me speed run through this uh let's go back to chapter five okay uh the reference okay reference is uh these two articles basic uh basically I just work through the first one the second one is a intimidating uh I I can't do it right now requires too much math so I can come back later you can see I have this work in progress label here yeah let's go over some uh facts about bs curve uh so this curve was designed to be a pairing friendly curve okay so uh

of course we can have like many many other the curves but to be pairing friendly you have to like specifically uh construct for it okay so this curve is like artificially constructed curve just to do pairing okay so um so why do we want it to be pairing apping friendly because uh in the last step of gr 16 you have this verifier step uh you have to compute pairing four times and then just like check the equality so yeah we want to minimize uh this step so so we had to use a pairing friendly curve uh so the naming of this curve

um bs1 12- 381 so 12 means uh the embedding degree is 12 we're going to talk about what is embedding degree later uh 381 means the the number of bits like the size of the FI modulus Q is 38 uh 381 okay so some basic facts about this curve um y^2 = X CU + 4 I recall that usually we work with BN uh 128 curve that curve is like plus three so this one is plus four like solo difference um so in the in the standard of the

curve you have uh you just have this capital x this is a constant that defined in the standard uh know that this X is not that X in the equation so they are different okay so this capital x so it is just like a constant defined by some trusted third party you know uh So based on this capital x you can compute for the the field modulus Q uh so this fi modulus it's not like coming from nowhere okay so uh so this one is like derived also the subgroup size R is derived so this R uh what I

mean by subgroup is uh think about that G1 G2 in in the pycc library okay so both G1 and G2 are subgroup and both of them having a size of R so this value is also derived from from a predefined constant okay uh so a pretty confusing topic is a field extension um so the 12 in in this name the 12 in this name means the degree of field extension so uh for fq the finite field fq we can only Define G1 group from here

so there's no way to define G2 group therefore we have to to do a uh Fi Fi extension until we reach this fq2 okay so this is still confusing notation but don't worry we we going to cover it slowly um so for constructing yeah let's just uh stop worrying about this q12 let's say uh how do we construct fq2 from fq okay so this is a simpler uh simpler example we can do some basic algebra right so say finite field of

modulus Q it is like Z qz right so you have a Q elements from Zer to Q minus one and then we Define fq2 in this way so we Define uh as a polinomial degree one polinomial where all the coefficients a z and A1 are from from uh the field fq okay so equivalently you know that uh so for a polinomial you always have that one x x squ x Cube that series okay so so that part is predefined so we can just simplify this polinomial into a coordinate uh coordinate representation

right so a z A1 it always refers to a z Plus a1x these These are equivalent definitions so for constructing a field we have to Define two operations cuz yeah recall that I feel is just a a communative ring where all nonzero elements have inverse okay so since ring have two B binar operations we have to define the same for a field and then uh for for addition this is pretty easy so you just do ab plus CD you can do some basic algebra like like convert

this to uh back to the polinomial representation and then do some basic algebra here okay this is pretty easy but for the multiplication case uh it it is subtle because we have something like BD x² that we cannot handle because in the definition we did not Define like what is X squ therefore we have to convert this x squ uh to some number right so for this case the rule is we Define x² + 1 = Z so this is the thing like we are extending the field R based on this rule so we are adding a

new rule because this uh like x² + 1 does not exist in R right so this one is a new rule that we added into here so we can substitute x square with negative one so it is pretty easy to see that um it is pretty easy to see that uh we can just substitute negative one here so this term becomes uh minus BD and you can do some algebra and Define this multiplication yeah so this is well defined now um what we did is extending R to

C maybe you can see that this thing is just the I the Val know I okay so I Square equal netive 1 so we are adding this rule into a some some original field and then we are extending the field because we are adding a new rule into it so that's the idea of field extens okay yeah yeah that uh that's a pretty simplified example by I found a quite easy to understand yes so I put it here uh General criteria for the rule for this rule okay so our case the degree

[Music] was degree k polom I'm a little confused here I think it's K minus one but but you get the idea okay so so the rule oh no no no oh this is correct so extension degree right now is two so we are adding a degree two polinomial here okay yeah yeah that makes sense so in our case R2 C extension degre is two then the rule is degree to pols yes and the rule must be irreducible so x² + 1 is irreducible in

R because we cannot further Factor this polinomial into like X plus something times x minus something but we can do that in C right so we can uh Factor this as x + I * x - i = z okay so that makes sense yeah that's a uh criteria for the rule and this is a fact that uh C is like the ultimate form for this type of extension because you cannot further extend it because there is no more irreducible polinomial in

C that is saying uh you cannot just like find something like that like x² plus some constant equal zero all the thing with that form will be reducible because of fundamental theorem of algebra okay like a variation of that theorem so you can always Factor things over C so there's no way to extend it what I'm saying here uh contrast [Music]

and Bri irreducible polinomial yeah I'm uh I probably made mistake here I think this is fqk or something right we can extend fq to fqk I think I miss something here yeah yeah I fix later so um in a general case we can find the irreducible in finite field and then extend that the base field to fqk right so the form is this long polinomial so the basic idea is the same as the the C case but this one is more more General and it is pretty hard to

say like this irreducible nomial I can find but yeah I'm just saying it is possible to do that and for our case we only care about F q12 yeah because we need to construct a G2 group uh G2 subgroup from it okay uh so in BLS 12 381 there are two curves so don't yeah don't as like assume this one is the only curve because uh from this curve we can only construct uh G1 we actually need another group to construct uh G2 okay uh so we were saying this one

should be fq2 but why is fq2 here because we can use that twist like sextic twist like I don't understand how it works but yeah so with that Technique we can transfer uh fq 12 to fq2 so the computation will be easier as you can imagine okay so word about uh the curve order so there's a theorem pretty famous theorem called hassis LMA oh no I mean has this theorem uh say capital N is the number on curve or a finite field of modulus q

and then you have this bound so the absolute value of this expression is bounded by 2 * square root Q you can just uh expand this to solve for n and then eventually you will see n is bounded by Q + 1 minus some square root and Q + 1 plus some square root so when Q is large you can see one is like useless so so we can ignore that right so when Q gets large square root Q is Rel atively small so we can just assume this uh n which is the the curve order is bounded by some some some margin of Q

right so so n will be like similar to q but um uh there will be a difference so the curve order and field modulus generally they are not the same but they are pretty close yeah so for for like further study you can watch this video pretty nice I watched the first half of it yeah pretty nice introduction um so the conclusion here is the curve order of the the first curve or I should say e Prime here okay e Prime uh the curve order of e fq is kind of like close to q and E Prime fq2 is uh close to Q

Square okay so that's for the curve order you can see um the first curve is much smaller than the second one so uh now we are constructing G1 and G2 they are the subgroups of the curves uh recall that in bilinear pairing we need uh G1 G2 group they map to a like we do pairing parentheses G1 comma G2 we map that thing to a point on the target group in general this should be like g12 G2 group here okay so G1 and G2 they must have the same order R we

call that R is a derived value from a constant capital x we just mentioned about okay so this value is is derived and it is a prime so it is always a prime and G1 G2 must have the same order but there is something you should worry about is if you only have e of fq there is no way to generate G2 so the only thing you can do here is generating G1 because uh efq it only has one large subgroup of order and so that's the only thing okay you just grab that thing and call it G1

and we are done here but we need something else to to Define G2 okay so we have to extend the efq to efq K do the field extension we just talk about uh just now okay so why we want to do that because in E of fq K there is a there are many subgroups of of order R and we are going to pick a special one from me so the special one has a property saying is a trace equal zero this one I don't I don't quite understand yet it's pretty involved math so I going to come back but for now you

just think about we uh we already construct G1 and from there we use that curve and we extend it to a higher curve right and then we find all the subgroups in it with order R and there is one special point that special point is a special subgroup the property the special property of it is Tre is equal zero why is that I don't know but this is G2 okay so so this is how G2 was constructed and so the K in E fqk is called embedding

degree uh you're going to see this work a lot in in literature okay so uh uh you can prove that e of uh fq2 is good enough to Define G2 so this is like the the bare Minima for defining G2 so we stop it here okay uh a fact is G1 G2 they share the same same identity element the point at the point at Infinity o okay so at this stage we construct G1 and we use some uh some cryptic math and uh constructed G2 we're going to come back to this math I don't I can't handle

it right now so uh we have G1 and G2 now we can do pairing uh yeah yeah we come to the to the most difficult part uh this one I think I got the idea but this one is still work in progress okay so um the idea is if yeah we were extending uh e of Q uh e of fq to fq2 but uh you can imagine the computation here is pretty complicated okay so uh for example if we want to use this in in production we have to

minimize that because we going to wrap that G2 into pairing again so so that is Computing G2 is already complicated and then you wrap it in the pairing just make things more complicated okay so we have to uh simplify this part so how it's done it's called like sextic twist something like that you can Google that it's pretty um I don't think I understand the math behind it okay so so this twist the main idea is just it can convert somehow can convert this large finite field into a simpler one somehow

and the like you can find a new sub group that is isomorphic to G2 so you can do all computation in the new subgroup instead of uh like doing over over this monster okay that's the idea how it works I don't know I'm GNA figure this all later yeah this uh this is the idea so I this at this stage we have G1 we have G2 from the new tic C the like the the one out like the one after reduction so we have a G1 a new G2 uh

the new expression of this curve is just times 1 + I on this constant term yeah like you uh you have to figure out this part in order to derive this equation but since I didn't figure out this part yeah you can just accept it as a fact for now like this one this one okay uh in G1 group a point is a pair of integers this is pretty easy to understand so this is just like a an elliptic curve on 2D surface uh you just graph it and you have a x coordinate and y coordinate name okay uh for G2 it is more complicated why because you can see we

introduce I here therefore the the coordinates become a complex number remember that for each complex number we have a real part and imaginary part so to represent G2 we have to use four coordinates so this one is the yeah just think about this one this one is like integer integer but this one is like a plus b i and C plus d i so they are so the x coordinate is a complex number and y coordinate is also a complex number which makes the thing like represented by four numbers but G1

is just two yeah this one was pretty hard to under uh to understand I think I can of understand the the ideas now but you know the math behind is still complicated so that that explains why G1 has two coordinates but G2 has four coordinates yeah because it represents complex numbers yeah yeah that's the short answer okay uh so for pairing so for pairing we still trade it as blackbox because I need to figure out math behind uh to do pairing for now we still use as uh as a

black box okay so we denote pairing as e um the domain is G1 cross G2 this is a direct product of um of uh the two points so for example like P we pick P from G1 and Q from G2 so p is a G1 Point Q is a G2 point you can say Oh e parenthesis PQ this is a pairing of the those two point so just remember when you do pairing one of the component must be um G uh G1 point and the other must be G2 Point yeah that's everything you need to know for

now so usually we call this pairing bilinear pairing so why is that because has some nice property so it is linear on both sides that's why it's called bilinear so for example if we have linearity on on the right this Q Plus R you can you can just say oh we can do pairing first and then the second pairing and then multiply them yeah same for for the for the first component okay so it's called bilinear because we have two linear properties here um a fun fact here is if you combine one

and two you can derive for uh an interesting fact so in general the proof the proof looks like this so so you you say uh bracket a times P so what is this this is just scal multiplication so it is like P plus P plus P for a times okay so this one same Q Q Plus Q Plus Q for for B times okay so first you can Factor this this this a you can take this out as a the exponent uh because we are applying like this number two property for eight times yeah so we got this okay so similarly we can Factor this B out and take it to the to the

exponent by using property one for B times okay and then uh the funny thing here is you see you can you can just take this a down to the other component here so a was on the left now it is on the right yeah this is pretty interesting and you can bring this B back to the other so pairing of AP BQ is the same as BP AQ so pretty interesting property here okay so uh the inside here is so why we do Define pairing because recall that over a tical over finite

field we only have one operation which is addition so the scalar multiplication is just a variation of that okay so pairing basically acts as the multiplication of a G1 point and G2 point but you cannot say that like rigorously okay so this is just like a easier way to understand but u in math this is of course wrong because because like they are not they are not even in the same Dimension so so so you cannot multiply quote and quote multiply that and another word about the embedding degree so yeah this one I think I'm

still a little bit confused on on why is that but uh there is an algorithm to compute K so so this ining degree K is just the smallest integer so this smallest is very interesting property because yeah so look at this so so you must satisfy rid Q to the K minus one but it has to be the smallest integer so so how do we do that yeah we can just use a for Loop start with k0 and then just increment it okay just compute because we already know R and then we can yeah of course we we already know Q so we can just say oh

Q to the zero Q to the one Q through two and then blah blah blah um iterate through all the possibilities and then you can find oh the smallest integer in our case for given R and Q the smallest uh the smallest integer is 12 that's the ining degree of BRS curve also it is the embeding degree of bn1 128 Cur same thing okay um that was pretty much the theory behind this so we going to talk about one application about BLS so I chose BLS signature this is very fun because I didn't know that BLS curve and BLS

signature they represent different people names you know so the L is the same person but B I think this B is then F and uh the b and s in the BRS curve I don't remember their names but B and S like they are different so this is a uh different B different s by the same L yeah pretty interesting fact um BLS signature is a uh still like a typical digital signature algorithm okay so you're gonna talk about it so first uh thing is the key generation part how it

works first you pick a random a random number between one and R1 so this is wrong ah this is the the unit group of zma RG the uni group I should put a star here a star here okay so there's no zero so so it's the unit group ofr Rd uh you generate a random number keep be secret this is your private key how to compute the public key you just multiply secret key I mean scalar multiply okay by G1 where G1 is a generator of the G1 subgroup for this one I think every nonidentity element in G1

should be a generator why because that corollary of L range theorem I think so because it says if G1 has Prime order then every element other than the I other than the identity which is a capital O point point at Infinity so anything other than that should be a generator okay so you scalar multiply your secr key onto the G1 point so this one is the exactly the same as the cdsa which is used in ethereum uh this one is pretty

common uh so why I label is G1 Point here because I want you guys to know it's pretty easy to mess up yeah so so everything we work with they are either a integer over finite field or a G1 point or a G2 point we don't work with anything else so it's better to just like label everything and then you actually code it in in Python for example yeah you can just put this G1 into the variable name so you can distinguish everything yeah yeah this is like just my experience um public key is pretty safe we can publish over internet internet is

an example of uh dangerous untrusted Channel okay so so we can probably it publicly why because it is protected by ecdlp we talked about this last time so ecdlp the discre logorithm problem on on the curve uh given SK * G1 is almost impossible to to compute this SK okay that's a e DLP we have private key and public key record in digital signature we sign a message with a private key and we let other people verify our message by no I mean verify our signature using

the public because that's the only thing they got this private key is your secret yeah so in the sending phase first we have to map a message M so this is our secret message we have to Hash it to a point on G2 so how is that hashtag um first you hash it um very likely you should choose something like DK friendly hash okay there are few choices and then you choose one of the hash function you compute it to an integer modle Q so Z qz or fq okay uh you map it to some large

integer and then you just use that as the x coordinate and you set y coordinate to zero Maybe I think yeah you use that point and check uh if that point is actually on curve if not you just yeah you have to increment that message plus one and try again and yeah just Loop it iterate all the possibility until you have something on the curve then you can say oh I have a point on G2 so I can just multiply G2 and get this Capital HF so this is the the hash so when you send the message you are not directly sending a message and because

remember we either work with G1 point or G2 point at this moment so we have to multiply HF which is a G2 point and then when you multiply G2 point with a scaler is still on G2 so this is still a G2 Point okay we call that public key G1 Point signature G2 Point sounds very good we have some uh some to work for pairing okay so in the verification phase um uh we have message H even message I think this is wrong as well I think this is hm because uh the

message is a secret how can it be given right I GNA take a look at this later I think it's wrong it should be hm something like that okay so so some representation of uh of M and then a signature Sigma public key uh the verifier has all the information and then uh the verifier verifies if the secret key is corresponding to the to the public okay so how it's done it is done by pairing we can just do pairing once first no I mean I mean we do the comparison ones we have to compute two

pairings first one is G1 and sigma the second one is public key and hm so after we compute these two pairings we can we compare the equality if it's equal then the signature is valid it is coming from this user okay so um yeah this yeah it is just pairing in pycc library in this brs2 uh underscore 381 Library okay so how do we know if the the thing is correct uh we can just derive the formula a bit using the the bilinear property okay so um start with PK

hm we have the expression for for PK PK equals secret key times G1 so remember this is a public key also this is a G1 point and hm weall that hm equals to yeah we just hash it and then incremented and then times G2 yeah multiply that by G2 so this is a G2 point so we have G1 Point G2 point we can do pairing on that well defined okay so uh recall that we can use a property like multi uh like by many many times times and then get this we can Factor

this SK to the to the exponent and then we can just drop this SK back to the other position yeah see that this is pretty funny but you have to this do this in two steps because if you got like from here to here then you Skip One Step Right but but here you actually you apply the the first property and then you apply the second property so so I have to write this step out okay so prop property one and then property two you see the effect is we change the position of SK and this SK * H1 we call

that this is just the sigma the digital signature so this is a g uh G2 Point G1 is is obviously G1 Point okay so this one equals to e to of G1 C Sigma G1 Point G2 Point well defined parent so this is the correctness proof so what's so good about this uh this uh signature scheme this pairing based signature it is because has a aggregation property so what does it mean so verifying a single F so a single message M signed by in parties it requires only two

pairings so recall that uh you probably thought like between two people we have to do two pairings already right so so between like n people there should be two n pairings but no because it has aggregation property uh we only need two pairings if un part is like many many people send the same message or if they are in parties sending a different un messages you only need n plus one pairing I think this one is a little B more complicated to prove so I have a example for the for the first property

okay uh so here's a proof so consider Sigma digital sign digital signature Sigma aggregated equals Sigma 1 plus Sigma 2 plus plus plus Sigma n okay so this is a G2 point public key we can also aggregate it just take the sum of all the all the public keys and then you get a G1 point and you can prove this fact so this is U the pairing of G1 comma uh Sigma aggregated this one is equal to public key aggregated comma hm so yeah you can just substitute this long expression

here and then prove this property so this is called the the aggregation property of the B signature scheme and uh you can see basically we have end parties and the and signatures and public keys but in the end we only do pairing once so this is pretty efficient okay that's all the all the info for today so for the readings uh we we mentioned this already so pairing for beginners this is very nice book like around probably 150 Pages yeah uh a little bit long but uh uh very approachable uh you can read this in V I

think PR nice uh details the math math details be behind pairings also I need to go back to this article I think it's a little bit hard for me right now I G to go back to this article okay okay so that's the all the info for today any questions wow oh that was a lot that was a lot info for me for my tiny brain it was a lot of info let me see the question so wow

there are so many question yeah yeah I didn't read your your question question because I have a that issue because I was sharing the whole screen yes yes uh please ask uh I think the the website has some issues when we are sharing uh but my question is if we choose like say smaller R uh could we just simply keep that uh we don't need to do the extension of the field we can still use original field to have two okay okay that okay so so first you are not able to

choose a small R because R is we need to do the extension for the field because uh uh we only have one subgroup that is larger enough uh with degree R uh I I think uh uh first you know R is derived from a given parameter uh Capital like the capital x right so sorry I can't hear I cannot hear anything that's weird hear okay okay I said uh uh first you know that R is derived from the capital

x which is a given parameter right so why is that X so large because security issues right uh like in the standard they chose these act must come from like many many concerns that have worked out in uh like like in the past uh there will be security issues if you choose like small parameters I'm pretty sure uh that's the reason but if you ask me like what attack can I do I don't know right now yeah I can of I going to come back to this part later uh I think it deserves more more research obviously

uh okay guys I going to go because I have 20 more minutes before my open zapping interview if you have more question please just ask me in Discord I think I going to clear my room a little bit okay thank you good luck your interior uh thank you thank you uh okay I will see you guys next week I will be here for sure okay next week we can we can actually go to some uh somek problem so I'm I'm pretty done with the the theory