ZkStudyClub: Part 2 Polynomial Commitments with Justin Drake

Transcript

All right, so this is the second edition of the polynomial commitments DK study club session with Justin Drake. Um, we today we're going to actually continue on from what Justin had started last 2 weeks ago. Uh, I think if you haven't already it's probably good to watch that video. Um, I think the plan for today is to go very quickly through those slides and then launch into the second part. And I think we'll leave it up like again to time. So, Justin, if you wrap up quickly then we can end in an hour. If you don't, maybe we can like schedule something for the new year or for the holidays.

Um, but yeah, welcome again. Okay, great. Thank you. Yeah, so I'll just quickly go through what we covered last time, uh, very quickly and then slow down where we left it. Uh, Anja, can you share the link to the slides? Yes. Um, Anja, can you share it in the Telegram? Sure. I'll do that. Thank you. Is it It's the same slides as last time, right? Yes. Great. Okay, so polynomial commitments they're like this really cool cryptographic primitive, uh, super useful in the context of universal SNARKs, uh, which is kind of the the new hot way of building SNARKs.

Um, oops. Um, so, you know, the basically I started with giving some context including historical context on, you know, when these polynomial commitments were first defined. Um, the first construction was by Kate and all in 2010. And then we saw kind of Bulletproofs and FRI kind of gave uh, polynomial commitments but kind of hidden. Um, um, and then, you know, we have this IOP and polynomial commitments kind of framework and we've had lots of innovation on the, uh um uh, IOP side of things. Um, and um, now we have this this is kind of

explosion uh, partly because we we better understand I think kind of the separation of concerns between the cryptography the polynomial commitment and the IOP. So I think this is a really nice framework to to innovate on in the future. So I kind of briefly gave the definition of polynomial Oracle and polynomial commitment scheme. And the idea of an Oracle is it's kind of a an abstraction which kind of tries to encode the a polynomial which could be extremely large with lots of coefficients into just a a single object which can be

queried. So you can make a query which will be asking for the evaluation of that polynomial at the point. And then we have the equivalent commitment scheme. On the cryptography side of things. And then we you know we have some formal definitions for cryptographers and by cryptographers. And then this is kind of the framework that was uh presented. So we have kind of three three buckets. We have kind of the computer science bucket where there's a lot of compiling going on. You have code and then you compile it into programs and RAM programs or circuits

and then you encode these into polynomials and things like that. And then you have this information theory land where you have the interactive Oracle proof as kind of the the meat of your proof scheme and then you have the polynomial commitment scheme here. And then at the end when you mix I mix all this you get a universal snark which is very nice. And yeah like different flavors of soundness. We go from perfect soundness, to just statistical soundness, and then computational soundness.

And then um kind of if we look at um the different oracle types that you can instantiate, which are alternatives to uh polynomial oracles, you know, you can think of set oracles or vector oracles or low degree test oracles, or even inner product oracles. And kind of there's this hierarchy because they have different um kind of power, and they're kind of related to each other um locally and um kind of historically the way we've built start SNARKs is is with this inner product um argument, uh which is kind of very costly because you either have to pay uh on the verifier time, so you lose

succinctness, for example, in the case of Bulletproofs, um or you have to pay with a trusted setup, which is not universal. Um and so we've kind of dialed it down to just this polynomial commitments uh scheme, which kind of reduces the expressiveness of the um of the PCP, but uh it's still, you know, powerful enough to do everything we want to do. Uh That's kind of great news uh here. So we found the sweet spot is the commitment here. And then I kind of gave an overview of Okay, what are these schemes in in practice? So we have kind of four flavors.

One, which is basically based on FRI, which is basically hash functions. Um And here you basically, the way that you commit is you um you evaluate your polynomial over a domain, um and then you take the the Merkle root of these evaluations, and that's your commitment. Um you have pairing groups, um where you have this kind of a powers of tau, so you encode a secret, and then basically you evaluate your polynomial at that secret point and the exponent um and then you have groups of unknown order um where here you do something very similar except that there's no secret.

Um and and then we have the final flavor um my slides will load um which is based on uh on the discrete uh log. Uh which is also very similar to the previous two and and these three are kind of um very algebraic whereas this one is is not so algebraic. I mean, it does use algebra a little bit because it's based on the on the roots of unity, so you can do clever tricks uh but it's it's very much a information theoretic uh construction this one.

Um and then we kind of saw kind of the the the benefits and the downsides and basically there's a there's a very large trade of space that you can uh uh pick from. So, you if you you know, you can have transparency, you can have um post-quantum, you can have an unbalanced setup um all all all these things are very different constructions. And even within the groups of unknown order, we kind of have these two flavors. We have the RSA group and the class group. Um and then in addition to kind of comparing performance uh comparing setups um and in terms of the the the qualitative properties, we can also look at them in terms of the quantitatively like um what are the performance and

