Episode 326 - MPC & ZK in Ligero and Ligetron

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week Kobe and I chat with m and carit from leero sometimes also referred to as liero we cover what inspired them to work on cryptography like MPC and ZK for almost 20 years and how this space has developed since they

started we discussed liero what led to the project the early phases of the project and the work that they're doing today we return to the MPC and the headwork and discuss how they have improved on this system we cover how MPC and ZK are interrelated how their system incorporates the advances and new techniques from both Fields the new legatron system and how they plan on getting this technology into the wild now before we kick off I just want to share an update about another project that I work on called ZK hack ZK hack is a Learning Hub for all things ZK just over 10 days ago we hosted ZK hack CCO which was so amazing and special 40 Projects were built at the hackathon bringing the total number of ZK projects built at our ZK hack IRL hackathons to

over a 100 and we announced in the closing ceremony of that event that we have an upcoming event that is zck Montreal which is bringing this event series to my hometown zck Montreal will be happening from August 9th through 11th and it promises to be a very special one once again we are hosting our ZK focused IRL hackathon this is the event you should join if you're looking to experiment with ZK Tech and tools it's also the first time that we bring our hackathon series to North America and just as an aside Montreal is also amazing in the summer so if you've never been to Montreal you should definitely check it out we are just kicking off the development for this one but wanted to give you a heads up applications are open so yeah I hope you'll join us one

last note there's no episode next week we are taking the week off but we will be returning the week after with our regularly scheduled program now tan will share a little bit about this week's sponsor Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission for a truly pure internet Alo has interwoven zero knowledge proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's unparalleled in its approach Alo is ZK by Design dive into their programming language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps this is

an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org and now now here's our [Music] episode So today we're here with M and carmit from liero also pronounced Leo Mutu is the CTO and soon to be CEO of the project kit is the chief scientist welcome both of you to the show thanks for having us it's great being here we also have Kobe as the co-host for this one hey Kobe hello let's start a little bit with the name because I've just basically shared two iterations of the name I always thought it was liero it's it's with a g in the middle so I

recently learned it's actually pronounced Le hero tell me a little bit about the name of this project yeah and maybe what does it mean so you know km and I our backgrounds I mean we did our PhD in computer in computer science specifically cryptography zero knowledge proofs and secure multiparty computation we actually did a lot of like theoretical investigations in these protocols uh about 7 years back out of a theoretical project came this zero knowledge system that we said hey let's Implement and uh I think the convention is you got to give a name and you know we were about to submit this paper and I was like okay what name should we give and you know one of the features of our system is uh it's lightweight so you know uh I'm a little bit of a Harry Potter fan so I was like let's use

Leviosa okay like it's uh you know featherweight from but my co-authors weren't like big fans of it so then I went around looking at every language what does lightweight Translate to okay and when I went to Spanish it said it was Lio and then there was Li for lightweight and E for zero and I was like okay you know this is this is good but I should tell you maybe even I don't know how to pronounce this well I have a colleague I don't know if you know Daniel benero he's actually he knows Spanish and he corrects me how to say leh hero properly nice cool that's a great backstory to the name of this project so when I saw it I actually thought maybe for a second it was Esperanto now I kind of want to go look it up but yeah because we used to do it

in cello oh yeah plumo right exactly nice okay so yeah you shared a little bit about like the history very briefly but I think it would be great to get to know both of you uh M let's start with you tell us a little bit about your background leading up to this and why you work on these problems sure the passion for cryptography of course started um when I was an undergrad with my uh undergraduate adviser uh but when I started grad school actually I wanted to do like I was going to do database systems but then I went to database privacy and you know I published a paper called L diversity which not many people know but among all my papers that has the most citations for some reason but

then from there I knew like what I wanted to do was cryptography you know once you learn zero knowledge proofs and secure multiparty computation you just you just fall in love with it and of course I was very theoretically motivated in understanding this like and when I say theoretically it's about hey like what is the minimal assumptions like what's the round complexity it's uh I'd say much of the initial works that I published uh they are not practically feasible it's actually more about understanding can a particular security or security feature uh be achieved but then out of one of these projects we had to design something and you know often in theory we say hey like you know if we put this

guard rail there is a chance that it'll be concretely efficient which is called a black box construction we ended up doing it and came out a zero knowledge system and we like okay you know I had a student who was interested in implementing it my PhD student Scott Ames he implemented it and it turned out to be fast and at that time there was only the zcash crypto system and our work actually precedes Starks M interesting so what year is this then what are we talking 20 it got published in 2017 but you know much of the work was in 2016 uh so we are actually one of the the first transparent ZK snark although I should say we're not a fully snark because it's sublinear as opposed to suin like we can talk about this later

but then after that I was like okay you know do we the co-authors like me kmit U and yal isai he's a professor at techon University we're like should we commercialize this and I just put the I put the invention in uh at I was back at University of Rochester a professor there they had a TR transfer department and you know they put me in touch with our other co-founders our business co-founders Scott Katlin and Matt DBC now what motivated us to start a company I mean little bit I'll say that we are definitely you know excited about this technology and like scaling this technology but also we wanted real world applications like we want the world to see what these uh Primitives uh can do

