ZKPodcast: ZKPs in Ethereum with Vitalik Buterin & Justin Drake

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me Anna and me Fredrik so today we're sitting with Justin and Vitalik from the a theorem foundation welcome to the show guys all right thank you it's good to be here first off I'd say we should do some intros Justin you've already been on the show you came on to do an episode about randomness quite different from I think

what we're gonna talk about today but welcome back thanks do you wanna even though you've already been on the show do you want to just quickly say who you are yeah so I'm Justin Drake I've been at the firm foundation since late 2017 and I've mostly been doing a research on a firm 2.0 but I guess now that you know the research for phase zero and phase one is to a very large extent done I've started to branch out a little bit to large cruise Vitalik this is the first time you're joining us yeah so I've been part of the etherium foundation since 2014 I've started doing and if each one things and then we've been doing and if

if two related research and many other interactions of research the whole time and I guess yeah recently what's the phase zero and phase one stuff kind of starting to get finished on the research side I've been branching off into different things - yeah it's kind of curious like what do you what do you work on right now what's your focus I kind of jumped between a few different things like in the very very recent time I've been thinking thinking about all the thing that I presented at SPC yesterday which was kind of ways of moving beyond 51 51 percent attacks and recovering from 51 percent attacks and trying to just make sure that the

network can and have coordinated on what to do in those kinds of situations also have economic mechanism things so like following the end of get Quinn grants a quadratic fund which I think you received quite a bit of money from last round and just kind of analyzing the economics of that and some other things before that hmm so on the topic of the name of the show curious to hear your guys's first introduction to zero knowledge proof what was that like do you remember when you first came across them your honor like was it that you immediately got the impact of that and like started thinking about applications or was it just the

thing that went by I remember hearing about them in 2013 and it was either adder around the time of the Bitcoin conference and at San Jose then and this was back when a zero coin this was the [Music] older more complicated protocol that had in a 50 kilobyte rands actions that used accumulators and an evil walk sized or proofs and other complex things was published and I just remember just being really excited that such a thing is even possible and then soon after that of course there was said the zero cash M proposal that was published and this concept of what back then was called

Dyne of scip and a secure computational integrity and privacy and the concepts was just kind of obvious to me in a very mind-blowing and revolutionary and so I was doing this kind of traveling between Bitcoin communities around the world at the time and a few months later a Avis in Israel and I went over to the Technion in Haifa and they interviewed I'm Ali back then so when I was at doing Bitcoin magazine so I've been excited about them ever since did you when you first learned about it did you go back and like do all the research kind of back into the early papers or did you really come in when it when it was more connected with blockchain I definitely

came in when it was more connected with block with block chains and I knew about kind of the existence of some of those earlier protocols but they just have seemed very and if complicated and just the fact that a lot of them weren't succinct and general-purpose just meant to me there and if there is nothing exciting about them what about you Justin what was your first impression of them so I think it was maybe 2015 around that time zero cash I had this company building on top of Bitcoin and open Bazaar so it was something that felt like dark magic that it was very curious about but I don't have the time to you know learn about them but you know my company wasn't

doing too well in 2000 like 17 and so I kind of decided to take a break and you know to relax I wanted to like learn about these their knowledge roofs so I started writing a blog post which I in 2000 June 2017 which was about using zero knowledge proof for scalability and back then no one was talking about it it was all about privacy and I happened to be very very lucky because I emailed Ellie like sent a cold email asking for review of this blog post and he gave me feedback but he also invited me to the Technion so I went to the Technion and I remember when the the it was the

speaker's dinner I was not a speaker but for some reason and he was like hey why don't you come like he he took a leap of faith on on on this random guy who I was back then and you know we I remember the dinner where there was like there was Ellie there was Zuko that was metallic and the imposter in the room was me did you were you the first person to write about that are you like this idea of the scaling the zero knowledge proof the scaling um I think it was such an obvious idea that many people didn't bother writing it but as far as I can tell I was maybe one of the first that's cool because really it was a privacy like the whole idea of they're not

improves even like the original inception with very privacy focused right and I mean it's natural that privacy is the first application because you have much smaller circuits when you want to be scalability then suddenly your circuits blow up and your pruvit time becomes unmanageable and so is that that's around the time that you join did your information yes so I mean we I remember having a quick chat with Vitalik what happened is that I was so excited bout zero noise proofs but then Vitalik like poured a lot of cold water he said but what about the data availability problem so I went back home and I spent like several weeks making about the data availability problem and after a few weeks I had these these

ideas which I think but at the time and not many people were talking about namely around RSI accumulators and so I emailed vitalik and we had this back and forth and like a few weeks later he offered to join the foundation do you remember that yeah I mean in my defense at the time half the community was denying that the data availability problem existed so right we both made progress yeah so one of the reasons that I really wanted to do an interview with with you guys was that I started to notice that the etherion foundation was sort of snatching up some really good zero knowledge proof researchers and yet I think we've actually mentioned this a couple times in previous episodes we

weren't we aren't completely clear as to why like what are the researchers doing in etherium and what are they working on at what kind of at what levels at what layers but maybe before we go into that I think it would be really interesting for us to understand it's a little bit like what is eath research or what is the etherium research team what do you know what do you guys do generally and then maybe we can figure out where the gerontology proofs fit in I mean maybe if it's a likes to talk about the the prehistory but from my point of view in the early days a lot of the research was done very very very small team possibly to a large extent just one person I mean

there's not completely true right there was people like like Vlad and Gavin and but when I joined it was I think Danny had just joined and the research team was surprisingly small I was shocked at how small the product would you had this you know this multi-billion dollar project and we were going to upgrade if you oh and there was like three people doing research as in the theoretical research we also have this other part of the research team which is all around the prototyping especially implementing the ideas in Python and seeing how that works out but now I think we've taken a different philosophy where we try we try and be