um there's also kind of a wide uh a wide uh trade-off space. And this is kind of where we left it uh last time. Um and you know, one of the comments that was made here was that this is a little unfair because we're basically um hiding the um the the the security parameter in in in various places. And so, it means that we're not really comparing um kind of apples to to oranges. So, for example, on the on the prover time and the verifier time, these are different operations. You know, these are multi-exponentiations uh inside a group, and you know, these are, you know, um hash operations.

So, I I just wanted to give a little bit of flavor um uh regarding this uh the security parameter. And so, what I'm going to do is basically give you the the the breakdown for the um for the commitment. So, right. I I, you know, I I mentioned that basically all these commitment uh polynomial commitment schemes have a constant-size commitment. Um but actually, in in in in practice, the the the commitment is is has a different size. So, no um So, uh you know, we have uh for example, the

uh in in FRI, you know, your commitment will be just one um hash hash function outputs, uh whereas for all the other ones, basically, your your commitment is going to be one group element. And these groups are going to have uh different sizes. And basically, the the the for for the for the algebraic um constructions, the the size of the group is um going to contain these relatively large um powers of lambda. So, you have lambda to power three, lambda to power three, and lambda to power two.

And you know, relative they're large relative to, for example, the the the the hash function here. Um and the reason is that you have these kind of subexponential um attacks here. So, um So, the the the kind of um algebraic attacks, which are sieve-based, so you have the uh general uh number field sieve algorithm, for example, that that is used. Um and this is kind of interesting to to see that there is some correlation between um the asymptotics of of the attacks and kind of the actual size um of your of

your group elements. So, for example, if you look at RSA groups and class groups, they're both groups of known order, but there's kind of different attacks that are known here. Um uh and so, this will mean that for RSA, if you're targeting 128-bits of security, you actually have a larger group group size and um 3,000 bits versus a class group, which is going to be only 1,800 bits. And um these these discrepancies between the various um commitment sizes will also reflect in the proof size. So, basically, you know, you have a factor of, let's say, 10

difference between a SHA-256 output and a um 3,000 bit um RSA um group element. And um this is something that I'm sweeping under the rug when when you consider um here and and here the the proof size. So, you're going to have something similar. And you know, this this table here also kind of sweeps under the hug rug um a bunch of uh detail regarding the verify time and the and the prover time. So, for example here um you know, the pairing will um will have a a bunch of of lambda terms, uh which,

you know, in practice will actually mean that you're you're comparable to to fry for example which has a a log log d squared so I mean one one way to to to simplify and and compare these is just to set kind of log d to be equal to lambda and then and then you have a way to compare them kind of apple to apple on on the on the bit level operation some points Okay so that that was just kind of an addendum to the previous talk just to give a little bit of flavor as to as to what's

what's going on with the the lambda terms here and it's kind of and the what I like to talk about now is kind of actual mechanics of how the the schemes work so I've told you how the commitment works but I haven't told you how you actually do the openings so any questions so far seems good also just just to note anyone who's kind of new to this if you do have a question kind of like and don't want to interrupt you can also put the note you

can put it in the notes we're sharing through there's a chat here and we can collect those for the next time Justin takes a pause Okay great so let's let's look into like how these schemes actually work and you know you'll notice that um like three of these schemes the the fry dark and bulletproof they have they have these log terms and this is this is not a coincidence and the reason is that the way they're they're built is you know you have this these log number of rounds of interaction between the prover and the verifier. And every round of interaction will have kind of a a constant size overhead in the in in

the uh well, at least constant size overhead in in the in the in the proof size. So, um And And what what I'll do actually first is, before giving you the the full polynomial commitment scheme, I'll give you something slightly weaker, which is the the low degree test. Um for for all the the the the the the flavors. So, you have your prover, you have your verifier, and they're talking to each other in in these three schemes. Um and there's a a log uh number of rounds. So, D is your the degree of your polynomial. You have log D rounds.

Um and in in every round, the verifier is just sending a a random challenge. So, it's a it's a public coin uh protocol, uh which can be made non-interactive with Fiat-Shamir. And basically, the way that the low degree test works is that you you start with the the commitment, which uh you know, the the prover uh already sent, and then there's some sort of reduction step. So, um to go from from f of 0 to f of 1, you basically reduce, and this reduction step is seeded by the randomness that was given by the the verifier.

And so, the point of this reduction step is that you go from a polynomial of degree D to one of degree D over 2. So, you keep having and having and having having, and after log D steps, you end up with a constant polynomial. Um and kind of constant polynomials are very, you know, easy to work with, and the kind of the the verifier can can can check that um everything is is consistent at this at this lower level. And um so you have this this constant polynomial check and then you kind of work the verifier will kind of work itself all the way back. So if this if this is constant, if f sub log d is constant,

then the one just before is of degree you know, two. Um or actually maybe one and then two and then four and then eight and 16. And so that way you you get your low degree test. You can prove that well, the verifier can be convinced that indeed this this polynomial f of zero was was small. And and it it turns out that if you this framework can also be used with with pairings. So um all all four flavors of commitment schemes that we know can can can be made to to fall into this framework.

