ZK Whiteboard Sessions - Module Four: SNARKs vs STARKs with Bobbin Threadbare

Transcript

[Music] uh hi everyone i'm brendan i work for polygon and today i'm here with bobin for a whiteboard series episode on starks so bobbin do you want to introduce yourself yeah so i also work for polygon and basically i got uh into zero knowledge proofs and starks quite a while ago um like late 2018 and um i've been kind of exploring and understanding them ever since and building a lot of tools around them so happy to share my knowledge okay we're coming at you live from a a

basement in amsterdam so i'm really excited about this art museum basement yeah so maybe if we start uh really basic what what does stark stand for so starks actually so stark says is a zero knowledge proving system uh and um the acronym stands for scalable transparent arguments of knowledge and you might have heard about snarks and starks and so um you know there's another big category snarks and um a little known fact that uh s and starks and essence darks actually stands for two different things so in starks it's scalable and here is the synced and there is actually quite a big difference

between the two uh and another difference is that hold up what's the difference so the difference and i'll get i guess we'll get into this a bit later in more detail but the difference is that uh for example uh for starks you don't uh necessarily need pre-processing and the program description is succinct so so what does so so s and snark stands for system synced yes so basically essence means that the verifier um is succinct you don't need to uh with this basically it's exponentially faster to verify approve than it is to run the computation so so we have a big computation yes yes exactly small proof or fast to

verify um and uh starks don't necessarily imply that what's scalable well so scalable also means the small proof exponentially smaller than the computation but they also imply that there is no need to do this extra step of pre-processing or taking the original description of the program and kind of like pre-processing it for the purposes of verifier to be able to verify it very quickly so so pre-processing is we have this circuit or we have this program and we basically take this long description and we compress it down to something that's much smaller that lets us verify proofs that use that same correct correct and yeah so and then the other term is transparent meaning that trans uh that

um you don't need a trusted setup for starks while you may need a trusted setup for snarks so so sorry to interrupt yeah a a trusted setup is just um when we want to uh to build azure knowledge proof we have to do this thing that uh basically requires at least one person in a ceremony to generate a secret and throw it away and if they don't then they then people can forge purse correct correct so ideally we would like to avoid that um so this uh um kind of i would say high level differences and they were much more uh important originally now the lines are blurring so you can have transparent snarks as well

uh and you can adapt some of the techniques from starks into stark so there is much less distinction now you know it's difficult to exactly say with a stark and what a snark but in general like starks are transparent no trusted setup so if it's not you know if it requires transit setup it's not a stark and then scalable uh as well if you need pre-processing you can also probably say that this is not a stark but other one and the other thing is that n here stands for non-interactive and starks don't have that end so start yeah starks could be interactive and in fact sometimes there is benefits to be having an interactive protocol like potentially smaller proof sizes but you can also have an inter a non-interactive target you basically

take an interactive protocol and use a fiat amir to transform it into uh to a non-interactive one so okay so starks can be interactive or non-interactive yep so if i had to do it i would draw like a diagram saying you know this could be you know starks and this could be snarks and if we put you know the non-interrupt non-interactive starks would go here and then scalable transparent snarks would go here so they're kind of an intersection of the two cool and in general when we think about like zero knowledge proof systems i think

there are two components uh that are used to build both starks and snarks and the first component is called arithmetization and the second component is polynomial commitment scheme so um you can mix and match different types of this and we'll go and uh i'll go into uh more details in a second but you can mix and match different rate mutation and polynomial commitment schemes um to get kind of different properties out of zero knowledge proofs so as an example well

yes veil of ignorance here uh what what do you mean by arithmetic so arithmetization is a process of basically taking a program right so let's say we have our program so and that's something in c or c javascript whatever like high level language that people are used to and we want to transform it into a statement statements about polynomials we need to do this so that the proving system can understand so basically you take a program and you do something to it and it gets transformed into a bunch of statements about polynomials and this is something that you know a stark or a snark system can

interpret and generate proofs for and then we need this poly commit scheme uh to make sure that those polynomials have bounded degrees of you know some sort okay so so i take my program yeah i turn it into some set of polynomials and then this the snark or the stark verifies that some relation about those polynomials holds and if that relation holds then i know that my program my statement is correct exactly the program was executed correctly um and yeah so basically the the step originalization is taking this program and applying some transformation to it to do this and there are different ways to do

it as well so this one so basically there are a very well known method of doing athletization is called r1cs so r1cs is very frequently used in snarks and what does r1cs stand for it's rank one constraint satisfiability um system maybe system um but yes so and the other approach is air and this stands for algebraic

