Zeromorph - A recipe for Univariate - Multivariate PCS transformations by Tohru and Patrick

Transcript

hopefully hello hello everyone uh today we have another lemon share session uh this time with Tohru from thick ER is basically going to explain xeromorph which is his latest paper if I'm not mistaken uh which is basically based on on some kind of isomorphism to put it on some sense in between the multivariate and the universe won't but I actually will definitely explain it better than me so thank you for coming and please feel free to to start thank you Carlos for introduction and invitation to give a talk here and thank you everyone for coming

so I'm going to talk about xeromorph this is a commitment scheme and then and the work is the joint work with Patrick we are working at Aztec so let's jump in the first I'd like to get it out what a zero morph is so zeromorph is a recipe it's a generic construction recipe to convert I'm sorry convert additive univariate PCS with degree check into a multi-linear PCS I'm going to explain what this degree check and Etc data but for the moment please keep in mind it's a recipe it's a generic Construction

okay so the plan of the talk is this first I explain the background of the research and then step back a bit and talk about the PCS in general then introduce our core concept main concept called univariatization and after that we explain the evaluation protocol and up until this point everything is a is a generic construction this is about the recipe part and after this recipe part we we explain how to instantiate this generic recipe with a univariate cases Universe kcg univariate commitment scheme using it as

an underlying commitment scheme and that's the second half of the talk and finally if we have time I will mention the shift evaluation which is an important kind of useful primitive for snug for applications not free cross okay so the background the background is the subject-based proof of circuit satisfiability this is what we are trying to do and what we want to do at the right now at Aztec and we start with this clongerismatization now what I'm going to say in this slide that applies also to like r1cs other algebraic arithmetization but for the

moment I have talked in mind start with it and usually plonk we prove our encodes weaknesses that is the wire values as by using this univariate LaGrange interpolation but this approach is a bit different we encode the weaknesses by multi-linear extension so to do this what we do is this we have the Y values of witnesses and improve and place them over the booleans hypercube no hyper hyperq and then take the multigenous extension of it and it is known that there is a unique multi-linear polynomial that extends the weakness

values placed over the Boolean hypercube and after making this witness polynomials in the in the making a proof that verifier needs to check the constraint for example the gate constraint and this constraint check is run by some check protocol and this cross this part is a very standard trick um we think of the constraint a constraint check is basically you have a polynomial the constraint polynomial and you plug in the witness values in it and see if the value is zero or not so to use the subject what we do is we take the random linear combination of

the constraint constraints and then we evaluate this randomize the sum of the constraints using a subject protocol at the end of the soundtrack protocol the verifier needs to evaluate the polynomials that on which the soundtrack protocol was performed and in this context this polynomial is the witness polynomials which are committed and here comes the the evaluation protocol and this is where we need a multi-linear evaluation protocol and for this purpose we want something efficient and we want it to be decay I'm sorry yeah

okay so we need it was a question or no no someone wasn't someone was a matrix but this muted totally apologies okay no no no okay so here we need efficient Decay marketing evaluation and by efficient we mean like of course the approval needs to be efficient verifier needs to be efficient but when we talk about the efficiency we we should also keep in mind this uh the the cost of random nonsense the generating the random analysis to high to indulge property it also it is also not material to consider so xenomorph is uh take care take care

of this uh kind of aspect as well but so before talking about the zero move let's step back a little bit and then talk about the polynomial commitment schemes in general so I think this is kind of already familiar to many people so we do it quickly but PCS consists of algorithms no setup that takes the security parameter and output public parameters which is used in this commitment and open algorithm open protocols the commitment algorithm takes the polynomial in of the input and then also public parameter of the input and output commitment element oftentimes it's a group element

and the open protocol is the protocol that take the commitment element and then a polynomial revealed by the approval and then verify you can check if the polynomial claim to be you know polynomial is consistent with the commitment this first three is just the usual commitment scheme the polynomial commitment scheme The crucial part is that next one more protocol built on top of the screen this final one evaluation protocol this the purpose of the evaluation protocol is to

if this look verifier has a commitment and then he doesn't have the com polynomial itself but verify it chooses a random point and ask the prover to give the evaluation of the committed polynomial and evaluation protocol allows the verifier to check if the claimed evaluation is indeed the correct evaluation of the committed polynomial and this evaluation protocol is is technically this is this is a protocol that allows the verifier to check a certain polynomial identity and yeah