Um it's just that for pairings we have this extra power that means that we don't even need to do all this interaction. We can just do it in one go. Um so you'll get even shorter proofs with pairings, but if you want to, you can go through this this framework. Um so what I need to tell you now um so you already know how the commitments work. Um and and you have this framework. So all I need to tell you really is this uh reduce function. What is it What is the reduce function and kind of what are the the consistency checks.

Um and it turns out that there's there's only so many ways that you can take a polynomial of degree d and split it and kind of reduce it into a polynomial of half the degree. And so you kind of have this um this even odd decomposition which is kind of the the Fourier decomposition. So, you take the uh, the the even, um, powers, you take the odd powers.

And then, each each of even and odd are individually, um, half half the degree. Or, you can think of the left-right decomposition, uh, where you take kind of the the the the this the coefficients for the this the small monomials, and then those for the uh, large monomials um, half and half, and then you you also get, um, kind of two polynomials of of degree, um, n over two. Um, and so, basically, each each scheme uses, um, uses slight diff- a slightly different variants, uh, on on the decomposition. So, for

example, FRI will use the even and odd decomposition. Um, I mean, it turns out you can also use the left and right decomposition, but you get slightly something slightly less efficient, uh, because you you you can't use the same kind of uh, Fourier-like, um, algebraic tricks, um, to, uh, to basically, uh, shrink by half the domain every time. But, yeah, that's a technicality. So, they use even and odd, and then you have, um, groups of unknown order, which kind of use, uh, left and right. But, it turned out here that you could you could also use even and odd, and the scheme would

work, you know, just as fine. And then, um, and so, actually, just to back up here so um, you know, the the the very standard way of, uh, combining things in in in cryptography is just to take a random linear combination. And and so, this is what we're doing here. R is the the randomness and so we're taking a a random linear combination of these these two things. Um and so the R is going to be the the randomness from the from the verifier. And then in Bulletproofs, we do something um kind of like the groups of unknown order, so we split in left and right, but we we do something two things that are a little different.

So one is that instead of taking just this unbalanced um linear combination where basically you have a you have a factor of one and a factor of R here, you have this more kind of balanced linear combination where you take R here and R inverse. So there's kind of this this nice symmetry. And in in addition to um doing a a decomposition at the at the level of the coefficients of your polynomial, you're also going to do a random linear combination, a similar one, for your um for the basis elements with which you do the commitments.

So it's kind of a slightly trickier scheme because you um it's it's just a slightly more complicated reduction. But if you want kind of the the the universal reduction that works um that would work for all schemes kind of optimally, it would be um R times even, so R times even plus R inverse times R. Right, so basically um it turns out that Bulletproofs you don't need to use left and right. You could also use even and odd. Um and in in these two schemes, uh you know, it's it's perfectly fine as it is balanced, but um you know

it turns out that the way that these papers were written were were not you know, in in the context of this more general framework, but it turns out that this there's this one kind of universal reduction function you can use, and it would work for all all the schemes, uh which is kind kind of nice. Any any questions so far? So, we have this framework where we have commit, reduce, commit, reduce. Every time the commitment uh is is of a function that that that that goes reduces in size exponentially, you have a a log number of rounds, and then you have these consistency checks, which I haven't gone into yet.

Um I have a question about the coefficients and basis. Like, can you go can you maybe explain a little bit more what those two things are? Cuz I think you just sort of threw them in, but I they're I'm not familiar with that. Yes. Um Okay, so that that actually goes back to an old slide. Aha, this one here. So, the way that you do the um the commitment in Bulletproofs is you have the the the coefficients of your polynomial A0 up to AD, and you you need to do it relative to a a basis. So, basically, you have these uh random elements G G G0 to GD, and

they were they're independent from the discrete log perspective. There's no discrete log relationships between them. And so, you can think of them as being basis vectors in this vector space. And so, your commitment will be just this one point in in in the vector space. And it's kind of very similar to to this. So, you can think of you know, Q to the I times G as being kind of your your basis element, and you can also think of this the same thing here for the with pairing. So, we have S to the power I times G1, G1 being the generator of

of your your big G1 group as also being the the the basis elements. Um so, yeah, these three schemes are very very similar to each other. Um and it it turns out that the way you do the reduction, you you don't have to mess around with the basis elements here. So, you just keep using S to the power I and G1, and you keep on using Q to the power I G. But, for bullet proofs, you need to do you need to be cleverer. Uh and the reason is that when you work with a discrete log group, it's just less powerful. It's less flexible. So, you have to to do a bit more gymnastics.

Okay. Um So, now now I now I need to kind of go go into the the consistency checks. Um and this is where the scheme is kind of uh become slightly different. Um so, in the case of uh FRI, um this is going to be your your your consistency check. Um and it it kind of looks um a little bit strange, but basically, if you if you take the two to the Z and you um you you you you you you divide it out everywhere. I just put two to the Z on

this side. Then, it turns out that this part is going to be the even part, um and this part is going to be the the odd part. So, um you have this uh this evaluation point uh Z, uh which was kind of chosen at the very at the very end of the protocol, there's a uh a random uh evaluation point by the verifier and it turns out that you can kind of check consistency of f i of z, f i of minus z, and f i plus one of z squared.

