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

Transcript

okay let's start uh so I I prepar some uh notes for the more engineering aspect of R1 CS this one is pretty easy to understand okay so so reference is a rare skills CK book and the circum tutorial also the circum dog okay nothing special uh let me go from here so um for the next four weeks I am going to cover grth 16 from end to end so we going to start from a single problem statement and build a python code to implement the

algorithm okay so uh this week we are going to talk about RCS next week is a qap and third week is the is Alpha Beta gam Delta thing okay so in the last week I think I can to implement some some high technology into this so so make improve uh make Improvement to my to my own code so this week is pretty easy um yeah you just rncs let's go from this uh problem so so in my implementation I chose this problem uh saying given a four four vertices in a graph your job

is to prove the graph is bipartite and of course in a zero knowledge way okay so so aover needs to handle four colors here so either the color is one or the color is two because by part time means we want to separate all the vertices into two two groups and it is equivalent to two coloring problem okay so for the vertices in group one we want to color it with one in the second group we color it with two so in a witness the form will be like 1212

here so this is a problem so the terminology I'm using is from circum so the witness means public input plus private input uh in C come the first entry is always one because it needs to handle the constant term so this this spot is always Reserve to be one and this is always public so in our case we don't need any um like sometimes you see out here but for this uh problem we don't have output so the only public input is one this constant term and uh we have four colors

they are either one or two so so so we are just like artificially uh set up the rule because you can also say like 01 here it doesn't matter or you can say 3 five doesn't matter so so the uh to make this simple we just say like two coloring one color is one the other is two and you need to give me four colors to prove that four vertices are from uh two groups so there the graph is byar cool so this one is called public input this R1 to uh X1 to X4 are called the the private inputs so the

terminology is a little bit different as in the book but this is what circum uses cool uh so yeah verifier has access to public input which is this constant term one prover has access to everything because this public input you can like everybody can see right so prover Pro prover actually generates this private input because he's proving the thing so he's he has access to all the private inputs of course and and also the public one okay so the verifier

uh verifier can see the first one and uh prover can see the entire thing yeah and also you can you can Define like intermediate signals in in circum but in this case we don't need it because the uh the problem is pretty pretty easy so the first job we are going to do here is uh turning the this problem into arithmetic circuit so this requires some cleverness you know like uh we are proving the vertices are bipartite so what does it mean

is we are providing four colors right so the first condition is they are either one or two the second condition is different vertices from different groups they must have different colors because the the the definition of bipartite so how to represent that in arithmetic circuit pretty easy if we want to check a value is one or two you just say Okay so X1 - 1 * X1 - 2 equal zero do the same for all the four inputs the four four private inputs here okay so that constraint s and you just yeah

simplify the equation a bit but but actually in circum you don't have to simp simplify this you can just say this because each constraint is quadratic and you can tell even in this form you can tell the the equation is at most quadratic okay so you can yeah you can just write this in circum but to make it easier in Python I simplify this this uh systems of equations right so into this form yeah that yeah that's the rncs form for condition one so for condition two uh we want to uh

say different vertices from different groups they have different colors right so X1 X2 one of them is one the other is two so the result is always two because we don't have other options here say for example in three coloring problem you have color one two three then you have to write down a a table here like write down table and pick out the the value that satisfy what you want to do here right but in this case is pretty easy because we only have two colors so the only possibility is one two or 2 one so yeah

we create create these constraints that's for the second condition and this is already in rmcs form you just have to move two to the other side so yeah that's the arithmetic circuit this you turn it into R1 CS pretty simple for this problem because we don't have to flatten anything but uh for example you have like a cubic equation here say time x1- three here then you have to manually flatten the the equations right so that will make the process more complicated but

this is pretty easy to do here because the problem I chose is is very simple okay uh so we have a system of equations of seven equations here the next step is to turn them into Matrix so why Matrix because after that step so after by everything we are going to do qap which uh is the L range interpolation stuff we we talked about last week right so we first turn R1 CS into a

