L12 - How do zk SNARKs work? | by Himanshu | BlocSoc Lecture Series

Transcript

so hello everyone today's lecture will be about ZK snars so in our lecture series we have seen ZK rollups where a ZK proof is submitted on chain so in this session we will see how the proof is generated and verified so Z SS are way to prove that you know something without revealing the information itself so they allow one party to prove to another that a statement is true without showing any details about the statement so the following components form the n it is zero knowledge it is suin it is not interactive and it provides argument of knowledge so zero knowledge means nothing is revealed other than a truth of statement and suent means that our

proof is concise uh like the size of the proof is not very big and it can be verified quickly or non interactive so there are two ways to approach a zik proof one is interactive and one is non Interactive so in interactive proofs um a series of question and answer is there uh verifier as Prov some kind of information and the Prov replies back and the verify again asks some counter question but in non interactive proof the proof is like in a stored version so verify verifier can any time check the validity of the proof okay and argument of knowledge um the

pro profile the verifier with the argument and that yes he knows some information so how are they implemented there are mainly five steps arithmetization R1 CS R1 CS2 qip encryption of QP and shifting salting and we'll go through each of them one by one so first is arithmetization so uh user if a user wants to prove some information that he has so he has to represent the information in some sort of like mathematical equation so let's

say it represented his information in the form out equal to y^2 + 4x² Yus 2 okay so now we will apply arithmetization on it so arithmetization is nothing but breaking down uh this mathematical question into simpler steps okay like you can see there are are many operations in this single equation like there are uh x² y there are three variabl multiplication here in y squ is also then variable multiplication and then these are added so in arithmetization we decompose this statement into like simpler steps okay so what's the rule the rule is simple

one line one operation that means uh in one line you can have only at most one uh nonscalar multiplication nonscalar multiplication means the multiplication between two variables so such as um like 5 into Y is not a uh it is a scalar multiplication so like that can be accommodated multiple scalar multiplication can be accommodated in one line but for a non-scalar you has to you have to take only one line Okay so so this is my equation and I have broken down into three uh constraint so in order to do this I have introduced two

intermediate variables V1 and V2 and uh this is exactly the same equation as above so uh one more thing like in your in expressing your information there can be some operations like comparators and some other operations like bitwise but the rule is that you want to represent your uh equation in terms of only addition and subtraction okay so if you have an operation like bitwise like left shift and right shift so you have to convert it into um addition and multiplication so suppose uh one left shift two you can easily M uh convert it

into multiplication using like one left shift 2 is equivalent to multiplying it with 2 to the^ two which is four so like there are other tricks to convert the comparators operation to the addition and subtraction we will not go into that so we now have our computation Express as a sequence of constraint so we will take it one step further and make another transformation that describes the equation like in a different format and that format is R1 CS uh our rank one constraint system okay so for this we will introduce a witness Vector witness

Vector is a vector of Dimension 1 into n which is a solution of the constraint okay so like this was my constraint uh witness Vector is a vector that that will have the values that will satisfy these constraints so uh its Dimension is 1 into and N is number of variables plus one this number of variables include all the variables whether it is input output or intermediate so this is the structure or of our witness vector and you can see there is a extra one here so what the importance of one it facilitates free addition and how is that I will come to

that later so for this set of constraint the W witness Vector is this is so this means that for x = 3 and Y = 4 and out equal to 199 uh it is the solution of our orinal equation so so our aim is to calculate these matrices a b and c um so ab and so ab and C are matrices that we uh use to convert this uh used to convert this equation into R1 CS so what are the

dimension of ABC uh these are n m n into m n rows and sorry it is misprinted n rows and N columns so n is the number of constraint so like in this example we have total number of constant equal to three and M is equal to the number of witness elements so we have seen number of witness element was number of variables and one so here if you count that 1 2 3 4 and five so five variables and plus one for the one and so the number columns are six now how to calculate this matrices a b and

c so these are our final matrices a b and c so like if you take uh we have three rows here first uh so the the first row second row and the third row the first row when you multiply the all the first row elements with the witness Vector this will generate the first constraint and similarly we can do that for second and third so like you can see if you do the simple matrix multiplication here the one is Multiplied with V1 and here the one is Multiplied with Y and here one is with Y so this will become V1 = to y s and this is essentially our first constraint okay so let's see how we can

