L13 - What are zk STARKS? | by Himanshu | BlocSoc Lecture Series

Transcript

so hello everyone today's topic is z stars in the last lecture we saw snars similarly stars are also proving system used to prove some information without revealing its details so first so first see let's so first let's see the difference between the stars and snars so talking about the transparency snacks are not transparent as we have to rely on The Trusted setup how in the last lecture we have seen that uh there's a third party that generates a secret ke tow um and from that tow that encrypted uh pols are calculated but in the case of but in the case of snacks there is uh but in the case of stacks

there's no trusted parting um so talking about the scalability the uh the St Stars has a logarithmic verifying time and snack say also logarithm verifying time but the difference lies in the proving time Le lexity the proving time of stacks is linear in polinomial size but that of snacks has no limit because of the extensive cryptography used so proof size the proof size of stars is larger than the snars and the reason we will see later in the lecture so the post Quantum secure we have seen snack use elliptic curve cryptography

and by an algorithm named shes algorithm elliptic curve cryptography can be broken so what do I mean by broken so in the last lecture we have seen that discrete logarithmic theorem in the elliptic curve which tells that if we know a point Alpha G in the elliptic curve then we can't infer what was the original value of Alpha from that elliptic point so but in the case of ZK stock some Collision resistant hash functions are used which make it quantum secure so stocks are scalable transparent and they provide argument of knowledge so how how they're implemented these are mainly the four steps uh in the stack implementation we will go

through each of them one by one so first is arithmetization um the information that the Prov wants to prove to the verifier has to be represented in some form of algebraic form so the algebraic representation has two main components first is execution trace and and the second is uh some set of polinomial constraint so let's understand it with an example so uh uh here's a sequence printed on the screen uh it's called cads sequence and its properties are that like we can start with any positive integer n and if n is even like if the current number is

even then the next number would be half of it and like this is 52 two it is even then the next number is half of it which is 26 and if the current number is odd then the next number would be equal to 3 into current number + one like uh 52 gives 26 26 is again even and it gives 13 and 13 is now OD so 13 gives you 13 into 3 + 1 = 14 like you can see here five is also OD so we get a 5 into 3 + 1 16 here so this it's this is a coll sequence so what does the coll conjecture say it says that if you start with any positive integer n uh like uh if you apply the

operations mentioned here then you will always end up with one uh this means that uh there would always exist a index I where the value would be equal to one and that is where our series would stop so let's see how I can represent uh it in the algebraic form so first is execution Trace so uh these are the uh so let's define what is execution table first so execution Trace is some kind of table which represent every step of my computation so like uh in this example

what is my competition uh I have calculated all the uh values of this series till I reach one so uh this is my competition that I go from 50 to like from every number to every number and while applying these operations so in the execution case I will represent all of these numbers and uh in this example I have uh represented them in the bitwise form where the most significant bit is in the right and the least significant bit is in the left and the next is polinomial constraint so like uh our problem has this constraint

that uh if a number is even then its next uh number is Def equal to two and similarly uh there is an constraint for odd number also so that would be our uh we will formally Define uh polinomial constraint for that so these are the four polinomial constraint that we generate for uh this problem so like uh this uh first term uh this first polinomial first constraint is uh like simply it's telling that the first term is 52 like you can see that this is a0 comma J so a z represent the first row of my execution trace and J is my column

number okay so like it's nothing but the expansion of this bitwise representation in the decimal form okay so uh it's telling that uh when I expand it to a decimal form and subtract the first term from it then I would get zero so it's equivalent to saying that my first term is 52 and similar similarly as the Collard conjecture say the last uh we stop when we reach one so the last term would have to be one like you can see here the last term is one and its bitwise representation is written here from least significant bit to most significant bit and here is the constraint for that the last row is

one and since all of the values are in this table are either zero or one so we also have a constraint for that like a i comma j s minus a i comma J equal to Z if you calculate the root of this polinomial then a i j would be either Z or one so this means that all the values in the execution Trace are bits uh now let let's come to the final constraint and this is the heart of our coll conjecture so uh this was our golden rule of the while generating a Collide sequence and this is what uh like written in the

