SNARK Research & Pedagogy with Alessandro Chiesa

Transcript

[Music] welcome to xero 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 [Music] this week i chat with alessandro kieza a professor working on cryptography complexity and security he is also a co-founder at zcash and starkware ale has taught many of our previous guests and in this episode we explore some of the work that has come out of his lab we also touch on the challenge of creating educational resources around snarks

especially since it is moving and changing so quickly we also look at which parts of snark understanding are somewhat stable and which parts are still very much open problems to be studied further this also happens to be the zero knowledge podcast's 200th episode and to be honest it kind of snuck up on me still i'm so excited that for this episode we have a deep zk topic and an expert guest seems very fitting i hope you enjoy but before we start in i also want to let you know about zk hack zika hack is a multi-round online event with workshops and puzzle solving competitions it's put together by this podcast and the zk validator it's supported by a slew of fantastic sponsors many of them zk projects from

the space it will kick off a weekly cadence starting october 26 2021 think hackathon meet ctf meets dark force round-based competition there will be a leaderboard and there will be prizes as well as deep dive learning sessions with the best teams in the space so do head over to the website now to join and if you happen to be in lisbon at the end of this month for the lisbon blockchain week over there be sure to check out the zk hack party together with aelio and noma we're throwing this in-person event a little bit as like a pre-party to the zk hack event itself so yeah do check it out we'll be sharing links on our twitter telegram we'll probably put some links in here once we have them as well hope to see you at the zika hack and possibly at the zeke hack party i would also like to thank this week's sponsor centrifuge

centrifuge puts real world assets on the blockchain allowing issuers to get liquidity on their assets and investors to make safe stable yields in the volatile crypto world it's built on substrate but they also bridge between ethereum and polka dot centrifuge are currently hiring for a number of positions including protocol engineer product manager full stack engineer security and devops engineer do check out the link in the show notes to find out about all of their jobs and i want to say big thank you again centrifuge for sponsoring the show now here is the 200th episode of the zero knowledge podcast with our guest alessandro talking all about snark research and education [Music] so today i'm here with alessandro quiesa a professor working on cryptography

complexity and security he's also the co-founder of zcash and starkware and actually ally you've been on the show before so welcome back to the zero knowledge podcast yeah thank you for introduction it's wonderful to be back so that last time that we had you on the show you were mainly here speaking with ellie about starkware and the research that you had done leading up to the project what we didn't really get to cover in that episode was your other academic work so you've been running a lab the laboratory for computational security it's produced a lot of research a lot of your students have come on this show to describe some of the work that they're doing and actually any subscriber to the zk mesh newsletter may be familiar with your name because you've authored or co-authored a lot of

the research that ends up in that newsletter so yeah quite excited to dig into all of this with you but yeah to start off i'd love to learn more about the lab and explore what you and your students have been developing and exploring in the last little while sure yeah so i started working as a professor uh six years ago and uh so it's now a good chunk of time and uh over this period i've been working on ramping up and running a research program that touches on many aspects of uh cryptographic proofs primarily snarks and what i mean by many aspects is that the research frontiers in this topic concern uh basic mathematical questions in uh low-degree testing linearity

testing these are sort of a bread and butter of where the succinctness of snarks come from to other topics in cryptography how do you take probabilistic proofs and like pcps interactive proofs and interactive oracle proofs and you convert these to argument systems and so there's the theory and foundations of these transformations and then there's the applied aspect that moves further from cryptography into apply cryptography and system security which is studying the practical aspects of these constructions and how to use them inside protocols to achieve interesting goals like private peer-to-peer payments like in zcash and as part of running this group i've

been trying to get some strong students interested with a variety of backgrounds maybe more on the theory side or more on the applied side and to kind of learn as much as possible the ins and outs of prolific proofs snarks so we can push the frontiers across this whole spectrum in a way that takes advantage of the fact that not only we understand the theory but we also understand the practice and so we can sort of in a coherent way push the boundary of snarks cool how would you break it down in the lab like how much is theory how much is actually applied would you do 50 50 or do you think it's more focused on the theory side yeah it's a great question uh what i found is that uh it takes several theory papers in order to get uh you know a smaller number of good applied papers and out of those there's

a smaller number of useful protocols in the real world okay the weight of i've been operating that i find is useful is more biased towards the theory because there that's where we want to push frontiers of like difficult questions and we don't want to be restrained by whether it's immediately practical or not that might be a concern that will come later it may never be but at least we're making an attempt to push the frontier and then usually to solving a hard question in the theory world will inevitably force you to come up with new tools and then what has happened time and again is that some of these tools maybe not necessarily as invented for a theory but morally those same tools end up being useful in applied context so a great example here is actually my first paper in uh

i wrote in 2009 was about recursive proof composition of snarks actually oh wow and at the time it looked very much only theoretical and in that paper we formulated this notion of proof current data which was sort of capturing what can be done with snarks in a recursive way and it took maybe till the end of my phd to have a first implementation never mind practical so like a running implementation of a recursing snarks and it took another few years for these to become practical enough to be useful in the real world but in the meantime there was like a lot of theory that was done to enable a little bit of applied cryptography to enable you know a few systems in the real world to take advantage of the recursive snarks so and there's several examples

of these that i can see over the past now i've been working in this rocket for uh 12 years uh six years as a you know before professor and six years as a professor and there's many examples of these where i see that a lot of effort on theory if you sort of tackle the hard questions then you will be able later to pick up new techniques and then leverage them for advances in applied cryptography cool i mean nowadays recursive snarks you can actually see them very much in the wild too like i believe filecoin is using recursive snarks mina is built around this concept of recursive snarks are those the same kinds of versions of what you had been working on or did you see like people kind of working on this in parallel or is this really kind of like

