ZkStudyClub: Part 3 Polynomial Commitments with Justin Drake

Transcript

hit record as well and then we can just start this off cool so this is the third part of the polynomial commitment scheme series that Justin's been doing even though it says part four on the screen it's actually part three for us and yeah this is kind of we have the first two I'll probably link to them somewhere in case somebody wants to see those before it's probably worth your while to watch that before you start on this one but welcome back to the study club Justin thank you Anna so yeah just to just to recap where we are so in the previous presentations we

gave some motivation for plenty more commitments that they can be useful in vessel snarks and we kind of gave an overview of the different constructions and their properties turns out there's you know a few that you can choose from and they have different trade-offs and then we kind of explored a little bit how they're actually built so some of the math behind it and some of the ideas but in this presentation in a way we're going to move away from Pawnee more commitments we're gonna kind of consider them as a black box and we're gonna see okay how can we use them to do cool things and you know the kind of ultimately we want to try and build

these snarks but as a kind of intermediate level of abstraction so between the IOP and the Ponyville commitments I kinda want to introduce this this new concept which I call I guess the plenum or gadget max kind of my own terminology and it's kind of the the Lego blocks the building blocks that you can reuse reusable blocks to build arrow keys so yeah so we have the i/o key actually let me just make my mouse a bit bigger would that be helpful for people I mean we can we can see it but okay Yop here the information free report and

then we have the cryptographic parts with the plain old commitments and what I'm suggesting is that we we have these kind of gadgets that we that we introduced as a new level of abstraction and as I mentioned these gadgets are useful to build our keys because they're reusable but it turns out that these gadgets are can be used to make the poly no commitments themselves better so you know we've seen that the basic building block like the basic idea of upon your commitment is you have a polynomial polynomial and you want to evaluate it at a point but what if for example you want to evaluate multiple polynomials at

the same point or maybe a single polynomial at multiple points like it turns out that if you use these gadgets you can enhance the point no commitments themselves okay and like one of the the key idea is that we're going to use kind of threw out is this the Schwarz Zippo lemma which is really really cool really really powerful I mean basically what it does is that it allows us to take a hard problem as an kind of computationally extensive problem of and I'm comparing polynomials so you know if you have a polynomial it

has a degree 1 billion and you want to check that these two polynomials are equal you kind of need to check coefficient by coefficient and that's a lot of work if you have coefficients so it reduces polynomial equality checking down to checking of one single point which is chosen at random so this is what it says here so f1 equals f2 with hyper bility if and only if F 1 evaluated at Z is equal to f3 relative Z where Z is some sort of random point and this is kind of the power of interactivity so did the f1 and the 2 are committed up front and then the very father sends a random point and then and then you can check it quite so polynomials and it turns out that we can

we can generalize what's that my this wonderful them are a little bit so um you know if you if you take a bunch of polynomials and you do operations on them so for example you have f1 f2 f3 and you kind of want to consider the Sun for example f1 plus f2 plus f3 and then you will compare it let's say to f4 x f v + f6 you know some manipulation of polynomials then you can do the same thing so you have this this G polynomial here which is kind of a which can kind of encode a relationship between polynomials you have a polynomial polynomial that that makes sense and then you can check kind of a similar

thing so you can check that these these relations relations between polynomials hold to just by evaluating at the single point and you can also add kind of additional variables so here for example I did this additional free variable Y if you want so kind of the the equality you know it doesn't have to so if you have a multivariate polynomial you can reduce the number of variables but you can still keep free variables around it if that's what you want so Y and then lemma is used all over the place so what I can't want to do is you

know as I said introduce these putting little gadgets and I kind of want to at the end I want you to have kind of a cheat sheet of the various gadgets you can just go to this one place and and have a synopsis of some of the main ones and I'll start with a very simple trick which is used all over the place which is the the range trick so what you have is a point pulling on your f and you have a set s so s is part of the devaluation domain of F and you kind of want to show that F vanishes on this set

so the set for example could be the roots of unity and you want to show that F vanishes on the community and basically the trick here that you need to do and it's kind of written concisely here is I need to notice that F vanishes on the range s kind of if and only if F is divisible by the vanishing polynomial s so this Z sub s s is the set the Z sub s is going to be the smallest polynomial as well as nonzero polynomial which