intermediate representation or some people say arithmetical intermediate representation uh and you know there are different ways of thinking of how you take a program and describe it using polynomials so in case of r1cs you can think about the program as an algebraic circuit and it is very similar to like an electronic circuit where you have a bunch of gates that are connected by wires and you put inputs on those gate on the input wires and like some signals on the input wires and those signals propagate through the gates and but just to jump into to be clear that this isn't like uh like this is in the circuit board that we're wiring up it's more like a conceptual framework that we're using to represent so those are not physical gates though what we call

algebraic gates or those gates can actually encode different things so if we wanted to kind of let me erase this so if we wanted to like describe or uh draw out like a circuit so let's say we have some inputs we have some gains now what what do those inputs look like so uh this inputs could be because the gates algebraic like in a in a traditional circuit those would be like a signal while including one or zero but here it could be a basically a value or a valid kind of an element in the finite field usually in the context of uh kind of generalized proofs this could be an element in the finite field which you can think of as a number uh so we put some kind of a number here

it would propagate through the gates and you can connect them in various different ways you know for example let's say you have some gate here here this one will go here and then you'll have some output here so you basically put some numbers here and then as they go through these gates they undergo some transformation so it could be an addition or multiplication or it could be something more complex than that it could be like you know think about some polynomial like a formula that you would you know multiply it by something raised to power three or at constant and things like that so so so maybe like here it's adding some constant and here it's maybe squaring both of these wires and and so so we're just like representing this

long complicated computation exactly like and and it could really be anything right it could be something as complex as um as an elliptic curve group operation or a hash like anything that we need to do in yeah in blockchain world we can do in this model yep yep so this is kind of the way you describe uh or could visualize r1cs so now the other scheme that i described is air and the approach there is very different so here we think about the computation of the circuit here we think about the computation as a machine computation which starts with in some initial states and that you think you can think about the state as some

set of variables and then you apply a transition function to the state so you update those variables in some manner but you apply the same transition function with every step and you can execute it for many steps so if we were to draw it let's say we have something like this so so this looks more like what a computer is like like this is a circuit and it does one thing um but here the uh there's just the state transition that's repeated like a cycle and a cpu that's just repeated over and over yeah yeah i think acpu is actually a very good analogy for this where you have some you know state of registers in within the cpu and cpu executes an instruction and it updates those registers and with every instruction you update some or

maybe all of those registers and this is you get the same thing here so you do it many many times so you have a very uh you know the same transition function and then you get to that so if we had inputs here as individual wires here the inputs would be in the initial state and here the uh output was like one output here and then here output would be kind of in the final state so so each one of these cells uh is is sort of similar to a wire over there it's just a yeah i mean you can think about a state as where you know you could put the wires against um sure like this two adjacent rows for example uh and then but then you would have to have the same wires uh going for yeah you could actually think of like we

would compress the circuit and put them as transitions between these wires and then we would have to repeat the same circuit over and over between each two consecutive set of steps so these two different ways so like in many starks as i mentioned this type of arithmetization is being used and while in starks we use specifically this type of arithmetization and there are a couple of reasons why for example we couldn't use r1cs and starts because well main reason if we were to use r1cs and startx and i'll explain why in a second we would not get the the scale of the scalable the s would not would not work there or at least not that s um and so so i'm curious is um are these are each one of these arithmetizations better

suited for different applications yeah so um well let's go kind of through pros and cons of this and like we i think that will kind of answer the question so basically um with this type of a computation what you have to do is you need to fully describe the computation using these gates which means that if you have a loop for example you need to unroll it completely for every number of iterations um and you know that allow that gives you kind of like one one thing that it gives you is that flexibility of mix and match so like once i have this computation described it's very easy for me to like add another computation that output of which goes as input wires into this computation and then i have another

computation here which you know takes the output of this one as an input and so forth so i can compose them very very easily together so that's the big advantage that r1cs is here for example we have this repeated structure that happens all the time but you know so if we want to compose them together so like here i have four cells in the in a row so if i if i have another computation that has five cells in a row it's not clear how to put them together you can't really stack them very easily one on top of each other and you know it basically uh makes it extremely difficult to compose different gadgets together so to say while here you can have like standalone gadgets you mix and match them uh it works out well so so like if i had an elliptic curve

signature verification i could plug it in with some hash vari image and and it just would work and i would generate a new a new description for the circuit and it's easy exactly exactly now if we talk about like what advantage does this have over this and why this is scalable and this is not uh is that here for the verifier to be able to verify the program they need to understand the entire circuit because the circuit doesn't have repeated structure you actually need to kind of like read in all the gates and that means uh you know the verifier needs to spend linear time uh to to kind of understand what the program is there is a way to kind of avoid this and