and I should just a side note like among all the things don't ask me what cryptocurrency to buy but I love blockchains right like I think the number of people excited about zero knowledge proofs and also more generally cryptography is just amazing and I think it's a large part due to uh the blockchain uh Community but anyways when we started this company uh I mean we were looking for applications in zero knowledge and multi party computation we were looking for applications in finance and you know our business uh co-founders I mean they are from you know Wall Street and have deep connections we we were looking at both onchain and offchain you know trafi as well as crypto applications we looked at multi-party computation more than zero

knowledge actually when we started and you know we actually have a scalable auction technology for dogpool auctions and a couple of more products that you know if we if it's relevant I can share later but along the way the last four years we also secured a DARPA contract to scale zero knowledge and you know we refined the Le hero system and uh right now I think it's an an iteration that um uh really I think can change the space and we needed a name for the new version so we call it um legatron which I tell more later but I will would you also pronounce that legatron I'm going to say that right okay that's legatron okay I just hope Michael B doesn't come and you know you

know say that I shouldn't use legatron that's exactly my excuse why I should say liero liero and Trum all right K let's hear a little bit about your background and what led you to work on this stuff okay so I have slightly different story um I did my bachelor uh and my master at band University and um but not crypto in crypto and then I took uh a course by uh back then was Amir urg who gave the the the course on cryptography and I was fascinated by this area and I decided that I want to do my pH in crypto but there weren't any anyone who can actually advise me because Amir was uh was full and then he told me you know

there's there's a new faculty member just came to uh to Baran and let me let's let's go and uh you can meet him and that was Yehuda Linda Yehuda was one of the co-founders of Unbound that got acquired by coinbase yes yes this is with Nigel right with Nigel by the way Nigel also had encouraged that I bring you on this show so shout out Nigel for another recommendation anyway absolutely cool so I went into uh yehuda's office and um he asked me about uh crypto and uh he told me there's he's working on the relatively new area called secure computation and started explaining that

and uh at the time it sounded like a really farfetch who is going to work on on protocols um how useful can they be but I decided that I I like it and we started working and uh I think I worked on the phrase practical secure computation before anyone actually thought that could be even practical what year is this roughly well so I can I can tell you a fun fact I started when I entered yehuda's office I was pregnant with my uh elder daughter and uh I gave birth soon after and she's over 19 today okay W that's a great way

to to know the timing yeah so almost for two decades I've been working on secure computation and uh we started uh looking into the practicality of of these protocols before people even thought it could be made practical our papers got rejected from conferences and yeah people have just dismissed our paper saying um know this can never be practiced ago little did they know right yes I think one of uh uh one of my papers that actually got published later on uh during my post talk in Denmark uh was about distributed RSA I think it got rejected over five times people didn't like the paper they

said no one cares about that it will never be I didn't say will never but it will not be useful today I think many people are implementing such systems uh people definitely care and it is highly cited nice so I did my PhD with Yehuda it was it was great it was a great mentor then uh uh we moved to Denmark for my post talk and I had the chance to meet um I think the mentor in in Practical secure computation Evan damgard was back at the time they were the first to implement secure computation with the sugar bit auction

oh yes and uh it was it was a great experience and then coming back came back to barand for to into um a different faculty and I guess uh a decade ago uh I Met m i mean we knew each other from before because I was a small community definitely back then but we never had a chance to collaborate and actually I think we met that time in Denmark right uh in in one of the tpmc we actually met once before but that's okay I remember that but I'm talking about day meeting where we started collaborating that is true and I think the rest is history right we became uh very close collaborators very close

friends yeah we've been doing a lot of great stuff since then then I want to kind of throw it back to the name because I feel like I've been hearing about this project since 2017 but maybe that's wrong like when when did this first you kind of H Ed there m that it might be more like 2020 when something was founded but when does the first work come out when do we first see this name and when is the company founded right um so our work got published at ACM CCS 2017 and in 2018 is when we started talking to our business co-founders and we incorporated in 2018 okay and we closed our seed round early

2019 all right I feel like I'd heard I've seen the name I've heard the name for a long time for me it was like somewhat under the radar until recently what were you working on early on has and has that changed that's actually a great question um I think one of the things if I if we look back in the last four years is we weren't as much self-promotional like in terms of what we had uh accomplished we were focusing on projects scaling our technology more than advertising not that you know we shouldn't but I do think that's one thing uh I would say uh looking back in the last four years one thing uh

regarding our company is we did have a more heavy focus on MPC or multiparty computation compared to zero knowledge Although our zero knowledge was being developed in parallel under the DARPA project uh to scale like I mean you know DARPA funds fundamental research and um it was great to I mean you know didn't have to raise Capital because that was great funding for us to uh develop our technology but our Focus was on multiparty computation and you know Banks like you know we talked to the big banks in Wall Street JP Morgan uh Fidelity City Group uh Etc and we wanted to build the auction technology and in parallel there is also this project that we took for doing the distributed RSA Generation Um for the etherium