your work would have been the foundation for some of this stuff yeah well the basic definitions such as uh what is proof carrying data mostly remain the same even articulating what is the goal of what you get once you recurse a snark it's actually not so simple once you see it then then make sense that's proof current data the techniques to achieve procuring data have evolved as it should be the case and even and it's not just in practice even let's say from a theoretical cryptography standpoint what kind of primitives suffice to imply proof current data has become weaker and weaker for example maybe back in the day in order to build proof current data you would need what we would call a fully succinct snark so a snark that to when proving the correct computation of machine running time t the verifier will

run in time polylog t with no pre-processing no nothing just like that that was the first instantiation of proof current data but with time we've been able to relax some of these requirements by having a more sophisticated and careful construction so for example the first relaxation was from poly logarithmic verifier to merely sublinear okay and that was not clear a priority would be enough okay another relaxation was saying well maybe we're not going to have a fully succinct snark we're going to rely on pre-processing of circuits that's something that wasn't considered in the beginning but later because in practice the first snarks to be practical were the ones with pre-processing we had to understand how to do recursion with pre-processing so that was something that was understood first in theory and then in practice

and perhaps most recently there was uh this line of work uh starting uh with halo and then accumulation schemes where even the fact that the verifier needs to be sublinear was removed and now we can do recursion even with a linear time verifier but there's no compression okay but somehow there is so-called accumulation that you're never really compressing anything you're just uh batching multiple statement into one new statement and then in the end you will have some verification check that is not smaller than any given node is the size of each of the nodes you had along the way but that's fine because you have it at the end and at least you're not paying for the length of the chain for instance [Music] that halo case this is actually something i wanted to talk to you about this interaction between industry and

academia so halo came out of the zcash engineering group i think they were trying to solve like a very problem right in front of them they used engineering techniques and then i know that there was a paper published that you're a co-author on this proof carrying data without succinct arguments and i know that this came out i think i mean we published in the zk mesh back in february and i know that like when that came out it was like the formalization of what halo had done and yeah this was kind of this interesting moment where you saw like a company or like an industry kind of like propose something and then academia formalize it do you see that happening a lot or do you feel like most of the time it's the other way well it's a ping-pong so it goes through cycles perhaps another maybe perhaps

even more serious interaction that impacted a lot my research program was when we were collaborating with the electric coin company team to deploy zcash it became clear that uh these trusted setups in the real world especially the ones old style that were circuit specific and not updatable were really really difficult to deploy and this is not at all clear like with my sort of say classical cryptographic training as a graduate student initially having a common reference string or a structural reference string how it's called today was a normal thing that nobody would worry about okay it was like a normal setting but once you were confronted with uh realizing this in a

peer-to-peer setting it became this was a major issue and so to me it made me and my colleagues are very interested in trying to address this so this was for example a direct motivation for a paper that was written for a tailored multi-party computation protocol to sample the reference string for zcash this was the paper that was then sort of the basis for the protocol that was actually run that was further developed and designed i think by sean andera and then run in the real world but more than that i sort of rekindled my interest into snargs based on almost nothing let's say random functions that have this bare bones uh setup is just like a strong

cryptographic hash function and in some sense the birth of interactive oracle proofs was a i view it in my mind as some side effect of the struggles of dealing with reference strings i was personally motivated and i believe some of my colleagues were as well to kind of go back to these what were unfortunately very expensive constructions and what could we do about it and somehow we found this way of saying wait what if we instead of building pcps we build pcps across multiple rounds and this led to the idea of an interactive oracle proof which ultimately in a span of five years from formulating the notion of an iop and then lots of research on iops has led to what are now quite efficient snarks that not really rely on any structure reference string all you need is a hash function

to me that was it would not have happened or at least i don't believe i would have worked as hard on the direction of iops if i hadn't experienced and seen how ecc had to overcome this huge barrier of reference frame very much of a motivator can you give me a little bit of an example of an interactive oracle proof version like do you still need a trusted setup but they're just way way more efficient or is this the replacement for a trusted setup when you say that an interactive oracle proof is the probabilistic proof that is used inside certain types of snarks all snarks must have a trusted setup there do not exist snarks without setup so we can only talk about the colors of setups some colors are nicer than others okay the best you can hope for is just a little bit of randomness in the sky

right just uh say a hundred random beats or 500 random beats that we can all agree upon where random for example you could pick the first so many digits of pi and call that you know randomness this is very easy to agree upon it and deploy it and such types of snarks arise from using the random oracle model to compile either pcps or iops which are a transition of that okay so this is the most desirable type of setup because there is no certain way to run right i mean yeah you could run a coin tossing protocol but nobody's gonna do that okay what you're really going to do instead is say i don't know sha of i don't know alessandro that we're going to give you some output and that's you

know random looking enough and nobody's going to think that alessandro as a byte string holds a trapdoor for sha so that it creates some uh weird looking random string that then the snark will will be broken under right i see so what you're saying is like there is always a trusted setup but like the trusted setup using iops is almost like it can actually be more safely run by an org it doesn't necessarily have to do the multi-party computation with all these different participants right iop based snarks right because like a pcp is just some some idealized information authentic model you cannot really use it i wish we could but we can't because the verifier needs to do things that it cannot do in the real world then use cryptography to kind of implement what the verifier should have had to do you