so let's look at this polynomial identity example of the polynomial identity and this is the multi-linear we are going to talk about multilinear cases polynomial identity here and which I chose this as an example because this is very important and for zeromorph construction is based on this idea so f is the commitment polynomial and then here here the the Bold f is the finite field and this superscript less than one denotes like multi-linear meaning that the f is a polynomial of degree 1 in each variable

okay and U 0 is u n minus 1 is a point in FN and this is the point uh the evaluation is carried out so the Okay so F evaluates to B this first equation is equivalent to the phone to the second one the existence of q i this is a Qi the polynomials such that this equation the last equation holds so if if you think of the N equals one case that is the one variable case the usual Universe kcg the left hand side becomes just a x 0 minus U 0 times q0 so

the statement is f evaluates to B if and only if F minus V is divisible by X zero minus u0 and in this univariate case what the verifier does with the verifiers job is to make sure that this equality holds and what happens is if it Provence to F initially so that's okay what proof approval provides the commitment to Qi to a verifier and verify your checks this equality using elliptical carrying for this multi-linear case as well there is a multi-linear SRS which is just a little different SRS from the

univariable case over the linear case again the approver provides the commitment to Qi multilinear commitment to Qi to a verifier and then verifier checks the equality using elliptical pairing but it's clearing as we know it is correct so pairing replaces one dot this multiplication on the left hand side so if you follow this approach when you have more than one variable you need to carry as many as n pairing computations on the left hand side and plus one for the right hand side so if you use the traditional approach incurs many pairing computations

and if if it's possible we want to avoid it and we in the market we just look around the market and we have this Virgo and Gemini Market linear protocols commitment schemes they are based on univariate evaluation protocol so their evaluation protocol is based on the univariate environment protocol and University values so the idea is can we do something like this to avoid many uh pairing computations that was the initial conception of xeromorph and so for example like you know this is what we are going to yeah so can we

apply some of the ideas of burgers and Gemini and at the very conceptual level Virgo and Gemini's really fundamental idea is to convert multi-linear polynomials into univarious polynomials so when we look at it this last map this is a map from the vector space of n variate multilinear polynomial to the univariate vector space of univariate polynomial of degree less than 2 to the n do we have some nice map that can be applied to equation two so that equation 2 itself will be converted

into a univariate equation that means this is a multi-linear evaluation protocol in where verifier needs to evaluate only univariate a polynomial identity well that's that's how we started so the main part is the first main task is to construct a nice map like this which we call univariatization map but perhaps at this point I think some people are already thinking that why why don't we just use Gemini because Gemini is reasonably efficient and my answer well it's not really an answer or problem or anything but the

first stumbling block for us was the ZK property of Gemini it's it is possible to add ZK property to Gemini by using a standard technique of using of of standard technique by which I mean like you choose a hiding polynomial as big as the commit commitment polynomial so in our case the commit commitment polynomial has 2 to the N the first line 2 to the N coefficients okay if we use the generic ZK technique then we need to generate 2 to the N number of random

nonsense and that's a bit too much and hope we just hope to avoid it and the second point is this is a minor issue maybe but this Gemini requires univariate evaluation at different points during the evaluation protocol and evaluating polynomials at different evaluation Point generally is a well more difficult than evalu batching different polynomials and open them at one point so if we can avoid it it's very nice and Zero moves does both of them so zero morph uses only logarithmic number of nonsense for ZK property

and zeromorph [Music] yeah opens the universe polynomials only at one point but then okay so now let's uh talk about the univariatization map that whose purpose is to convert multi-linear kcg polynomial identity into a univariate one which it's possible to check the identity so we need we we need to choose a right one something useful for us and our answer the suitable Universal map for us is the following I explained this with a bivariate case

first because it's much easier to look at so when you have only two variables our answer the univariatization map is this you have bivariate multilinear polynomial f and that is sent to a univariate polynomial whose coefficients are evaluation of f over Boolean cubes and the way we place this evaluation is is very simple so we interpret this red letters as binary representation of integers select 0 0 represents integer 0

therefore it is placed at degree zero term and 1 0 represents integer one but for us the left is the least significant bits the one zero is a binary representation of one therefore it is placed as a coefficient of degree one term and 0 1 represents 2 so it is a coefficient of the degree two term and 1 1 3 therefore is the cubic term now first let's observe one thing f is okay I said the f is a linear isomorphism but this is one what I want