vanishes on s and so it's going to be the product of X minus si where the S is are part of this and you can see that F is equal to to this expression and so if you can somehow check this expression then you'll be convinced that F is indeed divisible by Z of X and hence that F vanishes on s and so this is what the protocol looks like I'm so basically you commit to F you commit to the quotient you did prove and sends that information to the verifier the verifier sends a random opening point the prover

will will will open what he committed to and then the verifier does this consistency check there's you know and this is very easy consistent to check because we're working with field elements here it's just one field that elements equality and multiplication and so this is this is very cheap and I guess one note here is that in the case where s is the roots of unity and Z of s is actually very very nice it's just X to the power n minus one where you know n is the number of resiliency that you have and I guess if Z of s was some like really awkward set but for some reason you knew

it you knew about it ahead of time so in the in the pre-processing stage for example then it's you could also kind of commit to Z of s and then opens your s as well yeah but in this case like often Z of s is is designed to be easy to evaluate by the by the verifier so the verifier can check all of this yeah in one go any questions so far on this first basic example so I kind of walks you through and in detail I mean this is yeah it's a very basic example I imagine everyone in

the chat probably probably knows it okay so we can't show that the Ponyville F vanishes on s now it turns out that this is extremely similar trick which is quite cool which is the multi-point opening so actually you can think of the range but you can think of it as a generalization of the range trick because if you want to show that the polynomial vanishes on s that just means that when open that every point on s is equal to zero but what if you know the openings are non zero well basically you do the same thing but in addition to the quotients

you have this remainder so you take the remainder of F modulo Z of s and that's going to encode information for ethically this is equivalent but communicating this polynomial is equivalent to knowing the evaluations of F on on s and so this is this is how it works basically exactly the same thing but we have these these extra terms that are communicated so you know in in the in case it was implicit that the evaluations will be zero over here there's kind of extra information that needs to be communicated because it's possibly nonzero so you communicate F mod CMS and it's probably best to

communicate it in the law ground base and what this is my definition is going to be the evaluations of FMS and then in the consistency check you also check here the you add this extra remainder part and again this remainder part if if s is relatively small you know if you want to open generally you know you want open up a few points because you need to communicate this and in the context of a snark you don't want to be opening two million points you want to be opening two let's say a handful of points so this is very much can be evaluated by the verifier any questions so far so basically we have the same trick twice

but really it has a very different flavor so one is for ranges and the other one is for multi-point openings okay so and you know this is what I mean by taking taking a polynomial commitment I'm just going back quickly to the multi-point opening you have a plane of commitments which I can can open on one point and here you can enhanced it with a simple trick to open at multiple points and one of the reasons why this is cool is because every opening is expensive right so you don't want to do too many opening so you this is kind of a matching trick really and if you if

you look here you know you only need to open these two polynomials you don't have to open you don't have to open that every single point you can just open at one single point just this one point Z okay so so that you can do the same thing for if you have multiple point in Amiens there's also a bathroom trick and this is kind of a standard one where you have multiple polynomials of 0fk and you just take a kind of a random linear combination and but here instead of taking a random linear combination will

actually take a slightly more structured thing where we're given that a random point which is represented by this variable Y and then you take powers of it and the kind of powers of something right you know random kind of looks random but you know we can use the Schwartz I hold my to convince yourself that that the the sadness is is good so you know this protocol is slightly more complicated because we have these these two rounds so we have you know one one random evaluation point but also just a random challenge so we have these polynomials f 0 f K we kind of want to

batch the openings to the verifier sends the the opening point generally after the commitment and then the prover will send the claimed evaluations say I claim that F 0 at Z etc FK at Z is all these values and then the very price is okay here's a challenge oh and I want you to open this polynomial here so kind of think of it as a random linear combination of the of the F I open it add the evaluation point and now you kind of have two things you have this one opening right you have this batched

opening here and you have the individual claimed evaluations and you can do this consistency check as a verifier and if this consistency check passes then by the Schwartz a polymer then with high probability like the declaimed evaluations were correct so you can ask good is the intuition here similar to how we batch reaction ears trick where we have like two variables and take a random linear combination of the two and instead of having that you