matrix and then we extract every column vectors and then squeeze them into a polinomial so that's why why we we want to turn system equations into uh into Matrix form because that would be easier to do the luck range interpolation stuff later so yeah yes sorry I just wanted to mention since I have to run in a bit I wanted to mention for example um it's it's a really nice example and I think it's fairly cool like in the next chapter when when you guys read that to go back to this example and um check if like everything is actually constrained that you want it to constrain um because like I think there might be something that

um uh yeah you still might need to like constrain um for this but I think it's a very nice example to revisit after so just to mention uh before I run off uh you mean like constraint like part I'm a little lost oh um I just mentioned for example const that there only exist two colors and um that you are in an environment where an attacker could not provide you for example like you didn't talk about it now but um if you're in a binary if you're in a bit setting you would have zero and ones right um that's you would need to constrain that because otherwise an attacker would for example give you like another color and which would then um result in thinking like in depends on

the modular arithmetic you're in if you don't talk about it here um that you know the two would become a one in that setting or things like that like even I provide constraints here the attacker can do something else um yeah would like I think you don't like since you have like one or two um like I need to like think about an example but I think you can can give you an example where uh I can give you a different like different inputs you didn't con Trin the type of the input you didn't say what X1 X2 X3 and X4 um are supposed to be um they could be like if they're you know an F like if they're

just bit like B arrays you know it can be a lot of things or um integers or something so you would need to do a like you need to make exactly sure that they can only be um these two values um you know what I mean what I'm trying to say I understand what you mean but uh from my knowledge right now I think the constraints here are okay like like unless you provide like a PC to me okay yeah I can because I don't know like like like how do you attack this okay because I can stream the thing to be either one or two in the field in the scalar field

right so I'm doing this in for example like circum I'm coning all the X to be like field element module P like how do you provide something else because in circum you can only provide the elements right okay so I think that information for examples missing from this description I just wanted to highlight it because um like in the next like yeah I understand what you mean rag right exactly and like it's very intricate to design actually problems and circuits for it so that's why I wanted to mention it um and design constraints uh and I think it's a good example to you know U think about all

the like attacks that are possible um so yes yes yes that makes sense so I'm going to head off sorry for interrupting I just wanted to mention that for the next session oh sure sure sure okay thank you byebye yeah byebye see you next week see okay I going to take take a look at that later okay so here maybe yeah maybe you need to check something like overflow as well I think because you can provide like p+ one if p is a uh the the the scalar field modulus so it's the

curve order okay yeah probably something like that I don't know but yeah like in so in my in my code right now I only have this two conditions for the second condition can you explain why yes the last statement that you've written um it's implied by oh oh yeah yeah I forgot to mention it yeah because you see like uh X1 X2 you only have two options right so for example like X1 uh is one X2 is two so one two here and then you have two one

here or otherwise this is 2 one one two so that's the only possibilities right and so this uh this constraint I think is pretty clear if you write down the truth table uh this is implied by one combined with two so you are saving one constraint here but but you know like for such uh such simple problem you can actually just write down here like and then build a circuit from here it doesn't really matter because right now we have seven if you add this you have eight yeah okay yeah I think I need to

write in yeah in practice I think yeah you can just do a little bit more to be safe right if you you got a complex problem it's hard to figure out yeah yeah yeah but but but here yeah I'm just trying to be smart and skip this uh yeah because yeah the truth uh truth table tells you only two possibilities okay okay thank you okay okay go let's let's continue so we have some concerns here but we going to we're going to accept that seven constraints here are good for now uh let's move on yeah uh actually it doesn't matter if you add more

constraints you know like the the process is still the same uh the only difference is you have a bigger circuit yeah so when you turn the systems of equations into Matrix form I think this is pretty obvious if you have taken linear algebra class because in textbook they usually tell you like Matrix is for converting system equations into Matrix form right they tell you that in chapter one probably so and how do you do that let's look for an example so let's keep in mind that uh the the winess vector a is like the the

standard that tells me how to transform this Matrix right so the the final form we want is uh L * a this uh dot is a matrix multiplication okay this Dot and uh this circle is a hmar product what does it mean it is element wise multiplication so for example if you have two M matrices uh A1 B1 C1 D1 A2 B2 C2 D2 then you do element wise multiplication the first term is A1 A2 second is B1 B2 you got what mean okay so it's not like a