to say is that the math written here is a linear isomorphism I'm very sorry about this so this univariatorization map is the engineer isomorphism as you can see this is obviously additive in F and and this respects the scalar multiplications and now this is an isomorphism now look at the the Target and the source both of the vector spaces both Vector spaces have Dimension four so to show that this is an isomorphism we only need to say it's an injection so let's look at the kernel say that that this F of 0 x 0 x 1 is

mapped to zero polynomial that means all the coefficients of zero that means F evaluates to zero over Boolean Cube but the evaluation of a Boolean Cube uniquely characterizes the multilinear polynomial that means F itself is a zero bivariate polynomial so this is injective therefore it's a model and now and one more thing this is slightly uh not about the univariatization map itself but if we want to use this commitment scheme for snark robust then

a snug Brewer starts with the weakness polynomial yeah so they place the the weaknesses over Boolean hypercube type of square hypercube and then extended right so for this kind of prover the the universalization is free because he already starts with the evaluation of f over Boolean hyperte these are the coefficients of the univariate polynomial are just the weaknesses they start with and this property and this construction of the map naturally generalizes to uh

invariant case so here f is mapped to U of f and by we give the name U to signify univariatization if it's mapped U of f the polynomial univariate polynomial whose coefficients are evaluation of f over Boolean hypercube and the coefficients are placed according to their a degree they are placed in the proper degree place so b0 to B and minus one interpret this as an integer and then place it in this degree okay

now one easy example is the constant polynomial for V in the field f and we see this as an invariant polynomial in this case U of V is the polynomial region here all the coefficients of V because it's a constant polynomial so they evaluate V at every Boolean hypercube hype Boolean points and we are going to use this U of V later in this talk so yeah and to commit to multilinear polynomial f a zero morph proverb commits to the univariatization

U aware using a univariate commitment scheme so for any questions okay now we we know we just said how to convert multilingar polynomial into a univariant polynomial now let's talk about evaluation protocol we start with the kg multi-linear polynomial identity that we saw earlier today so F evaluates to B if and only if there

exists q i such that equation holds but now I placed a variable condition here x0 q i depends only I mean Qi is a polynomial only in the first I variables this is the condition I placed here and then the claim is even with this condition this this equivalence is true and now this condition will be used in the zero Morph Construction and this will be the point where that verifier needs to verify so anyways so we're not going to check this final equality with pairings what we are

going to do is of course apply the univariatorization on both sides and so the final one what is this equation equation 5 is the polynomial identity we obtain okay to check it let's so the idea is verifier can check this equation 5 at the random point invoking two schwarzen SQL argument now the univariate commitment to U of f is given as the initial commitment to F okay and suppose the proofer gives the commitment to U of q i as an open other evaluation proof

then the verifier can evaluate U of F and also U of q i at the random point and verifier can also compute U of V at random point because U of V has this nice form as we saw in the example before so if the verifier can evaluate the U of x i q i then the job is done because everything can yeah so can we do that if possible we want to do it with with the commitment to U of Qi without asking approval to commit U of x iqi for the cost reasons

and then luckily if the QI satisfies these variable conditions under this condition we can do that so this one the fact is G of x i q i is a product of the destruction and U of q i if Qi is a polynomial in the first I variable so obviously if you can evaluate your Qi then you can evaluate your backside UI so in this end we obtain this polynomial identity F evaluates V if and only if there are Qi with this variable condition such that the final equation holds

the verifier I can given the commitment to elqi verifier can evaluate both sides using univariate evaluation protocol now the extra task for the verifier is he needs to make sure the QI satisfies these variable conditions and luckily there is a way to do it and and it depends on this fact Qi belongs to this honest space satisfies the variable conditions therefore it is a polynomial in the first I variables if and only if there is our I

of bounded degree degree utmost 2 to the I such that U of q i is RI times v i and v i is in the polynomial of this ninth one so the idea is this instead of tasking prover to commit make improve or to commit to UI U of Qi we make them make the approval to commit to RI then let's just do the job but but before yeah let's pause a little bit and then look at the meaning of this fact

so that this fact actually means that if Qi satisfies the variable conditions the coefficients of U of q i is periodic in fact if you write U of q i equals r i v i in a more explicit way I mean if you write the vi in an explicit manner you got you get this U of q i is r i x plus and this because RI has a degree less than 2 to the I this simply says that the coefficients of U of q i is a repetition of the coefficient of RI in fact we even know that RI is a

truncation of U of q i it's just a degree less than 2 to the I part of your qi but then maybe it helps the example yeah so suppose n equals three N is a non-work variables so three variables and Q2 okay they it should depends on the first two variables so Q2 is the two for example 2 2 x 0 plus 1 X 1. in this case you can compute U of Q2 like this remember that coefficients are just evaluation of Q2 over Boolean

