Anish Mohammed - Succinct cross-chain bridges via backwards compatible SNARKs

Transcript

good afternoon so I can see in the audience uh you know a lot of the others and I think they contribute more than 30% of the speaker sorry audience so I'm a bit nervous so I'll try my luck they over there and if you have like very hard questions I'll Point them at you okay so the whole idea of this talk is like we had worked uh I'm from Panther I'm uh the CTO Chief scientist uh we have a small research team pretty much all them sat on the back except one person we did some work on a SN and we were looking for how best to actually put it to use and uh what we found out was you know there's a good opportunity in Cosmos so you know how do you

actually do s suent easily cheaply verifiable you know a set of Co Cosmos signatures so that's what we looked at and uh yeah so one of the things that we figured out was uh there two-part problem actually it's a multipar problem one of the problems that we have is like whenever we create a a proof that has to be evm compatible and uh because of the curves that are existing in Cosmos this becomes a bit more tricky and uh yeah that's the start of it so I should have actually shown the picture all right it's a picture somewhere else okay so what's the bigger

what's the elephant in the room kind of question so the elephant in the room kind of question is like doing all the things as nonnative field arithmetic right so that's quite a huge overhead because the curve that's being used is edd2 25519 so you know you can either choose one of the two parts you can actually do a massive paralyzation and have a proof ofation with the suitable proof system so there is a couple of them I think the secet dgo and pianist and then there is the second part which is essentially trying to avoid the nonnative arithmetic and uh you know especially for the scalar multiplication and and a su bridging scheme that's what we call overfly this is the you know our

proposal in that sense so we had a SN scheme and this is a proposal to have to do this so what's special about Cosmo signature schemes can I have a show of hands of people who are familiar with Cosmo signatures so I can right all right okay so handwave a bit so essentially the two bits of challenges one one bit is the fact that you have a sha 512 it's non- trivial and the even bigger problem is the curve so you have an adverse curve that's ed25519 so that's causes a bit of a problem for us so we want to actually solve for both of them so we could actually get uh you know smaller size proof make it faster so that's kind of

the objective so yeah kind of the normal Iceberg picture where you go okay what's the biggest thing everybody recognizes the Sha 512 but what's the bigger one is a non nonnative field arithmetic that you have to do to do this thing so yeah if you were to go a bit more into depth why is this a challenge so part of the challenge is first bit is the fact that the signatures are not not efficiently aggregatable okay uh I was told always been said that don't say that you can do half aggregation okay full disclosure yes that's possible and uh the second bet is the fact that the

curve that's there is not very how could I say friendly to snar so it's kind of a not a great situation to be and and uh there's also the problem of uh you know low to acidity and uh no large smooth orders of groups so essentially if you have that you can actually have some uh you know Ways by which you could do things a bit faster okay so what do people typically do so when you want to solve this problem what you do is uh you do multiplication over another field right and this typically has a very large

overhead and uh you know there has been some amount of progress in this space and even though uh there's been a bunch of progress is still is pretty expensive uh you know it's more expensive than the uh sh 512 so okay so what are the possible solutions and this is like one of the possible solutions so there like Solutions that's been proposed which are using you know what I would describe as field diagnostic fft free snacks so everybody's familiar with fast foror transforms okay all right okay so fast for Trans is the you know kind of the easy way to do some multiplication when

you have very large numbers so this is like typically when you have a snack you have two things the fast for transforms and multiscalar multiplication so in this we definitely have msms and the the possible solutions that are being proposed is like fft free free snars and uh what of the challenges with proposing things like this is the fact that you end up having large uh you know proof sizes and it becomes more expensive both in terms of overhead for doing the computation storage and communication complexity so there's also some linear time things with uh msms or with Mel hashing okay

so I'm not going to go into a lot of detail but in general as I was describing typically snacks have two sets of operations in that sense so you try avoid the fft bit to you know reduce overhead and then focus more on Mss okay so right so what is it that we are looking for we actually want to have a snot that's compatible with the field the underlying field this 25519 and uh what does it need to support and you need to have support for custom Gates and look up so in our case what we have is like we have a flish lookup