foundation actually this is one of the first Publications that came out of after the company was formed uh I'll just tell maybe one you know one minute about this project it was the first multi-party computation project that we demonstrated could run among 10,000 parties you know we had envisioned that you know everyone maintaining either the Bitcoin or the the main nodes maintaining ethereum could run this protocol and at that time this was you know people were looking at it for what is called verifiable delay functions we were able to scale this to 10,000 uh 10,000 parties I think our goal really was to take ZK and MPC and to scale it and following this we we defined our technology for uh for auctions and let

me just tell a minute about auctions so you know in auctions you have uh a bunch of people who want to uh you know bid on a product and usually it happens with a third party like you know a third party collects your bids and you know announces the winner but using MPC you can eliminate the third party you can just talk to the people bidding and at the end only the winner gets announced now this is very useful because it you know reduces the information leakage to the bare minimum only the the winner of the auction is released and we took this as a challenge and we actually have this product like if anyone's interested like we can demo this we can actually scale auctions for example imagine you take all assets in in the US and all assets

in in some other Market let's say that they are like you know 10,000 stock symbols we can run an auction in parallel for all these 10,000 symbols and complete it in 5 minutes like this is again it's pretty good one of the challenges we took and we were able to um we were able to deliver now while we are talking about MPC at least I'll say how people think about MPC today was different from at least two or three years back because when we went and talked to people about it they were like MPC is that zero knowledge and okay I I had to control my anger inside but also at the same time I think it falls under the Royal ZK some I mean the the Hot Topic on crypto Twitter now is is MPC also threshold signatures but yeah I

know oh no please don't get me started on that also um but we didn't realize that there is sort of an education problem blockchain has done great for zero knowledge but not yet for MPC and so we wanted actually we created a cute little product which is also available which is to schedule meetings now you can imagine this is a very basic task and you want privacy I don't want to tell what appointments I have even if I don't show what the appointments are I don't want to tell when I I'm am free and busy but you can use MPC to find a common meeting time H what's what's that called do you have it Mescal M HC L Mescal doccom M you have you have some good names that are hard to pronounce

there but um any but you know uh then came the zero knowledge proof and then you know I think um we have now I would say a little bit pivoted to exploring what the zero knowledge is going to do uh to the space all these other projects are still there like we have you know demos for all of them uh if anyone's interested I I can add I mean during all these years um we had two jobs our main job was we had uh like uh academic positions which are really really intense by themselves and in parallel we've been trying to uh run the company I mean this is part of uh why we've been slightly under the

radar and also as scientist I think we really cared about spreading the word about this technology I mean the place where we come from we really value privacy we really think of it as as a as an important value in society we really think Society can benefit a lot from uh um understanding why privacy is important and our goal our mission was to make MPC also now zero knowledge as a tool that people will really value and appreciate and would want to use it because they will understand that it's for their own benefit and I think uh privacy is

something that uh we should educate for for instance when I um I give many talks in high schools in Israel I mean people invite me for science days and so on and um I speak about crypto but every time I like I finish my talk with I have this slide on explain about privacy and why is it important and uh I mean you can see that it's missing and this is something that we should definitely educate more I think this is our mission as scientist so so first of all I completely agree with you kmit about that point and especially I think a all

of people are not realizing that they could have this kind of non-financial privacy in their lives and they take it as a given which is not not that good yeah and Moto to to your point I think that I also get why you you had to do MPC stuff for a few years if you were working with trfi people because I think that ZK really flourishes in this kind of crypto space because there are very strict trust requirements which don't necessarily exist outside so I kind of get it I want to just quickly return to what you were saying about like your

first contract being with DARPA what's it like working with them can you say anything so uh there are different kinds of projects but this project comes under a category of fundamental uh research um I think they really want to promote the technology like this is clear from their intentions uh the way DARPA works is actually you know we had an excellent program manager his name is Josh Baron and you know he finished his term and then we have another excellent person who's now his name is Dan balak but you know they said look we need to scale zero knowledge they kept metrics and we actually beat the metrics like halfway through the through the program in terms of how they wanted to uh scale uh with

Dara the the only thing is whenever you announce something publicly or publish you just have to get uh sort of an approval from them but this has never been sort of a bottleneck in terms of uh getting this technology out but um I think it's a really great program you're allowed to publish it it's all can you open source the work you do with them yes you can do you can do everything yeah you just need to get your permission which again you know uh uh I think this research doesn't is not too sensitive in that sense got it I think it was a great experience also collaborating with uh with many groups seeing the results of of many different systems I think it really pushed this project okay so let's talk about about

liero itself so the construction and the paper it had a bit of a history right it's based on earlier works like MPC and the head and so so how does that lineage look like let me give you a little bit of uh of a background on NPC in the head which I to my mind I think it was one of the most brilliant papers so and it's not an NPC protocol oh it's not not exactly let me let me I I will explain so um the starting point is H is a paper by four authors Shai Kushi L oski and the from 2007 they came up with a new technique to design zero knowledge

proofs now let me tell you that as cryptographers we care about uh the complexity class for which we can design zero knowledge specifically for in crypto we care about NP problems and this class is the set of problems where you can validate or verify efficiently now classical results on zero knowledge showed how to build zero knowledge protocols for this class by basically focusing on a class that is considered more difficult within this class these problems are called NP complete problems so like uh satisfiability yeah so if you build a zero knowledge protocol for this