standard matrix multiplication is is um kind of similar to do product but is between two matrices okay this is called the the HM product and the final form is this but if you don't see it uh don't worry we're going to walk walk through a an example right now yeah just one more comment that the number of rows equals to to the number of constraints in our case is seven so we have a a matrix now we we have three matrices of row seven and column five because the number of column is the the dimension of

the witness okay so so seven rows and five columns like a rectangle matrices okay so let's do an example for the the first rle of each matrices okay so for example here uh we write down this uh witness in a as a column Vector first right and uh uh for example we take the constraint one from here so is this one right we copy here uh this constraint we can see it is quadratic

therefore and we can break down into X1 * X1 equals 3x1 minus 2 that is saying okay we are breaking this equation into three parts so the first part is uh is one row of L so so the left one right left L right R and this is capital O is the result okay so this is the The O Part here R and L so after we separating this we can uh transfer into a matrix form right so for

example this R1 you can find it in the vness so R1 is the second entry okay so you mark this second entry in the row as one since there is no other stuff here you can just Mark zero everywhere okay so the first row of L is 0 one 0 0 0 because one represents X1 which is here so for example in the future row if you see oh X2 is here then you just Mark Mark this entry one cool so the same for R they are the same expression therefore

the the represent representation is the same so 0 one 0 z z okay so in the first row of oh you actually see why we added this constant ter one in winess because we need to handle constant part the constant part here is thetive -2 we can just write down2 here right yeah like imagine you you did not include this in the buness then we will be having a hard time here to to handle this constant term right so X1 3 X1 therefore in the second entry here is three okay so this is the the

thing secondry three a constant term2 and then you just do the same for the for all the constraints there therefore for you will have uh seven rows here seven rows and five columns that's how you transform system equation into this Matrix form right so so so why is a hmar product here yeah you can just go backward and uh do this computation I just did this computation for for the first R okay so if should be pretty clear that is it is hmar product instead

of normal matrix multiplication here right yeah this is kind of ugly because I only did one row but actually you had to compute all the seven rows and do computation here and verify is is good okay and question so far I think it's pretty easy it's like the first lecture of linear out class this is will be pretty easy okay okay no question no question good so in the end we will be uh we will have this a seven row and five colum Matrix times a we call that a is the

weakness uh witness usually we write as W but in the paper I think it is a in the grass 16 paper okay so I'm using a here and L * AAR product R * a just a quick question are these matrices public or okay but a is hidden or a is what I think matrices are public oh wait wait yes yes matrices are public a is go uh so right now like like for today just forget about zero knowledge okay so up

until rncs we don't have zero knowledge the zero knowledge part comes in when we multiply everything with the G1 G2 point we talk about last time that's the the quote unquote encryption part see yeah that's a zero knowledg uh R1 CS I think it has more Universal use like outside of ZK space I think this construction concept from some other part of cryptography you know like like this is pretty Universal like you transfer things into into um into a circuit and then into Matrix yeah um a is private here but why we can do this computation

because right now we are prover okay so so so everything we we are doing right now we are doing it as as a prover therefore prover has this uh this a secret a but later when prover generates that proof he needs to uh needs to to increas that that a you know like that information somehow into altic curves okay so in the end the proof the pro generates is three points on the on the curves but uh two of them are G1 point and one of them is a G2 point I

believe okay in graph 16 so right now there is no zero knowledge part and also there is no snark there is nothing um you see like the succinct part we will be talking about that next time in qap like right now it's not even sucn because you can see the Matrix is full of zero you can like abstractly you can think think of this information is pretty pretty loose you know like like I want to something succinct but imagine I have like a thousand constraints here then we I will have a thousand rows and most of the entries are zero so this is not very effective

uh how to make it succinct we're going to talk about that next time is a luck range interpolation okay so we actually we we talked about that last week but next week I going to show the code and also an example okay uh yeah that's all the theory uh after that is is engineering okay so I G to show you how to implement this rncs in in Python and these are all the libraries we we are going to use okay so to represent uh Matrix we use NP array so NP NP array uh is a pretty standard way to do Matrix