implement it using the random oracle and in the real world around the miracle is just something like chat with d6 and so as long as we agree that we're all going to use shadow 56 that is the setup right it's much easier to agree on the hash function than it is to agree on i don't know like a bunch of powers of some group element that have some structure right so can you give me some examples of protocols that maybe have been proposed that are iop based snarks like would marlin go in under this or fractal one of them yes and the other one fractal yes marlon no i think so marlin uses something that is called a algebraic or polynomial iop is essentially it is an iop where we give a little bit of extra power to the verifier that rather than accessing let's say strings by querying locations it accesses polynomials by

querying their values so unfortunately we don't know how to compile let's say in a practically interesting way polynomial iops into snarks by just using hash functions okay we know how to do it using say groups of an order but i'm not going to get into the difficulties of practical aspects of them so instead what we do is we use things like pairing or groups primordial groups where the discrete logarithm is hard to compile them and so that's what marlin is okay in fractal it is actually based on an iop okay it is a pre-processing snark for r1cs that is obtained by taking an iop for r1cs and compiling it with hash functions okay so that one is uh it's not used in practice i think it's a very nice purple it does what it's

supposed to do which is uh like a pre-processing snack from one cs but perhaps more familiar to the audience will be systems deployed by starkware so cryptographic proofs are snarks that are obtained from some type of iop rather the aop being 401cs it is for another language called air algebraic intermediate representation which is you can think about it some sort of algebraic machine so there's no pre-processing there there is some sort of uniform model of computation that looks like some algebraic machine so these things are practical they're running they've been running on ethereum mainnet for now maybe a couple of years and that's one of the nice things in that commercialization effort there wasn't an issue about how you deploy the setup well we just have to decide what the

hash function is and that's it so we just mentioned a number of works from student of yours these are the kinds of works and research papers that i sort of mentioned earlier in the show but can we talk a little bit about who some of those researchers are and the type of projects and even like full-fledged protocols that have come out of the work that you've been doing because i think what's interesting also to our audience is we've featured a lot of people who have gone through your lab on this show and so it might be cool to make those links i have some projects that i very much enjoyed uh working on one of them for sure is uh abrara this is a project uh with several of my students first one is a long time collaborator of mine eli ben sasson

which should be familiar to everyone in the audience as well as mikhail yapzev who was a student of elementary son also co-founder of star queer and then nick spooner a former student of mine madison collaborator of mine from my mit days and nicolas ward also another former student of mine and what was very cool about this project is that when we formulated the notion of iops at the time we didn't really have very interesting iop examples and and at some point we started thinking we were able to design some interesting iops where primarily they were for a machine computations and the problem with machine computations is at the time we didn't really have very good ways to encode interesting problems that people would

care about such as at the time that maybe the example was the zcash circuit right as a machine computation just doesn't look like that there's like a it really is more of a circuit computation okay and we did not have very good techniques for coming up with practically relevant iops for circuit like computations and at least in my mind the aurora paper was the first one we were able to say okay here's a instance of our one cs and we have like a direct protocol for it that we were able to implement and get some reasonable efficiency for and uh one of the things that we came up with in the protocol was this univariate sum check okay which was solving the problem of uh how to convince a verifier that a polynomial sums over

a b domain to a certain claim sum even though the polynomial has one variable unlike the multivariate sum check well known from the 80s and this univariate sum check was the sort of let's say the main engine of practicality inside aurora and it was later used in many other protocols thereafter both fractal and marlin ended up using it and so it taught us a lot even though aurora itself a view aurora is an example of a theoretical exploration that actually did have some practical implementation but it was not quite practical enough for usage for example the verifier was not sublinear had a linear time verifier so it was not a pre-processing snark but the techniques that we had to come up with to design an iop for r1cs were later

very influential in many of the other works that we did in the research group i was at the time very very excited i felt like we finally were putting our hands on techniques that uh were going to be useful uh later on i mean recently we did a study club on some work you did with some checks was that in any way like coming out of this original research was that like the formalization of some part of it actually it's unrelated but i can talk about that because maybe it is interesting so pattern match in here some check like techniques play um unreasonably large role in the design of snarks primarily because snarks contain probabilistic proofs there are ways to formalize the statement and so and in some check protocols play an important role in probabilistic groups

so that's that's why they show up and broadly speaking what you do as a sum check how you design a subject protocol depends on whether you're tackling you want to do the subject for a multivariate polynomial or a univariate polynomial for the multivariate polynomial we have an answer already from the 80s and for univariate polynomial we had this univariate sum check and uh we were interested in univariate techniques because primarily of fry right fry is a low degree testing protocol for inverted polynomials is very practical that's why in aurora we were focusing on that right now you're mentioning a recent work that i'm actually very excited about and it came about from a quite different motivation and it has to do with a work that i was not involved in which is the design of bulletproofs

bulletproofs is a logarithmic communication argument system with a linear time verifier also linear time improver based on discrete logarithms it's a very influential work it's a range proofs based on bullet proofs for example using monero and i was personally quite interested in that protocol because unlike most other snark constructions out there it does not prominently display an inner probabilistic proof compiled into an extent argument okay there are some ways to maybe force it out but it feels unnatural and at least i think that one of the difficulties of coming up with uh maybe post-quantum versions of bulletproofs