that this way involves pre-processing and that is also what makes this non-succinct or non-scalable so you need to have somebody kind of read the circuit pre-process and basically commit to it and then the verifier can um can be sure that they when once they value the commitment or look at the commitment they know that which circuit this is related to sorry yeah go ahead but but but that's because like i i can tell you everything about this by just saying okay it's this one state transition function yeah you just need to examine one small transition function and then you kind of can learn everything about this computation but but with r1cs it could be like uh some elliptic curve operation

it could be a this like a balancing arrangement it's very difficult to infer repeated structure from this from this circuit okay yeah so and then one thing to know though that in depending on your application this pre-processing may not be a problem at all uh you might uh you know if you have a very well-defined program you can do risk preprocessing once and then you're sure like that this is the program and then if you need to verify against this program many times you kind of don't lose much in terms of the sinkness or ability to do it very quickly so in many contexts in blockchain like let's say the cache verification circuit you when you have a very well defined program that has been uh kind of like uh pre-processed uh one

so you can even pre-process it yourself if you would like um and then you can verify all the all the transactions using that one circuit but if you have something kind of uh kind of like this then you actually don't never need to do pre-processing so it's kind of like a little bit simpler um and also makes it scalable if you have very heterogeneous computations basically where there are many different computations where you would need to pre-process potentially circuits as they come in and then you had a question which i said we'll talk about later uh i think that might have been the scalable succinct okay which so so in practice like there's not that much

of a of a sort of overhead for for most applications for most applications again the difference for example if you wanted to deliver build a virtual machine i think it would be difficult using r1cs to build a virtual machine while for air it's a natural way to describe a computation or like an easy way to describe arbitrary computations using virtual machines so so like for for myden which is the vm that you're building at polygon it sort of looks like you can think about it as like a cpu exactly where every step is verified with azure knowledge proof and so that sort of fits with the air exactly exactly yeah i think you can probably do like a

virtual machine using recursive proofs where you know you have this description of the transition and then you kind of verify it recursively but this is uh you know an alternative and probably faster approach in many ways to do it all right so this kind of covers the arithmetization part and the second part that i mentioned is the polynomial commitment scheme so if we take we can probably erase arithmetization so polynomial commitments you know assuming we have those polynomials and now we need to kind of commit to them so the verifier can open them at you know a few points

they don't need to see the entire polynomial otherwise it will not be succinct uh or scalable for that matter and you need uh to be able to open them at a few points and kind of verify this this you know air complies with those polynomial air or you know whatever r1cs complies with those polynomials and there are different ways of doing it um so there are different types of commitment schemes so two of the more popular ones is kzg which is frequently used in snarks and then there is fry which is frequently used in starks and so so snarks kcg yes

but they don't i mean they don't necessarily have to you can mix and match and you can use one and it's just what is more commonly used um well well actually i've heard about this new proving system yes uh like plonky two yeah and they use it's a snark but it uses fry yes yes exactly so i mean you could also say it's kind of almost like a stark except for the pre-processing step i guess so it's very close to stark but yeah so there are different properties of this so one of the reasons why we use fry in starks is that you want you don't want to rely on any kind of well i guess

you want to be transparent so so no trusted setup no trusted setup and uh to use kdg for example you do need trusted setup so that's one of the reasons why if you use kcga with starks that's no longer stark technically so fry allows you not to use trusted setup and the reason why you know there are technical reasons for that but for example fry relies only on hash functions and you can kind of do this polynomial commitment using hash functions and you don't need to rely on any other cryptography where is casey where's kcg relies on elliptic curve pairings for example oh i should mention the third one is the ip inner product argument um based polynomial commitment scheme so this one

is also used a lot of snarks i guess over here and so this kcg for example relies on the elliptic curve pairings ipa like so it relies on elliptic curves or yeah just elliptic curves and fry relies on hash functions so ipa is also transparent for example this is an also transparent commitment scheme so it means you don't need trusted setup now one of the reasons why sometimes kcg is preferred is because the proof sizes are very small because you can do kind of like because you can use elliptic curve pairings you can think that you can compress a lot of information into just a few points on this elliptic curves so like

frequently proves that use kcg commitments are way way smaller than proofs that rely on fry or ipa and then and so not to this is sort of off topic but an elliptic curve pairing is basically like in elliptic curves we have the group operation and so we can think of that as addition um and then a pairing is a bilinear map that lets us sort of impose another operation and we can use linearity and uh shrink something not not to go no exactly and then if we wanted to like kind of say that this is probably fry has the largest proofs out of the three so this is large ipa has smaller proofs but still in kind