and then uh Galla is for doing modular arithmetics over the finite field FP so the nice thing is this Library can turn matrices into into that field form also polinomial so we can do everything as a GF yeah we're going to call it gal field so so so GF something okay uh don't worry about this this is some python magic map reduce stuff okay so and also import the the ticer things here yeah we are not going to use them today for for next time okay this is for

the for the encryption part quote unquote so so it's not really encryption but you get what I mean okay so we are hiding the the thing so it becomes zero knowledge uh first we we initialize a Gala field uh with this curve water so I need to make a note here that uh in the entire algorithm we work with the scalar field so this c c order represents the scaler field I think we talked about that before okay so base field is field modulus we are not going to worry about that curve order is the scaler field because we are going to

convert everything into G1 G2 point with the scaler multiplication in in EC okay so we are going to work with uh this field but as a debugging trick you can define a smaller curve order and debug everything and then go back to the original thing because this one is going to take like a 3 minutes to to compile think yeah yeah on my on my wub to so so for debugging you can just specify something smaller okay so let's go through this Gall

Library yeah here I demonstrate how is used um you can initialize a GF this is a Galla field so initialize a field through this Constructor and then you can wrap normal integers into this this field elements like this okay so if you are not familiar with uh this uh python repo this is um this means the return value of the last computation like this uncore represents this gf3 stuff okay so

so you can wrap integer into a field elements and also you can convert it back into integers okay addition multiplication also you can do subtraction Al also division but remember this division is is not integer division this is the uh division in a finite field which means you multiply the multiplicate inverse of the thing okay this is the division in finite field this is very different okay so in in normal python you can you can do this so this power function you can

compute the multiplication inverse and specify the field modulus here okay yeah they are they are just equivalent okay yeah I said this just now uh you can handle matrices and uh polinomial pretty easily so you can declare a npy matrix as nonp array like this and then rapid is the GF GF is the field me just declare okay R here and do operations on the on the GF Matrix you can do the same for for pols specify field here okay so this is

the yeah this is uh these are the coefficients for X like like you can just read from right to left right this is constant and then the coefficient for X coefficient for x square coefficient for X cub and so on okay so this representation in Array is equivalent to the polinomial representation equivalent okay so how to implement this in Python pretty easy like we just computed this by by hand right we computed this LR and O matrices uh this is pretty easy to

understand I think the the the Nuance here is you have to consider negative numbers because you don't have that finite field so for the negative -2 constant term you have to wrap it with a curve order minus two because this curve order is is a modulus is a modulus of the scaler field right so you just like plus negative2 plus field modulus oh man this is so so hard to express because cve order is actually a modulus of the scaler field but field modulus is also a constant in the library field modulus is a thing but we

never use it field modulus is for the base field okay wa so if you had just written GF and then in yes brackets you put minus two that would not be the same thing um no because you know why because I don't think it works because if you put DF here then NP doesn't recognize Gala Library I see you know what I me right because is like a more Universal thing it doesn't consider like the small name like this I think gallawa is a small name library right

so this galwa has like a consider n p but not the the other way around I think I see okay interesting and so the only thing left here is Computing the busness uh yes because right now we are we are the the approver okay so we can generate this witness uh these are the secret values okay and so in practice uh you shouldn't do this in a public script of course

okay uh uh but for for Simplicity you know like uh just imagine we are the provs and we know the answer the answer is pretty easy just one two one two okay so this is uh so red green and red green this is a two coloring solution to the to the problem statement okay and the a the vness can be represent as a as nonp array as well okay so constant term public input these are the private input okay yes okay and then we can do an assertion to test uh if uh the matrices and the

vness are correctly generated yeah just just do the L * a handm more product the thing you yeah you know yeah so this this assertion is just the the the formula here this one okay good uh this is pretty easy to understand we talk about a lot about public input private input going to skip this part okay this is pretty easy to understand so the only public input in our case is the one

okay or the X1 through X4 they are PR so you can do a python slice like this okay so this is like slice up until the index before l+ one so so up to zero so this is like equivalent to a z uh this slice index if on the left it is mean it means starting from l+ one so everything after the index zero so from index one to the end okay uh that's the python part uh we can also do rncs in circum pretty fun this one is pretty fun