proactive on hiring so you know I've hired a bunch of people I think Danny has also made some hires and now we we try to build you know whole team so we like a whole team around cryptography and zero knowledge so what so what is e like when I say III search I realized I'm mixing it up cuz there's a website there's a resource called III search this is the etherium foundation research team so what did it look like or what's the history of it from your perspective italic yeah so maybe 2014 through 20 is 17 or so Roo and it was myself and Vlad mostly and in Gavin for the first year as well and then the Gavin and if we

went off to do parody which that new one off to do polka dot I think the main focuses kind of from the beginning were gonna primarily proof of stake in charting yes these are kind of the things that we said to the community that we would do even way back in 2014 and if has the answer is for well you know what about the blockchain and of burning a lot of energy what about the blockchain not being scalable and we said that you know we would figure out these things we had ideas but we would improve on them and there was this long period of time and there was even longer because they thanked both myself and Vlad and if came in not really understanding Byzantine fault tolerance theory there not being good explanations

of any of these BFT algorithms not understanding a lot of other things in protocol design but then you know if we learned and then over it's over time and Vlad started his inner CBC Direction I'm and then I have started worked with some of what I called a minimal swashing conditions which eventually turned into Casper FF Jia so at the beginning it was this kind of small motley group of people that were kind of just continually working on these things while you know jumping between whatever other things they were doing and then at some point I think in 2017 we started to realize that

it was zero knowledge is something that you know we need to take much more seriously there was this event at IC 3 this is the instead of annual boot camps that we have in the summer and the one and I think it was either 2016 or 2017 z cash people were there and we were there and they had a chance to ask some of them a bunch of questions about how a ZK snarks worked which was really nice that was when the idea for including the developed a curve pairing pre compiles into aetherium was kind of born and there was also this prototype that kind of quickly made a pre compile and then and if you may build an application on

it this was an F so easy cash on ethereum and a year later that became an actual thing there was the Byzantium heart fork that added that pre compile and people kind of started experimenting and of building on it and I think just even that being real and just there being the real possibility of building zero knowledge proof based applications on a theory I'm just gonna really galvanized a lot of attention from everyone mm-hm and so that's kind of where this idea came maybe originally to start focusing a little bit more on zero knowledge proof yep I'm curious what you see sort of the mandate of the foundation because some of the research as you say is work very focused like if you look at proof of

stake research and like consensus research it's very much about solving a problem that exists on the chain today but zero knowledge research starts moving more in like the direction of fundamental research like we're just researching for the sake of maybe we'll find discover something interesting yeah and I think at the beginning it was more and if application oriented it's like hey we wants to have an internal zero knowledge competency is so that we can do things like building and if at least the core of safe and anonymous voting systems or just $0 verifiers that people could put into their applications more easily and things like that and then over time I guess we've definitely

started doing more and more of just kind of fundamental research in the space and I think definitely Justin is mm thank him a lot for the progress in there I mean I'd say that I mean now it's pretty obvious that Suraj proofs are this mega trend within the blockchain space you know the address-book scalability and privacy to an extent and they unlock so many things I mean going back to you know what is the mandate the the remit of different foundation I think a lot part of it is supporting common goods and supporting the whole ecosystem beyond the layer one even beyond layer

two of a theorem but like the actual whole ecosystem and the nice thing about the UH knowledge proofs right now is that it's so nascent that there's quite a small number of experts and it's extremely collaborative and it's a lot of fun what else is like if you're in research what else are you guys working on because we just talked about like this your knowledge group but like are there do you separate it into different groups focused on different problems are you all one larger team that sort of move around between problems there's kind of different sub teams with different levels of fine of formality of their t---minus I think there's CBC for example as of correct by construction Cass burn there's Anna Vlad and Aditya and a couple of other people there

there's rig the robust incentives group which is and have started fairly recently and it's doing some economic analysis of the protocol and then otherwise there is just people working on different problems and within the cryptography team we kind of have a split so we have kind of the zero notch people which tend to be designers or builders and we're starting to build a competency in what I'll call crypt analysis which is basically studying the fundamental assumptions that we're making and stress testing them and trying to break them because a lot of what we're doing in fairness uses assumptions which are fairly recent

fairly exotic so one of the the highest that we made recently was a mystery cottage and we're hoping to grow this cryptanalysis team so like when you say research here like all right are you also building some of these systems out are you just specking them out like I'm kind of curious like I you know when you when we talk about Sara knowledge proofs I know that there is like recently a lot more zero knowledge proof engineering work happening is that happening in the research team or is that more outside yeah so like Barry White had said team for example has done a lot of things semaphore there and of zero knowledge of signaling stuff that's done by them and

it's been gotten pretty far recently and if may see them in minimal anti-collision stuff that's also come out of their team and its close to having a workable version at this point so there's definitely a specific given of course to application layer things being built to they've also started a perpetual powers of tau and that powers of tau is someone unique in the sense that it's one of the biggest I forget exactly how many monomials they have but something like 2 to 29 to 28 to the 20 errors which is pretty big so you know it will take quite a bit of time to run on your computer but if sufficiently many people do that

we're gonna have a nice robust powers of Tom what did you just call it what kind of powers of tau you just said I had them monomials no no not that special yeah is this like universal is this like thing or not is the updatable stuff the universal stuff which is basically the future I think all the other constructions in my opinion is like the beginning of the end does that mean like anyone can still join though is that like an ongoing yeah yeah oh cool yeah and traditionally we've had these powers of tell where it's one postponed at a time and so that can be really slow but because there was this recent observation where actually you can deposit of towel with like 10 people working at a time so potentially we can