convert this second constraint into the vector form so we have V2 here okay and the V2 position in the witness Vector is uh the last so in The Matrix C the second row of that will only have one at the last position of it that is V2 and all the elements will be zero let's check it yes it's true you can see there's only a single one here and rest of the all elements are zero and for a we have X here and for B we also have an X here so X is the third element in the witness Vector so we will have a one here and rest all of the elements are

zero so you can check it uh now I will explain the importance of one so so there's a general saying in the ZK that addition is free uh what does that mean so like you can see here uh there is a already a variable multiplication here and I said that only one line can have only one variable multiplication but along with that we have a V1 and minus two here so how we can comate it our R1 CS so let's shift V1 and minus 2 to the left hand side okay so and so let's expand the uh expand

when the third row will be multiplied with the weakness VOR so we will have a 2 into 1 + 1 into out + 0x + 0 y minus V1 and you can see all the terms are separated by addition because of the property of matrix multiplication and that's why like we can accommodate as many addition as we want so for variable addition we can mark the corresponding coefficient like whatever the co ient here is in the in these entries and if the so now I will tell you the importance of one Suppose there is a constant condition like in this the minus two so there there has to be a value which represent the constant value

in our constraint system so like the two will be multiplied with the one here and that's consistent with consistent with the equation here so actually it is not exactly written correct it facilitates addition of uh it facilitate free addition of constant but variable we can do without one also so this I have already covered so the next step is R1 CS2 qop qop stands for quadratic arithmetic program so we have transformed our equation to R1 CS now we need another

transformation that is QP so let's talk about what's the need for this transformation see the proof generated by R1 CS is not suing uh we want it to be clear and precise okay you can see okay you can see there are lot of multiplic zero multiplication and that is not adding up anything to our final constraint okay so uh that's a waste of time complexity and also space complexity so and that's the reason this conversion is there because qap are the reason the ZK SS are succinct okay so we condense Matrix to a single polinomial expression

using lrange interpolation so what is what is it I will come to that later um so at the end of R1 CS we got CW equal to a w into BW where c a b are my matrices so we will convert it into uh this part W equal to U into VA this represent the polinomial expression so so now let me explain you what is lran interpolation so like suppose we have these three points 1 comma 0 2 comma 1 and 3 comma 0 like interpolation says that we can exactly determine a we can uniquely

determine a 2 degree polinomial passing through these three points so that is easy like you can write the general form of 2 degree polinomial a x s + BX plus C and just substitute the value of y and x and you will get a B and C so generalizing it if you have end points if you are given end points then you can uniquely determine a polinomial equation with the degree of n minus one so that is the Gran interpolation so so my now my aim is to convert the ab C matrices into the polinomial expression so let's say the polinomial expression we are taking is in variable is in the

variable X so for and now let's make another assumption that this is not an assumption sorry uh that the first row correspond to the xal to 1 the second row correspond to X = to 2 and third row X correspond to X = to 3 three so what does that mean uh I'm explaining uh so let's say for each of the matrices a b and c and in each Matrix for each of the elements in the winess vector we will have a separate polinomial so like this is our Matrix a that we generated in the R1 CS okay so like these are the entries of x 0 1 0

so there will be a separate uh polinomial only dedicated to X so as I said that the first R correspond to the X = to 1 and the second xal and third xal to 3 so just take the point 1 comma 0 2A 1 and 3 comma 0 and you can you will get the equation uh - x^2 + 4x - 3 and you will do for each of the element for each of the columns so like substitute uh take 3. 1A 1 2A 0 and 3A 0 you will get this polinomial and similarly do that for v2 you can ignore the zero columns here because they

effectively give you the zero polom you don't need to calculate it so after uh so like after calculating it you will get this final expression so this is my corresponding expression for the Matrix a in the qfp so now uh I I will explain that what does that X first row first row means xal to 1 that mean uh let put xal to 1 in this equation so when we put x equal to 1 in this equation and uh the purple Matrix will come out to be zero and similarly you can see the pink Matrix will also

come out to be zero and when you will put xal to 1 here uh then uh sorry it is misprinted it is .5x s - 2.5x so you will see that if x = to 1 is put here then you will get one from here and so effectively when we put xal to 1 in this we get only we get 0x + 1 y +0 V2 which means we get a y so this was uh my Matrix a and let's came back to the original constraint system and you can see that the variable corresponding the a matrix was y so that's consistent with

