ZK Hack Study Group – MoonMath Manual 2024 – Week 9

Transcript

okay I'm going to start now um so uh still the reference is uh CK book by Rare skills and um today is the last meeting right so everything we work until now should make perfect sense and they are very close to to the final version of the of the protocol right but we call that like last time we had a balanced qap formula and we had a verifier step saying pairing of A1 and B2 equals pairing

of uh pairing of C1 and G2 right so there is a problem there so basically there are three types of three types of of attacks right so the attacker can come up with some problem like some uh some attacking scenarios so our scheme is not perfect so this week we are going to introduce um Alpha Beta Gamma Delta and RNs so Alpha and beta belong to a group and Gamma and Delta belong to a group and also RNs is another group so three sets of them they Sol three problems okay so

our strategy is first we consider what if I just don't use Alpha and beta and we ask that question is that okay right so we are going to show that it's not okay because attacker can do some attack on this so let's go through my notes and a first question okay so what if we just stop what we had uh last and we don't introduce often beta so this is the verifier step right so the problem here is verifier only accept three points on the eliptic curve and he

cannot validate if they are computed correctly right so the problem is what if a an attacker just come up with uh some random A and C which oh man this is C C1 C1 so what if the attacker just come up with some random random scaler and satisfy this equation right so the the verifier has no way to know and for a simple example so attacker can come come out with the 3 G1 5 G2 and also so 15 G1 so so he can just come up

with the number without doing any computation right so this this formula just holds because you can see that in Python if you compute this the pairing of uh of term two term one also term four and term three the result is true okay so so this is just a simple example so the the idea is say this is a b and c and the attacker just need to come up with some uh some number that has a property such that a * Bal C so so easy at that so how to deal with this attack uh we are going

to introduce Alpha and beta right so Alpha and beta are random shifts so Alpha and beta they are two random numbers and the the result is you need to let the trust this setup compute this alpha one so this is a G1 point so this is equivalent to Alpha time G1 this is equivalent to Beta time G2 right so you have to let the trust this setup uh compute this um these two two encrypted uh points and then you do a random shift on that so the computation is very simple because this is easy addition right you you just

have to like take the sum of the two scalers here okay so you do the same for B and this is a random shift on the scalar of old a and old B okay so this is easy as that so two random numbers but you don't uh you can't leak the value of Alpha Beta have to incude them into some um some G1 G2 Point okay uh question so far I think this is very clear right um hold on I see a message let me open this

uh okay so so I'm not going to discuss last week's question here because it's just some some tedious algebra really okay so so it wasn't very impressive so I remember like the the problem from last week was like the degree of of powers of tow for H Tow and T tow is one less than than that of A and B so it was pretty boring actually yeah just some TDS algebra so so so yeah I can I can show you how it works later okay uh don't worry about

that yeah there are just some like implementation details is not very important okay so yeah just try to grab the the main idea um yeah so so we come up with the strategy and we claim that this protection can protect from the forgery attack we just mentioned so how we need to prove that right uh the main idea is now you have to know Alpha and beta in order to 4J proof uh and the security of alpha G1 beta G2 is protected by

ecdp so uh prover only sees G1 G2 point and he cannot extract the data so he cannot extract the the scaler right so this is protected um but we need to show an an example that this forgery won't work and there are three attacks okay so in ZK book I think this this part was written pretty like confusing right I'm pretty pretty long so I come up with a simpler like very simple example okay so just say we want to

balance this uh paing equation right so right now we have ab and C also we have to do a pairing of Alpha and beta so why we have to do an additional term uh I going to show the math later here okay so don't worry about this and our objective now is to find a b c such that a * Bal C plus Alpha Time beta okay so so this is a pro strategy if he wants to fake uh Forge a fake proof okay so if this holds then

this paing checks cool so right now we introduce Alpha and beta so a a prime this is old a okay so a prime plus Alpha and B prime plus beta and we just subtit substitute this these uh identities into the equation and uh we can see here Alpha Time beta just got cancelled out okay so we only left with u so this term so a prime B Prime and this term C and also we have two very hard to compute terms which is a prime * beta Alpha * B Prime so we

only we can only know a prime and B Prime but we have no way to extract the information of Alpha and beta so these two terms are not able to compute by the by the prover okay so uh so in zik book uh basically I simplify three attacks basically they mean I'm an attacker so I'm aover I can come up with a a prime B Prime and I try to Compu C I can see here C equals a prime time B Prime but plus these two terms and I have no way to figure this out okay so second attack I I can do uh do that in the revers direction so I