have power which are 10 times bigger in terms of number of participants or 10 times bigger in terms of number of monomials I mean I want to talk so there's also some new structures where they you know you don't need the trusted setup and I want to talk to you guys about some of your ideas on that going forward but maybe before like before we move on to sort of the next section I wanted to ask you about collaborations with other projects so there are other projects already working on zero knowledge proof stuff and I know that there's a connection with Z cash and with stark ware and I'm just curious like kind of how those came about and if there's maybe some others that that we don't know about I feel like I've been friends with the Z cash people in Zucco in particular for many years now and you

know we've been going to a lot of the same events in the ic3 boot camp and that I mentioned I spent quite a bit of time with their whole team you know visited the Z cash offices and they're in a couple of their conferences now and they're a very solid and if technical team with and a very strong values and I have a lot of deep respect for them and also it's definitely very helpful that you know they're working on and interested in zero knowledge groups and we're working on an interested in zeroed out which proofs what does collaboration look like between those two groups so is it just sort of like a friendly networks or is there actual like we've co-funded things I think that's definitely been meaningful there's some overlap like you

the stuff Dean mentioned before where in the theorem network has implemented stuff like pre compiles to help bring in Z cash stuff and like help interoperability in some ways or help to build stuff on top of aetherium I mean I'm super Pro collaboration and I'm trying to push it forward you know my talk at Def Con was on collaboration I mean one of the teams I have a lot of respect for and we're very good friends with is the protocol apps team so when I was a Bitcoin open era building open Bazaar open Bazaar is built on the p2p so I got to know them quite a few years back and like the video project is also a great way to have more friends because

it's such an ambitious project that if you don't have friends you're gonna fail so at this point you know we have for blocking projects that are contributing funding so that's cosmos tezo's protocol labs and different foundation and this is for the VDS collaboration yes so well you know we're looking to build hardware is like you know roughly ten to fifteen million dollars but also you know lots of technical challenges things like the rsam PC and whatnot but yeah well you know we're also making collaborations with you know gr solana to an extent with you know near on education to an extent Algar and is helping with the BLS

standardization effort and I'm hoping we can work with even more projects things you know projects like like the affinity for example but you know definitely have been how to collaborate work because they're so secretive and they don't have much open source code but this is all still on the vdf front right what you just described or does that also cross over somehow into the journal so I mean the vdf front is where there's been a lot of collaborations but one of the other things that I've been actively involved with is the BLS standardization and here there was a lot of you know herding cats you know let's all use BLS 1281 as the blockchain standard and through this effort you can make new friends and that's kind of an

interesting point of collaboration where it's not necessarily that you're sharing engineering efforts or even sharing research but you're trying to get some sort of standardization and to do that you neva tably have to collaborate somewhere right and I think one of the future areas for collaboration will be wasn't because we have all these go team projects building and wasum and right now from what I can tell there's almost no collaboration which is drives me crazy yeah it's it's weird I mean it's it's a kind of a strange thing where everyone has their opinions because the difference is on the by code is none like the by code wise basically all look the same so it's like which what what the host interface looks like and yeah

like some projects like near have like in a synchronous model and some have a synchronous model and that makes a very big difference and like it's fundamental if you have a difference of opinion on things like that then you're just never gonna be able to agree because it's like Mac versus Windows people like they're not gonna agree but it's not for any real reason but it's it's kind of happening so it was that this was a conference last year and we had some of the Mozilla people over and they were talking about the huazi standard which is you know a host interface standard to run Watson programs on your computer and interface with like a UNIX type interface and we actually got the Mozilla people to kind

of agree that it would make sense to have like a blockchain subset of huazi and like that I think that's a good like thing to pursue yeah that's actually that's another that leads to another question about this like are you also seeing collaborations with other organisations may be non blockchain related organizations other open-source communities and academic groups are definitely the first place to start look we've had very long running collaboration with ic3 collab recently with and of Stanford CBR which if we were one of the founding sponsors of and you know Mesa going on in aetherium project is another one of

them and then academic groups in kind of in Israel of area of various kinds though that and that's been a bit informal and Elvis on Zorro SES and of his his team as well at Berkeley yeah and PDS is also a great magnet to get academics interested so we had vdf day number four just before the Stanford Boston conference and there was about I think 30% of the room was academics there were 70 people and they came from nine different universities from four different countries cool actually we one other group that we

haven't spoken about yet is Stark where what is the relationship with Stark where the etherium foundation and it paid or give a grants to us dark where to basically work on House Stark friendly hash functions right I mean the bigger picture is Starks is like the bet that we want to place for quantum security for a firm 3.0 so the cool thing is that journalize proofs are so flexible that they can be kind of this massive power tool to to rule them all so it can do signatures it can do prefer custody you can do videos you can do everything how do you see you know we kind of

touched on this a little bit before the the difference between snark or this is generally zkp constructions that need a trusted set up versus those that don't like how do you see the space of those that don't need a trusted set up like transparent proofs right so in the last year so you used to be I think mainly stocks from stock were transparent but now there's competition in the space so it turns out that if you have a polynomial commitment you can have Universal stocks and so the question and the the question becomes you know can you have plenty more commitments with

which all transparence because then the stock will inherent that property and it turns out that there they are so you can use the dark polynomial commitment which is using class groups there's no trusted side up there and just a few days ago there was this massive kind of announcement in the cryptography space where there's a new type of group of an order called Jacobian groups of hyperelliptic curves of King III and they also don't have a trusted set up and they have a very nice performance properties is that coming out of like snark researchers this somewhere else that this exists well so what happened is that 2013 19 was the the the

revolution for universal stocks and now there's like so much attention to these polymer commitments because they is a very nice framework and to work in and you know one of these play on commitments that was found recently was the the dark and that kind of led to that that led to the the need for more groups of unknown order which actually the basis for V DFS and and accumulators and vector commencements and all these desire things so if if it wasn't for all the blockchain applications we I don't think we would have today this group of