of kilobytes so maybe tiny yeah if i spell tiny correctly um yes so this is uh uh so we can get like just if a couple hundred bytes and that is enough for kcg frequently you know a few kilobytes or some somewhere in that range is enough for ipa and fry you know depending on the size of the computation could be like you know dozens of kilobytes so um that's kind of and and now what's the speed too because because we we can have yeah right because we can have fast proofs that are big and small proofs that are so interestingly uh even though fry has the largest proofs they're actually the fastest because uh

computing pairings is fairly expensive um you know elliptic curve operations are not as expensive as pairings but still you know requires some compute uh you know trivial amount of computation and then fry relies only on hash functions which are very very fast and they have been made fast uh you know over time and they in many cases you actually have hardware support for doing different you know specific hash functions so it's like very very fast to do fry proofs and so so to to kind of sum up polynomial equipments i can i can take a polynomial i can commit to it i can hand you the commitment and then i can prove to you that the value at some other point uh is is correct correct

well you need to yeah you prove that this what you've committed to is a polynomial of specific degree so you don't that's that's i think and then yes you open that polynomial at a given point okay cool i i think i'm starting to follow along okay we can probably erase this so let's go back to the question you asked so how does actually air arithmetization works and how do we get those polynomials going back to what i draw previously so like we can if we imagine uh our computation as a sequence of uh repeated states of a given you know uh which uh result from applying transition function uh to to an input we can think about like what we call an execution trace which is basically a matrix where there

are columns and there are rows yeah so where each row represents the state of that computation in a in a given uh at a given kind of cycle so to say so so that would be like the variables in the yeah the values of variables at that step of the computation so so again not to labor but i i start with a set of variables here yes and then i just do the the same state transition function every time and and that could be something uh like super simple like i could just add one to each variable or it could be something really complex like i could have like a cycle of uh basically cpu

that i can use to verify exactly evm transactions yep yep exactly so yeah so we can we have this execution trace and um the other important part of this uh kind of description of there so the first we've kind of described it as a set of kind of applying transition function is defining this transition function or like not necessarily a transition function itself but defining the relationships between the rows in the table and the simplest form is that we can take two rows in a table and we can apply a set of uh kind of equations to them and if equations this equations evaluate to zero then we say yes the transition was correct if any of the equations evaluate it's non-zero then we say the equation

is not correct so the the again the important aspect of this is that for us to encode the computation correctly if the transition is incorrect or if like there was one variable that was not set correctly at least one of this constraints should evaluate to a nonzero value so a simple example let's say which doesn't actually involve two rows but well let me think yeah so let's say we wanted to ensure that values in this column are always uh you know either the zero one and let's call this column like f0 something like that so what we would do is write this equation f zero squared minus f zero you know and this should be equal to zero

if we can see that this statement would hold true only if values in in this column are either zero one yeah because zero times zero minus zero zero one minus one right right and if we try to put like you know a value of two it would evaluate to some other value um so this is uh this is one constraint that is enforced against one of the columns but in our overall computation we want to make sure that we have many many of these constraints i mean it depends on the system but it could be dozens or it could be hundreds of this constraints or for some larger computations like an evm it could be even potentially thousands but yeah so you have a bunch of these constraints and this is how you get to your polynomials i mean there is there

is more stuff here but basically you can think about it kind of we need to evaluate these constraints on every two consecutive row so like you think we'll take these two rows and we get some result for this constraint then we would take these two rows and we'll get another result and then we would get this two well not this two sorry these two rows and so forth and basically we take every consecutive pair of rows and get some result by evaluating these constraints now you may want to say well you know this will always evaluate to zero on the entire thing so what's what's the use of a lot of zeros so we actually do something else before we evaluate these constraints on this table and this is called the low degree extension

and to describe and maybe let's erase this one with a lower degree extension does is that we take this column for example and let's say the length of this column is n and we would evaluate we would kind of interpret this column as evaluations of some polynomial on the domain of size n and not to get too detailed here but in the domain in this case would be like a multiplicative subgroup in the field that we're working in so one of the questions is like how do we know like uh once we know these evaluations can really get the polynomial back in coefficient form

and yes we can by kind of interpolating the polynomial and because we are in kind of this group the size of our domain is n we can uh when we interpolate this into a polynomial we'll get a polynomial of degree n minus one and this is kind of like you know follows from like high school math i guess where if you have you know two points you well yeah two points define a line three points define a parabola so like basically if you have endpoints you have a polynomial of degree of n minus one so and so we are are we uh interpolating with the values in those cells or just the constraints