So, if we if we kind of go back to this even odd decomposition, if you feed um if you feed z here on the left-hand side, you're going to get z squared here and z squared here. And if you if you feed minus z, well, the minus sign is going to to go away. So, you still get z squared here and z squared here. What changes is that you get a minus sign here. So, you have um kind of two linear two linear equations with with two unknowns, and so you can you can kind of solve it.

And it turns out that um you can basically solve for the even part and for the odd part separately, and this will be the even part. This will be the odd part. Um and this will be your your your z squared. And for every opening that you have here, um you have a corresponding Merkle path. So, if I if I go back to to this to this picture here, every commitment here is a single Merkle root. It's So, you commit to Merkle root, commit, commit, commit. And these commitments are going to be commitments to evaluations over a domain.

And so, um you know, you you can I'm just going to explain why the square where does the square go. Aha. So, the the square comes from here. So, basically um even and and odd, like the relationship between F even part of F and odd part of F, you have this square part here. So, So, what creates this?

Sorry what? What creates this? What creates this? Okay, so let's say that you have um uh a polynomial and you want to take the even coefficients and you want to take the odd coefficients. Now, if you just take the even coefficients and the odd ones, um then the this these these these polynomials are still going to be of the same degree as D. So, basically, uh if your polynomial is going to be, let's say, x to the power 4 + x squared and you take the even part, you're still going to have x to the power 4 + x squared.

Um you haven't reduced the the degree. So, what you need to do is you actually need to to consider the left part as a polynomial in x squared. So, as a polynomial in x squared, you're going to have x squared squared + x squared. And then, basically, if you want to consider as a polynomial in a in a new variable Y, you're going to basically have a Y squared + Y. Does that make sense? So, But Um the the reason you get the square is because once you do the decomposition into even and odd parts, you can kind of collapse all the squares into a new

variable Y, where Y is equal to x squared. Cool. Thank you. And once you collapse do this collapse this collapse this collapse, um you basically have a a polynomial of degree half the size. Um Yeah, so if you if you just work through an example, it will it will become very very very clear. Um and in order to do the collapse on the odd parts, you have to do a little bit more work. Basically, um you need to to to extract um an an X coefficient because you have all you have all odd uh powers in the monomial. So, you extract one X, and so you're left with um all evens.

And so there, you can again um uh kind of collapse the the the even ones into a new variable Y, where Y is equal to X squared. Okay, so you One more question. Yeah. Um uh about the next slide, actually. Is the consistency check is it the same for FRI versus deep FRI, or is it different for deep FRI, do you know? Yeah, so deep FRI, they from what I understand, it like the the new idea is that this point Z is outside of the domain. It's kind of outside of the box.

Um And so here, in FRI, you you you choose Z to be within your evaluation domain. And what that means is that um you can have a direct opening proof. You have this Merkle root, and you have the evaluations, and you can just open them by providing the Merkle path. Once you evaluate outside of the domain, you know, it it kind of gives you more flexibility as a verifier, because now as a verifier, you can check anywhere in the whole, you know, in the whole field.

But now, you're putting more burden on the prover to convince you that that the opening is is the correct one. And I I actually don't know exactly how how deep FRI works. Um I mean, does anyone on the call, um, know how how a verifier would authenticate the claimed openings, um, outside of the box? In the context of the prime? Uh, so what I do know is that It's like it's a no.

Um, yeah, I mean, it's on my to-do list to to read read read the prime and understand it. But what I do know that you get a better soundness. Um, so uh Yeah. So this is like a a half guess, but I think one way to do it is they they think of uh, the polynomial like f minus f of z divided by x minus z. And now if you have evaluation of f on a limited domain that doesn't include z, you also have the evaluation of this thing.

Right. limited domain. And you sort of you're sort of using it like a polynomial commitment scheme and now you can your evaluations of f on a limited domain give you evaluations on a limited domain of this thing. And you can use that to prove what f of z is. Uh, that's my half guess from things I heard in talks. Yeah, so I think that makes a lot of sense because, um, this trick that you just talked about where you consider f of x minus f of z divided by x minus z, this is something I will talk about next

and it's how you kind of take fry and make it into a polynomial commitment scheme. And this was kind of noticed by the matter labs people and they kind of noticed it after reading the deep fry paper because the deep fry paper kind of uses this this exact same lemma but in a different context and I guess this different context is evaluations outside of the box. Um Okay, that makes a lot of sense. So if you're slightly, you know, more clever you don't have to pick Z which is within your domain. You have this this trick which I will talk about in a few slides.

Thank you. So just to to recap this this consistency check is basically it it basically encodes um this this equation here. There's nothing other than this equation and the um the the the purple bits will be uh you know, part of the of the proof. So that they'll be proof elements. Uh so you have log a a log number of these because you have log number of rounds. Uh but the reason why you have this two factors of log in in fry is because each one of these elements also comes with a Merkle path its size itself you