unknown order and this interest and like this this sort of like yes attention on it and one of the amazing things about the theorem brands being in the firm researcher is that you send an email to an academic the probability that he will reply to your email excited is extremely high yeah who who was it that came up with the jacobian version so I think this is a famous guy called Galbraith I believe actually it's I think most of the credit goes to his PhD student I forget his name but one of the interesting things is that Dan Binet months ago I think in November he had this intuition that yeah

we can use high predicted curves but there was this one problem that he couldn't crack and it seems like these guys came up with a clever idea we're definitely after this we'll go find this article right yeah we'll try to find the paper and put it in the show totally mm-hmm speaking of groups of unknown order we just had Luca to fail on to talk about I Sajha nice and there's one interesting problem in there that's like that that's what I'm looking forward to in this space when we can construct elliptic curves of unknown order without a trusted setup so he says there shouldn't be a reason we can't do this it's just that no one knows how to do it yet we doesn't skoufis algorithm just to work on elliptic curves mmm you mean in

the context of isogen news yeah but so the reason this came up is to do asaji nice based VD FS you need to get to an elliptic curve of unknown order and the only way that we currently know how to get there is to do random walks across the space of all the curves using Asajj anis and then so that that random walk requires a trusted setup then so the way that I understood what we've always said is that basically you want to have an elliptic curve where you don't know the endomorphism group and so the idea is that you start with a hyper loop to

curve and then you do this random walk and so long as one of the postpones is honest then you'll get to a point where your the curve has unknown on the morphism group yeah and he said that there is a way to get that without the random walk yeah that would be amazing putting it out into the universe hoping that some listener will solve this problem so next up I want to explore a little bit more how zero knowledge proof are being used kind of throughout the eath to construction how you're thinking about them where they fit we've kind of covered if you're in research we've

covered some of the collaborations we've touched on a few of the projects but you have these great researchers in house some of the research as you mentioned is going towards kind of like general public good but I imagine there's also some really interesting applications within the construction within the eath to model so where are where do they live where do they exist I think again of the most obvious place to start subdividing in as stead of thinking about we are one applications versus and later two applications and by layer to I don't just mean scaling I well I get fine there's way or 1.5 there's also application layer things right so at the application layer and we've been seeing

mixers get in a fairly popular recently and you know in etherium there's been a bit of the sin of privacy awakening that's been starting and there were this incident a few weeks ago where I think one of the co-founders sold about 90,000 EF and this transaction was detected and the coin media talked about this and and then there was this other release by some groups that kind of traced a whole bunch of ENS names and so people are realizing and if their privacy is something that they should take seriously and the problem is that you could consider trying to get privacy by kind of sending your coins to a different account but then if you do that then make the link between the new

account and the old account is still and a very detectable in the clear and so what tornado cash offers is basically a and Ock snark based mechanism that allows you to just send coins from one accounts to another without and if the link of Kristen's to whom actually being public because you as II kind of style mechanism is used to enforce that so that's something that's been getting a lot of attention and then there's some other projects I'm like on III search and there's one called a zero pool that was published and there's also this longer term thing called the Aztec all by the way all all but zero pool not

but Aztec and tornado they've been on the podcast so we can also add the links in the show notes if something wonderful more yeah so there's a lot of progress on the in the payment space and then also may see this is in a minimal anti-collision infrastructure that's and of basically and if secure cryptographic voting where you know you want it to be anonymous but then there's this additional challenge that you don't want it to be possible to prove who you voted for because then that you can bribe people to vote a certain way and you came up with a kind of spec for that that basically and it relies on a central party for the collusion resistance but does not rely on that central party for anything else and the get coin grants quadratic funding people

like you know actually want to use this right because quadratic funding and kind of voting and all of these mechanisms in general you know have this proton this property that and if you spend $1 of your own money to cause an impact to someone else's money which is bigger than $1 and if like you need that in any mechanism of that kind of funds public goods and kind of counteracts the tragedy of the comments but the problem is that once that property exists then like a malicious recipient can just bribe people to take this action and then you know they they spend $1 then you get or the bribery gets $10 and then they kind of give $5 back and that kind of just breaks the whole mechanism and you know me seek and then hopefully

solve this and then all of those that you just mentioned those are all layered to there is a roll application layer yes if we were to look at layer 1 it's kind of confusing because if you look at the phase 0 and phase 1 spec there's no schnapps and we don't probably won't have snarks and phase 2 iver okay but the bigger picture is that you know there's this kind of separation between cryptical Norwex and cryptography and when i was doing research you know installing my motor was if cryptography doesn't work try crypto economics because usually you can find a solution that works what crypto economics but as you try and implement these things you

realize that actually the economics pulse is is the devil you kind of want to minimize it so I think you know moving long-term we want to try and take some of these cryptic anomic systems which have complexities around fraud proofs and challenge and response and you know you have assumptions around rationality and honesty and things like that and just replace them straight out with cryptography and the whole system becomes simpler so now I want to talk about layer 1.5 and what you just said this idea of going from the crypto economic to cryptography it's kind of interesting what's happened on one of the layer layer 1.5 projects roll up where it went well plasma ish like something very crypto economic to

something cryptography to with zk roll up to optimistic roll up which is again game theory so how did that happen yeah so ZK roll up and I Pablo this research post about about it about a year and a half ago and the goal there was just to kind of show that hey you know there exists this other category of scaling solutions and can get you up too back then 500 transactions a seconds now after we did the called data gas cost reduction in Istanbul 2,500 transactions a second and you can do this with these really nice property is like you know you don't need to really depend as much

on central operators and the system has better ways of recovering from failure you can deposit and withdraw immediately and all of these other nice things but the challenge with Z control up there were two of them right so one of the challenges that we had upon immediately as zero-knowledge prove her time is a very non-trivial so I remember matter labs actually implemented a CK roll up pretty quickly and they said they even got up to over a hundred TPS I think it was on main net but the problem is that the reason them that they said they didn't get more is basically because their servers were kind of at full capacity generating these proofs and the