so we're first step is we're interpolating as uh just values in those cells so um if you know kind of complexity of different algorithms you would say well interpolation is a very expensive operation it is you know the complexities of n squared and this will probably get expensive very quickly but one of the reasons why we do this in a multiplicative subgroup is because where there we can use a much faster algorithm algorithms for evaluation which is specifically like entity or number theoretic transform which is kind of a version of an ftt algorithm so that allows you to interpolate these polynomials in n log n time which is you know makes a world of difference between

n log n and n squared so um yeah so we do this if you erase this ones the whole matrix no just yeah this is fine so the next thing would be to like let's say we interpolate this and we get another table and now this would be let's say we would we run this like what is called the reverse entity algorithm intt and so so i guess we'll we'll just treat that as a black box and yeah it allows us to interpolate yeah we will not get into details of how this identity works but yeah what we get here like this was evaluations of this

polynomial so i would say maybe i should have left more space and here we'll also get our f0 but this would be coefficients so we'll get all of these polynomials in coefficient form now so we'll know you know actually the formulas describe that and so so again so we're trying to take um this description of a program and we're trying to put it into polynomials because then we'll be able to do some things we'll get to this yes yes we'll be able to do some things to to prove uh that our stark is yes the proof that all the relationships hold um

all right so the next step would be so now that we have polynomials in coefficient form the next step is um kind of like is part of this low degree extension is to evaluate over a larger domain and we do this for purposes of this read solomon encoding which i guess we will not get into well what's can can we talk about that sort of conceptually like why we would want to like what it is at a high level and why we wanted to uh well it reduces kind of this redundancy into the structure where that's one and then i guess once we do this result in coding we like increase the size of the domain and then

like it's easier to catch i guess like when you start querying these different points in this domain it's easier to catch the dishonest uh prover if they're trying to like cheat but i don't know how to explain it better maybe maybe we'll get into it with fry yes yes we'll get once once we get to fry we'll we'll get into it um okay so um so we do this extension and what this extension does if you like erase the lower part of this so i make i can make the table shorter yeah that's fine i'm just the same here and this extension basically let's say

we want to extend it by 2x or something like that basically keeps the number of columns the same because we still work with the same number of polynomials but now we have twice the number of rows so this is 2x extension and for this we use n t so so why do we want twice the number of rows again well so one of the reasons we want is because we want to like have this read solomon encoding um i guess the other number of rows like once we extend this like this let's say if i write the constraint here before that f f0 squared minus f0 should be well this expression like if i say our sum

you know c 0 this would be our constraint i should have put an x in there but fine um uh once we evalu evaluate this on a larger domain not all the values will avail evaluate to zero so we'll actually get some specific values for these polynomials and the degree if we think about the degrees of these polynomials that we have here so if we have here degree f0 was um well c zero is of degree two right so but this degree of f zero was um n minus one

so degree of uh like once we run each of these rows like the polynomial that we would get in this column would actually be um you know degree of yeah so in this case the degree of this c of x polynomial um you know because it is being composed with this uh polynomial degree of an uh degree of n minus one it would be actually like n two n minus two or i guess to make it more explicit n minus 1 times n minus 1 or

plus n minus 1. i think that's the right formula but basically you you increase the degree of the your your constraints and now you have like a polynomial it describes like if we didn't do it this extension and we try to evaluate this over let's say original domain this c of x polynomial would not fit into this original domain so we would lose some information in there as well yeah so like one of the things is that here i had a 2x extension and you know 2x extension is the minimum what you need to do but like in some cases depending on what your constraints are you could you need to do a larger extension so like if i had like a cube here for some reason so like if that was

my thing then you would see that the degree of this c of x polynomial would be bigger than 2n minus 2 so it would not actually fit into this just 2x number of rows so you would need to do a degree 4 extension one not degree but the blow up factor would need to be 4x because now it will not fit in there and then you know if you go even higher in terms of constrained degrees you would actually need to do much bigger blow up factor that's one of the reasons why you may need to do a blow up factor there are reasons why you may want to do a blow up factor is that the the higher the blow up factor is given the fixed degree