fourth constraint so uh if we say that like AI comma Zer AI for this is for all rows okay and zero here represent the First Column so this is actually checking if the number is even or OD if the number is even uh then the least significant bit of the number that number would be equal to zero and if the number is OD then the least significant bit of that number would be one so if the number is even then this term would be zero and this term would one so only this term will play into will come into the picture and if the number is OD then this term would be one and this would be zero and only

this term would be equal to this term only would come into the picture so uh let's say this is my uh ith row and this is my I + one one row okay so uh the uh number on the I row is even so this rule will be applied on it so like from this rule if n is even then n goes to n by 2 a i + 1 is equal to a I by 2 and you can see that uh that is what written in this square bracket that AI + 1 is equal to AI by 2

and so what's the rule for 3 AI + 1 is equal to AI + 1 so this is how I represent my like the constraint on our problem into the polinomial constraint formation so let's see another example this time it is Fibonacci number uh the information that the prover wants to prove to the verifier is that the he has calculated the Fibonacci number till 511 and he knows the value of the FIB 512 Fibonacci number okay so this is equivalent to proving that he has calculated all the

all the Fibonacci numbers till the 512 okay so what would be the execution trace of the this problem the execution trace of this problem would be all the Fibonacci numbers till uh till 512 okay so first Fibonacci is one and this is a Fibonacci sequence is written and this is a polinomial constraint on the uh for this problem that a 0 - 1 0 and A1 - 1 0 and for this is the Fibonacci Fibonacci recurrence relation that for all I in the range of this execution trace the Fibonacci recurrence relation should

hold and that is fi + 2al to fi + 1+ fi and this is the final thing I want to prove okay so so we have successfully represented the information in algebraic form now in the next step we will do some polinomial conversion so what's the AIM now so my aim is to transform the polinomial constraint that I generated uh from the given problem to a single polinomial that is guaranteed to be low degree if and only if the execution Trace is valid a very heavy statement but it would be clear as we progress to the lecture so

as we have seen in snack's lecture all the things we are doing is not on the range of all real numbers but some finite field so that is true in Stacks also so Pro will select a field on which all the mathematical things are happening let's say field the field he selected as generator generator element G so we now think of elements in the execution tra as evaluations of some polinomial f what does it mean that like we have this execution table Trace here okay and like we thought of every value in this execution Trace has to be some output of a polinomial FX where the uh XIs are the powers of the

generator element uh this table would make it clear that we are choosing our X to be the powers of the generator element and the corresponding uh output of the polinomial F would be the execution Trace element entries and this is the way we construct a polinomial so in the generalized manner it means that for all I Belongs To Zero from 511 F of GI equal to a of I okay so like now you will notice that all my AI become output of FX so I can just replace AI by FX here so you can see uh this AI are replaced by F here

because they represent the same thing so finally we have a polinomial FX and some constraints that the polinomial should satisfy now let's define some set of functions PX QX RX and SX uh their value is written here their expression is written here uh now if the Prov has truly evaluated the Fibonacci number till 511 then all the uh constraint should like should be true for the execution TR Okay so like this FX we we built on the

execution trace and uh this FX was satisfying this uh set of polinomial constraint so if we put uh xal to 1 in this uh constraint we get this constraint that F of 1 equal to 1 and if you can see that if you put substitute xal to 1 here then uh the denominator become a divisor of the numerator so this means that like if the uh prover has not truly evaluated the polinomial execution Trace so then uh the denominator would not be exactly

dividing the numerator like for example that could be of the form x - 5 by x -4 if you can't reduce it to a single polinomial expression but if the prover has truly evaluated it then it would become a simple polinomial expression and that is true for all PX QX RX and SX so now is now what is my equivalent statement to prove that the four rational function PX QX RX and xx are not some form of like Po in numerator and then denominator and we can't just reduce it to the single polinomial but they are actually a polinomial expression

uh next we do is we take a linear combination of all these four pols and generate a single polinomial uh known as composition polinomial we took some random numbers Alpha 0 alpha 1 Alpha 2 and Alpha 3 and generate a single composition polinomial through it okay so let's analyze one thing if all these terms are pols then this composition polom would also be a polinomial that is true uh let's say uh one of them is not a polinomial and like it's of the form x - 5 by x - 4 if you can't reduce it to a single polinomial expression then there's a like there's a very high