problem then you basically cover the entire set of of NP problems now the icos paper I'm going to denoted iOS by the initials of of the authors so this paper what they showed first of all they took a detour from the original uh way or the classic approach of Designing zero knowledge Pro for NP complete problems and basically build directly zero knowledge protocol for every NP problem and the way they did it is basically instead of having using reductions like you had to do if you wanted to work with NP complete they pushed the computational

task into building or using an MPC protocol by the approver now maybe it's it's a good time to distinct between zero knowledge and NPC because that was uh going back to the discussion we had before NPC is a generalization of zero knowledge right in zero knowledge we have two parties the approver and verifier in NPC we can have an arbitrary number of parties in in zero knowledge only the prover has a secret input in MPC basically each party can have a secret input mm and also the functionality right in knowledge the prover is convincing the verifier by the validity

of some statement yeah in NPC we could just compute an arbitrary function now why do I mention that because NPC is is General enough to have different flavors of security definitions or adversarial models and looking ahead this what gives this MPC and the head technique is flexibility because it can be instantiated with different protocols now going back to NPC and the head what iOS basically did is the following they said let's define a function or a functionality in this functionality take the secret input and secret share it among a set of

parties now the prover is going to virtually right this is where it comes in its head the pro is going to take some protocol and emulate this protocol in its mind in its head Computing a function that basically validates the witness now when you run a protocol you have a transcript or the messages exchange between the parties and Views a view is basically the secret internal state of a party and incoming messages so now after virtually running this protocol the Prov is going to take all these views generated by by the virtual

parties and commit to those views and this is the first message of the MPC and the head protocol now after committing to these views the verifier is going to challenge the prover to reveal a subset of this views for which is going to check for consistency so what does it mean it means that if for instance one party sends a particular message so it should appear in the view of the other party this is what they call Par wise consistency and what iOS showed is that if you have this par wise or local consistency you can prove that you have also Global consistency meaning that if every pair of views are consistent that

means that the statement could be correctly validated so this is the core idea of NPC in the head and uh it was also implemented for instance by uh the ZK paper yeah and it was it was implemented and already demonstrated to be practical however the basic approach is that you get a constant soundness so you really need to repeat the protocol multiple times if you want to get really small soundness and this is where for instance liero kicks in because if you enhance the properties the security properties of the MPC protocol you're actually using the virtual protocol then

you can get much better all the properties that the had has like going into sublinear and so on something that I remember about MPC in the head and ZK is that because if you want to enhance sness you have to repeat like you said is that you can run a lot of these in parallel and you know gain gain efficiency in that way is that also true for the so we won't have to do that because by choosing the right MPC you won't have to repeat it in parallel and also there is a difference between how leero Works to other systems like for example in Le hero it's not that you need to use large field sizes to get

good security which is H which happens in other systems where the security is is related to one over the size of the underlying field yeah for snarks it's very required yeah yes but in Le hero actually there is a different mechanism that you can repeat what we call like Code test and linear test that's part of it even if you have a small field and and get it now repeating and parallel this one needs to be careful and I actually listened to Justin's podcast last week that he talked about parallel repetition of these things and I just want to point out he mentioned that he blew away two two researchers by saying it and one of it was me so oh I'm just revealing the identity of uh nice uh one of them so I mean you you want to be

careful for the ZK boo setting repeating in parallel is fine because it's actually one round of interaction with the verifier Le hero is like three rounds of interaction and when you parallelize you're not going to get the best parameters so you would rather do it in the MPC uh itself but maybe I'll just tell a little bit about this MPC in the head from you know how it is today mhm one of the things also for kit and me you know in this thing was that we came from I want to say a little bit from the cryptography word as opposed to the comp lexity world for me like the works like Ellie bason and so forth like they I mean they come from this complexity world of doing problemistic checkable proofs and you know and you know which is evolved into interactive Oracle proofs as well as you know the

kind that's based on the Su Che protocol which also is from the complexity world but we started from the MPC world but actually now you can unify it everything is an interactive Oracle proof in what kmit described it's about committing to views of these players you can think of this as an oracle proof like these these views are being put in an Oracle and the verifier is opening a few of them to to check it now the difference between again the complexity world and the cryptography World here is actually the size of the symbol in the Oracle now in the complexity world including even Starks when the verifier queries one of these Oracle entries it's a single field element typically and because this is

how the complexity world has optimized probabilistically checkable proofs they care about getting the symbol size to small even Boolean but in the NPC world we don't care about it like the view of a party which is one symbol can have a lot and what we have found is that this actually helps us leverage things better than the the complexity world but also more from a concrete efficiency and usability standpoint but I want to say that NPC in the head can be viewed actually as an instantiation of an interactive Oracle proof interesting I want to just highlight it's funny cuz I think you're the second group to talk about MPC as sort of the The Meta the higher kind of distinguishing factor in ZK living

underneath it we on the ZK land think of the royal ZK which is just the umbrella term that VC's use to describe all advanced cryptography but um I'm sort of left after what you just said a bit confused about exactly what this is then is it an MPC protocol is it a ZK is it a weird new combination of the two like how how do you define this it sounds like you're coming more from the MPC land but yeah I'm just curious so this this is exactly what I wanted to add so as a PhD student in crypto or every PhD student uh studies like one of the most classical results in NPC how to compile passive to active protocols you