other challenge that the CK roll-up I think had or has is that people want to do more than just moving coins around and I think this is you know the big thing that's also led to challenges for all of the other if they really are two protocols which is I think people are on aetherium precisely because they want to do more than just moving coins around new people already have existing applications they want to move their applications over they don't wants to rewrite their whole applications in the process and so the thing that people actually want is basically a way or two that just behaves like the EVM and optimistic roll-up is actually enough capable of providing that right you have to do a couple of clever tricks like you had the optimism team for example have

this really clever and of code translator that takes like the SLO top code for example and they replaced every instance of the SLO top code with a call to a contract that checks the Morgul proof they do the same with s store with the do the same to kind of wrap external calls and then because those other manipulations kind of changed the code positions around zephyra the kind of added jet at a dictionary for a jump table so they've there's a lot of tricks that you need to do to make it work but like with optimistic roll-up you actually can make something that does actually you know the same thing that the EVM does and that's something that a lot of people are attracted to but do

you think like but DK roll-up you you're still working on cjs roll-up so where does that live then what how does that fit in like is it still going to be used for certain cases or is it more like once it gets more efficient I'll be fine so the the looping team for example has been making a lot of progress on a ZK roll-up recently they published some numbers with a version they released a through EDX about a month ago and they have implemented a Z key roll up for a decentralized exchange and the statistic that they gave was 0.3 cents per transaction for unchain gas and 0.3 cents per transaction for the approver

computing time but both of those numbers are still very far from optimal right because on the one hand the 0.3 year sense for unchain gas and was there just because they had fairly low volume and if they have higher volume then the per transaction gas Kosc and if the amortized amount goes down for a mil 2500 or 4500 that it was back then to a theoretical minimum of about 400 and if you have that then of course the 0.3 cents becomes the 0.03 cents and on the approver side and one of them just and have told me very recently that they made a and a factor of 30 improvements in proofer time and so it seems like

they've been doing quite a good job of making z key role of work at least for the Dex years case now the final frontier of course is can you make Ezekiel up work for a general-purpose computation and that is still to be determined I mean that's kind of one of the crazy things that I'm you know how remove this space move towards so you know there's like really that like snacks are amazing in all respects now except probably for the the approver bottleneck so how can we improve the about the bottleneck there and actually there's this there's a few ideas here so one kind of obvious one is a hardware acceleration so we've seen people use

use GPUs for example but once you become more ambitious and you go with for example a stock ASIC then you know you can get you know a thousand X speed-up so I mean the the rough ballpark right now is in terms of the comparison between native speed of a CPU and you know the speed within a snark circuit is you know between a billion two trillion X slowdown so you know we need several 10 X ideas to get to where we want to be one possible kind of 10x idea that I'm excited about and I'm working on right now is this idea of a sparse knock so if

you like as an analogy I think of a CPU CPU has about a single cores about a billion transistors and a CPU has about a thousand instructions that can be called and when you call an instruction the CPU will turn on the transistors for that one instruction and the rest of the chip is turned off so that's called dock silicon and the reason is that you want to save on power and you want to prevent the chip from just melting and maybe we can use something similar for snarks so you know one of the Holy Grails is general-purpose computation and that means like massive circuits but that doesn't mean that you have you know all the wires and all the gates turned on so what you can do is you can set almost

all the wires and all the gates to zero and then you want to try and use this sparseness to your advantage to accelerate the prover in that case is it like you're having other things use that sparseness like use that space or is it just speeding it up because you're not using those that space it's sped up because you're not using that space yeah so you know one of the typical examples is you want to do a conditional in a stock is like you know if let's say a equals B or if a not equal to B like in the traditional snark circuit you have to pay 2x the cost like foot both branches that that's very expensive you have this blow-up but if you can activate only one branch at a time

that's a huge benefit so you know going back to what I said around you know the key is a poly more commitment that is your starting point so you know a few weeks ago we discovered a a spouse put on your commitment scheme that could use the sparseness and then you can do so-called spouse had more checks and you know and that my own locks past snarks what's that called 20 what you just said this first snogs part sparse knocks but it's called sparse well that's not that's how I'm calling them because sparse part of the world commitment is a very natural term which other people are using and then that kind of extends to like the other tools in the stack cool I like the name yeah I mean another idea

that I'm working on is trying to simplify the prover and in particular when when you look at the prover there's basically three components in the prover there's the witness generation which you know today tends to be negligible like let's say 1% of the proof of time and then you have the FFTs which tends to be like 20% and then you have the multi experiencie Asian's which is 80% now okay you want to try and speed up the 80% and you let's say you build an ASIC but let's say you bring this 80% down to zero now you're still left with a twenty one percent or twenty percent so you've only sped up the whole thing by by 5x so now you need another ASIC basically that will do the FFTs so what if we can just simplify the problem and remove the FFTs

and also the FFTs are you know a pain in the neck because they're not super friendly to distribution you know they can be paralyzed but they have these these choke points and you know not super friendly to full for full distribution and they're quite expensive in terms of memory so I've been working on a point I'll commitment ski where you completely remove the FFTs and then you can do the same thing a harder more check with no 50s and then the snark about the fifties well what do you put in its place though do you just take them out like how do you why doesn't everybody take them out well for a long time people believed that it was not possible to take them out for fundamental reasons and I think that discouraged a lot of people from growing up that route but you know I came in you

know naive and with French ties and I guess you know there was a few tricks that had to be found actually vitalik helped along the way that when they helped along the way and yeah it turns out you can do it so if we are going to build a stock ASIC which I think we are and I think it's going to be a collaborative project for the production space then we will focus on the multi experimentation we can just forget about the fifties you just mentioned sort of three optimization things you said get rid of FFTs hardware so like using a six and the sparseness right is there anything else that would optimize right so I mean one kind of recent idea is this idea of custom gates so that goes