probability like uh close to one like approaching to one that the composition polinomial is also uh like a function of some polinomial written in numerator and denominator it's not reducible because like you can dry run it on on the paper and you will be convinced like I have done it and yes U I am like very much convinced if you can if you want you can also do that so my like my equivalent statement becomes now instead of proving these all four polom these all four functions to be polinomial all I have to do is just prove that this is a polinomial not a

fun not a like function of numerator by denominator so proving composition polinomial is a polinomial is equivalent to low degree test of composition polinomial so uh the number of elements in the execution C was equal to 51 512 because we have calculated Fibonacci number still 512 so when we calculate the FX polinomial to lrange interpolation that

we discussed in the previous lecture also the degree of FX will be at most 511 and we would use this fact to uh found the upper bound of the degree of this for polinomial okay so like the degree of FX is at most 511 and the degree of denominator is one so the degree of PX would be at most 510 and similarly Q degree of QX would be at most 510 and the degree of RX would be at most 511 511 minus 51 0 equal to 1 so degree of RX would be at most one so

like so if we can somehow prove that these four pols have a upper bound on the degree then our work is done so that is what low degree testing is for uh it's a method of it's a method of deciding whether a given function is a polinomial of some boundary degree so all I have to do is now that our the uh composition polinomial is a polinomial with a bounded degree okay so uh we do low degree testing for for this and I will explain two test for uh the the purpose of low degree testing first is direct test

so uh any polinomial of degree less than D is fully determined by its value at any D distinct location so like this is in consistent with the lrange interpolation like if you know D distinct unique points on the like number system like you can uniquely determine a polinomial of at most degree minus one passing through it okay so what the verifier will do verifier will ask the prover values of the polinomial at uh some D distinct points so he will generate some this D distinct points X1 to XD and a random X not point and he will generate uh provide this D+ one

points to the pr okay then the Prov will uh provides the value of uh F CP of X1 CP of X2 and CP of x0 to the verifier so like as I told that the degree of CP is bounded by the this FX so uh the verifier can itself calculate the uh can interp interpolate the polinomial GX from the output of the def points that the prover has provided him okay so like uh this D points will uh give allow him to compute a polom and then he will

calculate the value of GX note and then he will uh compare it with the value provided to him by the verifier and if that is true that means that the approver has actually done the computation and so the uh uh proof is done okay but there is a problem in it like you can see that the verifying time in it is linear in polinomial size but as we have seen that the in St the verifying time is logarithmic so so we have to improve it so that's uh where a technique named F comes like

let's assume this is a PO polinomial on which we have to prove the upper bound of the degree so we can represent this polinomial into like in the form of its even part and OD part so like f of xal to F of even x² + x into F of OD X squ so where F of E1 F of E1 repres F of E1 represents the uh represents those uh X values in which the degree is even so like f of even x = 19 + 34 + 43 + 10 uh sorry it's U Mis U it's 10 here and it is zero here and similarly F of or equal

to 56 + 48 + uh 37 + 0 here this is X Cube and this is X and we are calculating it on x² so for an extra xterm we have added it in like the outside okay so uh what Prov will do the pr will represent the polinomial in this form and then the verifier will choose a random number for example in this case he chooses R1 random number equal to 12 and then uh he will give this random number to the prover and the prover will now generate a new polinomial from the even part and OD part of the original

polinomial so like this is the expression of the new polinomial the pro generate F of 1x = to F of e1x + R1 into F of o x so as you can see the degree of this polinomial is three but the degree of this polinomial was six so we were able to reduce the degree of polinomial by half and that's the core intuition of the F technique like in uh we will do this step of representing the polinomial into its even part and OD part repeatedly uh until we get a constant polinomial so like we started with degree 6 and then we got a polinomial with degree 3 we will again do the F on the on this polom and we will get a

polinomial of degree one from here and if we again do it uh then we will get a constant polinomial which means the polinomial of degree zero so you can see that in like uh in log and log D steps you are able to reach the uh constant polinomial so that's where the log B Factor come and in further I will discuss how the verifier can then verify the proof so all the pols generated log the polinomial generated in this Pol this step the prover will store store it okay so the process is dially depicted here