[Music] Cube so if you evaluate them and if you place them you get something like this indeed repetition it repeats because Q2 doesn't have X2 inside so regardless the value of X2 Q2 take the same same evaluation that's why this this repetition happens in any case we can write it in this product form just the as the fact says okay so I just erased the meaning and example the fact is there

and our previous polynomial identity was this and we use the fact to replace q i and U of q i with RI okay and remember that RI needs to satisfy uh degree condition Roi needs to be less than 2 to the I and so now we get using the fact F evaluates to V if and only if they are RI which are the of degree less than 2 to the I and in fact yeah such that the last equation holds

so now this degree is something verifier needs to make sure it needs to check later okay so this last equation can be written in a slightly better way or like just better looking way because v i if v y can be divided by this denominator x to the 2 to the I Plus 1. and this this is easy to see from the the fractional form definition of VI Return above Indian v i divided by the denominator is just the vi plus one so you get the last equation so

yeah so this is the zero most polynomial identity so basically prover commits to RI of X as an evaluation proof and verifier evaluates the last equation at a random Point using univariate evaluation protocol verifier can evaluate r i and U of f U of V he can evaluate it himself then this big chunk in appearances right after the summation are all public polynomials so this can be done by the verifier so let's write down the evaluation protocol

so I just transcribed the last polynomial identity here on top so first the approver computes ri RI was just a truncation of U of q i so he puts RI like this and output the univariate commitment to it and I goes from 0 to n minus 1. and pmv proven verifier engage in a degree check protocol which we assume that the commitment scheme has allows degree chain protocol to check the degree of RI is indeed correct and then degree of U of f

is less than 2 to the n this last part I didn't explain this degree of U of f is less than 2 to the N this is a technical Point um we needed this to show the extractability of the scheme in standard model and that's why it's there but it's a technical point so and after this the verifier chooses a random point Alpha and this is the point where this polynomial identity is going to be checked and after that pmv engage in the univariate evaluation protocol to verify this capital F takes the value

0 at x equals Alpha so what is this let's look at this first we we assume we need the commitment scheme to be additive and the commitment to U of f is given U of F and our I are given to the verifier so verifier can simulate the commitment to f of x because this chunk appearances of the summation is already evaluated at our Alpha and checking that capital f of x takes value 0 at x equals Alpha is exactly precisely this

polynomial identity equation region on top top of this slide takes uh yeah that they hold at x equals Alpha because the f of x the capital f of x is the right hand side minus left left hand side partially evaluated and this is this is a schema and that one property right this is the property is if the univariate commitment schemes hiding in ZK and the degree Check used in the second step is ZK then the zero morph evaluation is ZK maybe we can look at this one by one

because the first part step one the transcript is the output commitment if the commitment is hiding this is uniformly distributed you can simulate that and second point is a degree check and all the transcript in the second point is internal to the degree check protocol so by assumption if degree check is also Decay that's the Assumption this can be all the transcript it can be simulated third point is a public coin okay you can simulate that and the fourth point is the evaluation protocol

and the evaluation is always zero this is not a message so all the transcript is internal to the univariate evaluation protocol again this is ZK by assumption so you can simulate that and this is all about the recipe and we are going we instantiate this to do that we use the hiding ktg commitment I'd encases your commitment either like a tweak of the kcg commitment in the style of headers and commitment thank you and yeah so so we make the cases you

commitment hiding okay hiding okay and then we also make a degree check protocol for hiding kdg commitment scheme commitment element and I'm going to explain this now in for the rest of this talk but uh is there any questions by now okay so yeah so for the rest of the talk I'm explaining this and logic logical ways of course we have to first we Define the commitment and then Define The Hiding

commitment and then Define the degree check on top of it but that's kind of messy so I want to explain the principles so what I'm going to do is this I'm going to explain the degree check protocol for ordinary cases commitment okay I do it for the ordinary kcg commitment and after that I will explain how to add hiding property to it and modification is straightforward so now we do the batch degree check protocol why suddenly batched because in the Second Step here we need to perform degree check for multiple rois and

multiple degree Bound 2 to the I so it's nicer to have a batched protocol and we are going to make it and there are two steps to do it the first step is the degree bound kcg evaluation so the so this is this is a building block and what this protocol does is allows simultaneous evaluation and degree check of a single polynomial okay and the second state step is the batching technique and this is the technique

