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

[music]. 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 into zero knowledge proofs and starks quite a while ago, like late 2018, and 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 musebasement. Yeah, so maybe, if we start really basic, what, what does stark stand for? So starks? Actually, so stark says is a zero knowledge proving system, and the acronym stands for scalable, transparent arguments of knowledge. And you might have heard about snarks and starks and so you know there's another big category, snarks, and a little known fact: that 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, and another difference is that hold up. Show more

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, for example, for starks, you don't 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 is succinct, you don't need to. With this, basically, it's exponentially faster to verify, approve, than it is to run the computation. Show more

So so we have a big computation, yes, yes, exactly small proof, or fast to verify. And 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. Show more

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, that 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 when we want to to build azure knowledge proof, we have to do this thing. That 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. So this kind of, i would say, high level differences and they were much more important originally. Now the lines are blurring so you can have transparent snarks as well 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 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 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. Show more

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 that are used to build both starks and snarks, and the first component is called arithmetization and the second component is polynomial commitment scheme. Show more

So you can mix and match different types of this and we'll go- and i'll go into more details in a second, but you can mix and match different rate mutation and polynomial commitment schemes to get kind of different properties out of zero knowledge proofs. So as an example, well, yes, veil of ignorance here, 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. Show more

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 to make sure that those polynomials have bounded degrees of you know, some sort. Show more

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. Show more

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, system, maybe system, but yes, so. And the other approach is air, and this stands for algebraic intermediate representation, or some people say arithmetical intermediate representation, and you know there are different ways of thinking of how you take a program and describe it using polynomials. Show more

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 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 draw out like a circuit, so let's say we have some inputs, we have some gains. Show more

Now what? What do those inputs look like? So 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 kind of generalized proofs. This could be an element in the finite field which you can think of as a number. 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. Show more

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 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 or could visualize r1cs. So now the other scheme that i described is air, and the approach there is very different. Show more

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 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, 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 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 is is sort of similar to a wire over there. Show more

It's just a. Yeah, i mean, you can think about a state as where you know you could put the wires against, sure, like this, two adjacent rows for example, and then, but then you would have to have the same wires 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, and so so i'm curious is: are these, are each one of these arithmetizations better suited for different applications? Show more

Yeah, so 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, 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. Show more

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 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. 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, 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. Show more

You actually need to kind of like read in all the gates, and that means you know the verifier needs to spend linear time 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 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 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. Show more

You might. 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 kind of like pre-processed one, so you can even pre-process it yourself if you would like and then you can verify all the all the transactions using that one circuit. But if you have something kind of kind of like this, then you actually don't never need to do pre-processing. Show more

So it's kind of like a little bit simpler 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. 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. Show more

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, 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. Show more

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 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. 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. Show more

You can mix and match and you can use one, and it's just what is more commonly used, well, well, actually, i've heard about this new proving system. Yes, 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 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 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. Show more

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. And then a pairing is a bilinear map that lets us sort of impose another operation and we can use linearity and 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. 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 that's kind of. And and now what's the speed too? Show more

Because because we we can have- yeah, right, because we can have fast proofs that are big and small proofs that are so, interestingly, even though fry has the largest proofs, they're actually the fastest. Because computing pairings is fairly expensive. You know, elliptic curve operations are not as expensive as pairings, but still, you know, requires some compute, you know trivial amount of computation. Show more

And then fry relies only on hash functions which are very, very fast and they have been made fast, 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 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? Show more

Going back to what i draw previously, so, like we can, if we imagine our computation as a sequence of repeated states of a given you know, which result from applying transition function 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 at a given kind of cycle, so to say. Show more

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 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 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 the other important part of this kind of description of there. Show more

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 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. Show more

So let's say we wanted to ensure that values in this column are always, 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. Show more

So this is: 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. Show more

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 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. 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 interpolating with the values in those cells or just the constraints? So we're first step is we're interpolating as just values in those cells. So 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. Show more

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, 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 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 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 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. Show more

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 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, 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, 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. Show more

So if we have here, degree f0 was well, c zero is of degree two, right so, but this degree of f zero was n minus one. So degree of like: once we run each of these rows, like the polynomial that we would get in this column would actually be, you know, degree of. Yeah, so in this case, the degree of this c of x polynomial, you know, because it is being composed with this polynomial, degree of an 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. Show more

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. Show more

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, the fewer queries you need to do. Show more

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. Show more

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, 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. Show more

Yeah, it's really cool. Yeah, i think- 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, you know, 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. 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. So once we get to the step, i guess let's erase this and i'll draw the table with this constraint evaluations. Show more

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 you know, we can apply the constraints, even, let's say this, the original constraint that i draw, which was like f0 of x squared minus f of x. Show more

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, you know, let's say, well, i need to get into generators. So like, let's say, if i wanted to hold on the first row only, we could do like x minus one. Am i saying something incorrectly? 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, and then we could keep going like we could say: well, we want this constraint to hold on the on the next row and so forth. So like x minus omega, squared, and that's until the end. 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, 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. Show more

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 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 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 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 and then, once all the numerators are evaluated, we can combine all the numerators together based on what the kind of the vanishing polynomial is. Show more

So, for all constraints that have the same numerators, we can combine them together and just divide them once. So, 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. Show more

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, 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 in a protocol. So i i guess just to step through it, for for my benefit as a beginner, we have, uh, we have polynomials that encode values in each of these columns and we can impose constraints on those polynomials such that they satisfy our transition function correct. We had so, like like f zero of one, is this value, f zero of, you know, omega i, like we can think of it. It's not two, but we can think of it as two, yep, i guess it could be two but. And so with that we can basically force that 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 it might be possible for a malicious prover to pick values such that they, like certain concerns, might cancel out exactly. So, and this is to be clear, this is an optimization step. Show more

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, 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, 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, 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. Show more

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 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 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 one field element right, if we can simplify there. And you know, as you know, multiplications, complexity of multiplications, growth super, super linearly with the size of the. I've heard it's n squared, yes, it was n squared- complexity. Show more

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 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 basically enforce that, like, for every row that those constraints that we care about are satisfied. Show more

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 allows us to verify that. Show more

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 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. Show more

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, you know, we would have evaluations of a polynomial. Show more

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, the degree of that polynomial. It's like the, the, the process actually called the degree is preserving degree, respecting projection. So we'll degree respecting projection, and what it does is that with every step folds the, the polynomial by can onto itself almost by half and reduces the mean by half as well. So we basically go from n or to n, to then n, to then n over two, and then until, at the very end, we can have a single, just a single value. Another point: 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. Show more

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 the way we do this is. 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. Show more

So we inside, here we get two polynomials of the basically the same degree. Now. So like 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 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 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. Show more

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 kind of get those points and make sure that like computes like a slightly different 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 to get the scalability property that we want. Show more

Yes, yes, exactly. But by the end of this query phase the verifier now is no knows that this is a polynomial of the 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. Show more

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 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 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. But yeah, so this is the fry protocol. Show more

So so now we have, we have our arithmetization, so we've taken our, 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 in the form of queries in this. So so i, i guess not to uh, take a tangent, but but we, we make this a merkle tree that allows us to. 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 to the very fire bobbin. What does one thing that we missed? What does fry stand for? So fry stands for fast read solomon 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, yeah, this has been a great conversation. I've, yeah, learned a lot and it's been a pleasure. Same here, thank you. Show more

[music]. Show more