mechanism and uh and one more thing we did did was like we we have two choices the choice of having a multimedia Point commitment system or a univariate point commitment system and we kind of stuck towards the you know univariate okay so the person who actually named the scheme is sat in the audience so if you guys like the name of light he's there it's a guy to be asked why he named it that way so we as I said we actually worked on this uh you know snar scheme for a bit uh bunch of the people that are here where you know the people were heavily involved in it and uh it

uses I would say it's us just like a a plish lookup scheme with a a CQ mechanism and uh one of the things we do is like we kind of stitch together do of proof systems in two 2 bn5 and get the results so I I have two slides which actually describe this so it's much more intuitive when you see the pictures so this is the first way of doing it the first way is like you have a number of ed25519 uh you know multiplication and then the validity of the Sha 512 and because of the way Cosmos actually has this rotating set of validators you take a

subset of them and then validate it and then you actually simulate the whole thing on top as a growth or other schemes on top of a BN 254 which is like kind of bit heavy so the the proposal or the the approach that's been taken is this so we do you know take a proof of n ed25519 have a look up argument uh just to validate this the rotating validator uh you know assumption so that like from the set of all publicly known valid dator set you have a subset and you want to check that then you have a on b254 a plun plus CQ scheme which actually looks for the you know validity of the nsha

i12 sign you know hash functions right and then you combine the two uh you could actually use growth or F Fong you know and it's it's a non native 2554 and then you get the results so that's the end of the verification so the difference is like this one you do everything in one step and uh you know it's this is our first approach we would probably describe this as night approach this is the more how could I say finest approach slightly better so I I could probably you know talk a bit more about where else we could actually use this so uh the other places this could be used is for b254

pro proof agregation in one layer and you can also use uh for SEC mean this is I'm just talking about the snar right the snars this is one of the places where the snars could be used and you can use it in other places as well that's the proofs of multiple z uh 256 uh signatures and for multiple BL signatures as well okay so the there was a talk that was given last year and the paper is there you could probably have a quick look I'll hand wve at the scheme so at least you have an idea uh as with most knocks it's a kcg commitment uh arithmetization is Spanish and uh we

have a mon univarate basis so this is kind of the thing that helps us to keep our size of the proofs within a you know when when there's non native arithmetic it you know doesn't really blow up so one of the bits that's probably of interest is the fact that uh we do the sum of the pomal products via multimodular fft so uh probably if you meet the team they will tell you the story of how they got there so uh the key bit in this whole scheme is a hadat product uh this is how it looks like um a bit more detail there like a in a larger sense this is kind of the

pivotal part of the whole scheme for the snar scheme uh you know the it kind of exploits the structure of the product and that helps us actually do this faster um and we also use the permutation argument and uh we would probably say this is somewhat similar to pl's uh you know scheme in that sense the real difference is we we use the monomial basis okay so uh we also have uh this ability to do custom GES uh which allows oh sorry uh we also have this ability to

support custom GS uh you know it's helpful for like addition and multiplication uh addition and doubling not yeah mean addition plus doubling is multiplication for 25519 okay so other bits that are there that that's probably is relevant would be like it also supports like a subsets and sequences in this instance it's useful because it's a subset set validation mechanism you have a set of all globally known set of validators and you want to check a subset and uh yeah so it just has like three elements in G1 uh merged into one uh field Diagnostics

knock I would probably skip yeah I mean just to give you an induction of the size of the proofs so we have two variant one we call the uh small proof and the fast proof variant the small proof is like uh 10 G points and 10 uh 20 elements in FP and the faster one has 14 and 24 so the small proof is like 1.4 KB and like the fast one is 1.76 and uh yeah so the verification mechanism it's pretty straightforward uh we have a few Scala multiplications in G1 uh that and again there's some

similarity to plon or the similarity is that we don't have any pairings in G2 so it's possible for us to actually to recursive aggregation okay so again uh now the you know the question about performance right how much time would it take and the largest chunk of computational time here is MSM on G1 so typically as I was describing uh you know if you take a normal what do I call a cloud classic uh you know snack you have a couple of ffts nfds and multiple msms so the largest fraction of the computational time here is