down to how you lay your circuit and that's that's a big area for improvement where so if you think the hardware nology kind of works well so if you if you're building an ASIC you know you have this so-called cell library now you could build everything you know in theory out of NAND gates but actually what happens in practice is that you have these cell libraries with with hundreds of gates that will do more complex operations and by using these these slightly bigger so-called cells rather than the primitive gates you get quite a lot of speed-up and so the same thing is happening and and this is something that is being led by the Aztec team so for like a perfect example is

let's say you have a hash function like NIM see where you basically rip repeating an internal round function if you have a custom gate for this internal round then you can really get a lot of performance benefits and then like another really exciting idea which lots of people are working on and there's now lots of different ways to do is is is a recursion so recursions helped with in in two ways one is that if you do for example one layer of recursion or a constant number of layers of recursion then you get a constant improvement in the in the verifier time

so you can take for example a thousand snogs and compress those into one single stock so there you go you have a thousand improvement on on on the verify time but you can go even further and you can you can have these systems where you always only have one single stock at the very tip of your system and so that's something for example that that coda is working on it's very exciting yeah we've we've done I think two episodes on recursion so far yeah cool and the cool thing is that these ideas tend to compose on each other so you know let's say we have roughly ten like five you know ten x ideas we need another five in order to get to where

we're gonna be the other end of thing that I think we want to optimize this range jacking yes actually there there is a paper coming out in a couple weeks range checking yes just a verifying that a number is between zero and two to the 60 or three or whatever so you don't overflow so what tends to happen is that you have your your Ponyville commitment and then you build gadget out of it so you can have a permutation gadget or shift gadget or a some gadget or protocol attic and one of the gadgets which is used very very often especially when you're doing like big integer arithmetic and things like that is a range tech gadget and you know I as I understand so like a few days ago there

was this really nice idea basically showing how you can use pointer commitments as a raincheck gadget and from what I understand in a couple weeks there should be a write up with pretty exciting ideas where you can batch these range checks this is kind of sort of unexplored territory that right these are like ideas at this point or I mean the amazing thing is that this is so much low-hanging fruit so I I know you've seen right in 2019 how much how many papers were published on the on the continuous basis and you know even in 2020 we're finding ideas new ideas you

know every week pretty much so why do you think there is that acceleration and in this space there's so much happening it's just that more people are looking at it the hardware got good enough that we can do it or what's what's the catalyst here I think a lot of people with kind of pragmatic and engineering mindset kind of gave up on 0 noise proofs as being kind of unique old magic that is not really useful but I think Z cash was like the big moment where everyone woke up like this is actually real and you know we've had this education period which has been somewhat painful and you know metallic has done a great job trying to educate people on

these on these difficult topics and now we're at a point where the people with both kind of engineering and research hat on are here to solve questions that are less about for example asymptotics you know researchers they love asymptotics whereas the the engineers they love constants so yeah the ball is being handed off to the engineers actually that's nice that you just mentioned the the papers or the blog posts that you wrote that Alec you wrote what was it like for on snarks 3 on snarks one on plunk three on Starks yeah and I know that those are actually like pretty important resources in the community when did you write the snarks

one figure was like 2016 to 2017 quite long ago and plunk would have been really recent yes and Starks was like in the last two years yes cool yeah we'll definitely link those as well I know that they've been a resource that a lot of people have learned from myself included and I think one of the things that's difficult in our space is that if you take a research paper you're gonna have a 20 to 30 sometimes 50 60 page thing which is undigestible and like generally speaking the the intuition the core part is like hidden on page 15 second paragraph and is like a few lines and I think one of the trick is you know to be able to

identify this and remove all the crap and I think the italic has a has a skill for them cool so we've talked about the application layer layer kind of 1.5 so what about layer one we mentioned e3 earlier is that where some of this is starting to come in or are you are you already imagining you know applications of zero knowledge proof on layer one yeah and I think in general we have a long-term goal of trying to kind of fit in zero knowledge proof in places to adjust remove as much as possible of the need for like lots of notes to Rivera Phi the same thing for fraud proofs to kind of cover cases where people did

things incorrectly as part of things like data availability checks for example so in a lot of any kind of places where right now we have some kind of more complicated protocol for collectively verifying something without having everyone personally verify it but a lot of those cases are situations where you can just simplify things a lot by just allotting is your knowledge proof in cool are there any other there's I mean there are a lot of places that you're looking at it there's a handful I mean one example for example is single secret secret leader election so the idea here is that okay so you have these validators you sample them at random using randomness but right now

the result of the so-called lottery is public and so you're gonna know who is gonna be cold to participate in the future and so that's the denial of service attack vector because you can do an network DDoS but there's also ever attacks like you can try and bribe them with a small contract or whatever so one of the great mitigations here is you have a lottery where you don't know who the winner is and there's a very very nice scheme that Stampin and I was came up with that we're looking to implement and one way to implement it is using an Illinois proof and that's the kind of clean way of doing it and then there's this other way which is kind of using crypto economics which you know we can possibly implement faster get off the ground faster but

it's it's it's more ugly another place where I think there's a lot of potential for snarks is in witness compression right in in phase two we have this idea of stateless clients stateless clients is when the validators don't store the state they only store kind of this small digest so called like accumulator which could be for example a miracle root and to counterbalance the fact that the validators don't have the state the users themselves when they make transactions they need to come with their own state and proves that the state is actually real so the miracle pass all the way to the medical route and in practice if you were to take for