start with a protocol with very uh benign security properties and you use zero knowledge to compile it into a protocol that is let's say much more secure or secure against stronger attacks and this is actually the very first application of zero knowledge proofs and it is called the gmw compiler M very very famous results and fundamental in cryptography now what iOS showed is basically the other direction so they showed how to use actively secure protocols to build zero knowledge so thinking out of the box because up

until their paper we thought of NPC as a generalization of Zer knowledge and we knew that zero knowledge can help to get better NPC protocols and they actually showed the other direction let me add one thing to this and Anna actually this confusion makes sense to me because U if you if you look at these two objects right as kmit said multiparty computation is a generalization of zero knowledge it's in fact more powerful and in the most sort of general form it actually demands more and let me explain what this is for zero knowledge proofs including the LI hero system you just need hash functions just like Starks you don't need any what we call public key

Primitives elliptic curves or like laes or anything we don't need public key objects for building a zero knowledge system but for multiparty computation this is necessary you need something called an oblivious transfer that's one of the minimal objects that you need and these can be based only on public key assumptions actually there are separation results that say you hash functions are not uh enough so when we are using MPC in the head this begs the question hey like I'm using an MPC protocol does it mean now my zero knowledge needs these public key Primitives and the answer is no okay and the point is that there are several variants of multiple part computation and the variant we are using is something called an honest majority multiparty computation which means that

you actually can build these without any cryptographic Primitives and it is those multiparty computation protocols that we plug into this compiler to get a zero knowledge system based on hash functions so maybe to answer your question uh it is a zero knowledge system like in the sense that it needs only hash functions but the techniques that go into it has come from the MPC World okay is it a ZK system then it is um actually this is one of the things maybe I I want to say that whatever we have designed like by default they are zero knowledge and I I kind of want to like compare it with like sometimes the other systems even

like some check protocols you know just when you use it like on on the face of it they need not be zero knowledge in fact jol is not a ZK VM is as Justin says it needs to be called a succinct VM oh wow okay yeah yeah it's not ZK but the liero system is zero knowledge by default and this is something you get for free because you do MPC because MPC you know has the Privacy already in it so uh you get it baked in so what were Leer's improvements above MPC in the had and other works that made it you know a new work so uh K mentioned this work ZK Bo in fact it was the first work we were really you know we really loved this work it was it appeared in USX uh it

actually got the best paper at usnick for implementing this MPC in the head and let me say that line of work is still active today and it's it is leading to postquantum signatures we're not involved in that but I want to say just give shout out to MPC in the head for uh you know postquantum digital signatures but to compare that kind of MPC in the head to what Leo does is that here is a challenge with MPC typically in MPC protocols as kmit said there are are these views that I said hey you can think of it as an oracle proof that you put in an oracle entry but the size of these views are proportional to the size of the computation standard Protocols of MPC this is the case now this is what

zkb did if you use this your proof lengths are not going to be short they are going to be the size of the computation but when you want to build snarks you want to put things on chain you want this to be succinct or sublinear so you want to device an MPC protocol where the size of the view of each of these parties in your head needs to be smaller than the computation and here there is again a work of uh you know Franklin and young back in the '90s they introduced this concept called packed secret sharing which said that you know standard secret sharing can only share a single secret but if you play with the thresholds a little bit you can actually pack a lot of secrets

in a single share when you distribute it among parties and this also led to multi-party computation protocol with exactly this feature so Leo took advantage and like actually you need to sharpen it and tighten it here and there to actually get a concretely efficient but the first version of Li hero was that and one of the again things about these MPC protocols is they had very simple structure they used like re Solomon encoding for which you have fast algorithms to to do it and as it turns out I mean Le hero remains as one of the fastest provs even even today and I'll tell you legatron is faster than Le hero but um it Still Remains as one of the fastest Prov time protocols and you know even if you look at papers today they

still compare back to the 2017 numbers we just didn't publish more faster numbers but they still compare with the numbers that we published in 2017 but Kobe to answer I'm only talking about Li Hero legatron has a lot more features which you know I can I can talk about but leero is as a protocol it's hash based it's not a Nar completely because it's not sublinear the complexity the proof length is square root in the circuit size as opposed to poly logarithmic which is what people typically associate with snarks but the second thing is also that the verification is not as is is not succinct but this is not again I want to say it's not a bad or a good feature in

fact all Zer knowledge systems the verifier needs to spend time proportional to the Circuit it is just that when you repeat it many many times you can do some optimizations but if I tell you I want to prove a single statement once the verifier at least has to read the statement otherwise it doesn't know what it is being convinced but in any case the verification is also you know it's not succinct it can be when the computation is structured which is what is the case in terms of machine learning applications or rollups and so forth the computation is highly structured when it's highly structured Li hero is both sublinear and proof but also the verification is suct yeah so why why do you think it hasn't received so much attention like