our uh with R1 CS so similarly if you will put xal to 2 in this equation you will get the final expression equal to X so uh this was a witness meor that only the Prov has so he will substitute the value of XY and V2 in this and generate a final expression for the Matrix a and similarly this operation is applied on Matrix B and C and you will get finally three pols a b and c so

now we will we got this polinomial A and C which is also W UA and VA and if you can see that the they are not balancing like the degree of the polinomial on the right hand side is four and the degree on the left hand side is two although on the values of xal to 1 2 3 which means like the number of the constrain numbers their values are equal like I have calculated it for the xal to 1 the right hand side comes out to be n and left hand side also come out to be n you can also verify that you for equal to 1 2 and 3 their values are same but

the pols are not equal but for the sake of zero knowledge we want that the pols are all same so how we can achieve that so this we can achieve that with the help of division theorem so we will divide our polinomial UA into VA which is of degree 4 with a another polinomial TX that will give you a quent HX Plus a remainder wa um this is like consistent with the polinomial division theorem which we have studied like PX equal any polom PX can be represented as QX into HX + RX so now question is what what would be

the choice of TX so in the Z KN TX is chosen to be as x -1 x -2 x till xus number of constraint so for our example it would be = to x -1 into x -2 into x - 3 and now the question is why this TX uh there are mainly two reason the first is like this TX is publicly known to both the prover and the verifier so uh it prevents the pro to forge the proof of the proof of the information like now he cannot just randomly pick up four pols PX QX RX and HX

and ensure that the polinomial division theorem is satisfied on it and provide it to the verifier now the TX is fixed so verifier can easily check that yes it is the TX that we agreed upon and the second reason is uh you can see the uh just I have already stated that the value of U into VA and wa are equal at xal to 1 2 and 3 so this numerator will come out to be 0 of 4 x = 1 2 and 3 so when it so basically TX is just a factor of the numerator so it will give you a perfect remainder um perfect quotient sorry okay so so far we have uh

generated the final Q final polinomial Expressions now we have to encrypt them uh so I will explain you the need of the encryption so this was the polinomial expression for a that we generated so uh let's say let's say the prover Pro provided directly to the verifier okay and uh at uh till this step the prover and verifier both have the same information like the prover verifier knows what are the set of con the pr wants to prove so uh he can also verifier can also reach till this point

so after this point the Prov provides the verifier with this information and verifier can uh now make an equation into XY and V2 like how he can just compare the coefficient of x in this and in this expression so like if he compares the coefficient of x to^ 2 it will will be it will give us Min - x this this was plus5 as I mentioned earlier so Min - x plus5 y + 2 V2 = to 29.5 so this will give me one equation and similarly two more equations will be generated for X to the^ 1 and X to the^

0 so this is three equations in three variables so verifier can easily solve it and can get the values of x y and V2 so that's the reason we have to encrypt this information of the polinomial so we need to encryp the polinomial to a homomorphic space using oneway mapping uh now I will explain you the meaning of the terms mentioned in this definition homomorphic means that there is a correspondence between two algebraic systems uh like let's say we have uh algebraic system like the normal algebraic system we are used to like the one is one and two is two and we are

mapping all the values in it to a new algebraic system s to the power a so uh we can pick whatever the S is like suppose we pi as s equal to do so not two will become four and three will become uh eight so this is homomorphic that there's a correspondence between two algebraic system that uh this means that if I apply an operation on the first system like if I apply a plus b addition operation on two variables on the first system then this will correspond to another operation in uh the second algebraic system and that can

be anything that can be like customly defined also so uh in this example the plus operator will be match to the multiplication and using oneway mapping oneway mapping is that we can't if we have the encrypted number we can't tell what was the number it was generated from that's the meaning of one way so like this uh let's come to the example take take s equal to two now suppose this s equal to 2 is known to the both known to both PR and the verifier and a equal to 3 so uh this is a equal to 3 is ma to eight now you will