example f1 today and you were to go in this stateless model you'd have a huge overhead in these in terms of bandwidth for these merkel paths and you know on the order of 10 x so what if we could take all these miracle paths and compress them into a single stock and remove this 10x overhead data availability cheques are another one so this is this other end of branch of research that I've been doing sit for about three years now and I've published that paper with Mustafa back in a 20-18 worry yeah have this scheme where basically you take some data and then you're in a erasure code that data using this and if two-dimensional reed-solomon

code and the idea there is that the erasure coding kind of transforms a kind of make sure 100% of the data is their problem into a make sure 50% of the data is there a problem and once you only need to make sure 50% of the data is there then you can use kind of random sampling to figure out whether or not enough data has been published in enough constant time this is a key technology that we wants to use for just enough scaleable validating that the data inbox actually that have been proposed actually has been published and the technique that we proposed in 2018 um is one that is very dependent on fraud proofs and in order to make the fraud proofs work we have to use a 2d

code instead of a 1d code and that has a suboptimal rate and that there's some annoyances in it but um we have a number of kind of alternative proposals so one of them involves polynomial commitments and the other one involves basically just using a snark to prove that a merkel root of erasure coded data was constructed correctly what phase is that right now though cuz it sounds like you're it hasn't been decided it's like there's some possibilities but yeah definitely after phase one got it I mean like the final thing that comes to mind is is very much related is around proof of custody so proof of custody is never mitigation in addition to the data

availability checks for the data validity problem and right now we have a fraud proof based scheme and it would be very nice if you could have a pure cryptography scheme so the the ideas way is very simple basically you have data that you want to prove that you have at the time you make a signature so what you do is you take a secret and you mix it in with the data so what you could do is you could have a zero knowledge proof saying that you've correctly computed the merkel root of the data mixed with the secret and that proves that you have had should have had the data another application and you kind of touched on this was when you talked about Starks is post quantum security for the chain like when does that enter the picture it's

this is definitely something that you know we're designing the protocol or Rao instead of being able to upgrade to eventually like there's there's some afid parts of the protocol that are not quantum secure at the moment but I think for every single thing that we use we definitely wants to have the ability to and switch to in existing and ready a quantum safe alternative when we want to the one that's probably the toughest at the moment is aggregate signatures you know so post quantum signature schemes exist but and even hash-based stuck one through secretary schemes exist by kind of post quantum aggregation friendly signature schemes has definitely seen and if considerably less attention and using

the snarks or in this case Starks it's which apparently are a type of snark now and to solve this problem so I basically just using a stark to prove the existence of a bunch of import signatures for example is one of the past solutions that we're looking at though in order to actually make that be possible we're definitely going to need some very significant improvements in approver time the whole difference between snark and Stark is funny and like everyone has a different opinions on what a snark is and what a Stark is basically the consensus seems to be that whatever comes out of Stark where it's a stark and everything else is a snark no the

totally unconsidered mental intuition that I had started with for some reason as like if it uses elliptic curves it's an arc if it uses hashes it's a stark and if it uses head in order groups it's a dark and then I started talking to people and then I realized other people have totally different ideas and I don't care so on the topic of the you know the quantum secure signatures that can be aggregated now this is a very hard problem and this is also an opportunity for us to collaborate with academics so we're currently working with a group called crypto necks and you know they have Zhang Xiao Jie and UW PA both experts in quantum security so yeah we

have a team working on that like is there anything in the construction right now that is similar at all - like what celos been doing with this like light client construction you sort of mentioned this data availability is that related somehow are you guys are you thinking about creating sort of like some like smaller like clients using zero knowledge proof that's definitely is the sort of thing that we wants to do kind of longer term so I guess and if the recursive sonarak I know like verify everything in one proof stuff that verifies data validity so if you download a block then you can prove to you that that block is the latest block

in a chain where the entire history is correct and possibly even proved to you and that that chain is better than in terms of kind of consensus priority than any other chain that you've seen but the thing that can't prove to you by itself is that the data in the chain actually has been published and even if all the data is correct you can do lots of really mean things by withholding data you can basically withhold information that other people need to make their own transactions and if sends things from other accounts and so it's almost equivalent to stealing from people and what data availability a check so what you do is basically a kind of randomly

sample of all of the data in the chain and if the data is erasure coded then you're just kind of randomly checks that and with very high probability at least enough of the data has been published that if necessary the entire thing can be reconstructed I'm curious to poke your minds on something that is I know without naming names some companies that have now gone we're not allowed to talk about their knowledge groups anymore can't mention it in the office become because it becomes a practicality thing where everyone instead of actually trying to solve the problem go zero knowledge proof will fix that

whatever will keep working like zero knowledge proof will fix that and like just kind of passing the ball I mean I think that might make sense as a policy I mean unless you're very serious and you have people that are dedicated to it I mean I'd say it's very similar you know comment maybe for blockchains even like you have all these companies they'll block chains will solve everything unless you have you know at least one blocking expert in your team block chains is probably not for you I've also heard companies I know some companies where they hired a zero knowledge proof researcher to kind of look into it but then realized that the space was moving so

fast and they maybe didn't have the capacity to fully contribute or fully keep up so they've sort of taken a step back and been like let them figure it out and then maybe we'll add it back into our system I mean this is almost the opposite of a problem that we that we had in in Bitcoin and the theorem which is that you know no one want to build stuff on the theorem that were or Bitcoin that was high volume because if they were successful then it then you know they're willing B's supports for them the system basically wouldn't have that fast enough but here's the opposite problem where the system is just adapting too fast that you can't even

keep up with it yeah and in a way that's that's sort of true like if somebody's gonna put in the resources to implement one of these things and actually this this was this was a topic that came up with like eath one would this idea that like certain I'm not gonna say this right but certain curves were I mean the pre-compiled that we talked about before that was added then Zeke a chef created like not using that curve anymore so it's kind of pointless that it was added and now we need to add like the next one and I mean that was a particularly unlucky case but it is it is a good point this is definitely a problem that a lot of kind of projects just have to deal with like at some point you have to just choose and say right now we're