uh the fewer queries you need to do there is more redundancy introduced like read some encoding introduces more redundancy in the structure so there is fewer queries that you would need to do later in the fry protocol and that makes your proof sizes smaller so there is frequently a trade-off that you can kind of dynamically tune whether between the proof size and the proving speed it takes more time to do a higher extension or extension by a bigger blow-up factor but you need to do fewer queries so in that case your proof would be smaller but it would take more time or you can choose to have a smaller blow-up factor in that case your proof would be bigger but then the computing list would would take much less time and you guys use it very extensively in plonky

to where like in some cases you do blow a factor of 256 and that makes proofs very small but they take more time or yeah yeah so so i i think that's an interesting thing with frye right because if you there's that trade-off whereas in starks like if you're using kzg uh your proving time is a certain amount and your proof size is fixed but with fry we can have really really fast proofs that are really big but it's really not an issue because eventually we recursively aggregate them and then we can shrink that final proofs yeah it's really cool yeah i think uh and you know maybe i should have even

mentioned it before but starks in general have more of these levers that you can pull at runtime that are not fixed by kind of some given parameters you can choose uh you know uh different security levels dynamically for example you don't have to like while with starks with snarks once you've chosen your curve and things like that your security level is fixed you can't do anything but here without changing arithmetization or description of the program we can make a proof faster if we allow for or make it improve smaller if we are willing to tolerate lower security level and so forth so in general there is much more flexibility in many different levels that you can pull with targets and there are with marks yeah we couldn't uh we couldn't generate a circuit with a particular curve and then swap it out because that

would ruin our pre-processing exactly exactly all right um so once we get to the step uh i guess let's erase this and i'll draw the table with this constraint evaluations yeah so one other thing that i should have mentioned about constraints is that we frequently want to define on which rows the constraints hold so like um you know we can apply the constraints uh even let's say this um the original constraint that i draw which was like f0 of x

squared minus f of x you know we may not want to hold make sure you know have this constraint hold on all rows and frequently what we have is this polynomial we divide this by this vanishing polynomial or constraint divisor depending on you know which terminology and you use but for example if we wanted to for this constraint to hold hold on a single point we could potentially do something like what is it x minus uh you know let's say um well i need to get into generators so like let's say if i wanted to hold uh on the first row only we could do like x minus one

uh am i saying something incorrectly uh is that the would that be how you um yeah occur yeah so and if we wanted to hold hold this on the next kind of on the second row this would be times x minus you know in in our case we have this generator of this multi multiplicative subgroup which is omega and it would be omega to the power of one so which will be just a mech and the reason it's one here is because it's omega two power zero so uh and then we could keep going like we could say well we want this constraint to hold on the

uh on the next row and so forth so like x minus omega squared and that's uh until the end um so if you think about your like domain that consists of many many rows like you would think well this multiplication should take a long long time to do so how is it succinct well fortunately again because we're in this structure of multiplicative subgroup we can we can very succinctly evaluate this and i believe the formula is something like x to the n minus do you remember i think it's x to that and minus one for all of this multiplication

yeah yeah x to the n minus one so like in this case uh all of this like until the very end would basically evaluate to this so we can replace if you erase this yeah so we can just divide it by x to the n minus one and that would give us uh like a statement that basically says that this constraint should hold on all steps of the execution trace on all rows and then if we wanted to say like frequently for transition constraints we don't want it to hold on all rows we want to hold have the constraints hold on all rows except for the last one so what we could do is just take this and divide out the last point which would be

you know x minus omega to the power of n minus one yeah so frequently we we use this uh as like this is that full definition of a constraint which specifies what is the relationship and which rows the relationship should hold on so these polynomials encode the like the values in the rows and then this is a constraint on those effectively on those rows exactly yeah and and the x has a domain in this multiplicative subgroup that basically like steps through each of the rows yep yep exactly all right so going back to our drawings of constraint evaluation so um

we actually need to evaluate this entire expression for like for each row so like when we do our constraint evaluation i i lied a little bit before we don't just uh evaluate this we evaluate this whole thing and we would get some values here this is frequently fairly expensive because we need to do divisions and so forth so there are a lot of optimizations that we do in practice for example you know in our system what we do is we evaluate only numerators uh and then once all the numerators are evaluated we can combine all the numerators together based on what the uh kind of the vanishing polynomial is so for all uh constraints that have uh the same numerators we can combine them together and just divide them once

so um and the way we combine them by the way that's another interesting thing is that instead of like having you know as i mentioned there could be hundreds of these constraints and we can evaluate them separately and put them in a big table but it actually frequently makes more sense to kind of like evaluate them and merge them together so at the end you kind of end up with a single polynomial let's erase this one and i'll call this polynomial c of x and this is frequently referred to as a composition polynomial so we merge all of the polynomials together into one composition polynomial