just show one yeah so just I mean this trick is used all over the place i i i can't see exactly which one you're talking about right now in the context of ehm ER but yes it's this trick is used everywhere I mean in PDFs is a good one I want em familiar yeah it's a very common one and so here what you do is you know where I had this generalized for the full Emma where you had this free variable Y where well basically you this is this is this is why I should follow the reason why I showed this this

generalized thing is that in in here in this specific trick you use the Y to calculate the random linear combination so you probably possible you applying the generalised rods illa ma shorts if all them are kind of twice maybe yeah but anyway yes you're right it's a very very common track on the previous slide you said use linearity and what you mean so you I guess you're not going to commit to this linear combination so I mean

something on the commitments they fare well with linear combinations yeah so a lot of the point more commitment schemes have this linear form a morphism so if you take F of 0 and F of 1 and you have commitments of those you can just take the sum to get the commitments of F of 0 and F of 1 and here you know the odds are just scalars so here you really have a linear combination so from the the commitments of the FI the verifier locally he can you know compute like commitments to the linear combination

and so can the prover as well yeah it's it's it's very very likely that this trick can also be I can also work without linearity so basically and if you don't have linearity I guess the proof I would have to yeah I'm not I'm not sure how I mean if you don't have linearity then you need to kind of prove consistency of a new commitment with with your your old commitments but then you kind of lose the benefits of matching because to prove consistency then I mean I mean maybe someone handed

in the chats could can figure out how to I think it would maybe it would just add another round you would have after sending this art he would have the prover would send a commitment to this polynomial let's call it G which is some R to the eye-fi right I mean that's just some other when R is fixed this is just some other fixed polynomial and and then I and then yeah you would need to on some random point to prove that really this is the commitment to to G but by comparing on some new verify challenge and then when

you've been convinced that G is the commitment to the to the right thing I think you you could you would just open and as you do here I'm not like I don't have it or like I need I would need to write it out but I think basically I would just add another round so it would still you would still benefit from batching K things right I mean it sounds very plausible I conceal the details but it definitely sounds close at all doesn't make sense to me we have to delete a cetacean quotient or something as well since we want to evaluate at Z and so the you write that in the internals of many of the pond your

commitment schemes you would do culture things are you pushing out by X - that but here I'm assuming you have your point on commitment as a black box and your API is kind of committed and open and there's no kind of culture thing yeah alright I was linear I can't show you how to get so right you say you already have commitments to F 1 F n F 2 and it's like some nonlinear commitment scheme and I ice now send you some G I've already sent it and I claim it's a commitment to F 1 plus F 2 so right so I think at this point if you if you just check at a random a that right the the

some of the openings of F F 1 and F 2 is equal to the opening of the third thing at a then I think from the Schwartz Apple Emma it means that the the thing I sent is really the commitment to F 1 plus F 2 yes what you doing so basically what you're doing is that here you are paying the cost of opening at some random point for every point on me also can you lose the batching properties but once you've done this one one-time investment then you can you can do the you can reuse this batching multiple times in the future oh so you know what I I didn't really notice that

I was for this consistency check I was opening everybody write a standard way so yeah I actually I did not notice that I was doing that so yeah maybe it's useful in some case but not others right okay let's move on because everybody is almost like my time and the other and have a look kind of cool trick and this kind of fits in the table of what I call basis independent trick so they work in both the monomial and the legrasse basis so there's kind of this degree Brown so let's say that you have a upon your

commitment scheme which can easily proved or that's even like a low degree test which can prove that a certain polynomial has degree at most M but in some cases you know your your n is kind of hard coded so for example if you have a powers of tau then you know you can you can prove that your polynomial has degree at most and but what if you want to prove that you're the degree has at most D where D is less than M well you know one one simple trick is to kind of prove that X times X to the power n minus D times F has degree at most and and therefore F matt

has must must have degree at most D and this is also helpful in the context of some of these logger you know some of these polynomial commitment schemes which have a logarithmic number of grounds and the reason is that basically for example if you take the the group's up under an order scheme you the the number of rounds that you do is gonna tell you is gonna give you a bound on your degree so if you have you know K rounds you know that your polynomial has degree at most 2 to the K but now if you

want to do these batching tricks and you want to to prove that multiple point on mules that say have small degree but different degrees and then you kind of need to homogenize everything and then you can do the batching in in in the given number of rounds so this can be a trick useful for that ok so these are kind of the basic tricks on the basis independence now I'm going to move to slightly more fancy ones and for that I kind of want to make sure we're on the same page in terms of bases so if you have like a vector of field elements 0 up to AD there's two extremely natural