um so in circum and how do we implement the problem we just talked about uh yeah just like this pretty intuitive so uh a convention in circum is you fed in the input if there are more than one input then you do do this like array form okay so so also you can say okay I can set the the length of the array of the input as a uh parameter n and in the main main function main component here you can

specify like how long you want the the input to be okay so this is four so this is four and the input is of length four so this is the witness okay so this is a secret input and we fit into here a convention is we do that in in Array so instead of saying all a b c d right that's pretty pretty annoying so so so we're going to say input as an array and then condition one condition two and put down the the seven constraints here yeah this is pretty easy to understand

like like yeah you just translate R1 to R4 like one to one right transfer into like in zero in one stuff yeah this pretty easy super easy okay R1 CS yes circum is just a repper of R1 CS together with some um some um functionalities to make your life easier yes life easier not very easy okay uh basically you are writing R1 CS in cir yeah this is a pretty low level language uh so a pretty important thing to to mention I think I just mentioned

it uh in circum every element is uh a field element so there are not normal integers for example like all the in zero in one here they are not integers okay uh there are field element in zma pz zma pz you should know by now is equivalent to find to find a field FP okay so so so in a field of this number yeah just remember like everything ends in 617 this is pycc BN 128. curve order okay yeah you can check that so uh just in mind in my personal experience I

never use this fi modul somehow I think it's because this information is embedded into uh altic curve addition and scalar multiplication I think so okay so you will never touch this constant so everything for example you uh if you want to implement this uh this algorithm everything you work should be like associate to curve order I think okay so yeah I never use Fu modulus yeah so just remember like like anything ends in 617 this is a curve

order cover order is the modulus of a scalar field and this is the modulus of the the the base field they are different okay so um they are similar because of a the I forgot the name man ah Something Like H hases bound something like that you know like saying field modulus and curve water should be similar but not the same yeah something like that uh I don't quite remember going look up and yeah yeah that's how easy it is to write this problem in in circum but yeah it's pretty high level so we going to

we're going to dig deeper into the into the compilation and see what's happening behind Okay so behind the scene uh how it works first we compile this uh using the compiler okay everything went okay so we know the our code is correct okay so generate rncs file so remember we were using a repper of rmcs we were not really like writing rncs so we need to generate that uh how do do that using uh this command Okay so D- rncs I also export the symbol file uh this is to uh we generate the symbols so in the future we can provide input in input.

Json add symbols so this is like the same idea in in binary files you know like like if you ever done reverse engineering you know you want to save a symbol file make your life easier otherwise you just like like the this compiler going to generate all the or the nonsense name to you okay so so so this is the symbol file and check out this rncs can see uh use this uh smjs to print the rncs file but the the content is pretty pretty stupid you know this is not readable why

because this isga -2 so recall this number is very close to field modulus 583 H oh man this I'm a little confused actually y 161 oh man wow I found something uh I going to put a question mark here I'm a little

confused um I going to tell you later okay I going to tell you guys in the in this cor but I'm a little confused on this part I think I think this should be negative2 right no this should be negative one and this should be negative2 why is this one 61 this one 51 does anybody know about whatever so so the idea is the idea is this large number is the curve order minus something okay so you our you our constraint I think this is

like P minus one this is p minus 2 but somehow it's giving me this oh I know why I know why I know why hold on hold on hold on oh I know I know I know okay okay this is curve order see curve order is 617 this one is a 6161 this is 6151 so I think this is bug you know could be circum f um so circum is appending this one somehow like like a placeholder or

something you see this one everywhere but it's actually not number okay yeah it's printing this one somehow I don't understand but this is yeah sorry what is this equation um showing us or what is it representing okay okay so so so this is RCS okay so for example just look at this uh this line starting with this info okay so this is the first constraint the first constraint is here so recall what was the first coning is uh X1 - 1 * X1 - 2 = 0 right so X1 is just the the the input

