Elliptic curves and SNARKs: past, present and future. by Youssef El Housni | Devcon SEA

[Music] [Music] uh hi everyone uh my name is uh Yousef yeah so I'm a cryptographer at consensus working on gnach the ZK Snak library and Linea the ZK evm um and today I'm going to talk about elliptic and SNS so I have two problems in my life one getting my wife to choose a restaurant difficult one and two ethereum supports only BN 254 promis so today I'm going to talk about the second problem because the first one we need more time right uh so what are these BN 254 pre compiles so BN 254 is a elliptic curve so it is this mathematical object on which we can do some sort of craphy and mainly these three operations that we call pre-compile so they are like native smart Contracting ethereum so you can do addition like take two points and add them have a third point and you can do Scala multiplication which is if you multiply a scalar by a point so you get another point which is like adding the point in times to itself and the scalar and pairing product check where you have some bilinear map it takes points on elliptic curves output them on some line some extension field and multiplies this and check if it is one so I'm not going to talk in details about these operations but you can look at the illustrations and pretend you got it so what is most important is uh what is is useful for so it is useful for doing snar verification on ethereum doing BLS signature verification on ethereum like doing some polinomial commitment like kzg verification on ethereum and some vle trees at least with what we have for now and uh so we've talked about BN 250 254 as an elliptic curve but there are so many elliptic Curves in the wi and what I'm trying to explain today is why there isn't like a single silver silver bullet curve to hold them all so you might have heard of bls2 381 SEC p256 so used for ecdsa signature on eum if you change a letter you have another curve you might have heard of ed25519 some Two Chains some Cycles like pasta twiddle some fancier names like jbjb Bender snatch gram King and some new names like lollipops yeah so many names so what I want to start with is some definitions of what is past present and future right so past are curves that have been used in snarks but not anymore present curves that that are still being used in snars today and future is Cur that's already exist in the world but not used in SNS just yet so if we follow this color scheme then yeah so we have some green was in the past like mnts or twiddle cycle some blue like BLS or two chains and some uh future purple like lollipops and yeah you we see that BN is half blue half green that is because it is still used in ethereum but it's not secure anymore or at least it doesn't have the targeted security so uh to organize this mess I uh propos to categorize it into three columns so I'm calling non pairing friendly curves pairing friendly curves and in circuit curves so uh again this pre compiles I talked about pairings but not all the elliptic CES are equipped with pairings or at least not efficiently and if your snar doesn't need pairings so you can use the cures in the First Column if your snug needs pairings then you need curves on the second column and in circuit curves are these kind of curves that were built in purpose to do some computations over the snack not to do the SN but just I don't know you want to prove some signature with a SN then maybe building an efficient elliptic C would help you so if we look uh if we take a closer look to the First Column so we have for example SNS like bulletproof or Halo or Nova they can use the curse from the first uh column but then the question is why there isn't like a single curve well it depends on what you want if you want performance then maybe ed25519 is the best curve if you want standard maybe the next curve if you're scared of this maybe you choose another standard like Bitcoin or ethereum curve like s if you want a recursion that is you want to do a proof of approve then maybe you can use SQ if you want compatibility with CP if you do not care about compa compatibility you just want performance then twiddle if you want more performance then pasta if you want hybrid recursion that is a snar from the First Column and the snar in the second column then maybe fluto Aries or grin BN if you want compatibility with ethereum what about the second column so the second column is for snars that are pairing based those are like G 16 or anything that is based on kcg like plun for instance so you can use any curve in the SEC in the second column and then again why there isn't a single curve if you want ethereum compatibility then BN if you want performance bls2 if you want one recursion that is proof of appr proof maybe you want to use two chains if you want infinite recursion with paing base so you have stuck with mnts but these are slow either slow or un secure if you want some hybrid recursion then you can also have other uh propositions here so the last colon is so for example if you want to prove some signatures like EDSA or ecdsa or some specific hashes on elliptic curs or some vehicle trees then you can choose from this third column but then again if you want just elliptic curve cryptography you might want to use jobjob if you want faster elliptic curve cryptography may be bander snatch if you want sping based cryptography then you need for example two chains or Cycles then bw6 or MN either you want one recursion or infinite recursion if you want to mix things and make them sentous maybe the lollipops if you want to make them compatible with BN then maybe grk so this is why we do not have like a single elliptic curve but on ethereum we have a single electric so what I want to talk about next is The Story So Far So gold vas mikali and ROV they invented zero knowledge RS and there have been a lot of papers both on the Practical side and the theoretical side sense yeah a lot but what I want to focus on is pairing based snacks because those uh constructions they were based on different assumptions and even those that were based on elliptic curves they we didn't care about which elliptic curves because we can take anyone but starting with paing BS we started constructing elliptic Curves in purpose for snars and for me the turning point was this paper by Bono and Nim it has nothing to do with snars it is a dou homomorphic encryption scheme that is you can do any additions you want on the cipher text and a single multiplication on the cipher text but it wasn't practical and this is because for the decryption we needed to solve a discrete logarithm problem so not practical but fortunately uh so researchers like gos G OSI and sahai between 2006 until 2000 yeah yeah until 20110 they built on top of this idea of w homomorphic encryption because they said well it's not practical but maybe in zkps we do not need to do decryption we just need some sort of a commitment then maybe we can ditch decryption and we can have zero know TRS and they did this but we didn't have implementation at that point and the Turning Point implementation wise was this paper by J all they propos insightful constructions for polinomial commitment and mixing this with the pairing based papers pairing based SNS papers well we started having implementation and the first implementation I'm aware of is this uh paper called Pinocchio and when I looked at the code it was proprietary still now but they used a BN 256 curve from another paper in 2010 binary all and it was uh it had 120 128 bit security at that time and two adct 5 so the term was not Co to adct at that time but it just mean for now like let's say perform performance metric um a few months later there was this paper parney where they implemented BST side license Pinocchio with another elliptic curve b254 from another paper in 2010 and it has a two addic 45 at that time even if we didn't know know about what is toct is for um so same year so basa and others they uh implemented so Pinocchio V variant and they used a very specific eliptic code I'm calling gmv 6183 it is due a to a paper to galberth mck and Valen and the implementation is still there today in libf it has a 2 31 the two notion was introduced in this paper but it had a security 80 bit so they just so it is like for those who know it's just like an MNT curve but with a co-actor equal to four so that they have like a a twisted Edward form so uh next year pretty much the same authors they uh proposed the BN the famous BN 254 curve the curve that we are using today in ethereum and what they wanted is a two add C to I mean BNS were used in pairing based cryptography but in SNS they want at two ad so they constructed this curve with two ad28 but my question is why they use the curve from Pantry which has already a 45 to adity and both on the prime field the the the base field and the scalar field and yeah I mean implementation wise the one that we have today in etherum is ugly especially when you construct the tower and this one was pretty much simple um but yeah parings were used in cryptography and so their researchers have been working on the Crypt analysis of pairing but the Turning Point Crypt analysis wise what this paper by Kim and barbulescu so they found a new complexity for solving discrete logarithm problem over extension field but to give proper credit it was this paper in 2016 same year by menes S and syn where they anal analyzed the conclus the I mean the impact of this kimon Bible School paper on the choice of elliptic curse and in their conclusion they proposed using bls2 12 curve and for the for the record BLS 12 there were curves from 2001 and BM from 2005 and few people cared about bls2 because of BN but because of this paper we came back to bls2 and I believe based on that forx ad zika especially shenbo they proposed the the the famous BLS 381 that we're going to have now in pectra upgrade in ethereum uh now if you want like a recursion you need two cures this is what we called two cycle so you you need two curves because to to express things efficiently in a recursion you need the curves to share some parameters and it was this famous paper uh scalable zero knowledge via cycles of elliptic curves uh by basol that proposed the first practical setting for recursion and they devised the MNT 4289 and uh 298 and to mn6 298 uh it has low security big at to add City and they also found another cycle but they updated the paper only in 2020 on ePrint 20 years later uh six years later I'm sorry but uh they shared the code with the they shared the parameters with Koda folks now Mina and they used Mina used this at some point so it is a paper from 2001 the construction of the elliptic curve due to M Tako but just to give proper credit again so it was a paper of 2008 by carabina and Tesco who established for the first time that MNT 4 and MNT 6 form a two cycle uh and yeah so because of security we need big parameters and it was or who gave I think the biggest one so far uh of size 992 so it is not practical I mean it's it's slow but yeah for research it's there but the two aity is small and it's very difficult to find a higher security with higher uh adity MNT Cycles but I think two weeks ago Costello and corpal they proposed this paper lollipops sing friendly elri and they solved the problem of higher to ad for MNT cycles and the idea was pretty much clever they took the Mt Cycles I mean the problem with MNT Cycles is like you need to solve this uh pale generalized pale equation and to increase your search space you need to increase the discret some discriminant and bigger the discriminant the harder it is to find the curves let's put it like this and what they did is like they took mnts and they use some super singular elliptic with some other algorithm called Boker and it works but it is still slow so not practical and uh also Santos Costello and Nik they looked at cycles of paring friendly not elliptic curves but Curves in general so and they propos some mix of elliptic curves ordinary super singular and also some hyper altic cures so it is as slow as MNT as far as I can tell and Al it is still early research so implementation wise it's going to be difficult to do like this a billion varieties implementations efficiently now if you want just recursion but not infinite recursion you just need to do a proof of approve maybe just for aggregation you need two chains so there is this famous paper called ZXI they introduced this curve called BLS 2377 which is used I think in in Alo and in Salo others blockchains and some pin six curve in I think 2020 on print at least and same year we proposed another so with or another bw6 curve that was more efficient and we generalized this to some other to to any elliptic Cur and families but it was just research uh implementation wise these two curves are like bls2 and bw6 are the most efficient nowadays for Two Chains uh but it was wasn't ZXI that that introduced the notion of Two Chains it was 5 years ago but hidden in some appendix of the paper jepetto so they use the same B250 54 curve from Pinocchio and they built on top of it a bw6 curve given the raise to the first implementation of two chain uh yeah but it was hidden in some appendix now if you want to do recursion without pairing pairing friendly snugs you just need recursion of some other snugs that do not need pairings then you can use plain Cycles so in the Halo paper they introduced the twiddle twiddle to uh two cycle and they then they replac it with pasta which is more efficient and it is used now in Halo to implementation it is used in folding schemes like in uh in the sonobi implementation but it was a year AG a year before that at least I've seen um a two cycle in the zero knowledge uh setting it was proposed by in this website by uh Andrew postra and it is the secp secq curve and he he in his mail he gave the the parameters so for me it was the first one in the zero knowledge setting but uh research-wise it was in 2011 it was called amicable Pairs and the alot cycles and the the Halo paper sites this one actually but actually I was able to find an implementation of plane two cycles back to 2007 in a different context for primality testing like when you test test primes you can test them with elliptic curves and it was FR in his implementation here where he was discarding these plane Cycles because they were bad for primality testing and the same year the definition was uh formalized in this paper by b m it's called dual elliptic Prime so dual elliptic Primes amicable pairs alot cycles and plane Cycles they are all the same thing and I think two week two two months no this this summer I mean this year um so Onan and others they looked at elliptic curves that form cycle from a mathematical point of view and they're calling it elliptic over hpair so all of these the same thing um and if you want to mix then uh snark based uh pairing based snars and non pairing based snars you can use uh hybrid two cycles so one of them is proposed by dut from zcash so this is uh the one uh and actually I was able to find another implementation with BN 381 in Mina protocol by uh Zach meckler but I don't think it was used anywhere it was just experimental and then if you want compatibility with etherum so Aztec proposed the grin curve that is compatible with with BN 254 from ethereum uh but actually I mean you can take any Prime order pering friend elliptic and by definition you can constract a hybrid cycle um and if you want to merge all of these like you want to do a cycle and a two chain so we calling it lollipops like you can have a cycle and then a stick it can be pairing friendly it can be nonp pairing friendly it depends on your use but together with Antonio sanso EF we proposed uh a way to build families of like when you have a parent friendly litic curve and on top of it you can have a uh a plane cycle uh and then I think couple of days after our paper oh Gil generalized our idea with some other families of Curves like KSS and then I think one week ago on at least uh oror and Simo Mason they proposed a even more General way to construct those lollipops without fix I mean with fixing the curve before we couldn't fix the curve we had to to to construct all the curves together but they were able to construct it on for example BLS 381 for instance and yeah then lollipops they found another way to do the lollipops with all the curves being pain friendly it wasn't possible at that at this point but they did it with super singular elliptic CS which are the find ere extensions so make things a bit more slower yeah uh that's it for me so many information but yeah thank you thank you very much um I'm here uh very nice good overview covered a lot of stuff there's a few questions I think two one that kind of leads into the other so maybe I can read out to you so uh yeah I think one that was asked even before the talk started so I think you have a f who's uh wondering what is the future of curve based snarks compared to Hash based snarks I was expecting this question by the way I mean yeah hash based snars they are fast because you can construct them over smaller Fields so you can speed up things but I still believe that uh curve based snarks they come with sness so there is like a place for both and today we see that for example for ZK VMS or ZK EVMS they do a lot of Stark proving so hash based snarks but then at the end of the day they compose it or they wrap it with a curve based snug so that they can get ethereum compatibility one and they can get sex sickness which is like P so small so I think I believe both are to stay good uh then so do you think recursive snark into Stark might present an interest to be postquantum here snark cannot be simulated by postquantum computer how snark and start Stark benches benchmarks gu so let me try to understand the question so I I I think yeah snogs if if we're saying that SNS are based on curves which is not really the case but I understand it like this well if it is based on curves it's not uh postquantum uh Stars well if they are based on hash hashes they are plausibly postquantum composing both means that the protocol is not postquantum um but yeah if you want uh postquantum some resistance down then definitely anything that is Hash based uh I mean yeah we can also talk about isogenes because they these are like uh curves based these are postquantum but I'm not aware of any isogen based SNS yet and so I think then the last part of the question how do they sort of Benchmark against each other in terms of efficiency so yeah yeah so it depends really on what's what's Baseline we benchmarking against um so it really depends but for example if we if we are taking any um so so snar they are they work on over like uh big fields defined by the elliptic curve so if we Define the statement over this field natively then it's competitive but in stocks you can Define them over any field and for example if you define them over binary field like B years then you can do things like K faster so it's really depends on the Baseline nice okay good uh some more questions came in in the meantime we have two minutes left so we can go into it sure how important is high two adicity uh can we get away without it okay yeah so uh the two adicity is um so so in elliptic C we're working over this subgroup uh of prime order and the two add means just this order minus one has to be divisible by a high power of two and it just means fft friendliness because the best way to implement f50s is like radic 2 A50 and uh for big circuits then you definitely need these two adity for small circuits maybe you can get away with smoothness like just some some smooth uh uh uh integers dividing like P minus one but yeah for big circuit like for example I I I work on the linear zkm we work on big circuits so yeah it's definitely a requirement for us and why do you want to get away without it I'm sorry why I'm just asking my uh follow on like from my own understanding why do you want to get away without it like what problems does it introduce yes so it's um it introduces the fact that you need a specific elliptic curve for example if I'm talking about ethereum so ethereum curve so the r minus one is divisible by high power of two but the P minus one is not so if you want to do for example a recursion over ethereum it wouldn't work on the second lay yes of course uh good then last question while we have 30 seconds left why is it crucial for recursion to have two curves uh where one is Prime and the other one is prime one prime is the order of the other yes so um we express the statement of whatever we want to prove on the subgroup or the or of the elliptic curve and if we want to do a proof of appr proof we need to do the verification as a statement but the verification uses these pairings and pairings are defined over a different field so if we want to do pairings in the subgroup you need the field of the pairing to match the field of your subgroup so that computations are native otherwise you need to emulate non-native field arithmetic which is quite costly I mean we do this but it's quite costly but if you have native then the number of constraints so your PO generation will be way way faster good I see there are more questions but we're actually out of time maybe you can catch him uh off off offline um but yeah thank you very much I'm like thrilled with the amount of questions uh great thank you very much thank you