to reduce multiple degree checks to a single degree Bond kzg evaluation that is the first scheme the multiple degree check is reduce the single not a single degree check but single degree bound cases evaluation so this evaluation is an additional part but then yeah so I will do it one by one so degree bound kdg evaluation um this is um inspired or hinted by Sonic paper and the scheme is very similar small difference though

so let's denote n Max by nmax we mean the strict upper bound of degrees of commitment polynomials we are talking about ordinary kcg commitment scheme here so this means that the KGG proverb key is the ordinary notation G1 is the generator of the first group and tau is the trapdoor and the SRS goes up to Tau to the power of n Max minus 1. and the goal of this scheme degree bound kcg evaluation is to evaluate f this is a univariate polynomial for the rest of the talk we talk about this underlying univariate schemes so

yeah so and probably until very last moment f is going to be a univariate polynomial from now on so it will evaluate every value takes the value V at U and check that the degree of f is less than some prescribed specific integer d and the scheme I'm going to talk about here works on only for uh works for non-zero evaluation point okay the idea is simple is to just multiply both sides of the kcg polynomial identity by x to the

power of n Max minus d so what happens is this prove our computes the ordinary kcg evaluation proof polynomial quotient polynomial Q of X and he raises the degree of Q of x to the by multiplying X this blue part and he commits to it and verifier check the equality of this identity using a elliptical pairing but to deal with the right side the very far right element x to the power n minus Max minus d

and verify an either higher G2 power G2 verification key but the idea is this so if why why is this enough let me explain why why this is enough so if the commitment polynomial F has a degree greater than D some illegal degree greater than d then this quotient polynomial Q has degree at least the and now this blue part has degree at least and Max

which because of the lengths of the SRS prove our Channel commit to so the fact that people committed to something already says that the polynomial has a yeah committed to the to to something already says that the Q of X or the commit committed polynomial has a proper degree n minus Max minus one and now that's how to assure the degree part and this if the evaluation part is assured by this if this polynomial equality holds then x minus U divides FX minus V

then that means of course F of U is equals to V now if if U equals 0 then x minus U becomes X so it may not necessarily divide f x minus V it can divide this higher V key part then that scheme fails so that's the idea but in any case the the protocol goes like this prover commits to this blue part and verifier checks like pairing and is using higher G2 verifier key

so this is the modification we need to make to the SRS the red part okay operations is that correct I'm sorry are you relying now more when applying Xenoverse on the speed of G2 operations or I just misunderstood the thing um so very so we changed the verifier SRS to include Tau and fair enough okay okay thank you okay thank you okay

so this is a degree one kcg yeah in particular this allows the degree check of a polynomial okay okay next one we are going to talk about the batch degree check protocol and the goal is to check a multiple degree bound like this degree f i less than or equal to d i if all the degree bounds are the same then it's much easier because what you need to do is to take the random linear combination of f i that is why I yeah what was written over here in this big bracket

you take this random linear combination and then just run the degree check on this single polynomial because if one of the FI has you know illegal degree big degree this coefficient will rarely be canceled out by random linear combination so with this idea this is a simple idea but maybe we can use this for a general case where degree bounds are different the idea is to raise the degree of fi all of them to the same level by multiplying the power of x so this is what we're going to do choose

D star which is bigger than any of the I or equal to d i and check the degree of this random linear combination if the this random linear combination has degree less than D star then red part has degree less than D star therefore the FI has degree less than or equal I mean I'm sorry less than or equal to d i right but to do something like this it's not a proper protocol yet it's just an idea but to do something like this we need approval to commit to this red part then after

then we need to make sure that this red point is consistent with the commitment to fi and this can be done for example by this method just choose a random small X and check the difference this red part minus partially evaluated red part evaluates to zero at x equals small X um then this is just an idea and then we combine them together the solution is this set Zeta sub X this is a polynomial and we have this blue part

which we see above yeah we also have this above blue part and then take the difference of blue part and partially evaluated blue part and we make the proof to commit to this blue part which we call f of x and run the degree bound kcg to check foreign less than D Star Plus One and Zeta x x is zero so let's say why why this is enough wrong for first by checking the degree of Zeta X is less than D Star Plus One

we know that the blue part that is the f of x has a degree less than D Star Plus One and this implies that the degree of f i is less than or equal to d i and here we are using we are actually regarding this Zeta X of X as a linear combination by this small X so that this blue part contains no small X and the second part of the Zeta X equation contains small X and we think of this as a randomization