zero and then there's plus mean in zero so this yeah this plus uh so so this one is a minus one but you cannot do that in a finite field therefore you have around so so this large number equals to minus one plus curve order okay so so this makes sense because curve order ends in 617 this is 616 but somehow circum is printing this one somehow so this is redundant this is like a bug or something okay yeah I just make a comment here spining one at the end of

each huge number yeah yeah I hope people reading this not conf figure out yeah yeah this was pretty confusing so so whatever this is a p p minus one this is a p minus two okay so thing yeah I got confused but but but whatever okay yeah I think the rest are pretty easy to see yeah see is printing one everywhere so this term should be two is printing 21 somehow yeah it's kind of stupid okay and we finished that part uh okay

so we can computer witness but first we have to generate this uh web assembly file somehow I don't know why but I have to do this part so it generates a directory called the the project namejs so you go into that uh directory you're going to say uh say okay I going to create a new file called input JS no no no input Json um so what is this this is uh R1 to R4 these are the private inputs so so in input ad Json this is

not weakness okay so so this is just users input which means the private input uh in our case private input is X1 X2 X3 X4 okay so there's no no constant one term in the fr okay so this is input private input you going create file call input that Json and yeah copy paste this into the file as input then we can uh compute the the winess so you are using this commands Okay so in the end the busness is uh one one two one2 so this first term is the constant we just talk about

okay okay that's all for today any questions so far yeah I think it's pretty I think it's pretty easy to understand okay so compared with the book right uh my Approach would be very easy to understand I think this is just like high school level okay so the only confusing part we got stock here I figure out so this circum is bringing this one somehow at the end of every number somehow pretty stupid okay we figure out we figure out everything did you did you use did you use circum for the gr 16 like the entire implementation uh no I I use circum for

for my rare skills book and homework I see so GTH 16 was pure python so so I wrote like 300 lines of python including comments so is a pretty small right pretty small program but you have to figure out the math because although today we don't we didn't do any math we GNA do that next week uh next week is pretty heavy and the week after is even heavier so math is going to come uh but it's not like a high level math it's like a polinomial inner product manipulation is pretty pretty annoying

okay and why I C uh yeah I just want to introduce this because the the behind the scene part is pretty interesting also this is not everything because uh next week we can see under the hood circum generates that powers of towel no uh I mean snjs is generating the powers of towel stuff and like how to prove things in practice we can we can demonstrate that next week okay awesome and are you done with the rare skills boot camp was it uh I I finished the DK boot camp um nice I finish uh I do I actually yeah I do

recommend it because um I I can tell you that it's pretty hard to do it on your own so although the bookham doesn't provide any secret knowledge um I think you have you will have a higher probability to finish the entire thing and have your grass 16 implemented at the end I see but yeah but why I say with high probability because I think only like three people like we have like 11 people at the end no from the beginning okay so in the end I think only three people show up so you have like 30% 30% of chance if you join the BAM but if you didn't join

the bookham you know like how many people talk about ZK last year you know on Twitter right like I see hundreds of people talking about it but they they still didn't learn anything you know so so so yeah join the bookham but you have to study on your own yeah and just one more question regarding that did you get uh uh did you up for the one-on-one mentoring sessions as well oh I didn't because I yeah I I'm actually mentoring other people oh wow wow because yeah I mean that's just an additional cost I wasn't sure whether to yeah I know but uh uh I don't know if Jeffrey will be happy with this no I don't think is I don't think

he worthy to to to do one-onone because you have to do your own work I mean right right unless you are super rich and super busy like you are you are senior or you are CTO or something probably you right okay uh I mean the course is pretty well structured you can you can do it on your own like okay I spend probably like uh five hours per V okay wow that's not that much yes uh I mean I mean DK is not very hard if you learn it the easy way right yeah I think it's just a very steep learning curve in the beginning but once

you get through most of the overwhelming mathematics I think it becomes easier I think is I don't see why people think it's hard at least uh I think for me ZK is okay it's like it's actually yeah average is difficulty I think it's fine yeah thank you for feedback app okay thank you for attending yeah I hope Jeffrey won't block me after this okay so that's everything for today uh next week we gonna go over qap L range interpolation and schw Z LMA yeah uh

next week is all about polinomial okay all right thank you for your time okay thank you thank you I will see you guys next week byebye