ways to interpret them as a polynomial so one one way is to interpret them kind of in the monomial basis where you have your monomial monomials X 0 up to X D and then you take this linear combination and then you know that's the polynomial that you can evaluate and then the other really cool basis is that I crouch basis and basically what what it means here is that the the polynomial evaluated at a 0 I'm sorry at the 0 root of unity is going to be a 0 etc so basically these

these L L is at the Lagrange polynomials and they're designed to kind of be 0 everywhere on the roots of unity except them at the 1 and the INA fruit community so if you familiar with the the Kronecker Delta notation the Delta Delta IJ where it's equal to 1 if and only if an I equals J otherwise is equal to 0 well that might be helpful but otherwise you know just think of it as the polynomial which is like a vanishing from noise zero everywhere on the roots of unity except at one root of unity and for for every one of the the tricks that

I'm going to learn next there's going to be these two flavors and the two flavors are gonna be different and what you can do is you can you can move from one basis to another so you can do a basis change but that's gonna cost you an fft and so you're gonna have this this log factor over here then also it's gonna cost you some memory to duty hey Justin really quick before you move on um the LeGrande so I just having done an episode with Ariel and talking about plonk L'Orange was highlighted as like one of the distinguishing factors that they're

using that does that suggest that like other commitment schemes are using the other one or is this all new in plunk I'm just curious if this monomial basis if it's being used in the other ones so I mean I guess this is a choice that has to be made at the IOP level so kind of one layer above and I think historically you're right like for example Sonic is built on the monomial basis yes okay and you know Mobius is very natural and kind of what you learn at high school and so you know people would naturally go for that but I think one of the big takeaways in hindsight is that like

Roger base is just strictly better than the monomial basis at least for you know the IOPS and the plain your commitments and the world stuff it's like it seems to be strictly more powerful and it seems to just lead to more natural constructions they just typed in the tags them are fighting words oh I mean I'm more than happy to have a debate on this this is amazing it's very natural and I mean actually my last slide is about plunk because you know I'll be able to show plunk in one slide I've showed all the tricks and and also I'll

show you why the clash base is more powerful anyway I'll try to argue that right so and then the the this this is one of the reasons why why the like Ron face is so cool so I used to think and many people used to think actually vitalik used to think and Dan Boneh used to think that's one of the key superpowers of the monomial basis is that you can do evaluations in linear time right so if evaluate this thing here at Point Z then you know you compute the powers of Z and then you take a song all in a time whereas here if you want to evaluate it at Z is kind of less clear because each

one of these polynomials has degree n and you have n of them so you have come n squared and I mean okay you could go from here to here you know you could do an inverse f of T but that's gonna cost you a login factor so that's no longer than your hyper but it turns out that this really cool formula which very few people know I mean it was mentioned in the physics paper but other than that it doesn't seem to be well-known in our space and it turns out that you can evaluate in from the Lagrange's s so from the evaluations of F this is an evaluation of F at the roots of unity you can evaluate in linear time you have a linear sum here any evaluation so this is f of Z so this is the evaluation of F

at the point Z you have this this formula that holds which is really cool and you can think of it as in the product right exactly the same as the the monomial basis so here this this expression here is the inner product of the of this vector the a is by the X vector so the vector of monomials and here is the same thing here you have the inner product of the F to the power Y which you can call a I if you want the same here the a is and then you're gonna have one over kind of like interesting right the symmetry so here you have here

you have powers of X and here you kind of have inverse powers of of roots of unity anyway it's just a very cool trick that I think more people should know so yeah just to make sure we're on the same page though so we have these two ways of encoding you can either encode a vector in the garage basis or the monomial basis and encoding is like a really natural step is like one of the first things you do in you in your IOT right so you have you have your circuit you know which can be expressed in high-level code and then you have your witnesses and then you know you want to do this basic

arithmetic and so you kind of want to encode things into polynomials and you have a bunch of coefficients and these two natural ways to encode and so you have for example the billion coefficients D could be a billion and you include it into one single polynomial so yeah the polynomial you can think of them as inter information-theoretic places like capsules to store coefficients and then once you've encoded you can do a query right so if you want to query the AI F coefficient you kind of want to do the inverse operation from encoding you can just evaluate the AI fruit of opportunity and you can do something similar in the Mahna Mahna Mahna basis