random linear combination by small X so if you see it from this point of view then the degree of Zeta X is less than D Star Plus 1 implies that the blue part has degree less than G Star Plus One so that assures the degree bound of fi but then we need to make sure that this claimed commitment to Blue part was indeed honestly computing and to make sure that this is honestly computed this part is done by this evaluation evaluating Zeta x x at x equals x small X

and so that it becomes 0 is enough to to ensure that the commitment to Blue part is indeed correctly formed yeah it turned out it was enough okay so if let's write down the protocol is getting a little bit confusing and afraid but okay so here the notation the same as before and the protocol goes like this verify and choose is random line approval chooses commitment to improve our commits to this first part the f of x

verifier chooses X this is evaluation point and proven verifier could engage in the degree bound kcg and this protocol this degree check protocol is ZK this is a property we needed for zero morph to be ZK and why is this GK let's go one by one step one the Y is random simulatable two this can be simulated by the simulator because simulator has commitment to look at the definition of f x stimulator has commitment to fi and Y is

already simulated and here is this X this power part x to the power of D star minus d i plus 1 this takes just a trapdoor and simulator is allowed to use it therefore step two is simulatable and step three is a independent random noise and step four this is degree bound kcg and degree 1 kdg is actually just like ordinary kcg transcripts are deterministic to the input so it's everything is simulatable here so what we need we got the ZK degree check protocol then we have the kcg

commitment scheme then we need a hiding hiding kcg the hiding property is what is missing to instantiate the zk0 move now and here's how to make the hiding property as the hiding property so this is this is a particular special case of the lease equal paper and the idea is from I think idea is the same as the fetus and commitment and while working on this we we found that the proof in the recycle paper wasn't exactly correct so we corrected that and get the new proof in our paper but the idea is randomized kcg commitment with a second trapdoor simply

increase the second chapter to the proverb key in verifier key so to come oh yeah to commit by the way I'm focusing on the the commitment part only and so I I temporarily forget about the degree check so I didn't include the higher G2 Powers here and make it into us randomized uh hiding ktg and to for the hiding kdg approval commits to when improver commits to f urther computes the ordinary commitment F Tau 1 and then randomize it with the

second trapdoor by choosing a known Stars and to evaluate for the evaluation protocol approval provides the ordinary uh completes the ordinary cases evaluation quotient polynomial QX and commits to it and it randomized the commitment with a random nodes s and now to verify of course these two c and Pi are not enough for the verifier to verify anything because RN has a completely independent so we need an error term approval knowing SNR both of them the proof I can compute this error term

what verifier does is the usual kdg pairing check just adjusts the difference and this is still ZK this is now a randomized so this is a hiding kcg and we might be afraid that we might have lost that ZK property here but but it's not the case it's a bit why is that because first the transcript is Pi Pi is completely random so the simulator can simulate this and what about Delta because Delta

depends on r or but but then it's fine because when the in the honest proven case when the pairing check passed pairing equality exactly means that Tau minus U pi equals c minus V minus x i Delta and verifier has all the access to all of them it so verify your nose no I'm sorry the simulator knows the Tau U Pi c v x i all of them so simulator can compute Delta so this is decay yeah so let's talk about the cost

evaluation of this scheme when the zero morph is instant situated with the hiding MGK kcg and if we perform a little bit of optimization we get discussed and capital N is the number of coefficient okay the approval cost oh and I I didn't include the field field operations in this cost but that is a yeah field operations are linear in n i mean in capital n with small coefficient so we ignore it prove a cost is G1 MSM of total size 2.

and this is the cost of evaluation protocol I I don't include the commitment phase here so approval cost is a G1 MSM the first elliptical group MSM of total size 2.5 n plus one and by this total size I mean this is a MSM of not one polynomial but several polynomials and total size means the total number of coefficients verify a cost is the G1 MSM total size 2 log n Plus 2.

or maybe I should say one more thing so proof of course is this most of these uh thing the G1 MSM comes from the commitments to r r i's and what is this the commitment produced during the evaluation protocol commitment for the kzg evaluation proof those account for this 2.5 n of the approval cost and verify your cost is yeah just a 2 log n plus two and two G2 operations three pairings

improved size is a log n plus 3g1 elements and these are mostly commitments to our eyes and log n plus two proof analysis and this is all for hiding kcg commitments so for the ZK property we use only log n plus two nonsense and three verify analysis and the protocol is constant five rounds yeah that's the that's the cost any questions I was gonna ask