were directly related to the fact that maybe we didn't quite fully understand uh bulletproofs and in a in a recent work with uh two postdocs uh a former postdoc of mine jonathan bootl who is also co-author of bulletproofs and katerina sotiraki uh who is a currently a postdoc at uc berkeley formerly as a student at mit with vinod vaquentanatan we were very interested in designing a post-quantum analog of bulletproofs and the way we went about trying to tackle that rather than trying to directly design some lattice-based protocol we went back and tried to understand what was really going on in bulletproofs and we made some what i think is a very exciting sort of finding which actually when can view in retrospect bulletproofs

literally the subject protocol run on a cryptographically hard group with some consistency check at the end and you can actually like phrase it like that okay and it was just a soundcheck in disguise that interestingly was not run on the usual domains like finite fields but on in some basically rings okay by sort of understanding the protocol at a higher level abstraction we were able to basically push it at a high enough abstraction layer that then we could then instantiate it with completely different domains polynomial rings where there are hardness assumptions on lattices for example a short integer solution problem is hard okay i think all of us on the paper were very happy about this discovery or invention because it

somehow helped us explain in a coherent way like a long line of works that was working on bulletproof style protocols making all kinds of observations that were also shared by some check-based protocols they were talking about space efficiency or ram around soundness and all these things that bulletproof style protocols were having also some checkpoints have but there was no real reason there's no clear reason why they both have these properties now there is one now you know that's so cool actually yeah so we did a study club on that i'll add the link in the show notes so that anyone can like dig in deeper to this particular problem i do want to go back to maybe some other projects that came out of the lab that you would like to highlight because i know you had a couple in mind i'd like

to maybe spend a little bit of time to talk about what i consider to be the simplest snarks those are snarks built just from random oracles i have a little question because you're saying the word snarg and not snark i wanted to make a quick distinction there because i know like in a lot of your work you are using this snark so it's s-n-a-r-g well first i'm not being careful in this discussion when i'm being careful the g simply means that i'm not highlighting the proof knowledge property and the k means that for whatever reason i'm trying to highlight the proof knowledge property but please don't pay attention to the difference in this uh sort of high-level discussion i may be saying snark or snark okay um yeah it's interchangeable yes for a technical perspective it specifically means whether you require proof of knowledge or not got it so this

goes back to snargs with let's say the simplest types of setups just a hash function right so i find these fascinating for multiple reasons first we will always have hash functions maybe 100 years from now 500 years from now a thousand years from now regardless of what happens with super computers or quantum computers or whatever computers it is likely we will always have hash functions that are sort of secure enough for doing uh hashing of things so you get random outputs okay it's not clear that the same will be true about the hardness of discrete logarithms the hardness of factoring problems about lattices hard problems about exogenous we don't know right there's structure in these problems due to geometry or number theory that can

be exploited by adversaries but hash functions is reasonable to believe will always have them so in some sense progress in snargs based on hash functions is i view it as most fundamental or at least in the sense that it will stick with us for the longest amount of time so the holy grail in some sense is understanding what is the best possible snark based on hash functions that we can obtain and if that snark based on the hash function is good enough for practice then we can actually make it part of digital infrastructure without worrying about whether we'll have to swap it out in the future or not okay and because you can actually study hash functions in this idealized model of random function that is a random oracle

we can actually make very precise questions about what is possible and not possible for such snugs and there is a line of work for example with a co-author elon you give who by the time this heirs might have already given a zika study club on this study club where we basically study the capabilities and limitations of these primitives for example we prove that any snarg in the random oracle model must have a verifier that makes more than a constant number of queries to the random oracle this in some sense is a barrier to recursion because whenever you recurse a snark you will have to express the verifier in terms of elementary gates to prove things about it right which means that

if you have many calls to the random oracle then you will pay more in the circuit of the verifier okay and so that's like a barrier that says there are limitations to how efficient these things can be for recursion a major open question that is i think one of my favorite questions right now is whether do there exist snargs in the random oracle model with linear size what do i mean linear size linear in the security parameter we do know that the answer is yes in other models for example based on discrete logarithms or based on pairings we essentially know that the answer is yes we have linear or nearly linear proof size that's also why in the real world they actually have smaller size because asymptotically we actually see that for example graph 16 has a constant number group elements those group elements have size that is a linear in security parameter

i mean you need to pick an embedding degree of the curve to be large enough but once you do that then it is linear and so and asymptotically instead the best snarks that we know today in the random world commodore are at least quadratic in fact the practical ones are closer to cubic that's why things based on random oracles have proof sizes that are more like tens of kilobytes rather than a few kilobytes that is exactly why is an example of that starks then they're quadratic or even cubic exactly they're at least quadratic and a little bit more than that because yeah there's other reasons and so that's why you you see this like maybe 30 kilobytes so 40 kilobytes rather than 2 kilobytes okay like once you have ironed out your concretely efficient

constructions the asymptotics speak and you will feel them in the real world okay and so there's a fundamental question is it possible let's say to have maybe a long time from now a one kilobyte stark right wow that question is basically in some sense are there snarks in the runway model with linear size and kind of the common belief is that because you have to ask many queries to the iop and each query needs to be certified by a path in the merkle tree used to commit to the oracles there is an inherent quadratic barrier because you have to ask security parameter number of queries and each query is certified by a digest that is at least size of the security parameter you're going to get

security parameters squared okay and a recent work with elon yogev the work that he will talk about or will have talked about in the zika study club we're able to construct a snark that has a sub quadratic size slightly subquadratic it's not linear and we just don't know what the right answer is like we broken the quadratic barrier so some of the common belief that quadratic is inherent is not the right answer we have something slightly sub-quadratic um and the jury is out about whether this strange expression that we obtain is actually the right one or one can do even better and obtain linear and i think it's a beautiful open question and uh somehow any progress in this direction will be in some sense eternal

