ZK7: Pairings in a SNARK - Youssef El Housni - ConsenSys

Transcript

[Music] so hi everyone so my name is yusuf i work on gnark at consensus i'm also doing a part-time phd in parallel so i'm going to talk about pairings in one cs so we had this presentation if you were here before or on arithmetization so including l1cs so that's cool um so i'm going to talk about oh yeah just some preliminaries on snacks and pairings and then some motivations why we would like to to write pairings in l1cs and then how we would how we did optimize the pairings or the number of constraints of this circuit

so here i just give two examples of uh yeah girl 16 and plonk so um what is most important for us is the proving time so uh basically if you you reduce the number of constraints then you would use the time to to generate this pro so this is why why we want to reduce the number of constraints um so billionaire pairings also yeah this slide is just for annotations so you have a an elliptic curve here given in short fire transform so defined over some finite field of prime characteristic or a power of a prime and it has a subgroup order which is a prime so it is pairing friendly it means that it has an embedding degree which is not too small

not too big maybe in the range of 10 to 30. so the impeded degree is this integer k which is defined as the smallest integer such as the sub group or the r divides q to the k minus one so a pairing is a bilinear map that goes from g1 cos g2 to some target group gt g1 and g2 are defined over elliptic curves so one over the finite field the other over some extension and gt is also a group of order r but this time it is defined over an extension field that not occur so it is for some kind of pairings the authors of unity so motivation why we would like to do

pairings inside a circuit so um so for example if you take us 16 pulls or planck proof so so the the proofs are constant size so it is a bunch of elements in g1 g2 and the verification is also a bunch of elements in those pairing groups g1 g2 and gt and the verification equation is this pairing equation so this equation one and if you manage to verify this pairing equation inside a circuit then you can aggregate proofs another exam another application is private computational as xe and so ali is using this in production to to to have these verification keys as secret so that you have a universal uh it should fix itself yeah

so on a universal circuit so another application is so bls signatures so the bls signature verification is also this pairing equation and the cello is using in production a snark to prove this bls signature so this is another uh application and finally maybe if you want to put to to to verify kzg very kgb verification equation inside a circuit so this is something that we can we are considering for zk evf so when you want to do a recursive process of zika evmk kcg base zk evm so also the verification is uh is a pairing equation uh so

why we're talking about this because it's not easy to do this because we have actually an arithmetic mismatch so uh the computations of the programs uh you know are expressed over fr without the subgroup order of the elliptic curve that you use to to instantiate your snark the proving will also do over fr but the verification is a pairing computation which takes place in a different field which is f q to the k and q is different from f so maybe you can take the same analytic for which r is equal to q but this is just the security assumption is is broken the second attempt would be to simulate operations so this is quite inefficient in l1cs but maybe in planck we have more

um tricks but anyway it it will be slower than native arithmetic so we will not use the same ellipticals but two elliptic curves to do the the trick so what i mean by two elliptic curves so whether we need a cycle of elliptic curves or two chain of elliptic curves our cycle you find two elliptic curves for which the sub group order of one is equal to the field size of the other one and vice versa or maybe you just need a relaxation of this notion which is just you start from a an inner elliptical so the one in the bottom and then you construct a curve for which the subgroup order is equal to the field size of the inner cursor so this is the inner curve the outer curve we will be more talking about these two chains so we had a paper

accepted this year to eurocrypt where we construct these elliptic curves basically for gauss 16 applications or kcg based applications this is not what i'm talking about today but what i want to talk about is these pairings so there is a line a long line of research on how do you efficiently implement pairings outside of the circuit but there isn't a lot uh of research how do you implement this efficiently inside of a circuit so our pairing so is a non-degenerate bilinear map so if you do not want to look at the equation just look at this uh tick z by diego aranya so you have two curves so

billion linearity means if you pair a times p and b times q with a p and q points on the curves and a b scalars then the output will be the pairing of p and q to the power of the scalars a times b so there are many variants of pairings so here i'm just mentioning the most efficient one the eight panel optimal eight pairing uh so it is done in two steps uh so what we call the miller function and then what we call the finite exponentiation so you just need to compute a function and then you exponent to q to the k minus 1 out of r so for bls12 will be