come up is a c I try to factor C and try to get this a prime B Prime but I going to fail too because I don't know this beta Alpha I have no way to balance out this equation okay so uh the third attack this is different from the first attack okay so so this time I come up with A and B therefore so I come up with a and b here okay so I try to compute C the formula I'm going to use is a * b = c plus Alpha Beta so if I want to compute C I just do a * B minus Alpha Time beta but I don't

have information on this product either therefore uh my conclusion is if you want to protect from these three attacks you you cannot leak Alpha you cannot leak beta also you have to protect against this Alpha times beta product so this product uh is uh should be a secret value as well okay so that's the main idea okay so do we have questions so far no question okay then continue uh so this part is a continuation of the discussion here like

why do we have another cell of pairing on the right hand side right so why is that let's go to the step uh go to the step before pairing okay so we are not going to work on the pairing equation because this is very hard to compute we going go back to the the qap equation so the first line here this is the old qap you should be very familiar this by now and and we are going to continue from the second line because now we introduce Alpha Beta which is random shift like we Define that here right so we just write out a like old a and o b in this inner

product notation and we do a random shift by Alpha random shift by Beta And you multiply them together we try to get uh try to compute what is the new right hand side right so this is just simple algebra right so you just break down like do the multiplication here this and this multiply this and multiply this plus multiply those two okay so in the last term we here we see that we can use the old qap equation to substitute this with the right hand side here okay so recall that this should be

an identity because without Alpha and beta this is true this is always truec uh because yeah we prove this like two weeks ago okay so this should be true this should be always true and we can substitute this as an identity into the new equations here and therefore the new equations becomes like this right hand side okay we're going to put this right hand side here we going to delete like delete this part okay so after that now we see we can actually combine these three terms in the middle so in

the ZK book uh I found an error right so so this image was copied from book and I think Jeffrey made a mistake here uh I I told him yesterday okay so this step we should be doing a combine here because why be first because the summation index they all start from zero and M right and recall that these are just some inner products so they are some pols okay and they also have a common term AI here therefore you can Factor this AI out and we call that AI is just a an entry in the in the vness vector

okay uh so we take AI out we combine this summation and we reach the final equation okay so you can see this Alpha Time beta get Factor out so so Alpha Beta here and we combine rest of the term and then plus HX TX okay so after the combination uh well I shouldn't call it combination whatever so so after the code and code combin step we have this inner product the new inner product but we Factor AI out and like this inside the parenthesis we are going to create a new the set up for that okay so this so so this computation this part

should be should be like oblivious to to the the prover and he only knows this AI okay and AAL C plus Alpha Beta And if you do that in in G1 G2 equation you you are going to reach to to this step okay so A1 you just compute this term and wrap it in a G1 point and then because this is just a easy addition you can just break down this into two G1 points and then you can factor out this this AI term because it's just a scaler okay so so the like this this part and this part

so everything I have this uh red underline here means prover is now going to uh do that on his own because he doesn't know this to therefore he relies on some information provided by trusty s which is the powers of to but uh so right now the powers powers of tow we just need some new new sets of power therefore trusty setup is going to compute like like all the things here because prover does not know to okay okay and also this therefore we need like um four more trust the

setup here I think like or five or yeah just whatever so so so the setup is going to do more pre-processing okay to satisfy this computation but in the end uh prover just computes the same proof okay so so proof is just A1 B2 and C one and send this to the verifier and we just show that uh this is true from the qap equation okay so the new so new verifier step has an has an additional term pairing of a alpha 1 beta 2 because we just did the new qap equation and it has

an additional Alpha Beta term okay so this is the story for for Alpha and beta do we have question no question no question okay so the takeaway uh the takeaway is Alpha Beta is a protection mechanism to protect from forgery right so so I think the essence of this part is just oh I come up is a attacking Str uh strategy and I I come up with Alpha and beta random shift to protect from all

three attacks okay that's the reason why uh gr uh 16 had this uh this Alpha and beta parameters and let's continue to gamma and Delta so what's the motivation behind this right so this uh the motivation is we want to separate public input and private input so a good example in circum for example is for example a circum template I want to I want the prover to give me two inputs as the factor of an integer okay so so this is the integer factorization

problem I can set the product of those two factors as a public input therefore or I can reuse the circuit right so so for example I I can ask you what are the factors of four and next time I can ask you what are the factors of eight so by setting the product as a public input I can just keep reusing this circuit I don't need to write a like a separate circuit for for for each iteration right so so in practice we want some uh public input uh also we have some private input so in our case there is no uh like