and you can already see the minimal basis is more awkward so you kind of need to isolate but you isolate the I've monomial and then you have a left and a right right where you the left polynomial is gonna be of degree you're gonna prove that it has degree less than less than I and then this part here must have degree at most at least I plus one because you have this I plus one contribution and therefore you can prove that you know AI is indeed in the I coefficient so hey you can kind of see some of the separation between the basis the Lagrange's at least for queries more

more more natural and then you have shift so shifts are one of these really awesome things so you have this this vector of coefficients and you want to shift them and like how do you get the result what is the resulting polynomial if you shift everything and in the log knowledge basis is very clean you have you just basically multiply the inner part of the basically you input two function f by by a root of unity and so that's gonna be a shift by by I I co efficient and you can kind of see that

because the roots of unity form a cyclic group and so you're kind of just rotating everything you can think of it as a rotation and so this is a shift with wraparound so the the very top evaluations will wrap around all the ways the beginning and then you have something similar in the middle your basis where you take F and you multiplied by X to the power I and that's going to shift everything but you again you can see how it's actually way inferior to the like ranch basis and the reason is that this shift here does not have wraparound okay so it's going to

shift everything but the very top coefficients are not going to wrap around to the bottom and so if you do want wraparound which most of the time you do is kind of a very natural things you want you kind of need to do a bit of surgery you need to take the top bit can I need to rotate it flip it and then take it back in and so you get you get a similar mess to the queries of a question here a question from even considering barycentric interpolation how much FFT can we remove from the prover so if you want to do just evaluation you can remove all the 50s and actually if you want to do any operation on on the Khattak poly no

commitment scheme you can also remove all the 50s so that was one of the realizations that I mean recently do we have to do it at all or can we just stay in the Lagrange's all the time I have great questions so you can stay in the leg round faces all the time and yeah that's something I would recommend and it turns out that you know even if you stay like ranch bases a long time for example in clonk there are some instances where you do want to do FFTs but i I have this this write-up which I've been published yet

but I've showed it to a few people and I believe you can completely remove authorities from from a variant of clunk so you can do you know the only computationally expensive thing involved is basically multi explanations so you have to do a bit of gymnastics to remove all the affectees but I believe it can be done at least I have a proof of concept and and I'm hopeful that people will be able to improve upon that you're welcome ok so we have the the shift which is super nice in the garage and if

you won't wrap around pretty bad in the monomial basis and then we have the flip so the flip is you know as the name suggests you kind of want to to flip the coefficients so you can kind of think of it as like a mirror symmetry kind of thing and you know you can just take take take the universe here in the garage basis and then the the Mahna Mahna Mahna basis is kind of slightly more awkward you also have to in addition to taking the universe here you have to do a bit more work to kind of um basically when when you take the inverse here you get 2 you get a low wrong

polynomial right where the the the the powers have inverse powers and so you have to to renormalize everything with by multiplying by X to the power D anyway flip I don't think is used that often but still interesting to put them and then you have you have a really cool one which is is this some so basically you have you want it you have you know your vector of a zero up to 80 and you want to try and get the sum of da eyes and here it's it's a really cool idea

which actually is is in the plum paper but I think it it was used before it was used for example and in Sonic and even before that's kind of the idea of an accumulator polynomial so you have this this G and you want to kind of gradually accumulate something and so in this case we kind of want to gradually accumulate a a son of a is so instead of taking the sum in one single go you kind of build it over time and so this is where you use the shift the shift is very powerful

so basically you you have your polynomial F which encodes the DA is and you want to build this accumulator polynomial such that the G at at the zero roots of unity is equal to F at the zero feet in read community and then G had the first root of unity is going to be equal to the sum of G of zero at zero from the first and then the zero of the first and the second etc etc so it kind of accumulates and so the the shift allows you to kind of access kind of a

neighbor right so you can this will be the this will be the neighbor relative to this guy and so the neighbors are related to each other via the action um is someone speaking okay and so this this is how it looks like in in the picture just to show you how it works so you have you have your F which you want to take the sum you have G which is your accumulator polynomial which is kind of uniquely derived from F and then you