less 24 this is what you need so what are these functions so this is just a definition from so for what is a miller function with algebraic geometry notions but we do not care about this because algorithm wise we just use this trick because at the end of the day we do not know what is this function we just need to evaluate it at some point p so we use this iterative fashion uh if you have a so so basically this this equation so which gives us this algorithm so basically this algorithm is an iterative

algorithm so it's a loop so it's you take the the bits of so the what i call the size of the miller loop the points q p and q and you compute so some lines and some multiplications some squaring so basically it just boils down to computing some arithmetic over the curve so here we just have doublings and additions and over the finite field extension we just have some squarings and some multiplications so as i said there is a long long line of research in order to optimize those pairings so you we need g2 operations so we do not work over the full

extension feed f q to the k but we can compress the coordinate to some subfield so to so q to the k out of d with d some some some twist degree that parameterize the the curve and then we do not use a fine coordinate we use projective coordinates maybe so homogeneous homogeneous projective coordinates for instance because you can share computations between doublings adding some line evaluations so there is a long uh so many tricks on the finite field you can also construct the finite feed the way you want uh you just need to go through fp to the k out of d because you know you need this for g2 and you we have also some tricks in order to do some efficient

multiplication in the finite field when the elements are uh as pass and finally the final exponentiation is the raising to this power f q to the k so p to the k minus 1 out of r so we divide this into two parts easy part and hard part so what you need to learn is that it just the easy part is uh easy it's just a polynomial in p and there is in an element to a polynomial np is fast because you use forbidden use maps so for the l sub it just cost a foreign map that conjugates an inverse under multiplication in fp12 and the hard part is more expensive we have some tricks based on

vectorial addition chains or lattice based optimizations but the dominating cost at the end of the day for this hard part is squaring and multiplications in this finite field so it's only now that i will talk about our work but it was necessary to introduce these techniques because what we want to do is we want to implement pairings for inner bls 12. so those curves are always of the form y square equal to x cubed plus one so they are polynomial base which means other parameters are given in polynomials and so k is 12 d e6 so gt is over fp12 g2 is over fp2 because you divide k

12 by 6 and then you can choose any any tower field construction you want but inside the pairing we will choose uh the first one i mean the difference of performance is slightly the same but if you use the second one outside of the circuit you you have better compression so you have a ratio one out of three and in the one the first one uh one out of two but those are details so the point is we need to implement this mirror function and then this pairing this exponentiation inside of the circuits efficiently so here are the the the papers or some of the papers that best implement pairings on bls12 so

i'm not going to talk about l1cs but what i want you to know is it's just about quadratic equations so you just need to write your to whatever statement you want to prove with these quadratic equations and so this is a famous example by vitalik buterin and but at the end of day you just need to write o equal to l times r so with all those techniques we know about to implement pairings so pairing over bls237 is just well less than one millisecond if you just try to naively port the best optimizations we know outside of the circuit inside of the circuit the number of constraints will be 80 000 which is quite a lot

so the point is to reduce it significantly so when you see when you look at on the internet or for pairings inside of the circuits there isn't much literature so they just are github tickets on zcash and implementation wise there is just i believe arc works and maybe lip snark for so for some other cars mnt46 so artworks reduce the number of constraints to 19k from atks which is quite a lot and we were able to reduce it even further to 11k so we went from 80k to 11k basically so how we did this uh is this list of tricks that i will

detail so um so as i said the l1 c is about 18 0 is equal to l times r so squares and multiplications in the finite field are the same constraint wise but inverses are not because inverses are caused the same as a multiplication plus one constraint so instead of doing the inverse you just compute the inverse outside of the circuit one out of l is equal to o and you provide o as a hint so inside of the circuit you just compute l times o so you substitute an inverse by a multiplication and then you check that it is equal to one division the same not one but it is up and also outside of the circuit we always do inverse plus multiplication but inside

of the circuit we can just do division and then we get rid of the multiplication uh cost of constraints over an extension field so squarings are not multiplications because we have other techniques to so to to to reduce the squaring and all the the the inverse and divisions uh tricks are the same so outside of the circuit we always use projective coordinate or jacobian coordinates because we do not want to do inverses here we don't care about doing inverses because they much they cost almost as much as as