know, of of log size. Okay so um now let let me go to to docs. So if you recall the the commitment scheme um I'll just say it again for for docs. So you have this you have this group of unknown order and then you pick one uh generator and then you you take um this this generator times f of Q where Q is a very large uh uh, integer. So basically you take your polynomial, you encode it into an integer,

and then you commit to the integer in the group of unknown order. Um, and this this equation here basically is the the exact kind of analog of of this equation uh, uh, uh, of this equation here. Um, or maybe Uh, yeah, this one. So, basically, you're going to have um, this this uh, this sum, and you're going to have the the multiplication by a by a shift.

And so, multiplying by Q is the same in in your commitment is the same as multiplying by X in in the in the polynomial land in the uncommitted land. Um, and it turns out that um, if you take the sum of the commitments, you get the commitments of the sum. So, you have this um, uh, this this nice linear property, uh, linear homomorphism.

And so, it you can just directly work with the commitments, and it it's it's it's all simple. And the and the RI here is the going to be the random linear combination. So, again, just to to recap, you have a a polynomial F which has a certain degree, you break it up into two um, smaller uh, coefficients, even and odd. You take a random linear combination here, and then you do the consistency check. Um, and here you have this nice kind of superpower of the the commitment scheme for Darks, which is it's kind of fully homomorphic in the sense that in addition to being additively homomorphic,

you have this shift homomorphism. So, you can multiply by X and multiplication by X is the same as multiplication by Q in in commitment plans. Does that make sense? There's a little question in the chat if you want to take a look. From Ivan. And also, Ivan, if you want to say it. Uh yeah, sure. So, I might be mistaken here, but uh f i + 1 should be f i at the reduction, right? So, shouldn't this be like uh in the reverse order in the groups of unknown order?

Yes. Yes, it does it does look like I messed up my i's and i + 1's. Yes. All right. Thank you. Yeah, and and and and George is asking um is that the order should be unknown and big enough? Um So, yeah, so you you you kind of have two kind of big enough things here. So, first is you have the group of unknown order in in the in the basic kind of construction of your of your group, and that just needs to be big enough and kind of just difficult to compute the the group of unknown order.

But, there's another big enough that comes in, which is this this Q. Um and it it it it turns out that um in in order to do these um these to apply the homomorphism, so to apply the addition homomorphism, and to apply the shift homomorphism, you need to make sure that the encodings of your polynomials don't overflow. Um so, you have uh you You if you if you consider um kind of polynomials when you manipulate with them, the the the the coefficients of every monomial is is independent

um and will will not interact with the other ones. Uh but um when when you work with uh integer encodings of polynomials, then it becomes different because integers, when you multiply them, you have you have carries. So, in order to avoid the carries, you just need to pick a large Q. Um And so, what you're going to do in in in Darks is when when you reach the um when you reach the end here and you do the the constant polynomial check, you're going to do an extra check. Not only you're going to check it's constant, but you're also going to check that it's a small constant.

Um and if you have a small constant here, that means you have a a small a polynomial here with small small enough coefficients. And you go up and up and up. Every time the coefficients can go larger and larger and larger, but you have you have kind of a very controlled bound on on how large these coefficients can be. Um and they're basically small enough that you can do apply all the homomorphisms that you need for the consistency checks. Okay.

Um and kind of the the the final one, which is under this framework of of a log number of rounds, is is kind of bulletproof. And um here what you do is that you you you you you check that the commitment of you know, F I and F I plus 1 are consistent. And then you have these um these extra terms here. Um and these extra terms kind of correspond to um kind of cross products. So, remember you have you have uh basis elements and then you have the the

the coefficients. Um and it turns out that you you kind of need to to cancel off these cross products uh for things to to work out nicely. And um yeah, so you have these these resi- residual terms. I I mean, to me Bulletproofs is kind of the most confusing of of all the schemes. Um like the the FRI and Dark um you know, even though this looks a bit dry, actually it's very very natural. Um here there's a little bit of cleverness involved uh to come up uh to come up with this.

Uh but yeah, it it works. Okay, so now now I've kind of told you um like the the the the low degree test, but the low degree is not is not sufficient. You actually want a polynomial commitment scheme. Uh and so in addition to to knowing that something is a polynomial is kind of low degree, you also want to know what is the precise opening of f at at z. So, you want to know this f of z.

Um and uh you know, I I as as was mentioned, basically you have this trick uh for for FRI where so it's it's kind of the the quotient trick and it's used in various places. It's kind of a a neat trick to keep in mind. So, if um basically f of z will be the the the evaluation of f at z if and only if f of x minus f of z is divisible by x minus z. So, if you plug in z in both the left and right-hand side, you get you get f of z minus f of z, so that's zero.

And here you also get zero, and so you have this you have this quotient here. Um and so generally the the trick involves the the prover uh yeah, kind of calculating the the this quotient, and then uh convincing that this this is low degree. And then so this this is ex- exactly what um FRI FRI does. So, um instead of showing that f is low degree, well, first it shows that f is low degree. Okay, fine. And now we want to know the opening, and so we're going to we want to open outside of the box.