kind of want to show that the G is consistent with F so what you want to do is you want to show that this this put in your Q which is going to be the shift of G so the G at the next value the neighbor minus the current value of G that should be a minus sorry minus the current value of G minus F is going to be zero on on on on the vanishing polynomials on when the S here is the roots of unity right so you want this expression to hold on all of the roots of unity and if they hold on all the

roots of unity then in particular they must hold for the very last roots of unity and the very last roots of unity will contain the whole sum and also that and then what you do is you just query the G on the last roots of unity and you get the sum so I do have a question here because what happened the extern add up to zero I ran for each community how does this work because we wrap around right well did it need say that's not to be unity mmm so can you repeat the question so so we need if if F is defined that all the roots of unity then

it needs to sum up all of them to zero if you want this to accumulate and all three community we've got to sum to zero because G back to that so why would this sum why would they accumulate to zero if they don't how is it true that G of the first unity is equal to G of the first unity so you can enforce that by construction so you can write okay so you're saying this expression won't hold on all of Z of s it will hold on s - the very first point I need to ask not to build actually and I think you're right yes so we kind of want to take the

vanishing point known as - the very first root of unity and then on the first root of unity you have this special condition yeah you're right and the good news is that if you take the vanishing polynomial on s and you remove the first root of unity you still get something which the proof that can compute easily here it's still very nice kind of sparse polynomial and then here this this trick with the quotient is the exact same trick as the vanishing trick I've I haven't done anything different here but I guess one thing which which is different is that you know I'm opening I have this this point G and I'm opening at two points I'm opening it at

Z and I'm opening it at W Z and this this means that I kind of I don't need to commit to the shift of G I can just open if I have a commitment to G that's that's enough for me to to get openings of shifts of G and then I can just check the consistency here hey Justin just a quick check on timing what like are you are you good on this okay cool have 13 minutes I'm going to finish this okay okay so yeah this is the some trick and there's a kind of an alternative way

of doing it which is like the project hold it some check records some check and I think is using fractal and other places and basically this if you're working on the roots of unity that's like an alternative way to get the sum using this formula but the reason why I like this one here is because it it Maps well where the next one which is the product so you can use this exact same idea of accumulator polynomial and but this time in will be product and this is one of the arguments that's used in plunk so you have this what they call the grand

product so I guess the first one should probably be called the grandson and the exact same trick happens if you have a vector of A's and you want to know what the product is well the prover wants to show the verify that the product is a certain product and you can use the same trick here and you know in the monomial basis this is what Sonic does and it's like is really ugly I still don't haven't fully wrapped my head around well how they do it and you know Mary suggested not spending any time on it yeah

so here again it's like the lagron faces is so much nicer than the basis and then we have this this other really really cool arguments which also is part of plunk which is the permutation document actually that's the key in plunk and here it builds upon the grand product so you're gonna you have Sigma which is a permutation it's a permutation of the set 0 the set of indices from 0 to 2d and basically you want to prove that if you take F which encodes the AI and you were to

permute the AIS according to Sigma then you'd still get the same thing and and this this is kind of the the three line kind of synopsis but let me kind of give give a few more details because it's a really cool argument so we have this signal right which is a permutation of the DI is and what does it mean to be a permutation of the eyes well it means that kind of AI is equal to AJ whenever I is equal to Sigma J for every pair kind of i inj it's kind of just a reformation of the definition and

then you can encode this this this top line as polynomials right so you have you have a polynomial which are degree one that means they have two coefficients here in here and if you have equality as polynomials and that means that that the coefficients must match and so it means that AI is equal to AJ if you know AI is equal to Sigma J kind of just really this is just an Irish memorization step really I'm from just write some things in in polynomials and then we have this this other reformulation in terms of multi-sets right so here you instead of having many

polynomials you just consider just one multi set for each of them so this line here is equivalent to two to these two things being equal as multi sets multi sets of polynomials and then if you have multi sets you can arithmetic is that as as a polynomial so we already have the the X variable which is used so I'm going to use a new variable Y and basically if you look at the product here of here for example you look at the left hand side you take the product well the roots of this product is going to be this multi set

