ZK Paris: Tohru Kohrita - Zeromorph Zero-Knowledge Multilinear Commitment Scheme

Transcript

um so next up we have xeromorph zero knowledge multi-linear commitment scheme by tobu karita at Aztec thank you for the introduction and uh this is a nice opportunity to talk about xeromorph this is a joint work with Patrick Tova who is uh he's my colleague at the Aztec lab and I'd like to also give thanks to Ariel who is here today because he helped me a lot to learn the basics of the commitment schemes when I was working on this project Okay so

okay that is the following and we first talk about what the zero morph is and this is a polynomial commitment scheme and then so we talk about the commitment algorithm evaluation protocol and finally touch upon the cost evaluation of a particular instantiation with uh kdg polynomial commitment scheme so what is zeromorph it is a recipe to obtain a multilinear PCS from additive univariate PCS with degree check protocol by degree check protocol I mean the protocol that allows the verifier to check the upper bound of the degree of the committed polynomial and we we require this degree check protocol to be

knowledge sound the first I will talk about a little bit of the motivation behind this work and that is this we are interested in this assumption check based proof of circuit satisfiability and we expect that the subject-based proof of cells proof is more efficient than the traditional univariate Planck proof system but to use the subject-based to prove Samsung protocol we need to have a multivariate commitment scheme and that was the background of this project and so the zero morph is based on the same multi multivariate polynomial

equality check as the multilinear kcg but we do this with univariate commitments if if you follow the recipe and if the underlying commitment scheme is hiding and underlying evaluation protocol is ZK and the degree check protocol is ZK then the resulting xeromorph evaluation is also zero knowledge so the okay so jump into the commitment algorithm so the idea is to convert multi-variate multilinear polynomial into a univariate polynomial and commit to it using a univariate commitment algorithm and so here what we we have to do is here

the source of this map is denotes the vector space of the of multilinear polynomials in N variables and the target is the univariate polynomial of degree utmost 2 to the n and our goal is to make a nice map between them and the two Vector spaces are abstractly isomorphic of course because they have the same Dimension 2 to the N so the question is what is the most suitable isomorphism for our purpose and the map we use is the following like n equals one case the bivariate case now this is the simplest one we map the bivariate multilinear

function f to the univariate polynomial whose coefficients are evaluation of f over Boolean points but the question is how to in the way we place the this evaluation of a Boolean points is The Following this this the red lettered ones these are the what is this Boolean points and we interpret it as a binary representation of integers for example 0 0 representing the zero so we place it as a coefficient of the degree zero term that is the constant term and one zero represents integer one so we place it as a coefficient of the degree

one term so the left is the least significant bit in this convention and 0 1 represents integer two so we place the evaluation over 0 1 as a coefficient of degree two term and so on and this obviously makes sense for any n so for the general case we have this isomorphism and we use this one and we call this currently you to remind ourselves this is a univariatizing process so General case the multivariate polynomial f is mapped to the univariate polynomial U of f the coefficients are U are the evaluation of uh Boolean points f of b0 to B and minus one and we place

it as a coefficient of the corresponding degree to commit to F the multilinear f a zeromorph proverb comes to U of f using a univariate commitment scheme and the reason we we choose this map is the following so we are interested in this proof of circuit satisfiability and approval of this kind this this approver usually starts with witness values and Returns value and then he take the multi-linear extension of it and then commit to it but the U of f is free for such an approval because he started with the coefficient that the witness values itself

so now the evaluation protocol we have the univariate commitment to U of f and we have to open F itself not the U of f so this is the non-trivial part so to explain the evaluation protocol let's fix the notation f is the commitment polynomial and variable multi-linear polynomial and Z 0 to Z and minus 1 is a point in FN this is evaluation point and the claim to prove is the F evaluates the V the value V at this evaluation point and we know that from the this is well known that this statement is equivalent to the existence

of q i the polynomials such that the equation two holes this is the usual multilinear kcg evaluation evaluation equation so over here I wrote in red x i minus 1 this is a condition this is a tested claim I make I'm making here and we we force the approver to follow we force the prover to find the QI that is a polynomial in that only in the first I variables and we are going to use this in zero modes later so this is the point to force the prover to do it okay so back to the usual multi-linear

kcg what the verifier does to verify the quality too is he the verifier receives the commitment to Qi from the prover and then he uses elliptic curve pairing but for zero morph we are not going to do that but what we are going to do is to apply the U that isomorphism in the previous slide to the both sides of two make it into a univariate polynomial and the verifier check the quality at the challenge point so this is what we are going to do so the verifier needs to check that there is Qi satisfying this conditional variable that satisfies that yeah such that the