like it we will always have hash functions and any further understanding we have will benefit us forever what is the name of this work just for reference point for anyone listening sure this work appears in crypto this year and the title is subquadratic snargs in the random oracle model perfect cool and we remain very interested in this question and we'll keep thinking about ways to either prove that there is some inherent superlinear lower bound on the size of arguments in the random work model or we can improve uh the the upper bound with like better constructions and right now we don't know this kind of goes to the question of like how you're picking what you're doing but do you look at a protocol and then like there's pieces of it and you start to optimize or think about specific pieces is it more like you're starting with a

clean slate and you're trying to kind of build something brand new i'm just curious like how you approach some of these problems uh well definitely not a clean slate that would be that would be suicidal i think a common theme that uh i use for myself and i try to i think it's a powerful theme when i try to teach to younger co-authors is modularity and deep understanding so just the fact that you have a protocol you can prove secure and is doing something interesting does not mean you're done if you just try to digest it and understand where does it come from why does it exist you will understand that actually it is not just some isolate or some cool hack from a prior protocol if you're actually doing something interesting there are

going to be deeper reasons for why that exists and time and again in research that i've done with colleagues it has always always been the case that when you try to understand something better you are actually making like making more problems for yourself or no no like you're not making you're actually simplifying like it gives you a better platform to then make further understanding later and also sometimes you thought you were solving a problem and you did but by understanding it better you actually solve the problem more maybe like you understand that uh actually achieve more than what you thought or maybe that there is some beautiful connection with another line of work and by understanding that connection you are able to import more techniques maybe not in the same paper

necessarily but in following one right and so this uh keeping like yourself to a high bar of not just saying do i have a theorem that i can prove but do i understand where the theorem comes from why does it exist all these kind of sanity checks and the sort of introspection of why is the word like that is has been enormously helpful into making sure that not only we're making progress but making progress on the hardest and most fundamental questions as opposed to i don't know just random optimizations which are useful they can be useful for all kinds of things but are not necessarily going to propel you forward into tackling the hard questions right so the hard questions will be

we will win over them only for deep understanding okay cool i'll mention another beautiful open problem about snargs in the random oracle model and that has to do with constructing snarks that are so called complexity preserving so let me explain the term complexity preserving is a notion that actually introduced with uh old collaborator of mine near bitansky many years ago and it says suppose that you want to prove some computation that runs in time t and space s okay ideally you would like the prover that is proving this computation to running time and space that are close to that okay what typically people do in snarks is to say no no like we want the time to be close and then we sacrifice space so for example anytime you use an fft fast for

a transformer your space efficiency may go out the window because you will have to write everything down and then compute on it and so if your algorithm was running in a small space i mean the computation you were proving was running a small space then you've lost that so how can you do that and about 10 years ago we showed the first construction that satisfies this property not practical at all it was using fully homomorphic encryption and multiple interactive proofs it was even private coin not even publicly verifiable but since then there's been a few more works that have made progress on that reducing the hardness assumptions so we know how to construct this under like nice cryptographic assumptions improving on the fact that it was only private coin now we know how to do the public coin okay but in some sense the hardest setting of

all remains to be where you have nothing but a random function and there the problem remains open so we don't know whether you know we have good snarks there's time and space efficient or complexity preserving in the random oracle model and the reason is that we don't have iops with that property if we did we could have them and so that's like a fundamental question about iops that remains open uh it's a beautiful question is this a trade-off that you're describing though this idea of time versus space like if it's longer time would the space actually be smaller or is it like always quicktime big space ideally you would like to preserve both and say that whatever was the time and space of the original computation you want the prover proving it

to run in time that is very close to that so for example if the time was t and the space was s then you want the approver of that computation to run in time say order of t and space order of s like roughly that now one could consider of course relaxations of this ideal goal and say all right we don't know how to do that let's maybe play some trade-offs and you might take a hit in your running time in order to preserve space and in fact that's roughly what is true today we have constructions that are either linear time but large space or slightly more than linear time in good space and that's the trade-off that we have today but we don't know how to achieve it together even outside the random oracle model okay but the work that you just recently did does that address this question or is that more

like this is a question that arose because of the work that you did and you realize that this isn't something that's quite solved yet this is moving on a different uh before i was focusing on the size of the argument right in the random oracle model whereas here we are specifically asking well get me some decent proof size maybe it's going to be i don't know cubic in the security parameter like something succinct but the emphasis is on the prover resources and why because time and space they both matter okay so you cannot scale a snark to large computations if you have large memory constraints because you get stuck conversely if you have good memory like space complexity preservation but your prover time sucks then you're gonna have to

wait too long okay and both of these are limitations in the real world in one way or the other they come up and they impose sort of issues on real world systems you can try to mitigate them with systems techniques for example one work that i can mention is dizik from quite a few years back this was with uh howard now atalayo wenting she is now professor at cmu reluca and john there we were exploring how to scale up snarks by spreading the prover computation on a cluster right but the fact that it can be done doesn't mean it's easy and convenient and the reason why we had to do it is because if you want to scale up a snark you just run into memory constraints and there's just no computer that has so much memory and you have to put together a bunch of computers that