right all I need is a minus sign there should be minus y here but if you look at the roots this corresponds to this and this corresponds to this and so two polynomials are equal if and only if they share the same roots and so basically you've been able to encode this permutation thing into a equality check of polynomials and then by the the for the polymer you can replace did why you can just evaluate at random points I'm r1 and r2 and then here you you've you just have a single check of

fuel elements and so you know we already have product on difference and and you know it's it's easy to build this with with linearity so well yeah it's easy it's easy to build you know what's inside here and so it's easy to kind of build a permutation argument from from this kind of arithmetician of Sigma and this is what is used in a plunk and then kind of a final thing which is just to to cover everything in the in the list is the inner product so

you right so you basically you have two polygons f1 and f2 and taking the product here over the lagrange basis is the is the same as entry entry why these products so if you have a 0 up to ad and B 0 to B D and you multiply the polynomials corresponding money polynomials you have a 0 times B 0 in the first century and the zero entry and then a a 1 B 1 in the press center etc so it's what's called a Hadamard product which is kind of entry wise product and then you can take have an inner product

by summing over this had one product and you know there's a corresponding way to do this in the minimal basis as well and here I just wanna kind of show that this there's some things that you can't really do in why these I don't know how to do in in the monomial basis so for example this this had a more product will just talked about you have f1 and f2 and you just take the product you know it couldn't be any simpler that's something I I don't know how to do in the monomial basis so it's one of the super powers of the like ranch basis and I guess partly why my plonk is built on

on the like orange basis and then yeah similar thing you know in a prod in the products come from how the my products so I'm a similar thing here and also the little in check which is basically like like you have the yo-yo yo-yo your vector a and here this time you want to multiply it by a matrix so you want to take linear combinations hence the you know the the term Lin which stands for linear and here you

know mullion shows you how to do it I guess in the leg not racist but III wouldn't know how to do it and the minimal basis okay so this is kind of my final slide that I wanted to get to so we have an arithmetic circuit and what does it mean to be an arithmetic circuit it kind of means that you have four things so you have your public inputs you have addition gates multiplication gates and wires right and generally your gate will be arithmetic gates as opposed to boolean gates meaning that you know the inputs and the outputs will be if you field elements kind of launch the

other elements and in in in plunk like everything is just simple so you have your public inputs and you encode them using the encoding trick you know in the Lagrange's and some polynomial I for inputs and then you kind of have addition gates so addition gates have left right and output wires and you can encode each independently so left-right outputs you can encode them each as a polynomial and then you can check the consistency here this is very you know just need to open at a random point and

this is kind of the generalize Schwarz lemma that you can use here um open at a random point and check consistency here and then here it's it's it's you know you can use the DD the Hadamard Hadamard trick hannahmont product and the range trick so basically you consider M L times M minus M 0 this should vanish on the roots of unity and yeah so like here e in a way it couldn't be any simpler and then the big question

is how do you do y is how do you connect the various gates and so here what you do is kind of you you consider your big you know witness polynomial which we can think of it as the concatenation of all all all your previous wires that were defined here and then you have a permutation argument over those so you consider all the inputs and all the outputs to your gates as one big vector and then you permute them and so if you have a connection between you know this this input and that output well that means that there's a cycle which contains which contains these these two

indices and so you have equality in that way and that's you know there's kind of a simplification of the plunk constraint system so in plunk in locking in in the real world oh they'll come up with kind of optimizations but that's kind of a simple way of thinking about it's kind of conceptually oh you have these different things and they're each handled independently by different metrics and that's it and I think I'm just some time Wow there was a question I don't know did you get a chance to answer that other question I think it

was back on slide like 80 went all up like there's somebody grassed it aha yes so OTP is asking regarding the formula evaluating a polynomial give render like ranch basis at some point Z how is he how efficient is the computation of one divided by and Z minus WT I so then you have to look yeah so you're asking like this this part here how efficient is it well I mean you can pre-compute WTI right and you can also quickly compute 1 over W

swarm and then taking the this sum here this subtraction is easy and I guess like you did I think it's the inverse are you talking about like how expensive is the inverse and I believe in a finite field is like it's like one exponentiation so I guess I guess you're right you have to do any explanations so I was just wondering so it if it means that it's not evaluation is not linear in the degree general the time well I