question that okay I know as equal to do I know the mapping is uh mapping is eight I know how the things were mapped so I can just easily like I can take the log of 8 and tell what was the original value so log of 8 will be three and guess I got the value in the first algebraic system so how it is one way so modulus to the rescue so we will calculate every encryption modul some prime number P so let's say after uh calculating S the^ A we are also doing it modulus with the number seven so uh to 8 will become one 8 7 equal to 1 so

now I am aover and S equal to do is known to both Prov and the verifier and a equal to 3 is already all only known to me so after mapping it to the encrypted space which comes up to be 8 mode 7 equal to 1 I gave it to the verifier so verifier what what does what information does the verifier have he knows s equal to do he knows the ma value is one can he guess AAL to 3 no because simply uh there can be a many possibilities because 2 Cube mode 7 = to 1 and 2 the^ 6 which is 64 uh when you take the mode of 64 with

seven uh it also comes out to be one so now the verifier can't tell what was the pre-image of the encrypted message okay so this was one sort of encryption but in the ZK s uh elliptic curve cryptography is used to encryp the pols so for those who don't know the elliptic curves I will brief you about them so they are used to Define robust poision resistant and oneway function that are used to map the polinomial generated after the qap so we have some set of polinomial that we uh that we have after

the qap process and now we want to encryp them so for that elliptic curves is used so they are defined over a finite field um this means that they are not defined over like a very large number uh the number can goes to Infinity um we are already we are only we are only concerned about a limited set of numbers and uh for example we can take only 0 to P minus one number where p is a prime number uh they are cyclic so what does do that mean I will explain you with an analogy analogy so we have a set here 01 to till

P minus one it is also finite field just like I explained here so uh if I have to done addition modulus in this um on this finite field okay so you can see that uh it is cyclic because if I choose a generat element one so so first of all what does cyclic mean cyclic means if I take a element from the set and apply the operation defined on that set repeatedly then I can generate all the elements possible in the set so like uh in this set the generated element is one because like 1 + 1 is 2 and 1 + 1 + 1 is 3 and I can

apply addition on one like several times so every element possible and how zero can be generated from one I can just add one p times so this will G gives you a zero and when you add one p + 1 times this will again come back to one so this is cyclic so just like how addition modulo was a cyclic group uh elliptic curves are also cyclic this means that there's a ex there exist a generator element on which if you repeatedly apply your operation uh it's not necessary that it it addition it can be anything in this case this is point addition so

if you repeatedly apply Point addition to the elliptic curves to the generator element G you can get every possible element so like G plus d equal to 2G and so on you can generate every element possible for some are R into G equal to Z so one thing to note that here the plus sign doesn't mean that it is the actual addition you know it is point addition like it is some kind of operation that is defined specifically for elliptic cves you don't need to know the how implementation of it for the sake of lecture you can just remember uh in this lecture that they are just a simple plus

sign so so let's talk about the discrete logarithmic theorem it's a very important theorem with respect to the elliptic curve so this tells you that if you know elliptical point x into G which was formed by repeatedly applying operation uh repeatedly applying the binary operation on G so you cannot and for what was the value of x from it so just as an example if you know a0 five in a domain and if you apply the operation on the generated element G five times you will get 5 into G so this is what exactly it means that

if you have an variable X and if you encrypt it to the value X into z x into Z you cannot tell what was the X if you destroy it after the encryption so let's understand it with uh our previous analogy so this was equivalent to the analogy I discussed earlier like you cannot like in this encryption we were not able to tell that AAL 2 a was 3 or 6 so this is also exactly it also work like this so that was all about eliptical curve um this this will be enough to

understand how the Q are encrypted so at the end of our my qap process quadratic arithmatic process I got some sort of some set of polinomial and this equation was generated after the qap uh this was a question just it is rearranged TX is Multiplied here and W is brought to the left hand side so now I want to encrypt it uh in the elliptical curve field so just remember for this lecture that whenever a variable has a square brackets around it uh this means that it

is a elliptical curve point so the UA polinomial will be encrypted to a and the VA polinomial is encrypted to B and similarly they are W is encrypted to C and H XTS is encrypted to HT so this statement is equivalent to a into Bal to C+ H2 C HT so how the encryption is done in a trusted setup it's a third party setup a secret key tow is picked and powers of tow is calculated so whatever the max whatever was the degree of this polinomial up to that power