collectively have enough memory but now you have to manage the distribution or computation guiding the results to produce the final snark ideally if your original computation did not have such large memory footprint you wouldn't want the prover to have such a large memory footprint either yeah do you think all of these things are possible or do you think there will be a point where like you just get the closest approximation to what you want it was almost like can you hit that equals two or is that just like that's the goal we're going to try to like optimize until we get close enough yeah look i don't know i've definitely had wrong intuitions before there was a period a few years ago where i was just not convinced that there exists a linear time iops it just looked like ffts are they are to stay they were like in the way of

everything just wasn't clear what to do if you're not running an fft on a computation and it just looked like all right well i guess we don't have linear time iops but things changed there was a very nice work in asiacrypt 2017 by you know several people including a former postdoc of mine jonathan bhutto uh that showed a linear time iop with square root time verifier so not really like fully succinct but you know showing that you could do something that is towards the direction and then in a paper with jonathan and jens grot a couple of years ago we were able to bring this down from square root to any root so like cube root or fourth root or and more recently we were able to get poliogarithmic so now we have a linear time iop with poliography

verification at least for computations that are algebraic over large fields the question for boolean computations is still open this was something that i did not have the intuition was possible but somehow in the end we do have a good understanding why they're possible so these things have happened several times in my career and at this point mostly i suspend my judgment i just try to follow what seemed to be the most interesting leads for a positive or negative result sometimes it's a negative result like with the paper with a loan proving lower bounds on the complexity of the verifier in snarks in the random record model that was bad news okay but uh sort of gathering intuition from the is it a

negative result or is it a positive result is actually useful back and forth okay because uh if you get stuck proving negative results that may give you like a possible progress or attack or approach on the positive side and vice versa if you can really get stuck on a positive result then you might be able to somehow formulate a barrier that says as long as you will use these techniques or this approach you cannot do better than that right so it's a very useful research trick or strategy yeah it's almost like you're framing like known possibilities but like they don't work together yet but this is a space that could be developed like we know we can do this in this context over here can we bring that into the context that we're trying to solve in i'll finally mention maybe two works

that are not about constructing new protocols rather they're about proving existing protocols let's say more secure and specifically having to do with quantum attackers quantum adversaries and here snargs based on hash functions were have been widely believed to be post quantum in some way because if the hash function is post quantum why shouldn't the whole protocol be post quantum given that is the only cryptography that comes into the protocol and i will not talk much about these but i'll just mention that over the past few years there has been nice progress into formally understanding the post-quantum security of these protocols into two settings one is a paper from two years ago it's called succinct

arguments in the quantum random oracle model this was a with uh two students uh peter manohar and now at cmu and nick spooner where we were able to prove that uh constructions in the random oracle model based on pcps and iops for example the ones used in starquar are formally secure in the quantum random oracle model which is a the model where attackers can query the random function in superposition and so now we know that gives us much stronger evidence that yes the intuition of post-quantum security of these protocols really is there and more recently there's a paper with uh fermima who is now a postdoc at simon's institute at uc berkeley again nick spooner and mark gendry where we studied the so this is not in a idealized model this

is like a sort of what cryptographers call the plane model so it's a interactive succinct argument this is called killian's protocol where you compile a pcp using a collision recent hash function into a for message public coin succinct argument the classical proof of security involves rewinding the adversary but rewinding is difficult with quantum adversaries because when you start going back and forth and measuring then the adversary notices that he is leaving uh in a security reduction rather than wherever he was living and then he stops working okay and in this work with lots of hard work by the the two students fermi and nick that really did a fantastic job they developed new techniques for rewinding quantum

algorithms and now we do understand that uh also in this interactive setting from plane collision resistant hash functions or in quantum these are things are called collapse binding hash functions we do understand post quantum security and this is a long standing open problem and so this is basically with time we are obtaining better and better foundations not just for now but you know for the long term security of these uh snarks which are more and more part of digital infrastructure and we need them to not just be yeah it looks secure or yeah i proved to secure classically but it should be postcondom security we really need to go through and put all the bricks of all the foundations uh because if they're here to stay for a long time especially the ones

based on hash function they will be with us for all i know for hundreds of years we need them to be like really understood yeah so i will not say more if you're interested in the postcolumn security and those are two works that you can look into cool this actually leads us a little bit into a topic that i wanted to talk about with you and that is teaching all of this stuff teaching snarks teaching zero knowledge techniques and like basically breaking down these systems to be learned and understood you just mentioned like you know there's certain things like hash functions you can assume will be with us for a long time but then there's also other techniques that are kind of like they come they might not be used they might be found to be less efficient how does that impact the way you teach like how can you create

a syllabus or like maybe an online course that you hope would like last the test of time if this is changing so quickly yeah these are complex problems there are various things to say here first uh snarks are a rather technical area in the sense that they involve knowledge that touches upon computational complexity cryptography and possibly also applied cryptography so like sort of an understanding of how algorithms such as multi-scale multiplication or fast-forward transforms or other things perform in the real world on and so because it touches on so many areas it's a bit of a challenge to train students and sort of bring in talent uh who is in principle interested to understand this area but

then needs to be somewhat initiated and so in my own uh experience as a professor i'm also an as an educator both of uh my own students in the group and more broadly like in classes i've been confronted with this problem very much directly in particular when i started as a professor it was this tailored training where i would talk about what i know to students in my office and then if a new student would come i would have to say that again and it would be like a very time consuming process for students and for me to communicate this knowledge over time it has gotten better i've had sort of several efforts in this direction one effort that has i think come a long way is to basically take the part of snarks that