and this composition polynomial the way we build this together or the way we combine this individual polynomials into composition polynomial is by using like randomness uh uh random coefficients that kind of in an interactive version of a protocol the verifier sends to the approver in a non-interactive version you kind of derive from like previously committed to values uh in a protocol so i i guess just to step through it uh for for my benefit as a beginner we have uh we have uh polynomials that encode uh values in each of these columns and we can impose constraints on those polynomials uh such that they

satisfy our transition function correct we had so like uh like f zero of one is this value f zero of uh you know omega i like we can think of it it's not two but we can think of it as two yep um i guess it could be two but um and so uh with that we can uh basically force that uh these constraints are only valid if those polynomial relations hold correct and then exactly we can can basically compress them all into a single polynomial but we have to sample some randomness because otherwise uh it might be possible for a malicious prover to pick values such that they like certain concerns might cancel out exactly so um

and this is to be clear this is an optimization step theoretically once you have this polynomial described and you've like you know computed them all you don't need to compress them that still you could still kind of uh let's say run fry individually on each of the columns but that would be fairly wasteful so we would like to do it right run fry only once because fry actually contributes the biggest part to the kind of the proof size is probably like 80 percent uh if not more sometimes is actually the fry proof so we want to do it only once and that's why we compress them kind of together into a single uh single polynomial the other thing to note is that when we do this compression um we need to as you said draw

randomness so like depending on which field you're in you may not get enough randomness so like if you're in a 64-bit field uh this is just not enough for random values there is too much probability well i mean not too much but from a cryptographic standpoint there is too much uh kind of intuitive to chance or potentially brute force attacks of some sort so we need to draw values from a larger field and that's where like for example would have to go to extension field i think that is probably too much to go in in detail to go into this but uh this is one of the reasons why if you run kind of like in a small field there is some additional tricks or steps that you need to take to make sure that you have enough soundness in your proof and but and and we like small

fields because cpus use small fields and so it's just more efficient if we can fit uh one field element right if we can simplify there and you know as you know multiplications uh complexity of multiplications growth super super linearly with the size of the uh i've heard it's n squared yes uh it was n squared uh complexity so going from a 256 bit field for example to a 64 bit field is not just a forex improvement it's more like you know 20 or 40 x improvement or something like that so so i guess to uh you know hopefully our viewers have stuck with us so far but but we we've taken we've taken a program

and we converted it into uh this matrix that where we start out with our initial values and we define our state transition function and then so so we we basically convert this program the execution of this program into a matrix where every row corresponds to like the state of the program at each step correct and then we take that matrix where all all these values throughout the entire computation and we convert them into polynomials and we with those polynomials we can uh basically enforce that uh like for every row that those constraints that we care about are

satisfied yes and then then we have some more tricks to kind of compress those polynomials into something that's a little more easy to work with now that we have this polynomial as we discussed we need to prove that it's of specific degree and this is where polynomial commitment scheme comes in where you need to come into this polynomial and we could use kcg as we said before but in star context because we want to have this tea we use fry and we also want to be very fast that's why we also use fry all right so what does fry do fry basically takes this polynomial um and very efficiently uh allows us to verify that well it takes a commitment to

something and very efficiently allows us to verify that this commitment to this you know set of values is actually a polynomial uh bounded by some degree um now again the naive way to do it would be to send the whole polynomial or a whole set of evaluations and let the verifier kind of read that and verify that it's actually the correct kind of polynomial and so forth but that would lose the sickness or scalability and and probably would not work in our context so what fry does it actually it's a very efficient and very ingenious algorithm it basically breaks the polynomial so if we now think about if you erase this one yeah we can do the whole thing

so we'll now draw our polynomial horizontally so let's say this is the commitment to the polynomial so what we do um sorry to stop you but but what does this look like what are the values in these cells well so the values in the cells would be also elements in the finite field so this is a you can think about as an array of elements in the finite field and then fry has this step where we reduce the size of this polynomial by half with every step or it could be more than half but basically we repeatedly apply this i'm sorry so so are these coefficients or what what do those elements correspond to

well in phry this is actually evaluations of the polynomial these are not coefficients i believe in kcg they are coefficients but in fry it's actually evaluations of a polynomial over the domain so this would be you know if we had our domain of size n yeah and we did the 2x extension this would be the domain of size 2n so um you know we would have evaluations of a polynomial um but it may help to think about it like initially as coefficients because we'll see so like if you think of this is you know a polynomial degree uh actually n minus one in contained in this here you can reduce it like and you can reduce the uh the degree of that polynomial it's like the the the process actually called the degree