mean these are filled explanations right they're not crude exponentiations right so you what are you saying is that you your your unit of cost is is a full field operation and here you have N squared mm-hmm I mean that's that's a very good point I know that I think Zack is the knows this better than me but but there's this batch in version tricks so so i guessing you can do it in total of n field operations right

so I think you can do it maybe if you like in the in the context of the circuits you can do I can understate the termina stick things like that like these tricks maybe that's what you're referring to no no as I as I understood it and I didn't see the algorithm myself there's no just to compute many inverses in the field there's some sort of batching technique right I mean one one easy batching trick is so you want to compute one over a B right where a and B are two distinct values so you want to compute a

of 1 over a and 1 over B well first we compute 1 over a B so that's one explanation and then you take that and you multiply it by B you get 1 over a and then you multiply it by a and you get 1 over B so actually you're right so you can do to to experience asians and the cost of just one exponentiation in two multiplications and I think the trick kind of generalizes so if you have 1 over a 1 it would be 1 over C just you only compute 1 over ABC and then and then you kind of clear the things that you don't like yeah that's a good point um area but right I need to confirm so basically

the question becomes is it is it more or less than n log N or we pull - yeah that's a good question thank you dear maybe this is actually a question we could put into the study club chat see if anybody has any ideas on that mm-hmm no is there any other questions or points I mean we started a few minutes after the hour so I think we can stay another a minute or two if you guys have some other questions comments I mean what would be curious to know is are there tricks that I missed out so

basically the reason why I build this table is because every paper uses a different set of tricks and all the tricks that kind of split over many papers I was trying to put everything together in one place what have I missed in terms of tricks feel like this sounds like an open question maybe for people to be I don't have an answer to that I'll give my one main comment that I'm interested I didn't think of the this group this grand something that you could do it like with this the way you

did it so I'm interested now if you to do like a sub check if you'll plug that in yes instead of the some check technique in Aurora and in Marlon and fractal right I am curious how that that will affect their numbers yeah that's a good question so yeah I I think I discovered this I came up with it I don't know if anyone before came up a bit in the reason why I discovered it is because I was filling this table and I some in the monomial there's like okay how can you do it AHA you can just do the same trick as the

product so one of the cool consequences of this some which might which might be relevant for prank is that if you so in in plunk you have this problem where addition gates are not free so and so one of the problems if you have like a massive addition gate with a huge fan in and then you're gonna have to pay a lot because you have to build it in terms of small addition gates which has small fan in and then the cost really starts you I don't but what you can do is at at this at a constant overhead for the verifier you can build an addition gate with arbitrary fan in so if you wanted you

could you could take a linear combination over every single kind of wire with a single with a single kind of of these kind of global gates global addition gates so if you if you have a circuit which has just a few that say a handful of very very large addition gates then really you should consider this trick I mean it will increase the proof size by a little bit something like one one group element maybe or one group element and one fuel element per gate but it might be work within some instance this and the reason is that

yeah so you can combine this wave with a selector polynomial so instead of just F you do F times Q where Q is a selector polynomial and then you take the sum and so that allows you to take arbitrary linear combinations over all the wires which might be interesting yeah so I mean so you'd need like a selector polynomial per per gate I guess if you yes yes yeah yeah maybe I should be so yeah totally honest I'm more interested to see how this will affect like Marlon and because it'll be more

sort of a smooth plugin but but yeah that's also a good direction cool well I think if it's okay for you guys I'm gonna wrap it up but I don't know if you have anything else you wanted to share Justin are you good - oh that's it thank you so much I'm not for having me this yeah thank you so much for doing this this third part of this series I've been hearing so many I said this to you kind of before this this version or the before we started today but I've been hearing so many good

things from other people who've been watching the videos and so I I really appreciate you coming on and doing this yeah boy I went I have a suggestion which you can totally ignore but there's well I was like called zkp taught science I think it's run by Strad you'd have to double check yeah and I would suggest you submit this table maybe there would be some way it could be added to by people or something but this common ontology is really oh that's great yeah I mean so Daniel from zk proof asked me if I would write kind of a a blog post on on this and I kind of agreed so we'll have a blog post and it's also possible that I'll give them

kind of a two-hour crash course on this at each CC as well okay thanks cool all right so thank you all for joining the study club I think this concludes for now the polynomial commitment series however we have some ideas for some follow-ups but we'll chat more about those like in the in the group right thank you all thank you thanks thank you