only has to do with computational complexity so that is designing probabilistic proofs i view it in my opinion as the technically most complex part and designing a course around it this is a course that i've taught now three times in semester courses and a fourth time in a summer school and i've been trying to digest and reorganize a mix of foundational techniques and modern protocols by trying to select for the ideas that seem to be most useful most productive most flexible and leaving out maybe ideas that they were maybe useful and led to nice papers but did not seem as impactful okay and uh what gets selected and how does it get organized

it's uh mostly a question of experience and having an understanding of what's more foundation and what's less foundational and um yeah it's challenging but we've come a long way so now for example if you're interested in understanding holistic proofs there is almost a course that is on autopilot that you can run i guess anna will put an in the description a link to this summer school from this past july where there are 20 lectures with 20 problem sets that will teach you about interactive proofs pcps and iops or at least what i consider to be the most foundational techniques and ideas for having a precise and deep understanding of this area now there's probably another 10 or 20 lectures on top of those that one could put with other very

useful things but not much more so this really does cover a lot and i think so we had 75 students this past summer so the process of training and taking into this area new talent uh not just from cryptography but also from complexity or mathematics has become a lot more attractable and i think we're going to see sort of an influx not just thanks to this but also thanks to this of talent who is able to design uh probabilistic proofs that are sort of high quality with tackling difficult questions and it would really would not have been possible otherwise because there's only so many experts they have so much uh advising bandwidth and it doesn't scale but uh i think that

sort of having precise deep and technical courses that are not trying to cover everything like this course does not talk about all of the whole scenarios landscape but specifically a coherent set of materials that does not require too much background heuristic proofs does not require any cryptographic background will help with this periodical problem for sure but like you sort of mention here you're tackling one part of a snark because that's the part that you feel could be described as foundational what about all of the other stuff like the things that are moving quickly how does one get into that i mean we've had that question come up a number of times in our channels people just being like they are technical they want to jump in they don't know exactly where to start it sounds like your course would be a great

place to start but once they do that like how do they then understand the other parts that are changing well the rest is a work in progress in a sense that it is uh working progress by researchers because they are changing but doesn't mean that there will be always changing right so more and more territories of the snark landscape will become well understood over time so that's one aspect and the other working progress is that more pedagogical resources will become available for example justin tyler has a wonderful a monograph that covers both snark compilers and a little bit of holistic proofs so i don't cover anything in my course about cryptography i just touch upon killian's protocol and

using hash functions but i don't talk about bulletproofs i don't talk about sort of how you compile linear pcps into pre-processing snarbs because that would require in the course bringing in or teaching about cryptographic background but justin has done a wonderful job assembling an extensive monograph that will help people to understand that the other parts are not covered and over time this work in progress will mean that experts might be finding opportunities to systematize digest and represent other pieces necessary for a full understanding of this area and it will get better and better now yeah so but there's no i would say there's no easy silver bullet here in the sense that the research is still very active so it's not like people are saying well

you know we got all the low hanging medium hanging fruits let's just go and write books and tutorials because there's nothing better to do in my research group we have plenty of exciting things we're always working on and it seems that just they keep coming and so the resources towards pedagogy are more an active effort but they're not like the the majority of one's time because you know that's how it is i feel like this thinking though intersects with the idea of standards like zk standards standardization sort of like decisions that like this is what is going to be used for now maybe that is more on the implementation side of things but i know that there's a group like zk proofs they do workshops

and they actually focus on standards and i did wonder from where you're sitting like what do you make of standardization bodies do you feel like those are good for research bad for research like yeah how would you like do you want standards does that even factor in i think standards are wonderful but they're more for industry right so i i wouldn't say that uh from a research perspective they carry like a large um sort of uh impact and you can see this also forgets you know standards for encryption standards for digital signature they're not so much about sort of making the life of researchers easier rather it is more about coming up with the references that practitioners can look up and not have to directly consult with experts of the area right

and similarly for pedagogy sometimes getting certain ideas across is not about what is the most efficient protocol but rather what is the simplest protocol that captures the use of that idea to achieve a certain goal and that helps you understand what is the power of that idea okay and so then you feel it and you're able to use it in other places for example you may be able to effectively use it to design practically efficient protocols so in pedagogical resources there is more of a push towards examples that illustrate challenges and how you overcome them with specific ideas okay but then those have to be presented in sort of the cleanest most uh sort of uh unconcerned place

right you shouldn't have to worry about other issues like how are you gonna implement it you know how is it gonna be efficient because you're trying to get across the power of a certain tool or what is a certain definition about uh about and how to understand it so and uh for researchers and even practitioners before they get to implementing they want to understand what they're operating with what they're working with that's what you want right so that's pedagogy is about digesting re-digesting re-digesting or digesting until it kind of explains itself right so um like for example things that are topics in undergraduate textbooks for standard courses are there because they've been digested

a million times and there are very effective ways to understand and motivate them and explain them to the point that people in their second and third year university can absorb them it does not mean they were always like that they were potentially much more complicated and better in not clear settings maybe with additional bells and whistles that turned out they were not so important in the end but it was a core idea that was much simpler so something like that has to happen for snarks to create some sort of syllabus that will be widely accessible and what i've been trying to do with this course on probabilistic proofs is doing that thing not for snarks but specifically for probabilistic roofs where snargs are one of the major applications and the course has gone through various iterations and at least

i've learned a lot about what works and what doesn't work what is core material and what is less core material so i yeah that's a bit different than standards one kind of last question that i have for you is what is your motivation in doing this like what is the thing about teaching maybe specifically this that excites you yeah i would say impact on students so i think that these topics around the succinct arguments and the prollistic proofs are beautiful they're powerful they're challenging and there's lots of talent out in the world and if i can improve the mechanisms and materials that bring in more talent more people to think about these questions