equation 3 holds so suppose that approva provided the commitment to U of Qi then the verifier can use the univariate evaluation protocol to evaluate U of q i and U of F at the random point and verify I can compute U of V at the random Point by itself because it has a nice explicit formula the question is can verifier evaluate U of x i q i at the random point and the way we do is this a nice fact U of x i q i is actually a product of U of q i and this fraction so if

and for this fact we use that q i is q i is a polynomial only in the first I variables so throwing this one into the previous equation the verifier needs to check this equation for f evaluates the V if and only if there is q i satisfying the condition on the variable such that equation 4 holds now if you have a commitment to U of q i then you can evaluate both sides at a random point the problem now is to make sure the q i satisfies this variable condition and the way we do this is this

Qi is honest if and only if there is univariate polynomial RI of degree less than 2 to the I such that U of q i is a product of RI and v i and VI is a uh yeah polynomial written here it's in a fraction form but this is divisible so it's a polynomial so throwing this uh defect into the previous equation or the principle we obtained this F evaluates to V if and only if there is r i of this bounded degree such that this last equation holds

now if you have a commitment so that it goes like this the proverb computes and commits to RI and verify improver engage in the univariate evaluation protocol and all and then evaluate both sides at a random point and then verify an improver engage in the degree check protocol to make sure that RI has a bounded degree and by the way that last equation can be written in a slightly Slimmer way I just use that VI divided by this this chunk is pi plus 1.

algebra here so this is the equation to check say valuation protocol P computers are RI and commits to univariate commitment yeah commits to RI using a univariate commitment algorithm pmv engaging degree check protocol to make sure that RI has the correct degree and also degree of U of f is less than 2 to the N I haven't talked about this yet but I'm going to mention this last check later which uses a random nonce at challenge point a PMB engage in the evaluation proc univariate evaluation protocol to verify that capital F takes a value 0 at x

equals a so if f of x takes the value 0 at x equals a if you throw the plug x equals a on the right hand side you see that this is just the right hand side minus left hand side of the previous the equation in the previous slide so this is about yeah okay [Music] and then the reason we do F the final one in this way because if you it's much more efficient than opening U of F and RI of X individually and also if you do it do it this way in one go you can you do not need to reveal the evaluation of U of F and r i of X at the challenge

point and this is handy because we have less transcript so it's easier to make it into zero knowledge okay and maybe I should also say that notes that the verifier can simulate the commitment to f using the commitment to U of F and RI of x okay so if univariate commitment scheme is hiding and ZK and degree check is also decayed and zero modification this is a fact uh okay about the degree check on the U of f so we wanted to prove this evaluation from the knowledge soundness of this evaluation protocol in the standard

model and to do that we needed to extract we need to extract the small F but then we do not perform the actual evaluation univariate evaluation on U of f so we couldn't do that there is no way to do it and therefore we invoke to the knowledge soundness of degree check protocol which we assume okay so finally the cost because this evaluation by the way doesn't look so efficient but if we instantiate it if we use the kcg protocol univariate commitment scheme as underlying commitment scheme we can merge for step two and four together and then do some optimization and we can

achieve the following the capital N is okay let capital N be 2 to the N the number of coefficients of the commitment polynomial the approval cost is G1 I'm sorry so G1 means that the first pairing okay the underlying univariable commitment scheme is kcg so there is a pairing we use the elliptical pairing and then G1 denotes the false bearing group G1 MSM on size n plus 1 for commitment G1 MSM on total size 2.5 n plus 1 for evaluation total size means it's not just one one polynomial is actually several polynomials in the total number

of coefficients and the size of the MSM is 2.5 and verifier cost is the G1 MSM of again total size 2 log n Plus 2. and two G2 operations three pairings proof size is logarithmic and we use the log n plus two random nonsense and this is kind of optimal because in this instantiation log n plus 2 is exactly the number of independent transcript that proverb produces and finally the evaluation protocol is constant round and five rounds yeah that's it thank you

[Applause] awesome thank you taru do we have any questions for toru um um how do you compare this with a tensor check that we did in Gemini because we had only two pairings for no just like a couple pairings for verifications without all these msms yeah so uh so for Gemini I counted the performance and the open protocol after some optimizations and using the Splunk protocol

uh yeah first Gemini you need to use open the evaluation at multiple points yeah that's about the standard batching technique yeah yeah and so the evaluation protocol cost uh at least three and and zero more of course 2.5 n 33n msms yes three n msms but this is like a like a log n number of three and divided by log n MSN I just need to compute one quotient no no in Gemini no you have to come commit to the folded uh yeah Fold It folded polynomials

okay I see thank you okay uh yeah any other questions thank you Terry foreign [Applause]