explicitly say there are any public uh public input because one and out they should be always public right in in like Common Sense uh because this one is just a constant term and this out like output like why why would you hide the output right so so usually yeah just the inputs are are private and in uh this is the inner product representation of C C1 no I mean c in the qap formula right so so usually we say Okay so the first L terms so from index zero to L so in this

uh for example in this case we have one out as public then we can say Okay L equals one so index zero and one they are public and index starting from two to the end they are private okay so this is how we separate the PIV uh the public and private input and uh there is a problem here oh you can see uh the verifier steps uh gets updated okay so right now you have to compute another term okay okay

so so notice that uh this is the first part of the C right so this is the public part okay so so right now C1 is the oh man this is C1 C1 okay so we separate the public part and private part and the approver only computes A1 B2 and C1 and therefore like this long thing here is not coming from theover is um verifier public knowledge

okay so the design is like this but there is a uh there is a problem here because you know public inputs they are public therefore in the design we don't want the approver to use the public inputs right because we assume that only the verifier knows no no no I I mean only the verifier uses public inputs in in actual computation we want the the approver only follows the guidance of the trusty setup okay so the problem here is since public inputs are public prover

can use public inputs to to generate some proof but this is just a theoretical attack I don't have an example here because it is very hard to generate a proof just by using public inputs as the additional knowledge okay so so this is like gamma and beta protection is only protecting a theoretical attack which has uh maybe maybe very low impact okay but it's better to be safe so this is like another layer of security okay so the idea here is just gamma and

Delta they are protections against prover using public inputs for generating a fake proof which is a theoretical attack okay so question so far no question good um so we are going to introduce Gamma Delta so how they are used they are used as some uh some division parameters here right so why is division we're going to see that later so so so recall that in finite field division is just multiplication by is inverse so so this is doable

okay yeah I think this is very clear since we talk about this like like this long formula it is the coefficient of each term in the in the polinomial okay and when we evaluate the polinomial at to this becomes the powers of T right so yeah maybe I should say this is the EV eval evaluation of like one here is one comma X x² yes so we start from the constant term right so this will be like T like one t

t Square t Cube and blah blah blah okay and and this value is the same as in the last step but right now the the new thing is that we divide this this value by by what is this uh gamma okay okay so very similarly oh yeah this is for public input so the index start from zero to L okay so for private input very similar formula but this is divide by Delta okay so basically we take C out and

break down into two parts and for the public parts we do divide by gamma and for the private part we do that by divide by by Delta okay so uh recall that you have another like a trailing term here it is HT T to we want to combine that with the private uh the private input so it also divid by Delta so you can take the sum of those okay and so right now uh since we have introduced two parameters we have to let

the trust set up published um gamma as a G2 point and Delta as a G2 Point okay so how that works basically we are going to change the verifier step so in the last two pairings here we are going to use gamma as G2 and Delta as G2 as a parameter here so if the prover follow the guidance of trust setup he c will have a division by

c yeah that c will have a division by Delta term like for every single term therefore when I do pairing they all canceled out okay so the idea here is just my objective is to stop the approver from using public inputs and therefore I introdu these two parameters I'm am going to divide it for for like every single term in the polinomial and also I'm going to multiply this term in the final pairing step and therefore if you follow my if you follow my guidance your terms should

be having this like Delta inverse in every single term and therefore they cancel out perfectly okay so if you try to use public input directly you are not going to come out these numbers to cancel my terms because uh gamma and Delta are secret and they are protected by uslp again okay so this is is the the production from from the approver using using public inputs for Generate Improvement okay so this is gamma do question so far no question wow you guys are smart yeah we are doing pretty quick

today so we finished like 66.6% already okay so the last part is an is another set of parameters called RMS so so right now our scheme is pretty is actually pretty secure already be uh but there is another attack which is the boo Force attack so how this how is that possible for example you consider a like a voting game okay so you

[Music] are voting for example like like like some president candidate okay so there are two candidate in the last round so you you are going to provide a a witness Vector for example say one comma out comma input one and input two but you are you are going to say the input is either zero or one okay so so represents like I'm going to vote or I'm not going to work so so for each candidate you are going to say either either zero or one so in this case the the zero knowledge is of the scheme is

broken because the attacker can just come up with a winess vector say okay I going to try Z 0 0 one one zero and one one uh it doesn't make sense but yeah you canot say like one one yeah maybe you yeah yeah I'm going to have three options so so either I'm I'm not going to vote completely or I'm going to vote for a or I vote for B so there are only three possibilities and the attacker can put Force this okay so so this is a simplifi example and see why we need to introduce RS is to stop this br forcing