We want to open outside of the domain. And so how do we do that? Well, we just show that this is low degree because this is is low degree if and only if you know, f of z is is is is the correct opening. Um and yeah. So, there's a little technicality that you need to be within the the unique decoding radius, but uh you know, that's that's that yeah. That's all there is. So, so basically FRI very easily kind of elevates into a a polynomial commitment scheme.

And this is what was noticed by the the Matter Labs uh team. And then it turns out that this exact same trick is used uh in the Kate scheme. And this Kate scheme you can forget all the all the gymnastics that you have to do with the the the prover and the verifier talking to each other. You can just do a a single kind of direct proof. And what you do is that you you basically check this equation in in in the exponent basically where using pairings.

So this the commitment of F minus F of So the the verifier is already given the commitment of F. The prover is going to commit is going to compute Q and and commit to that. And and this equation holding is basically if and only if this times this is equal to this times this. So you can kind of think of pairings as products. So it multiplies the left-hand side with the the right-hand side. So what is the the left-hand side here? It's going to be F minus F of Z. That's that's good.

And then what is the right-hand side? This is just a generator G2. So there's a little one which is hidden. So it's this times one which is just this. Is it equal to Q which is this times the right-hand side and the right-hand side is going to be S minus Z. S is going to be your secret point in the powers of tau. And so the S here will correspond to the X. Right. So this this pairing check kind of immediately checks this and so immediately proves that the evaluation of of F at Z is F of Z.

Does this make sense? So I mean one one reasonable Sorry. I have a question. Could you return to the like the previous slide? Could you repeat where is the even and odd side in Fry? And why? I as a kind of Okay. So, um I wish I had the kind of whiteboard. Um but this would be the even part and this would be the odd part or vice versa, but I'm I'm I'm going to be sure this is the even and this is the odd part.

Okay, so let let's have a look. So, we're going to let's look at f of f of z plus f of minus z. What is that equal to? Well, so we're going to take this equation and imagine that you duplicate it. So, you have you have f of f of z here and then you have f of minus z. And basically, this this even part here is going to be exactly the same, right? Because z and minus z squared, they're the same thing. Right?

So, this part and this part, this imaginary part below are going to be the same. Okay, now let's look at the right part here. The odd odd of odd part here is going to be of z and minus z is also going to be the same because you have the squared here, but here you don't have a square, right? So, really what you're going to have is going to have a minus this part here. Right? So, you have f of z and f of minus z. What if you add the two? You add these two, so you have this line here and the imaginary new line here with a minus instead of a plus. What if you add these two? Well, the the plus and the minus are going to cancel,

right? The this this odd part is going to disappear. And so, you're going to get two times the even part, right? So, basically, f of x f of z plus f of minus z is it going to be equal to two times the even part of f evaluated at z squared. And So, so thanks, I got that. Yeah. That's my guess. Yeah, that's that. Yeah. So, basically, does that make sense? Yeah?

Uh yeah, so so so you also add you also multiply by R the old part, right? Yeah, so that's That's the randomness. That is the randomness in the linear So, it's here, yeah. So, so far you don't have it. This So far this Yeah, there's no There's no randomness involved here. It It comes in here when you want to do the the reduction. Because basically you have two polynomials, each of degree half. And if you if you keep on kind of um taking one polynomial and and splitting it into two, then you kind of have an exponential blow-up in the number of polynomials. Um so, what you want to do is you want to simultaneously keep the

number of polynomials that you have constrained, and in this case we have one polynomial at every step, but you also want the degree to go to fall down. And the way you achieve that is you do the decom decompose and then reduce with a a random linear combination. All right, thank you. Yeah. So, this is why it's a called a decompose-reduce kind of framework, I guess. Uh and it's kind of Actually, um just so you know, we have 10 minutes till the hour is up, so just uh I don't know if there's any planning, but cool.

Right. So, I mean, I think we can finish part three. Good. And then there'll be kind of an optional part four, um which people might be interested in. Um Okay, yeah. So, this is how you do the openings for Fry and for for uh Cathy. And you use this this really cool trick. Um And I guess, you know, you one natural question would be, okay, why does that trick not work for docs? Like why can't I get like a a single direct proof like like parents because after all kind of groups of on on order they have all these nice kind of homomorphic

properties, why can't I use them? And basically the the problem is that you need Q to be to have small coefficients. And in in it turns out that there's kind of two problems here that arise. One is if you do find such a Q, well you still need to prove that it has small coefficients and the the way the only way that I know of is basically that is efficient is to to do this this log number of rounds. So um you know, you'd still have to pay but there actually there's a there's another problem which is that if you take the quotient of if you take

this part divided by X minus Z, what you'll get is a polynomial with random looking coefficients. Um and so they they they they won't even like with very high probability these coefficients won't even be small enough. They won't be small enough, they'll just be random. Um some of them will be large. Um and so you actually have a completeness problem. It's not just a soundness problem but a completeness in the sense that you can't even prove this thing because Q is an object that you you can't work with. You can't apply your homomorphisms uh to.