and catalyze faster progress in this area to maybe answer open questions earlier than later to then cause more technology transfer of these ideas um maybe even far beyond blockchains so this impact i find it exciting and i cannot do it alone i need the brilliant collaborators but the brilliant collaborators you know have to be interested in this and know about the topic and so through the teaching and education i can affect change onto others with respect to these topics is it partly that like there are things that you just want to know are you looking at like these are these unknowns that you just want to eventually know the answer to or see something like in a direction or is there any sort of like other maybe outside of math

uh reason that you that you want to see more development in this space well so on the research side yes there's lots of questions that i would like to know the answer of you know very visually because they're very exciting but i mean i think i step back these topics i find them exciting because they're just the goals that are achieved are magical so many people are attracted to cryptography because it's kind of in some sense magic right you're able to do all this crazy sounding uh goals like zero knowledge or exponentially fast verification secure computation obfuscation all of these capture the imagination of people they're evocative and you want to know how to do them in my particular case i find

this exponential speed up in verification or computation to be you know it's beautiful and awesome yeah it's awesome and it's also powerful like you can actually do you don't have to come up with uh convoluted fairy tales about how it's useful in real world it's just useful like in fact it's not just useful it's directly thoroughly needed okay and what's exciting here is that somehow making progress on this topic brings you back to basic mathematical questions in computational complexity property testing and cryptography and now you have this leverage this powerful leverage that theoretical ideas can push boundaries not of knowledge but of technology so

and it is something that you sometimes read about and you see in movies maybe but you never really feel but when you feel it on your skin and you see the power that foundational progress brings to technology later then this is definitely inability right and uh so yeah to me that's a strong motivation when i talk to students especially young ones i tell them you know there's an infinitude of well-posed mathematical questions that one can work on it it does not mean that one should work on any one of them because some of them are silly or just i don't know i mean they're well posed but just why are you wasting your time on it right so given the limited amount of time that we

all have i would rather spend it on questions that i find interesting and i think that are impactful do you ever have any concerns about some of the like cryptography like would you ever be worried about something you built being used for bad does that ever come into your mind kind of from the research side yeah it's not like uh i'll make an analogy right so people always say oh a knife right you can use it to you know cut vegetables or people right but i think the analogy here is more about the raw materials for protocols right so maybe the wood that makes up the knife or the steel that makes up the knife so snarks are so foundational that you know they are currently being used in certain protocols but i think eventually will be used in all kinds of settings and they're such a basic building block that uh

at least the way i feel it in my mind is just so foundational that i don't really come up with considerations that sort very different is to say if you start designing protocols that are achieving specific things for example there are legitimate questions to be raised about uh say private peer-to-peer payments like a zero cash protocol right and so then the the way to address them is to say well you know maybe we should have some programmability that you know introduces some accountability into the system and for such types of directions then it becomes uh i think a bit more subtle you know still proponent of privacy and the fact that you start with privacy and then you build an accountability rather than you start surveillance i'll take always the trade-off uh more

on the um sort of on that side but uh when you're not really building protocols for specific security goals of like real world protocols but basic cryptographic primitives then uh um yeah it's not not something i really think about much do you think there are real opportunities for zero knowledge proofs to live i mean this show and a lot of the kind of community and everything we tend to focus on the blockchain applications of zero knowledge like it's always in that intersection almost always i think i only have like one or two examples outside of it but are you also looking towards or working towards non-blockchain zero knowledge and maybe it's so foundational that you can't say like it could be used for blockchain or

not blockchain i don't know i think it's too early to tell i mean so look in principle i am convinced that uh zero knowledge proofs and succinct arguments will find plenty of applications beyond blockchain now what are those i don't know yet i guess if i knew maybe i would grab a few friends and start a company direction but also you know um technology moves slow which whatever we think of it it usually does move slow uh especially when it's existing industries right so still uh snarks are not that old uh like uh i'm not old and i've been working in stuff but they've been there yeah they've been worked on right so

it will take more time there are companies that tried to explore the direction but uh you know it goes slow and then when you have the opportunity cost of saying you could invest as a startup energy in the blockchain space and have a much shorter time to market and and and these interesting funding mechanisms yeah right as opposed to something more traditional longer term right maybe it even was going to work out but simply the fact that you had a choice means that the development of a technology in the more traditional world will be delayed by the fact that there is a greater opportunity potential in the blockchain space right now but over time i think this will kind of i don't know if it will correct itself

but just like through the statistics and the serendipity more applications will come up very cool so i am absolutely positive that they will i don't know exactly when and in what form nice ali thank you so much for coming back on the show yeah no thank you so much it was lovely to be back it's always a lot of fun to chitchat about snarks with you and there's plenty of things that we could have talked and we didn't have time but for the audience if they're interested to follow more of the research coming out of um research group then you can sort of google my name and find my webpage it's usually up to date in terms of recent papers you can also look up the summer school and the videos and problem sets there and

i continue to the research and some of my students have graduated and as always i'm looking for strong and brilliant students and postdocs who may be also interested in probabilistic proofs and succinct arguments so if you're interested to talk about opportunities to work with me i can hire you if there's a good match so write me an email and you can find the email on my webpage very cool all right so i want to say thank you to the podcast editor henrik the podcast producer tanya and to our listeners thanks for listening