you know others snarks protocols like growth 16 plong and Starks I have my guess but I'm curious what you think okay I wasn't prepared for that question okay so let me try to be as less or as much controversial now um you know even after building a a system I think it takes engineering it takes also applications it also takes I should ADM some bus savviness to uh you know to bring in the U in the Forefront now maybe just comparing it with uh with Starks also maybe one more sentence I'll say here because I listen to Justin's podcast maybe you know someone needs to

be quick sotic and like hey go for MPC in the head like he goes for some check but uh maybe we'll do that is that you okay I mean in all it's hash based it's it's you know postquantum secure just like Starks are postquantum secure in fact I mean uh Starks scale poly logarithmic while Lio scales uh square root but for up to a mediumsized circut actually square root beats polog and this is one of the misconceptions also that Justin had actually written about comparing liero and um Stark proof lengths I mean I didn't answer your question Kobe but maybe the the answer to your question it's more that um we

didn't find the right application until now for showcasing this technology and let me also say that we have applied our zero knowledge technology in the MPC world and this goes to also Anna like maybe just your question before I had just one sentence to add to what kmit said there is a symbiosis between MPC and zero knowledge right I mean MPC is more General than zero knowledge but the techniques wise they have gone from one to the other and back mhm right so uh in that sense we have actually employed zero knowledge quite a bit in fact our first RSA project as well as in our auction project we have used the zero knowledge insights that we gained in Leo

back in in NPC yeah actually and I'll maybe one thing tying back to the name of the company I didn't get to name this our original work Leviosa but the following work on MPC there is an a work on NPC with kit me yal that we named it levosa okay that does exist in the world yes cool yeah I guess I'll add my guess again going back to Justin which is the hidden participant in this this episode as well he's just right across here in GE exactly so one one point that he made in his recent post was that as a community at least in the crypto space we've been

very very focused on optimizing verification ation time and you know onchain verification and so on and like you said people still compare proving times with your 2017 paper and now there are other use cases and other applications where proving times are much more important and you know you'll deal with verification times in other ways so I think that's that's one of my guesses at least this is U absolutely right one of the hidden things that a lot of the ZK system maybe this is the controversial point is that they hide what are the proval resources that are spent in in building their products and I think for systems like rollups and so

forth I think this investment pays out like uh you know you can push those cost back down to the uh to your users but in many scenarios this cannot be the case and focusing on Pro time is important in these settings like I mean we're looking at client side proving with our technology as well as proving very large scale computations frequently like you know machine learning inference and here prer time is going to be important and let me just say I would not say Prov time I actually would say Pro Resources because that's different yeah that's true so you have teased legatron already in this episode what is this I'm assuming it uses things that legero has

in it or is it a new proving system or is it a new construction yeah tell us what it is so so um I I want to think of uh legatron as uh liero 2.0 okay and really legatron follows the blueprint of leero but differs in two key aspects one is that it is memory efficient in fact I would say that it is the only zero knowledge system that is concretely efficient that is memory efficient without using techniques like recursive composition and incrementally verifiable computation so it's as it is a memory efficient zero knowledge system and the

second key factor is that key differentiator is that it can consume web assembly programs as input in that sense it's almost a zkm I can tell you where it isn't and you know how we are making it a zkm or a zkm but it can take as input a web assembly as a you know program as an as an input and one more thing I just want to kind of tell about this is that it's also maybe this might change it you know ZK advances come you know pretty fast but I want to say today it stands as the only one that can run completely from your browser so we actually have this like if you go to legatron domcom you can put a c C++ a rust program well right now only C or

C++ rust is not integrated but and compile it to web assembly and you can run the entire computation from your browser we have tested it up to a billion Gates it takes 10 minutes or 20 minutes on the browser to to go to that scale but it will run and the memory required by the zero knowledge system is closely or proportional to the memory required by the underlying web assembly program understood and that's pretty impressive because it's also fast for a billion Gates yeah but also also a lot of other systems almost inherently require you to to have all of this in memory at the same time or at least in some level so yeah that that's pretty cool it's pretty unique the

current technology again I'm not going to say that look like we observed the memory bottleneck a couple of years ahead or at least you know before the the blockchain community did uh with their rollups because we had to do for DARPA they wanted to scale trillions of gates on commodity Hardware right like they didn't want heavy Hardware but they wanted to go up to trillions of gates so we had to solve the memory uh bottleneck I want to say that uh this Dara program we are actually part of a group you know with stealth software Technologies is another MPC company there are other groups as well that participated I bring this up because almost all of them did not work on a snark they all worked on what are called V based zero knowledge

which is an interactive kind they're not blockchain ready as is like you got to massage it but it is not meant for blockchains in some sense like it's not in non it's not uh publicly verifiable it's not publicly verifiable I mean there are new works that are trying to do it but Asis it is not uh publicly uh verifiable but we focused on snugs and I want to say for the V based that's actually more close to being an MPC it uses public assumptions and so forth but they get memory efficiency a different way but in the snark scenario you know I I think either we were lucky or so forth we you know we encountered this problem and we tried to to solve it and uh we really I I want to say that one of as part of our mission we want to make it easy to use