the powers of to is calculated so we will calculate to0 to 1 and to to encrypted to the G and because of the discrete logarithmic theorem we discussed uh if we have these points after we generate them and if we destroy the tow after generating them we cannot tell what was the tow here so now here's the question so why Prov can't why PR is not allowed to pick that secret KY to before that if you are confused the tow is nothing but the value uh to is nothing but value of x

we can put x equal to to we are putting x equal to to here and that is encrypting so like it will be forming to square tow so it is encrypted to this set of elliptic elliptic points so why the prover is not allowed to pick to why the third part is picking up to because if the pr was allowed to pick to then he can forge the proof like he can generate any like he can generate any litical point such that they satisfy it a such that satisfy this conent AB equal to C plus HT and it's not

difficult and so the verifier will doesn't know that the this elliptical curve points came from the qf or just randomly generated so that's the reason the secret key to is picked up by The Trusted setup not the pr uh similarly we can encrypt the polinomial V and wa and that result us into the polinomial elliptical points b and d and similarly the encryption of polinomial TX and HX is done and after that uh HX encryption of HX into TX is done and that will give us a point HT

so uh finally we want to prove the very this equality a BAL to D+ HT so C let's say Cal to D+ HT so the Prov will then provide this values a b and c to the verifier and the verifier will then check if U the pairing of ab is equal to the pairing of C with the point G2 uh you will be like confus that from where there this point G2 came so uh the thing is that the point the the point a is generated uh the point A and B are generated in different uh groups like

they are they are elliptical curves but they are part of like separate elliptical curves so uh let's uh the a is point of a G1 group and the B is a point of G2 group and the D is the point of G1 group so you can also see here the a is G1 and B for the encryption of va we have used a G2 here and that's the reason we were using this two set of encrypted points and um for the sake of this lecture just remember that the pairing of G1 and G2 gives you uh another point that is in another uh ring that is g12 so this is like like like the uh one and

two there are two groups G1 and G2 and they gives you a point in another field in another algebraic field so when the pairing of A1 and B2 is done you get a point of g12 and you can't just directly create this two the C1 because uh they are then they will be a member of two different groups so that's why we paired it with a G2 so that here pairing of one and two will also result into a g12 so on both sides we are comparing uh g12 member groups group members so this was like a very high level knowledge about you can just

remember that we are we are only doing a b equal to C so what are the problems in it uh the Prov can simply invent values where c equal to a and then uh encrypt them and then provide this to the verifier and the verifier will check Cal to a into B so for this U some modifications are there shifting salting so uh in 2016 uh a person named growth proposed this modification uh that's

why like this was the growth 16 algorithm so the Rusted we have seen that the Rusted setup was encrypting a secret key Tow and um The Trusted setup also pick two Al points Alpha and beta and encrypt them to to form points Alpha G1 and beta G2 so now after encrypting them he will uh throw the Al and beta just destroy them so that uh one can never be able to find the pre-image of these two elliptical points and he will give these

two points Alpha G and beta G to both the pr and verifier so how does the prover uh will use them so the will updates their uh A and B elliptical points by adding Alpha G and beta G to respective A and B and this will give uh Prov the updated A and B points so like this was the equation a into B = to C+ HT so when the addition of salt is done Alp beta uh Alpha is added to u u is equivalent to um elliptical point a and v is equivalent

to Elliptical point B so when Alpha and beta are added to this then uh the final question generated is this and this has to be verified by the verifier so these underlined Parts these underlined parts are calculated by prover U and they will form the ABC and point and the pr will provide the a b and c points to the verifier and there's a extra alpab beta term here alphab beta is the pairing of Alpha G1 and beta G2 and it's again a g12 point okay so it's consistent with all um it's consistent with all we will

do like we will do the pairing of ab that give that will give you a g12 point so Alpha Beta is also g12 so it's consistent so Prov will calculate a b and c and will provided to the verifier and earlier I mentioned that Alpha G and beta G are provided to both the prover and verifier the prover we have seen that how the prover is using them to update the points A and B the verifier uses them in the very verifying stage uh that uh that's um how uh he calculate this pairing Alpha and beta Alpha Beta if he has Alpha G1 and beta G2 and

simply he calculate the pairing alongside when he is calculating the pairing of uh a and CG so this was all about the lecture uh in this lecture we have seen about snacks and uh do 16 in the upcoming lecture we will see about the plish arithmetization thank you