I was going to ask what is the 0.5 uh like which polynomial has is 0.5 and ah right oh yes this is the degree check polynomial so there was this point oh yes so this F polynomial here we commits to f now for us this fi are the RIS and the the maximum degree of RI we have is n over 2.

so we have we actually have n over G coefficient to commit to f f x in application has n over two coefficients that's where the 0.5 comes okay got it thanks thank you yep so now where we don't really have so much time but let me just advertise a little bit about the shift evaluation even though it is going to be a very sketchy explanation but just tell you what feature we have and you don't worry

like don't worry about time like if we're all fine so like just take all the time it needs you to explain it as well as you want thank you yeah so yeah shift evaluation is is not really about the polynomial commitment scheme it's it's I mean it's about the polynomial scheme but it's something interesting for snack applications especially when you need to do something like a lookup protocol or permutation argument and here is what it is every step polynomial this is the witness polynomial okay and say the witness polynomial has the

form okay every witness polynomial such that it's univariatization is of this form so a0 A1 A2 these are evaluation of witness polynomials over Boolean hypercube that means by definition a0 A1 A2 these things are weaknesses now the shift of the weakness polynomial shift of f is defined as the polynomial defined as the polynomial such that the U of f shift is this guy the coefficient is shifted one down you see a0 became A1 A1 became A2

so this guy in meaning the shift polynomial F shift is a polynomial evaluates to weaknesses shifting a little bit different in the hero yeah so so that the weakness placed on the origin is now A1 instead of a0 like f what witness plays in the position one is A2 and position two is A3 so if you picture it as a for example like a that the execution single weakness as execution trace of a a

socket then this f is a polynomial corresponding to the colon that starts with a0 and then goes down a0 A1 A2 A3 and F shift corresponds to the column that starts with A1 and A2 and A3 so it's shifted one up okay and in the lookup protocol or permutation argument the consistency check ranges over two rows of this column so it's nice to be able to open both F and F shift with one commitment it's about the application thing but

if I fall formulate say it in one word our goal is to is this with the commitment to F of U not F of U shift evaluate F of shift and the short answer is yes we can do it if at least if a a0 is zero then when a 0 is 0 there is a nice spawn x view shift is UF that we can do by by leveraging this we can do this just a short answer and one more thing I want to mention is the batch evaluation this zero move

comes with a nice batch evaluation so you can batch standard multiple you can bet multiple standard and shift evaluations at a single common evaluation point and this is what we need in practice so the single point evaluation is already interesting in practice and so it's very nice and when we do this mode dodging the proverb only needs to work with a batched polynomial so prover's main task is to compute RI the evaluation proof and commit to them but prover can first batch the polynomials and commit compute RI for this single polynomial

so he doesn't need to do you know multiple works and then batch or anything like that it can touch first and compute Roi um yeah that's the feature of Xenomorph um yeah this is the end of my talk thank you thank you very much uh if you have time uh maybe there's questions so uh yeah we can if you accept maybe there's one in the chat uh if you want to read it out loud excuse me so perhaps I just wanted to add

something perhaps that should be stressed a bit it's mainly about the the costs of xeromorphs so one is here one key property here is really that you can get is your knowledge with only login randomness and you have to think about it what n is in practice so n is like a million so 2 to 20 in practice and if you had to generate like a million random field elements in practice means you first have to run you know a PR a PR prng on your software uh sorry on your Hardware then you have eventually two um you eventually have to you know make sure that from these random bits you have to get an integer that is really

between zero and the size of the field minus one and make sure that the the distribution is very close to uniform so you can use several techniques like which is sampling and everything but the point is that doing that in practice actually is very expensive you usually you know if you do it one billion times so zeromorph is really you know at least to the best of knowledge the first uh persistent that achieves you know zero large which only log and Randomness while maintaining all the other aspects uh all the computational aspects you know to the best that we currently have in particular also having only constant number of pairing pairing computations to do for the verifier so that's just one main point I wanted to stress uh

about your move and yes that's uh to answer the other questions in the chat thank you that was really insightful um I will read it out loud so that we have it for the recording uh can you summarize the changes in the Universal setup um setup uh how does the number of G1 or G2 elements change okay yeah that's a good question yeah so uh G1 stays the same no G1 we need to include what is this the second trapdoor right that's not going to use my screen

okay for for G1 we need to include this because I want for G2 we also need to include because I2 and we need to include this higher G2 power we talked about here and in that xeromorph scheme the degree check we perform is of the form 2 to the I degree bound is always 2 to the I for zero moth so what we need is the Tau that the higher Z2 element of the form Tau n Max minus 2 to the I so that means a logarithmic number of