the system I'll say that you know I've again not pointing fingers or naming names I've tried downloading all these open source repositories and I did quite a bit of coding as an undergrad but you know let's say that my skills aren't but our top Engineers have taken hours to compile and use this right like there is still like a significant learning curve to start using this technology and I'll say like our browser implementation like anyone write a simple C program you can do it from a browser today and this is one of the things that we want to keep in mind as we are evolving like we still I think bringing Web Two to web 3 which is something that we feel like strongly about like I think this is going to be important you want to make things that

people are familiar with web to so that you know bringing development here is it's easy when you talk about memory efficient I actually don't really understand what the memory is there can you describe that and and and I it sounds like there are other techniques to create this memory efficiency like recursion you kind of highlighted but yeah what does memory efficient actually mean here the current zero knowledge systems the way or the snarks let me just be you know specific so that uh I don't bring other techniques in you have to first run the computation and You observe all the intermediate values of these computation and really the Z the modern ZK snarks what they try to prove is that every intermediate computation

was performed correctly now the way they do it to get succinctness is you need to do some kind of mixing in terms of checking these constraints this is where all the error correcting codes all these things like you know polinomial evaluations help you in sort of mixing the constraints in terms of checking it now one of the things that modern snarks need to do is when they run a computation they have to take all these intermediate computations and have it in your head or you need memory proportional to like imagine that I expanded it out as a circuit I have wi values I have to put all of this in memory and then after that apply certain cryptographic techniques on top of this

so in this sense when I say memory efficient I the memory I need is proportional to the entire computation as opposed to but when you run your program you have a you know when you run your program on your CPU or anything like it does not need to keep past values right like I mean I only keep what is in my registers and a little bit in my memory but as I do the computation I don't need to keep the past values in memory okay now when I say Le hero is memory efficient it can also do garbage collection this is what I mean like in in modern computers you know you don't want to waste memory as you do computation there is something called garbage collection that removes all unused stuff okay now modern ZK snarks or at least what the last two years what

people are trying how they trying to address this is something called continuations or like recursive composition is one example where you take your entire computation you break it into chunks and you prove each chunk separately and then you combine these proofs using a second layer of proofs and you can do this multiple times you can have like a tree like structure and you can you can do it now this is memory efficient in that each chunk or Shard can be you just need to choose the size for which you have memory so then you after you have done the proof you can move to the next Shard but this is not actually how people do this because if you really did this you'll run forever because you going to do the first chunk

then the second you'll do sequentially this is going to take a lot of time in fact for example stet what they do is they have 200 computers that does this in parallel and then they do recursive composition so one thing that I want to kind of highlight here is back to my point about Prov resources these techniques of of recursive composition and incrementally verifiable computation can get memory efficiency but at the price of very heavy Hardware but Lio on the other hand we can get this memory efficiency on standard hardware and if you throw in more Hardware you can leverage parallelism but on standard Hardware you can already get this memory efficiency so when you when you talk about web assembly and legatron it's one instantiation of how to use legatron

right is building a specific ZK VM for wasn't and I guess my question is is it especially useful to use legatron or you know liero for ziky VMS or you see other let's say specific instantiations for other applications like zml or other kind of things um actually your former question sounds to me more like a business answer and the latter is a little more technical but I'll try to address both these uh question for the ZK VM itself like we are I mentioned that we are almost a ZK VM so where are we not a zkm is that we can

only take programs that have what I call oblivious control flow meaning that I cannot have an if then else in the program where I branch on a secret value because the verifier needs to know really exactly how you flow through the program we have a couple of papers in recent uh like I mean the last year and this year that show how we can remove this which is in the pipeline to make it a full-fledged uh ZK ZK vasle and it is different from how risk Zer sp1 and jolt are doing it they have this fetch decode execute cycle for every instruction to solve this problem for us we're going to solve it differently that's going to give us a lot more mileage instead of

fetching instructions at a time we can fetch blocks at a time so this amortizes the fetch code over a block as opposed to per instruction so uh we hope to get much more mileage from uh from making it a ZK vasm but in terms of okay are we going to build this now I think the way at least I'll say it's all a little bit in flux but uh we want to think more about where this technology is going to be useful we want to think about products there's no doubt we're going to improve our ZK Tech right like it's going to like we want to make it faster we want to still keep the memory efficiency we want it to uh still be easy to you know code applications but

we want to think of applications and the two domains we are looking at one is Enterprise where we are looking for uh client side proving for transaction level privacy for tokenization and on the other end we are on the crypto side we are looking for um like verifying Ai computations and I just want to maybe uh mention uh one Benchmark in the in the AI computation space and how it ties back to web assembly which is one of the questions scob you asked is that modulus Labs recently made an announcement a couple of months back where they were able to verify actually the first that verified the gpt2 inference on chain really very impressive very impressive and so we uh in collaboration with Nim Network we said okay let's also

Benchmark now our proofs can't go on chain yet which is I want to just point in comparison to modulus Labs but what we wanted to really do is we wanted to make it easy to do this so we really took a pure C program it was called by there was one of these GitHub repository for by karpati or someone who uh did for the Llama 7 billion model which is five times bigger than the gpt2 XL model and we just compiled it to web assembly and ran it we did no optimizations no lookups no nothing like we just ran it through our system and it came out in 14 hours which was sort of like a 60x Improvement but if you look at the hardware we were like 100x better Hardware than than modulus Labs so um just coming back I think okay between