is preserving degree respecting projection so we'll um degree respecting projection and what it does is that with every step folds the uh the polynomial by uh can onto itself almost by half um and reduces the mean by half as well so we basically go from n or to n to then n to then uh n over two and then uh until at the very end we can have a single just a single value another point um the verifier can send that single value to um well the prover can send that single value to the verifier and the verifier can as long as we can convince that this

degree respecting projection was done correctly at every step and we get that final value we can convince the verifier that our set of values is actually a polynomial so so we send this and then or so so if i'm the approver i do this process and then i send you this and then i'm going to go through another we're going to play another game so i can convince you that this actually commits to the right polynomial right well so you need to we need to be convinced that that comes to the right polynomial but also we need to be convinced that these degree respecting projections have been done correctly and uh the way we do this um is uh so let's talk about first what a degree respecting projection would be so the way to think about this if we

have a polynomial which is like let's say simple one x to the power three mine you know some i guess a b to x to the power of 2 plus c x to the power or just x plus d right so this is our polynomial the way to fold it in half could be just take the odd and even coefficients of this so we could group this as you know a x cube plus c x plus b might be is like a six squared plus d so like we think about this as

two kind of separate parts and then we can just move x out of here and what would we get is x here a x plus c and here we would get x yes b x squared plus d and this is a b um so we inside here we get two polynomials of the basically the same degree now so like uh this is and you can notice well i guess it's not half but if you think about the domain size it's half you need half the domain size to do this so the way we combine them together is um uh we again take this random coefficients and like add them up and we

kind of like end up with a single polynomial now with degree like uh abcde so let's say it would be e x squared minus some let me see f so this is our new polynomial after we went through this degree respecting projection where like the coefficients e and f are basically kind of a combination of coefficients from previous these two polynomials mixed in with some randomness so that the prover or cannot pick like the values that we will make them cancel out and then we repeat this process again and again until we get to a smaller value now this and i probably should have started with that the fry actually consists of two things there is a commit

phase and the query phase of the protocol so the commit phase is kind of doing these things where prover does this the degree respecting projection and commits to each successive layer and sends the commitment to the verifier and then once the commit phase is done we then start the query phase where the verifier now asks the prover to send like picks random points in this domain and asks the approver to send all the relevant values for each layer from this from this domain and then the verifier queries uh kind of get those points and make sure that like computes like a slightly different uh expression but it's an expression that allows

verifier to be convinced that the this formulas were computed correctly at each step so we we can't again just send all of this information because we it wouldn't be succinct so we have to send like some small subset of it uh to get the scalability property that we want yes yes exactly but by the end of this query phase um the verifier now is no knows that this is a polynomial of the uh of a given degree and then there is some more work left here to how do you tie this polynomial back to the original trace and there are several methods to do that one of them is the deep method where you actually do another sampling outside of the domain and that allows you to kind of tie all the models together we didn't cover it

in this in this session but the other approach is to kind of do query the original execution trace in multiple points in the consecutive rows and do this constraint evaluation and have enough of those points that tie back to this uh polynomial as well so there are kind of different ways of doing that with i think the dip method has an advantage because you reduce the number of uh kind of this computations that the very fire needs to do to figure out on how many like what are the constraints at a given point um but yeah so this is uh the fry protocol so so now we have we have our arithmetization so we've taken our uh we've defined our program and we execute the program outside of

azure knowledge proof and so that execution allows us to fill out that matrix with all the values from each step of the computation correct and then we take that matrix and we can convert that into polynomials for each column and we can enforce constraints in those polynomials that basically make it possible to check that that state transition is valid and so now we have those polynomials which we compress and but i can't as the prover just send you that polynomial because it wouldn't be succinct like its size would be basically linear in the in the size of the computation so then we run fry to get a succinct commitment to the

polynomial which is uh in the form of queries uh in this so so i i guess not to uh take a tangent but but we um we make this a merkle tree that allows us to uh one of the things that i didn't mention is that you know it's more abstract commitment but in reality as for commitment purposes we've just built miracle trees and sun the roots of this merkle tree to the uh to the very fire bobbin what does one thing that we missed what does fry stand for so fry stands for fast read solomon uh iop which itself stands for

interactive oracle proof of proximity oh oh oh i opp iopp yes yeah yeah cool and so an interactive oracle proof in the zkp context basically just allows us to like sample like sample a few points in such a way that we can like guarantee with high probability that some polynomial relation holds correct correct cool well uh yeah this has been a great conversation i've uh yeah learned a lot and it's been a pleasure same here thank you [Music]