as multiplications so this this is the number of constraints for doubling and add-ins so the doubling is has more constraints than addition which is funny because so when you do this miller loop so the size is fixed so you can do an addition a short addition chain for this uh for for this loop and short addition trays always when we create short addition chains we look at maximizing the doublings and minimizing the additions because doublings cost loss it costs less but inside of the circuit it's the other way around so

this is one of the tricks the other one is so when the bit is equal to 1 so we do doublings under addition so 2r plus q but i said that doublings cost more than addition so we can just instead of doing 2 times r plus q we do r plus q plus r so it saves us two constraints but then we can do event better so in the first addition you can just omit the y coordinate and this would reduce the number of constraints to 17 so from 22 to 70. and you do this whenever you have a bit equal to 1.

so the line so the line evaluation so the line is a so a y plus b x plus c and we need to evaluate uh this line at some point p so whether so the line that goes through uh two points so two points or the tangent line so there are a long a lot of tricks for this outside of the circuit but the best one is this so paper from alania barretto and others so it is a sparse slide so it is an element in fp12 but we have like three zeros three fp two zeros so the multiplication is spas so in constraint wise it's cost so a full

multiplication cost 54 but this past multiplication cost 939 so the trick we can do inside of the circuit is we pre-compute one out of e so so the the inverse of y and the division of x of p so that doesn't cost five constraints that does cause just one constraint one constraint because p over uh so the point p is over g one not g2 but anyway so it's called just two constraints as a per computation and then you multiply this and the line you had is uh this one so in blue so this if you multiply an element in fp12 with this sparse line it costs 30 constraints so compared to

30 to 39 so these are the tricks for the for the middle loop for the final exponentiation so the easy part is just this code so you do a conjugate no constraints added and inverse 66 constraint multiplication 54 four being a square no constraint and multiplication 54. so as i said you can merge inverse and multiplication so you just inside of the circuit you just get a just just get get rid of one but we were able to do slightly better so more on that later but we can reduce the number of constraints from uh 174 to 60.

and we cannot do and we can omit the decompression as well as i will explain but why is that so i will move to the hard part and then i will explain why so uh outside of the circuit there is a recent paper by higher sheet i also implement this hard part with lattice based reductions so uh it so this is the the code basically in go and um [Music] so what why is in blue is what cause constraints the others are three constraints wise so it's just about squaring so i call here circle atomic square multiplications and xpt xpt is the exponentiation by a constant so we can so it is always the same constant so we can have a short addition

chain for this so it's cost multiplications and sql atomic squaring is also at the end of the day so uh we would like to optimize these squarings inside of our circuits so outside of the circuit the best algorithm to do the signal atomic squarings generically speaking is a paper by granger scott so inside of a circuit it costs 18 constraints and the normal squaring costs 36 constraints so there are also two pages so another paper by calabina where we can do 12 constraints or 15 constraints but then we need decompression which costs 19 constraints or eight constraints and then there is also this taurus t2 paper by

ribbon silverberg where the cost is 24 and the compression is costly the compression is costly constrained twice so why we would use this but the takeaway is that if you have just one or two square two consecutive squarings you use grand just cut inside of the circuit it's 18. but if you have three squarings you would use carabiner the first version or more than that so far you you would use carabiner because you amortize the the cost of the decompression because the decompression is done only once uh multiplication so the multiplication costs 54 constraints over fp12 and in taurus based it costs

12 constraints less so 42 but then you need compression and decompression but the nice thing is that you can do t2 you can do squarings for both t2 and satoru is based and squares so you can amortize the compression and decompression you can do it you can do compression at the very beginning and decompression at the end so you can do the whole final exponent exponentiation in comparison so instead of working over fp12 we can work over fp6 and better we can even get rid of the compression and decompression because as i will show you we can absorb the comparison costs in the easy part computation and do we really need decompression

because in the applications i mentioned we just need to verify a pairing product so you just need for example to check that two pairings are equal so whether you check them in compressed form or in the compressed form we do not care so decompression can be amortized uh so we can get rid of decompression and computation on our test okay uh definition of what is uh now i'm going to talk about taurus so algebraic story uh so this is the definition um if you want to read it so the the so you just have this uh norm uh but uh what is what the takeaway is that

if you take an element in fp in fp to the k q to the k or fp12 then if you do the exponentiation to the easy part then the element is in the choice and if it is in the toys we can use these uh multiplication squaring techniques so the t2 crypto system was introduced by ruben silverberg it was fashionable at that time because it was a replacement to msa but no one is using it why no one is using it because here are the algorithms to do arithmetic over over a choice of choice so there was a long line of