web assembly and say risk five there is a question and I can spend a whole hour why web assembly is better but the long story is that web assembly is more versatile and uh we we pick that for that reason but there is no reason to keep that like we can really do any VM that you know that we choose but web assembly has some very nice features that we can take garbage collection being one of them and like do do you specifically like VMS because it's highly structured it no easy to deploy like easy for people to uh write applications that was really I mean our motivation was to get a good intermediate representation like I mean rather than using R1 CS or like these specific uh circuits that have you know

a learning curve we wanted to pick one that's easy okay and maybe like you said the elephant in the room it's not onch verifiable yet but how optimistic are you that it could be made uh I won't use the word optimistic here like I mean I'll say that we are going to get the proofs on chain um the there are two steps specifically that we have to do the first step is we have to go to what is called the pre-processing variant of this this is the kind where I said like hey I want to prove something but I'm going to prove this over and over which means now I can give a small amount of like a hint or information for the verifier that can verify these computations over and over again so uh this is still I mean uh we have the

research written you know internally we know how to make Le hero pre-processing this is required because we have to reduce the verification size yeah now our estimates say that the from proving a statement to verifying its proof there is a 50x reduction so just to give numbers let's say that I start with a 200 billion gate circuit which was what the Llama 7 billion model like if I get a 50x or or 100x Improvement it reduces to 2 billion or like 4 billion m i can recurse it one more time and I can make it like 100 million and now I can put any anything like we if you want into PR networks deep ends anything like you can just push it and like we can get it on chain um we are not looking to optimize

I mean we will do the research but uh it'll be easier for us to just plug into some other system to finally bring this once it becomes a manageable size we could just plug into the system one point I want to mention here is that being ZK by default actually helps here because we don't need to worry about the composition giving us privacy if you start with a snark as opposed to a ZK snark when you compose it which you have to to bring proofs on chain for many of these systems you want a zero knowledge system but you know are you going to trust some other service to do that but for us we don't care because the first step is zero knowledge we can push it in any network because the Second Step you only need a snark privacy comes already

in the First Step At what stage is the project so legatron specifically like you've announced it but are you buing it how far along are you with that latron asses I mean this is fully functional people can start using this with the caveat that you need sort of oblivious control flow on your C program but where we going with it actually is we are right now aligning design Partners to really build some products in the space to educate us how to evolve the Z ZK infrastructure and we are starting with I mean we're close to having two partners one in the Enterprise space uh you know with are Wall Street connections where we want to use ZK for transaction level privacy for

tokenization and this is going to require things like Anonymous zet and zet that they want but with kyc AML in this sense we are different from like ashtec and zcash that uh don't have that in their um or at least in their immediate goals we want to do it like we want to be regulatory compliant and so forth so we are going to enhance our browser based ZK for these application that require client side probing and on the other end of the spectrum on the crypto side uh you know we did this llama 7 billion inference we are thinking about how to build the next infrastructure for AI and you know we're looking to collaborate with this Nim Network for bringing uh AI gaming on chain both of these in some sense I mean

the first step for us is to bring the proofs on chain as you know Kobe said that is kind of one of the biggest uh Milestones which I think we should I mean my estimate is like 2 to three months we should be able to bring uh the the proof on chain but the way I think about it is like we we're going to have like some design Partners to build certain products but on the same end we want to build a unified ZK that's going to help everything right so because when we bring a unified ZK it what we're really unifying is the the developing tools more than uh the underlying U ZK now what about the future research work like are you actually going to be doing a liero 3 yes without a doubt right like I think um again one of the

things for kmit and me that's been like really fantastic working in this is like the amazing research both from the industry side as well as the academic side like how ZK has progressed is amazing and you know I'm going to be humble and honest and say it's like you know it's not going to Le hero or latron is not going to remain the best if we don't improve it and I'll say for now kmit and I have five improvements down the line like that we know what to do but you know we don't know what new improvements are going to come down this year that one other thing that I want to point with the MPC in the head is what kmit and I have like really sharpened our skills in the last four years is we have looked at all the optimizations that go on elsewhere and we know how to

bring it back into MPC in the head so we we hope to continue to do that and you know stay competitive what's the most exciting work that came out recently to you outside of your own I'm a little afraid to say this because I haven't done the diligence but I do think that the works of like lasso like of of Justin with the lookup argument as well as Bas which is also something that U is making its rounds I know how to bring all the lookup arguments into MPC in the head I don't know yet how Bas does but interestingly the Bas commitment is actually the the structure is the LI hero polinomial commitment scheme oh interesting so um I hope that that's

going to um also improve what we uh what we build interesting so I want to say thank you to both both of you for coming on the show and sharing with us the story of liero or liero the Advent of legatron and some of the future work you have planned uh yeah thanks so much thank you it has been a pleasure and thank you Nigel for making for the recommendation yeah and thanks Anna and also actually special thanks to Kobe too who's also been advising us through this uh through the last few months and thank you I hope maybe someday I'd like to ask the two a few some questions in some in some podcast because I have so many to ask you

guys yeah it was a great conversation thank you for sharing all of this cool all right I want to say thank you to the podcast team Rachel Henrik and Tanya and to our listeners thanks for listening