attack okay so this is the idea um how it works RS they are they are used uh as another set of random shifts so so recall that alpha 1 this is already a random shift okay but it is not enough since we want to do another random shift here so this is another G1 point so it is R times uh gamma as G1 point and similarly you plus this s uh s times Delta as g a G2 Point here and uh you are going to compute another Point copy

one so this is same same formula but you are going to evaluate everything as a G1 Point okay so in C1 the computation is a bit long so I don't have a proof for this step but you can actually compute the qap formula again so for Simplicity you can assume that Alpha and beta they are just zero and Gamma and Delta you assume them to be one okay so your goal is to try to prove that a * Bal C

here without changing the the verifier step so my claim is after I introduce RNs like this and also I change my C1 formula into this one thing uh my claim is the verifier step is is exactly this okay so so so equivalently my claim is uh the introduction of RNs does not change uh the verifier step okay so you can prove it but the proof I think is pretty hard to work with and basically just some some simple

algebra but pretty tedious okay so if you are interested in this please do it on your own and and I I think that's the end of today any question guys yeah this is the end of today we are we are fast so by now you should be able to uh to like Implement grass 16 code on your own actually so this is everything okay so this is everything everything in the in the paper

and the Finish yes so so the question is what are the resources I recommend besides uh DK DK book and first I think you should learn more circum okay so so in practice is uh you are not going to worry about the the math behind the protocol you are going to see constraints in code so the best way to start is doing circom um what are some the

resource actually it's very hard to find circum resource on the internet I think you should be like there is a a tutorial provided by skills for sure and that one is pretty easy okay so after that just read circum documentation maybe after that just recode in in circum lib there is no way to to learn circum systematically right now I think I don't I don't remember any any resource other than that actually yeah uh

the theory it really depends on your goal for example my goal is to find bugs in in circuits right so so my study like after grass 16 my study focus on uh Plank and planky and ZK VM and nothing beyond that oh and a little bit more Stark because they use star in dkv and and that's pretty much about it and I don't continue uh I don't plan to continue studying more Theory beyond that so so so short answer is Plank and Stark

yeah uh you don't have any idea about parrying me either but I'm going to take more time studying that okay uh oh I just oh I got a friend wrote two two pairing articles I going to share with you later okay I'm going to find the links uh he wrote two two articles name like paing for the rest of us okay so so so I'm going to share that link to you I know your mic isn't working but I can see your face oh I checked the original paper only for

the formula yeah I don't think the original paper uh actually tells you like all the motivation behind this for example like the motivation behind Alpha Beta these things I don't think is in the paper Okay so uh yeah but but the question is in the future for example there is no good article on the internet you have to read the paper so so yeah I think in the future I need to get used to that yeah uh but PL yeah yeah the resource for PL is also I don't think there's any good resource on the internet in

English I actually found a good resource in Chinese uh and for planky and there is no article for planky zero I mean plk E3 uh Stark Stark has uh uh yes start uh first I think you can start with the the the ZK viard session right the uh they have like one video on Stark and also have a video on ZK VN they are

pretty good uh watch that um yeah the resource for Star should be should be plenty [Music] yeah I am still working as auditor and I probably will still be doing auditing for a long time okay so so I only learn ZK for for like getting a new skill to to stand out a bit but I I don't have plan to go o in ZK right now yeah I think the market like the market is is pretty small compared to to Cel

and and salana at this moment I think right but but uh uh I don't know man yeah I don't know the future of about ZK but but thing I know is this skill is pretty hard to learn therefore if you have some opportunity in the in the future if you learn this early you going to have an advantage compared to others for sure how did I get into the audience industry uh yeah that was probably in in in last year January I think yeah it uh it was pretty pretty common story just called Arena Cod Arena Sherlock cold Hawks yeah

auding contest and then I do private AUD this yeah yeah nothing special about that oh that video uh yeah you need to do some some additional research yeah yeah because the speaker assumes you have some knowledge and they are not going to start from the beginning okay they they just they kind of like assume you are a working professional in the industry and they they they don't tell you about the

foundations you have to do additional research oh sure uh if you have question like after this session uh you just message me in the channel add me uh anytime if I have time I going to answer for sure yeah and and for myself I think I'm going to one I'm going to work on pairing a little bit more and also Moon maath chapter 5 yeah I think I struggle with that chapter I don't I still don't understand many of the things in there okay okay thank you guys if no more

question I going to take a short break I have another talk at def def High collaps later like 10 minutes later okay thank you guys so we have three three people graduated from this study group in week one I remember there are like more than 100 people yeah yeah 3% graduation rate