Um yeah, so that's why you you you don't have this this trick apply for for docs. Okay, so now I need to tell you about how how do you do the actual openings for the other two schemes for docs and bullet proofs. Uh we we we You of have the low degree test but we want to go a bit further than that. Um and the way that it works for darks is that it's basically um in line with uh with the uh the uh the logarithmic number of rounds.

So, in addition to communicating commitments, you're also going to communicate evaluation points. And in the exact same way that you have a um a consistency check on the commitments, you can have the same similar consistency check uh on the uh on the evaluation points. So, um basically let's say that I'm interested in F evaluated at Z.

Um the prover, in addition to giving me the commitments of the even part and the commitments to the odd part, he will also give me the even part evaluated at Z and the odd part evaluated at Z and I can just check is F of Z equal to the even part at Z plus the randomness times the odd part at Z. Um Yeah. Um so, actually there's a F of I plus one here and then F of I on the right hand side or vice versa. Um so, it's kind of a in line in line thing that you do, uh very similar here. And for Bulletproofs, it turns out that the the the scheme can be naturally

thought of as an inner product argument. And so, uh what you do is that you you you're going to take the inner product of um F, the coefficients of F, and the powers of Z. This should say powers of Z not powers of X. Um and if you think about it, so the powers of Z will be Z to the power zero, Z to the power one, all the way up to Z to the power D. The coefficients of A will be A0 all the way up to AD. And if you take the inner product of that, that's just the same thing as F evaluated at X, F evaluated at Z. So, you know, that's why the inner product

argument is kind of strictly more powerful than than a polynomial commitment scheme because it is just a very special case where the right hand side turns out to be the powers of the point that you want to evaluate at. So, that's that's how you would do the the the opening in the if you were to use a a bulletproof based um polynomial commitment. And the in bulletproofs, is it like the same efficiency to open as a polynomial in a general Uh-huh.

inner product? So, it turns out that as far as I can tell, the the prover time is exactly the same is basically the same for commitments and for openings. Um and that's why in my table I kind of talk here about just prover time. You know, but actually there's two prover times, right? There's the time to commit and the time to open. And the kind of the reason they're they're the same in the context of these logarithmic arguments is that um here you commit to F, and then you commit to something which

is half of X, so that's going to take half the amount of work, and then you commit to something a quarter of the amount of work. And so, if you add up all the work to do all these commitments, you get basically twice the amount of work. So So yeah, so all the all the work to do the commitments below here are equivalent to the amount of work to do the original a commitment at at the very beginning here. So Yeah, in in every scheme um because you you're reusing the commitment internally and these commitments become smaller and smaller and the total work is the same as as this. So

the very top one is what you'd call the the master commit and then all the other ones would be the openings. Uh but it turns out they're kind of equivalent. And um it's the there was kind of something that I discovered uh only a few days ago or I guess a a few weeks ago. Um the same thing happens for Kate. So um and it it So it's it's it's it's it's kind of obvious that for Kate um the the the the commitment and the opening I have the the same cost if you work in the monomial basis,

but it's not it's not obvious if you if you have something in in the Lagrange basis. And the reason is that your powers of tau is is given to you um in in the monomial basis and so what you do you know, traditionally is you'd um you you you take your your polynomial in the Lagrange basis, you do an FFT to go in in in the monomial monomial basis and then you you you do the multi-exponentiation. But it turns out that this trick, which it seems like no one is doing it, but it's kind of a cool trick where you can precompute your SRS in the Lagrange basis.

Um so you you take the monomial basis and then you do this completely trustless and transparent transformation to transform it into the uh the Lagrange basis. And then when you want to do an opening or a commitment, you can just reuse this precomputed uh basically new new new SRS. Um and you you you don't have to bother with the with the FFTs.

You're saying that uh I gave you the the point to open and you can compute this uh f of x minus f of z divided by x minus z, you can compute it uh without any FFT. Yes, that's correct. Yes. So, this is this is really a very cool trick and actually there's there's another trick which uh is in part four, which I guess I could tell. So basically you're given the you have a polynomial in the Lagrange basis. Okay. Now, you want to compute the this this quotient polynomial also in the Lagrange basis. Well, that's that's that's that's very easy to do in linear time

without any FFT because you just you take what you have, you remove f of z everywhere and then you divide by x minus z everywhere and you can all you can do this in linear time. And now that you have the quotient and you have the precomputed SRS, now you can also do the the the commitment as as in the opening, the commitment of the quotient, i.e. the opening, also in linear time. And so, this I mean I mean there is one one caveat, which is like how do you compute the evaluation itself in linear time.

And this is where another trick comes in, which is a really really beautiful trick, which it seems not many people in this space know, uh which is this one. It's called the barycentric Lagrange interpolation. So, let's kind of uh unpack this equation a little bit. So, you have you have your roots of unity, which are the the WI. So, W to the zero all the way to W to the to the N or W to the T. Um and then you you have your Lagrange you have F in the Lagrange basis. And what that means is you have the evaluations of F at your roots of unity. So, this is your roots of unity. You already have F