MSM so the second is like a the hadat product calculation in that sense so largest chunk uh goes to MSM and then the hadam product right so as I was kind of describing like when we do computation we end up doing the computation using multimod ffts so uh to be you know one might wonder what's the benefit of doing such of things uh so there is this upside of actually fft that can

be fft can be paralyzed and the inverse can be bashed as well so overall you could Poss do some precomputation and save some some more of it shave a bit more of it we haven't done a lot of Shaving in that sense so U if you were to look at it we have an implementation so one of the person who actually implemented is here the other person is not here so if you have specific questions you can find them and ask them so uh the the SN was implemented for the current form that was implemented it has like 100 bit security and and uh the pairing used is like eight pairing and takes 4.7 uh milliseconds on a normal 8co laptop not very V normal laptop okay uh

so we also have a rest implementation this is an AWS instance I'm pretty sure everybody sees this everybody has like a 64 Co you know a instance and the approval time was 24 seconds and the verification time is 15 seconds or no 8 go right a laptop rather the other one is a this instance okay so we have some you know benchmark for multiplication on a single instance the 1.76 one the faster one uh it takes 45 seconds so we had two two of them the faster one and the smaller

one 1.4 kilobytes and 1.76 this is 1.76 one okay the 14 G elements and I can't remember the second number of so in the same machine we did the simulation for uh b254 grow 16 and it takes less than a minute and uh in total if you were to combine all of this it takes sub two minutes to do the whole thing right yeah uh again you see the picture this is like you know comparing before and after so uh talking about you know sha 512 so as as we were describing uh you

know typically everybody recognizes sha 512 as being very computationally expensive it just expensive there's a lot of lookups it's not really uh friendly with a1cs kind of mechanism so uh the the cost of uh scal multiplication is uh pretty high and actually dwarves the you know the cost of actually doing sha 512 so we also have a lookup a CQ lookup uh so this is literally using Aztec batenburg Library apologies if I butcher the name and it does have lookup tables and it's like a a six cap hash kind of thing so you know it's a scheme that has actually come up with uh aliel gabison

and I can't remember the second order so it's it's a lookup mechanism we liberate that so in you know last of the bit is combining the two of them and like uh if you were to think about this it it cost like two native multiplication BM 254 per signature so if you have n signatures you know 2 N times that okay so yeah that's pretty much the whole thing so this work was done by a bunch of people in Panther and some of them left and they moved to mazak so they are working working on you know continuing the work on whatever they're doing in Panther so we had a choice it's

more like metrics the red pill versus a blue pill kind of situation do you actually look for minimizing nonnative field arithmetic or do you want to do fully distributed proofs so they have come up with a way to actually do both so you don't have to choose one you can just have both you can ideally have both both woods and uh yeah there some more work that's being done so you know a fully distributed snar agnostic snar which actually you know allows all of this it's the Blends the strength of both the snar that I describ that were there and a Pianist which is one of the schemes I described there were two choices we had one is to massively paralyze so some of the you know upside of actually having a massively

paralyzable you know snar scheme plus whatever that was there which actually reduces the overhead for doing things in a nonaromatic so that's pretty much what it was if you don't have any hard questions I'll be okay if I have hard questions I'll point at people over [Applause] there thank you I love the slide with the iceberg but we have questions coming um please raise your hand for the questions none of my team members are allowed to ask me questions right exactly exactly okay so we can do around so maybe you

have a question that we can have like vote up like put up your hand and so with the voting I don't know who would like to try this cross uh cross Bridge uh it is it Oracle or messaging what is that it's a bridge bridge it's a bridge because there are as part no there are bridges and there are messaging protocols so it's like uh okay so the the difference between okay so you could do bridging by messaging or by true brid this is It's IBC so it's more I would describe this as bridging this is bridging all right so would you like to use what exactly now was presented raise your hand okay there's some GitHub stuff

there so yeah and there are guys sat behind you there's like a whole row of them you can get hold of one of them and talk to them the guy in the red t-shirt and the rest of the guys in that room all right all right all right right good good good thank you so much wow impressive all right give a round of applause thank you