the verify uh generates a random number Al it's equal to R1 and then the Prov generates some set of F1 here and the verifier again gives some random number Alpha 2 and the prover again again generates some F2 here unless the pro is able to generate a constant polinomial so all the work done till now in f is done by the prover except for the seed provided to the prover by the verifier so now verifier needs to be convinced that the prover actually calculated all the pols so how the verification is done let's

see so this was the polinomial that the pr had to prove the bound on so this we uh have this we saw that we can represent it in the form of f of V1 plus X into F of for now if you substitute xal to Min - x here then you will get this equation and if you rearrange this equations then you will get the expression of f of V1 and F of odd in the form of their original polinomial so like you will when you will add these polinomial add these two equations then this term will be get cancelled and uh you can get the expression of f of V1 and similarly when you will subtract F

of minus X from f of x then this term would be get cancelled and you will get expression of for f F of odd so the Prov has generated expression of f of even and F of odd in their for in the form of their original polinomial so now uh let's uh take this equation into mind and like we have representing uh let's suppose that all the polinomial generated in the F step in a hierarchy like he has F of 0x in the initial and then from this he generated F1 and from this he will generate FS2 F3

F4 F4 till he reach a constant polom so let's assume they are in a hierarchy so so you can see that uh in the hierarchy uh the I +1 polinomial is determined by the IAT polinomial the even and odd part of the IAT polinomial so if we can somehow represent the even and old part of the polom in the original polinomial that means I have represented the F of I + 1 polinomial in terms of the previous polinomial and that is what we have done in this slide if we have represented F of V1 and F of in original polinomial so if we sub just

sub substitute these values uh into this equation you will get final this equation okay okay so uh in the generalizing it it means that if you know uh if at the if for the ith polinomial you know the value of f of x and F ofus minus x on it then you know the value of f of I + 1 at x² so we will use this to uh verifier will use this to verify the transitions uh that the pr made in the F steps

so here is my CP the comp the composition polom the original polinomial it's denoted by CP here but the CP here is same as the uh uh F0 here so what will the verified do verified will generate a random number X and then he will provide it to the prover the prover will calculated calculate three things that is CP 0x um f which is also f0x CP 0- X cp1 x² and Prov will provide these three values to the verifier so what the verifier will do from these two values CP 0x and cp0 minus X verifier

will compute cp1 x² and from the computed value uh he would compare his his computed value with the value the Prov provided to him so if they are equal uh so this if they're equal that means that uh the pr has actually like not cheated in the transition from the uh composition polinomial to the F cp1 polinomial and this step would be this step is done in all the F stages okay so that's where the that's why the time complexity for verifying the proof is LD like there are

order of LD polinomial here and in every polinomial you can see that there are in every step there is some only a constant time uh in proving the transition from the higher step of to the lower step of hierarchy so this is how the Prov will the verifier will verify the uh f pols and uh how the prover will prove the transition of the trace polinomial to the CP polinomial let's see what is a trace polinomial here Trace polinomial is nothing but the FX polinomial which we generated original from the execution

Trace okay like this was the polinomial we generated from the execution Trace so Trace is like another name of the like original problem original polinomial so uh now what the verifier will do verifier will again generate a random number X and provide it to the prover and prover will calculate four things f of x f of GX and F of G SX and CP 0x and we'll give the all the four values to the prover verifier and now what the verifier will do ver will compute its own cp0 X by using these

three values FX F of GX and F of G SX and how he would do that he would just put these three values into this set of equations and from this he would get PX QX RX and X SX and by he knows the values of alpha0 Alpha One Alpha 2 and Alpha 3 because they are publicly available so he would get the value of composition polinomial at the value X so he would compare this computed value with the value provided to him by the prover and if they're equal that means that yes the prover has actually made the transition from the trace to the CP

polom so this slide represent the summary of the whole lecture this is the computation that the pr wants to prove that he has done and he would represent it in the form of some algebraic forms uh he would uh generate execution Trace from it and it has some constraints and from the execution Trace by the legran interpolation he would get a trace polinomial and from the uh constraint he would get some set of quotient pols and from the quotient polinomial we get a composition polinomial and on the composition pols we apply F and then the verifier uh

ask queries to the F and this was all about the lecture thank you