evaluated at these roots of unity. So, they're kind of already on your hard drive, and you can just read them off because you have them. And then there's this equation which says that F of Z I'm missing F of Z. F of Z is equal to this thing. And this thing can just be computed in linear time because here you have a a sum which is linear, you know, N. Um so, you you just go through every element. Here you you just read from your your your memory or your RAM or whatever, and then you divide by this which which take constant time.

And and and this is just a constant that you have to to compute once for for for for the whole sum. So, basically in in in summary, it turns out that you can do kind of optimal commitments and and openings with Kate just in linear time regardless of your basis. So, if you're if you're in the monomial monomial basis, it's trivial. If you're in the Lagrange basis, um you need the precomputation and you need this formula. But, it turns out that you can pick any arbitrary basis.

You can go like really creative and pick some exotic basis, and you have equivalent formulas here. The formula is not as nice. You know, there's a few extra terms because you don't have the nice algebraic properties of the the roots of unity, but you can still do it. And the the pre-computation trick of the SRS can also be done for any arbitrary basis. So, where where are we at right now in in the presentation? Have we finished section three?

Yes. Uh we Okay. Yes, we finished section three. Um Cool. Actually, no, there is one There's two more slides which are Well, one more slide, which is basically open problems. Like, you know, like, can you come up with new constructions? For example, you know, we we've covered large parts of cryptography with hash functions, pairings, you know, elliptic curves, and and groups of unknown order. And so, there's a there's natural questions like, can you use the other things? And one of the prime constructions that we have is lattices. So, can you come up with up a new scheme with lattices?

Another interesting question is, can you come up with uh more groups of unknown order? So, we have RSA groups, class groups. Can you come up with something new? Um and actually, that Dan Boneh is trying to make um hyperelliptic curves work. Um and so, it as I understand, these hyperelliptic curves they um they are groups of unknown order. It's like really difficult to compute the group of the order of the group, but they have um they have a problem, which is that you can compute the the the order of some elements in the group.

Um and it turns out that you need a bit more than a group of known order. You need um you need the so-called adaptive root assumption to hold. Um and this doesn't hold if you know um, even the order of of one group element. Um, Yeah, and then there's all sorts of kind of take It would be interesting to find new polynomial commitment schemes which apply to very specific use cases. So, for example, if you have a sparse polynomial, uh, you know, you only have a um, so it's a it's of degree D, but most of the terms are zero, for example.

Can you find, uh, ways to to commit and open this polynomial in, you know, in time significantly less less than D. Um yeah. And actually this this last problem, you know, about FFT minimization techniques, uh, you know, when I wrote my slides, that was one of the open problems, but I guess at least in the context of Kate, this this has been solved, which is kind of very nice. What's the delta?

Was it the Yeah, so there's two tricks. Um, so actually this this barycentric trick was co-discovered, co-reinvented by Vitalik and Dan Boneh. So, Vitalik had this intuition saying, "Oh, I I think I can do interpolation in linear time." And he came up with this this recursive kind of program. He wrote Python code and he tested it. And he showed the code to Dan. And Dan was like, "Oh, I can find a really nice closed formula for that." Oh. Um, and then, you know, I discovered that actually this formula was known, you know, like 30 years ago.

All right. Um, and then there's the other trick, which is the the SRS precomputation trick which um, which I just came up with and as far as I can tell, no one is is is using. Oh cool. Yeah. And the reason why I was going down this road is that I'm I've been thinking for several weeks now, for almost a month, I've been trying to build SNARKs, which for which the prover does not require any FFT whatsoever. Um and if you can crack that, then you can get basically optimal SNARKs, uh where both the, you know, the proof size, verify time, and prover time are optimal.

And when you remove the FFTs, you also really allow for very large circuits. So, for example, you know, you like trillion trillion gates kind of circuits are not out of the question. And the reason is that these the the rest of the work that needs to be done, which is these um multi-exponentiations, they are they can be massively parallelized parallelized, and they don't require much memory. Um and you know, they can be accelerated with custom hardware. But the FFTs are kind of very awkward to deal with because you need a lot of memory, and you need quite a bit of communication between the various parts, so it's

there's there's a few moving parts, which make it much more difficult to scale than than the the rest, than the other operations. Cool. Yeah. So, I think we're going to wrap it up. We've gone a little bit over time. Um but yeah, I guess thanks so much for putting this together again and running us and walking us through it. Do we need another session? So, the final part is what I call polynomial gadgets. And basically, the way that you you build these IOPs is really you don't reuse the low-level polynomial commitment scheme. You have this this new layer of abstraction, which I call polynomial gadgets,

um which are slightly more powerful. And these are the basic building blocks, the LEGO blocks, with which you build your your IOP and so um you know, I would present the gadgets um if there's time. So, there's yeah. That sounds good. So, I think we'll talk about maybe doing a third and then um yeah, in the meantime, thanks for joining everybody. I think we're going to we're going to wrap it up now.