research to do compression in finite field extensions so xtr lucas sequences but those use traces they are not groups so you cannot do multiplication you can just do squarings for instance um but then you had this paper which introduced t2 and kylie character systems where you can do full arithmetic but the problem is that well there are inverses so no one is wants to do arithmetic with inverses outside of the circuit but as i said in l1cs well we do not care to use uh inverses so it is pretty much l1cs friendly so when you see here the compression cost just one one inverse in fp6 not fp12 so the

decompression cost one inverse in fp12 the multiplication cost just so one multiplication fp6 one division in fp6 and the squaring costs just one division in fp6 inverses are just a negation so they are fair so this is what we use and then as i said we will absorb the cost of uh compression uh in the easy part so in the easy parts we need to care to take an element in fp in fp12 to the power p to the sex minus one p to the p square plus 1 so this is the p to the k minus 1 divi divisible divided by the sickle atomic polynomial so

the simple trick is to take the numerator to p to the 6 and the denominator there and p to the 6 is just a conjugate because we are working in fp12 so we divide by c1 so at the end of the day compressing it is we can merge the compression and the the computation of the easy part so it just costs uh one division and then we need to rise to p two plus one so uh exponentiation to p square is three and then you just need a multiplication so the cost of doing the easy part and compressing the the element is just 60 constraints so just a multiplication and

a division in fp6 so we have also further optimization so uh the point is two k so this is not implemented so the 11 000 is without this so the point is to carry the miller the the whole miller loop in campus farm so but the miller loop happens before the the the easy part that puts the element in the choice so how can we do this is well we will just take this trick here whenever we have an element in fp12 in in the middle loop so we will just compress it this way and we will use t2 square synchro atomic squaring and not normal squaring and the line so the trick for the line is since we divide

divided by this y so we have the first part so the the first fp6 part is just one and the other one is is a full element so when you use the same trick it's just an inverse and even better we we we won't even compute this inverse because we will also absorb it in the computation in the in the multiplication in compass form so at the end of the day it will cost just a division and a multiplication in fp6 um so the implementation is open source it is on mr so it is mit apache licensed so it is on gnarc uh library in go so an example for vls2 377 so the number of constraints is 11

thirty five so we went down from nineteen thousand two to this so i just give an exam examples of gross 16 verifiers bla signature verifiers and kzg verifiers so they cost 19 14 and 20 000. so for bls12 it costs more than that because we have fp24 so it costs 27 constraints so we have more optimizations in mind not implemented so the these are the so to reduce the number of constraints even even further um and finally so you can try the code of in this playground so play dot gnark dot io so i don't have wi-fi

yeah but the idea is we have a playground in gnark where those examples are are pre-built and you can do gross 16 recursive pose or bla signatures inside a snark or kcg inside the snark and you can do this with both planck and the ghost 16. so the numbers i gave are for alphago 16 but the same tricks works also for plonk but maybe for plonk we will have more optimizations that will come up soon uh yeah yeah sure hearing like the optimize like the miller loop on another one yes the other like weird way to con pairings like

using elliptic nets yeah i wonder like in that case like the elliptic nets are not really faster than this i wonder will so the number of constraints are more than that familiar so there are a bunch of tricks that works outside of the circuit so if you notice i just crossed this one so this is a recent paper by patrick longa from microsoft to do multiplications outside of the circuit and he managed to reduce the number of uh the the time for a pairing uh for example also on ethereum so for the bn or the bls 12 but inside of the

circuit it increases the number of constraints so i've looked at some tricks that works well outside of the circuit but inside the circuit this is what i just come up with maybe there are more all right one more question if you have like a product of several variants will there be circuit yeah so what i didn't tell you is that so this is the cost of just appearing so the ghost 16 verifier the bla signatures and the kcg verifier so they it is a product of pairings and the cost i i'm giving here is not the the cost of a single pairing separately but it uses multi pairings so we also implemented multi-pairing tricks inside the circuit so you can like

neutralize some squarings in the middle loop you can also multiply the lines together before multiplying them by the accumulator so it is already implemented if you want to look at the code perfect thank you [Applause]