building with this set of technologies and like yes we know that that means that we have to do this stupid multi rounds a trusted setup and then maybe four months later and maybe ten months then twenty months later plunk is gonna be ready to use and that whole effort will have been for nothing but in twenty eight months in the future like people might be talking about well why you spelunk when plunker 2.0 is gonna be ready it's so I hear they just actually add letters before plunk so it's long it's uh what Ariel had another one this this problem of curves that you bring up is is very serious and it kind of goes against the whole universe universality

revolution that we're seeing and the reason is that for different use cases you want different curves so you know you have BLS 1281 which is the standard we're going toward the then you have this ever curve because 12 377 and then you have the MMT form and c6 cycle and then you have the BN to 5-4 cycle which is the legacy curve which is the only one that a firm support so that's what everyone is building on in practice and you know this is this is gonna I think unfortunately this is gonna hurt us maybe one of the kind of advertisements for the RSA based snarks is that they're in several ways truly Universal so there's no kind of bike shedding on the

type of RSA group there's only one type I mean you can choose your the bit size but you know you'd think that people would agree on that say three thousand bit RSA group that's plenty of security but the other interesting thing about these RSA based snarks is that they're not bounded in circuit size so you have a powers of towel it only goes up to let's say 2 to 28 and if you want to go beyond that you have to restart your parcel to tell from scratch whereas you don't have this limitation with RSA groups one more use case of snarks that might be relevant is in Casper CBC the validity conditions for blocks are kind

of very simple conceptually but they're kind of fairly involved and complicated to actually verify so the validity condition basically says that for a block to be valid the block must be the the blocks parents must be the winner of the fourth choice rule executed using all information that has been included into that block where it's history and like there's a really nice and cleaning out of mathematical intuitive sternness to this but the problem is that this takes kind of event time to evaluate and snarks are something that can possibly help with this so I think we've I mean we've come a long way I think we have a way better understanding of what's going

on with zero knowledge proof in these two worlds and all of that like at all the different layers but I think a nice way to close out the episode would be to talk a little bit more about this future idea for it you sort of mentioned Starks and III but where else like what else are you looking at in terms of just like the larger zero knowledge proof ecosystem are there other places that you're just sort of keeping your eye on or other ideas and there's also enough areas of cryptography other than zero knowledge proof s-- multi-party computation and homomorphic encryption code obfuscation there's definitely quite a lot of use cases for each of those do you are you hopeful that those will exist anytime soon or like if you imagine 10 years

from now like which of the these things are in practice an MPC and have already exists but it's not efficient for all things and I definitely expect the set of things that MPC is efficient for to improve the question is just by how much I mean the RSA NPC is really pushing the boundary so we're doing a I think the record for the NPC's was actually set by Aztec so they had a 173 participants and it the the ceremony lasted one month we're looking to do an MPC with over a thousand participants and if everything goes fine it should run in about ten minutes so we're really like shattering the the records here you mean like ten

minutes per participant like on their computer ten minutes total for what all possible cuts so the catch here is that all positive hands need to be online at the same time and if one of them disconnects we need we identify them so it's you have identifiable boats and then you have to restart so that's why I say in the best case it's ten minutes but we'll see well it said ten times F minutes and BFD one go all right I mean one thing I'm quite excited about just from a nerdy perspective is the the i/o like indistinguishability obfuscation like a piece of magic which you know as

far as I understand can be unlocked by this cryptographic primitive called try linear maps so we have by linear maps with the pairings you know which gives us narcs and which gave Els signatures when you go to trial in their three is so much better and you can do IO and just you know a couple days ago there was a new paper by by Huang who apparently is very well respected with a very promising construction that's interesting I mean we had Anne Bonny on the show and we he at the end he talked about what he's looking forward to and challenges that are unsolved and he mentioned try and try linear maps and then code obfuscation as one of the big unsolved

problems that he's very excited about and I after that I looked into it just like holy this this changes the whole landscape of smart contracts it just it does so much like it's amazing I didn't know that there was like actual results and that super exciting I mean I mean just for the listener who doesn't know what it is I mean one of the consequences is that you can have a small contract which holds a secret in the code of the contract so you can have a secret which performs a specific task so for example it will only sign a message if the message has a certain structure but at the same time even if the code is public no one can go extract

the secret and sign messages that the contract was not meant to sign some of these ideas I mean they're going past blockchain right this is not a particularly blockchain focused concept is it they have very interesting cool applications in marching but no certainly go way beyond blockchain yeah do you do you do either of you sort of see or are you excited about zero knowledge proof past blockchain or outside of blockchain because I know that that is something that I'm starting to see bubbling up so one of the things that I've observed is that a lot of small people that I've tried to hire say no I don't want to join because blockchain I am not fully convinced yet you know it's kind of but then you tell

them you can learn about zero knowledge proof and then they can see a career there because it's it's an easier sell they can see that even if the blockchain world would go to zero the zero is proof of our huge applications in an industry and I think kind of the blockchain space is going beyond blockchain and this is kind of one thing that I'm excited about and I guess what I mean by that is just the communities that are trying to and if build things on blockchains and trying to build some decentralized finance constructions daos and all these other things i think there's I think definitely area of increasing realization and if the

blockchain isn't the only tool that they should be using and the right solution and it probably involves like using a blockchain for some things but it might end up including you know some compact components of an MPC architecture some people some components of something else and just a kind of branching and if I would out answer just thinking about it as and if how do we use cryptographic and economic tools to build the things that we want to build that's a good way to think about it I want to say thank you guys so much for coming on thank you so much that's was great no thank you and I definitely want to extend an invitation to both of you to come back

and maybe do deep dives on some of these topics that we covered or some others if you have some ideas yeah thank you very much it was awesome and to our listeners thanks for listening thanks for the