G2 elements does that answer your question thank you is it yes yes thanks thank you and the possibility question is uh what if and you are in a deployment that does not care about the hiding property but you run into the slides and highlighting those elements uh kind of give the answer right so there's elements you need for the degree bound and then element you need for a tahining property e yes yes so two two elements yeah for

hiding property and degree check property I I do have two questions uh one of them is kind of related to that which is if the underlying scheme that you use like I don't know blog or whatever is simulation extractable using xenomorph on the top breaks the simulation extractability property or not the question is if I use this scheme for Planck arithmetization yep can I still simulate the the transcripts and everything is that question so I think I think what he means is that you can still extract you know basically

from a from a brewery exactly even if he has seen uh even if the proof has seen simulated proofs exactly exactly um we haven't really thought about simulation extractability yet um but since what is at the heart is really just kcg if Planck manages it I don't see why you know this wouldn't work as well but you know I don't want to commit on any answer there because we just haven't you know thought about simulation extractability and the second question is in line to what you said Patrick uh about generating like millions of filter elements of randomness so just to see if I um if I follow your idea uh the motivation for this work is

basically the fact that you needed a way to basically be able to prove uh within long case liquidization or whatever uh big amounts uh of of let's say statements that require big amounts of paintings so you actually needed a way to reduce the the amount of paintings needed to prove and verify these interactions to the minimum possible I'm sorry if that sorry were you done with your question or do you want to add something oh oh I was muted I was asking the next question I didn't answer the dude I did hear the question about you know the pairings and

everything like yeah no no I was I was asking the second one so really the one of the bearings it makes complete sense and it's completely clear uh but I was asking another question to you after that but I I think I was muted and you didn't you didn't hear uh yes please so um so mainly the the the thing that I want to understand is related to the statement that you have mentioned uh about the generation of Randomness in random Elements which uh seems also to be like highly impactful here not only the fact of reducing the amount of paintings required but also the amount of random field elements that we need to generate um my question is

like how we can Envision that more clearly because I don't see like what prevents you from actually having I don't know some some selector uh enabled which allows uh everything to pass you only turn up this this selector once within the intellect sequence and you put a random witness value there and then you have kind of blinded everything once you batch and accumulate the entire thing or that's at least maybe that doesn't call it objective but that's what comes to my mind so can you give some intuition on why you get such a reduction on the randomness that you need to generate and also if you foresee any other ways to do all that way

um okay so perhaps through yeah if you're so I'm just trying to reformulate your question to make sure I haven't sure thank you essentially to achieve a zero noise property you want to place a random witness value uh basically you want to have like an extra role in plunk argumentation when you're sure random value basically randomize everything even if you do that um you know this would probably help you when you commit to your wire values but you then have no guarantee that you um by the way first you need to do something slightly different but it would be in that in that direction but even if you were to do that you have no guarantee that your evaluation proves

afterwards you know leak more than just the the claim evaluation can you explain that so when you do some check you know at the end you have your evaluation proofs sure yeah so if you want your entire protocol to be zero knowledge first you need a zero noise version of subject to make sure you're not leaking sure values but at the very end since the very far is not the one doing the evaluations and the other finally has commitments to wire values you want to make sure that your evaluation protocol itself is zero knowledge as well so basically you need that every bit in

your I see if every component is your launch yeah so in particular you want that your evaluation protocol for your multi-linear scheme is zero numbers as well if you want the entire protocol the entire arithmetic size availability circuit to be zero launch probably makes sense thank you so yeah and perhaps something was a bit confusing about the pairing so I would say um you know multi-linear kcg already gave you you know the answer for multi-linear evaluations with login pairings if you optimize Gemini you actually get a constant number of pairings I think it's like three or something burning computations so you know like silver said at the

beginning the the main motivation was actually not yet the pairings the number of pairings you would have to do um but rather you know you wanted to reduce the amount of Randomness as much as possible without sacrificing the already constant number of pairings that we had with Gemini makes sense thank you are there any other questions from anyone I'll assume not I'm not going to see anything in the chat either so yeah thank you very much uh Dr for giving the

talk and also Patrick for being here in in providing some additional support and or answers to all of the questions um congratulations on your work guys and thank you very much for for being here today uh sharing your knowledge with with all of us I appreciate it so much thank you thank you very much take care have a nice day take care