ZK and cryptography with Justin Thaler, Valeria Nikolaenko and Joseph Bonneau

Transcript

[Music] now I'd like um to introduce the cryptographic side of the research team and so the format will be similar for the for the first session um so let me just ask you know all of you just say a little bit about you know who you are and your background and sort of your interests and again maybe to to make just make concrete the kinds of work that you do um you know maybe both something on the research side that you know very Cutting Edge that you're super excited about could be your own research could be you know something that's just you think is amazing that's happening right now also maybe sort of a concrete sort of anecdote about how you've collaborated with some of our portfolio companies so Lara I'll start with you sure uh so I'm Lara Neno uh I am a cryptographer research

partner here on the team uh I did my PhD in cryptography then I was working for the DM blockchain a Libra blockchain at Facebook for three years as part of their research team and joined a6z two years ago um I wasn't into blockchain during my PhD I was doing MPC multiparty computation and postquantum cryptography and then I got into the blockchains at Facebook since then I mostly worked on threshold signatures um on data availability a little bit continue working on postquantum cryptography as well um everything cryptography excites me so if you have a cryptographic problem uh come talk to me yeah about research and most recent results there's always something exciting cryptography

just uh never boring um just maybe to name a couple that are kind of of general interest uh last August I think in crypto there was a paper suggesting a resolution to a paradox of black holes suggesting that uh they might use some cryptography and cryptography was actually like resolving this physical Paradox in the universe which was kind of mindblowing um that you know cryptographers think about problems you can look up the paper online it's kind of technical but Quant I think has a very nice article about that um just recently two weeks ago we had like a little panic in the

cryptographic community because uh somebody um Chen um put a paper on archive saying that lot is cryptog here's an algorithm Quantum algorithm polom time algorithm that breaks Lattis based cryptography and so Lattis based cryptography if you haven't heard of it is like this new uh very exciting topic it's um from people started looking it into it in 2005 but right now everybody uh is kind of Shifting towards using lates because of their postquantum security so people worry that when quantum computers get built you know they will be able to break our current cryptographic schemes so we won't be able to continue using them and lates kind of come to the

rescue those are the most performant uh schemes based on a US assumption and we don't know if it's uh we we conjectured that it's quantumly intractable and so this paper was saying oh no here's a Quantum algorithm to break those assumptions and everybody had a panic because uh you know people had been some of the phds dissertations were based on just working on lates along and but fortunately a couple couple days ago I think they found a bug in the paper and they don't know how to fix it so at the end there is no break but it was quite stressful a couple weeks um and uh yeah there are always new results uh even with simple schemes like thresold thres signatures like ecdsa

signature scheme that we all love uh to sign transactions for Bitcoin and ethereum has been around for a while and still there are new results uh coming every year on how to make it uh MPC friendly how to improve the algorithms um so you can split your uh key and uh use two devices or two people to cost sign the transaction um yeah so exciting field um on the portco side collaborations you know portfol companies always just show up with an interesting research problem that they can't find a solution for and we brainstorm together with them and sometimes that leads um to some results um sometimes we find an attack and they

kind of pivot and build some build protocol in a different way um optos recently launch a Randomness Beacon it's super exciting protocol that allows you to call a function from their smart contract get Randomness and then do something with it maybe select a winner for the lottery so they were designing a protocol for them for that getting our feedback and we were like oh here are a few problems and then they pivoted to more secure version so that's an example I'll pass it to Joe than okay hi everybody I'm Joe um so I work and applied crypto I did my PhD uh in crypto actually uh well up the up the road in Cambridge I was back there

yesterday which was kind of cool so it's good to be back in the UK um I actually it was interesting being back because it made me remember the being a research student when the Bitcoin paper came out and being assigned with like 24 hours notice to read the paper and present it to the group on a group meeting which only happened because the regularly scheduled speaker canceled and we needed replacement at the last minute so my supervisor was like Hey people keep asking about this Bitcoin thing I think it's BS but uh just read the paper and then tell us how it works so so yeah so so anyway so I've been you know working in crypto for about 10 years um I'm also a a professor at NYU

so I uh teach crypto I've taught a cryptocurrency class to undergrads um and grad students every year for the last nine years running now I think next year's going to be my first break from that um and my goal is to rewrite the textbook that we've been using so um hopefully that uh that project gets off the ground uh before coming to a16z I was working as an adviser to uh uh I guess four different companies I worked with aloran zcash Chia and uh Mina 01 Labs um and uh I think Tim said you know instead of like advising these companies here and there like come to a16z you can uh you know work with a hundred companies so uh so it's been

been really great okay I mean I I was this is what I thought Lara was going to talk about this FDX work that we've uh done recently Fair data exchange so that FTE may have sounded like I said something else but I didn't uh but the uh uh but yeah no it's it's it's really exciting like we uh wanted to I think it was a it was a great demonstration of the research team I think I mean Lara led the project um and but we had at least four different interns uh plus me working on it last summer um the result I think was a I think it turned into a much bigger engineering and research challenge than we thought it was but um the idea is that uh Bob has some data

you know Alice wants to pay for the data they want to do Fair exchange so you know Alice only gets the data if she pays and Bob is guaranteed to get paid if he gives up the data um so it's something that you know cryptographers have thought of for a really long time how to do Fair Exchange in general and there's some kind of old results that say um this is uh impossible in a certain setting um but with cryptocurrency with blockchains we can actually solve the problem um and we showed in this work you can actually solve it really efficiently where you only need to to put a constant amount of data on chain so you could potentially pay for a really large data file that could be gigabytes uh but you only need to post a small commitment on chain so

you can actually it and you can do it efficiently um so I think it was a really great example of the the kind of work that we do on the research team it's like a really practical problem um that maybe the broader you know uh cryptographic research Community was say like oh it's sort of solved in the 90s but they hadn't really thought about all the kind of complexities of doing it efficiently you know using modern cryptocurrency as the as the basis for the exchange um so yeah so really excited about that work it's online now portco interaction let's see uh well I've been working with a a portco called XMP that's doing uh secure messaging um you know uh using your uh

crypto wallet basically as your identity and that's been been really exciting because I worked on secure messaging for years with like with signal and uh with with WhatsApp and other U you know messaging tools um so it was really cool for me to sort of bridge the gap between those two um um and that interaction really took the place of me setting up like a monthly call for a while where they were defining their new um I mean they were basically taking a theoretically standard uh encryption protocol called MLS um but as always happens and this is I think a lot of our interactions take this shape U people find what seems like the solution to their problem that's written up in a white paper or exists in some form and

when they go to actually implement it they run into a ton of question questions and they find out the white paper is not fully specified it doesn't really say how to pick this parameter sometimes there's even you know bugs or mistakes that you know the original authors didn't really notice sometimes there was no implementation in the original project um so it's just a series of uh you know often like we would book calls for an hour and they would they would go overtime a bunch because there were so many little questions about like what should we pick for that parameter could we change this what would this mean so it was a really fun interaction just kind of geeking out over the details of uh implementing this new protocol MLS um which it turns out they might be one of the first teams that's actually

implementing this protocol um so that was a great collaboration uh so I'll pass to Justin thanks Joe hi I'm Justin I'm a professor at Georgetown and a research partner here in the research group at a6z my background is originally in like algorithms and complexity Theory um but I uh focus a lot on zero knowledge proofs and snarks so I've sort of picked up cryptography as needed to to work in that space so it's a little funny I'm like uh compared to Joe and lra like within cryptography I'm very very narrow very focused specifically on on zero knowledge uh but then I also do some stuff outside of cryptography um so both more narrow and and and Broad at the

same time so I mean one thing I'm excited about um is uh which which Eddie mentioned before is is this new jolt work uh which is sort of um largely developed internally it's a it's a new like general purpose proof system um which I think has a really nice combination of uh sort of friendliness to developers but also also performance um and I think uh like uh Michael Sam and Noah uh two of whom are are here this week um sort of went through the same process I had to over the years of uh picking up cryptography as they went to build in this space um and uh sort of remarkably quickly figuring out how to

do that um I I was just telling Noah sort of uh at some point people were going to call him a cryptographer and it actually be true um and we maybe already passed that that uh inflection point uh at this stage um so yeah I'm I'm excited about uh the development of of that system but more generally the techniques that underly it I've sort of been advocating for for uh many many years now and there's been some strange resistance I've never been been able to fully understand um disbelief that it's sort of the right techniques uh for performance and people are finally catching on um it's kind of my view they sort of don't have a choice anymore uh but to accept it uh so I'm excited to

see how how that progresses um in terms of I guess uh portfolio collaboration uh maybe I'll highlight um so I've worked with a company called Jensen actually since I my I my right when I started at the firm with as a visitor I guess two summers ago now um so I was uh every summer we run kind of an intensive research program we bring in a bunch of interns and faculty visitors and visitors from the industry as well so I was one of those first visitors and right around that time I just got a cold email from from a company called called Jensen which is sort of focused on uh building like a a decentralized version of like Amazon Cloud compute um particularly

focused on ML applications um and the gist was to get the um uh the guarantees they needed they they just could not pay a performance price uh that like existing general purpose uh snarks or ZK proofs um provided like you know they they could tolerate maybe uh 3x overhead and the existing snarks were 10 million x overhead or something like that um so their their only hope was they they sort of independently discovered um some of my early work on on these techniques that I've been advocating for sort of the the only hope to achieve this kind of performance um and then uh so I work with them um just sort of on a informal basis um for

several months and uh sort of by a happy coincidence like six months later they became a portfolio company and now I get to work with them much closer um and it turns out you know there's just like uh endless problems to solve given given their goals and the the snark problems are but one tiny part of the picture um there are a lot more problems with incentives and actually they probably uh work more closely right now with Prav and and Tim um since those problems are more urgent than than the snark ones um so uh one it's it's really cool just to you know work with people who have interesting problems in the space and then uh to you know welcome them to sort of the family and get to work even more closely with them um and to like to to

sort of see the whole system um and you know contribute to sort of a aspect very deeply but also get the big picture it's just endlessly exciting and interesting I should point out Jensen is one of our UK Investments as well um all right so one one broad I mean you know one thing I think cryptography uh is that's amazing about it is stuff starts as just you know Moon maath as they like to say just like really hard kind of abstract Theory and Mathematics and it's often the time scale of decades right by which that actually starts becoming practical right and you know snarks I think are a great example I mean for me the intellectual Heritage there is sort of back to like the PCP theorem which is literally one

of the deepest results in theoretical computer science now what sort of 32 years ago something like that um and lots of other examples of cryptography so you given that we're here with some people right at The Cutting Edge I'd love to hear some sort of predictions right so what are some you know to this point just theoretical constructs that you think might actually become kind of production ready in the next 5 years 10 years 15 years so this is to all of you as anyone who wants to jump in we definitely see a lot of progress in NPC in general purpose uh secure computation where there are multiple parties holding secrets and you want to compute on those secrets and function such that um every party holds the secrets to themselves

without telling any information about the secret to the others has tons of application outside of blockchain as well just from say Computing and medical data something that's uh very hard to share um tons of progress there um new papers every year so that's definitely moving to practice something I'm personally excited about but it's not yet practical as FH a fully homomorphic encryption when you encrypt something store it on the cloud and then the cloud can compute on it for you uh maybe that's your photos that you store encrypted and you do some pre-processing on the photos or that's your email and you do some filtering of those encrypted emails

stuff like that um we see uh surprisingly companies in companies that are trying to build production r f and um I think third thing I hope I'm not stealing from everybody third thing I want to mention is as6 and Hardware acceleration for different cryptographic Primitives that's kind of something new that will move a lot of cryptography into practice hopefully I'm I'm person person Al pretty excited about delay functions and hardware for computing them this is I've been working on this for almost 10 years now um I mean I guess the the concept of a vdf is about 5 years old now so my prediction is there will be widespread in another five

years because it's 10 years is kind of like the median time for cryptographic papers to become reality I think um but yeah really useful uh a way to sort of add a hard time delay between things that happen in any kind of uh protocol so you know we found uses for them and consensus protocols Randomness beacons auctions voting all sorts of things MPC in general actually I think vdfs can really help with so uh but they rely on Hardware um to really be practical as Lara mentioned so um yeah so I'm really excited uh to to see I think that's you know eventually the next step for reducing trust in a lot of a MPC and I well also since you brought it up

earlier I I think so this is is like probably the easiest way to nerd swipe a cryptographer right now is to ask if lce assumptions are going to survive um uh I don't think I think within five years there'll be I I think that we the bug in that paper will be fixed and there will be a way around it personally but yeah that's that's a pretty big open open question yeah um so of course my answer is uh is is snarks like ZK proof so I think they're pretty close to Crossing uh some kind of threshold uh where they're much more applicable and useful than before so uh for a long time I sort of had the very sort of grumpy view that um they weren't really progressing that much despite

popular perception um that basically people were running with uh suboptimal techniques and they were making the suboptimal techniques closer to what the optimal techniques could already achieve but weren't being developed um now I think uh people have con are starting to converge around the right Tech techniques and then I'm excited that those techniques are finally actually progressing further um and then I think uh the biggest issue with with snarks will become um that they're complicated protocols and full of bugs uh so I think we're crossing a performance threshold um and sort of a usability threshold um and then the the remaining barrier will just be that um they're not actually

secure because they're not implemented correctly um so my hope is that once we uh Converge on how to design secure and usable snarks then we can focus on um the kind of the grand effort of how to actually Implement them correctly and be confident we implemented them correctly because until we reach that point like the blockchain systems that use them they're not really secured by the snark because the snark is not secure it has bugs in it like they're really secured by the obscurity that only you know like 30 people in the world could hope to find the bugs and hopefully those people are not going to you know put on their black hat and sell the secret or exploit the secret or something like that so I'd like to get into a situation where the snark itself is securing the system and

not the fact that it's just takes a PhD to find the bug in the implementation or something plus some training wheels that people kind of build around their snarks today right that too so it's not okay it's not only secured by obscurity so there's also some training wheels although I think the training wheels uh are starting to come off and that's a little bit uh scary actually I mean if you haven't heard that ter I guess the terms different terms are sometimes used but there are a lot of systems today that are starting to have a snark that proves something but there's also a signature from one or more authorities that say that it's true and you sort of need both so if the snark falls apart because of some bug uh you know the the signature and that part of it's not red decentralized will still protect you and

they call it like you know training wheels until we can fully trust the snark I think we need a better term for this it's just permissioning really yeah well people don't like that term either I think maybe like belt and suspenders or something I want to open it for the group but before I do that I just want to get on the record Justin Lara's reactions to Joe's prediction that postquantum cryptography will be dead in five years well maybe not all of postquantum crypto but lattice based fa lce is I mean it's possible it will all disappear but no good point good point Lattis is specifically I mean you know that the like odad regab who's kind of like the the founder of the whole thing stopped working on it years ago but he he he thinks it's not going to last yeah

he's like my colleague at NYU I guess but he yeah I don't know so over under a five years for lates you take the over you take the under well I think um even if they're not post quantumly secure they're still the only assumption we know of how to build FH from yeah so fully homomorphic encryption everybody would love that and until we have quantum computers that will still make lates survive even if they're not postquantum heart I think it's unlikely that um we we're going to break them classically anytime soon because they um also have connections to uh coding Theory and um coding theorist have been thinking about similar

problems from their perspective for a long long time not much progress has been made so classically it seems like they're still in a good standing quantumly yeah this result kind of shaken it and Justin also mentions a lot of cryptographers now express some skepticism and said that they they've been doubting that lce is a quantumly secure pH I think that drag who kind of initiated this whole field started working it just trying to break them quantumly and that's what he was uh his his main motivation was first to like they must be quantumly easy so let me try to break them and he was not able to and that's how this whole field started um but I I think there's also value in

um you know when people think that something is easy it's very valuable property to have of an assumption because for example factoring right factoring is super easy to explain like um Elementary School student probably or middle school so it's very easy to think about this problem and when the problem is easy to think about you know more people will try um and try to break it so there is value in kind of thinking that the problem is quantumly easy so more people will try and come and break it and if they're not successful uh will have better Assurance rather than trying to break some complicated problem so I think even if people think that they're quantumly easy that might be a good thing actually um

Not a Bad Thing necessarily I mean I think that the recent paper is going to be a really good thing just because it's got It's going to get a lot more people to work on the problem and I think I mean sometimes some of the biggest problems in cryptography that you hear about like factoring discret log you'd assume that like most young cryptog grad students must try to work on that problem but I think it's sort of the opposite I think everyone assumes it's a hard problem and smarter people are working on it so it's not you know it's not worth like risking your whole PhD on something that is unlikely to work and I actually don't think there's a lot of people like people from a crypto angle really working on factoring today it's like one or two research groups and that's kind of about it so and I'm same

with I mean more people will work on Quantum algorithms for luses now which is a good thing yeah so I'm sort of have the same take as as Le and and Joe I guess I I I don't think I lates will hold up for postquantum security I think we'll find other reasons to like them for classical security um and in blockchain settings I don't really think postquantum security is super important I think the urgency with postquantum security is that you know nation states will just Hoover up all traffic and sit on it for 50 years until there is a quantum computer and then they'll decrypt the traffic and you know um you actually wanted to keep those uh messages secret for a century and that's so that's a problem whereas

in blockchains like once there's a quantum computer that might be used to break your blockchain application you like you know upgrade to something postquantum then except for privacy applications I mean yeah but for in for snarks you sort of we typically have unconditional privacy and it's sound um that uh is you know um based on cryptographic assumptions that quantum computers might invalidate um and so as long as you're confident that you know the the rollup you know produced a proof today um and there's no quantum computer today that that rollup had access to like it doesn't matter if there's a quantum computer in 50 years so in blockchain settings the urgency to

switch to postquantum things I think is not as motivated as um you know the NSA and nist winnings you know something tomorrow um because they need to keep things secret for a century um so anyway I think uh luses are um probably not postquantum would be my guess uh but that they have a lot of lattice based crypto systems are really nice not just because they support fhe but we're going to find out that they're very friendly to snarks and things like that and that'll be another reason to like them and so maybe we'll be using them in blockchains you know for the next 30 years until the quantum computer comes around or something like that interesting great uh we do have time for maybe one or two questions from the

audience so an eager one from the front row so it's more of a sort of prediction question um do you think developments in uh things like MPC FHA FHA and similar will kind of provide a stronger alternative to the model of you could say data exchange so what do I mean by this is essentially a lot of systems that we build um operate around all orchestrating data you could say do you think a different sort of model of computation will come about where you're orchestrating compute you could say Federated computer similar in the future good question I I think the Richer our toolkit is the better so um we have snarks now which are

practical MPC is kind of getting practical FH is further down but the more tools we bring the more freedom we have in designing these protocols maybe another way of saying the question like do you think I like is our mental model even going to change once you have like off the-shelf multiparty computation yeah I think we'll see more privacy tools being built I mean um right now our privacy toolkit is very um very poor I would say like uh data gets leaked all the time you you have data breaches all because the data is stored in the clear somewhere in a single place and with MPC you can shift it around you can secret share you can do all kinds of new stuff

but you know right now in order to do that you have a team of crypto you have to have the team of cryptographers building that and the team of Engineers so it's very hard to to acquire talent to but once we have have enough libraries I think people will uh will assume that one thing I would add is like there zero knowledge there's kind of been a transition where like you know 20 years ago anything you wanted to do with zero knowledge involved some like handcrafted Sigma protocol that was complicated to reason about and we're getting closer to the era where you just write a short program compile it using a generic snark and then you get your ZK I mean there's tons of stuff people are doing today that is MPC like threshold signing um all the like sort of auction

or private voting stuff like those are all MPC under the hood so we if we had like really great MPC in the future we would stop having to like carefully engineer all these special purpose protocols and just throw it at some general purpose MPC I don't think that's like going to is around the corner in the next few years but that would be the the dream world that you can just Express anything really simply and then get MPC sort of you know for free with generic techniques hi guys um so first off uh I'm very excited about dank sharding and uh just like my jam so you know like in your paper you have an excellent example about incentivizing you know data archival nodes as a result of um Fair data Exchange in Vex I was wondering if

you could just speak to some other outcomes opportuni you see that um FTE could provide good question I think uh some of the projects might use FTE instead of building a data availability layer because we see a lot of companies um needing a data availability layer and because current data availability doesn't support their needs they want to build it themselves so we see a lot of initiatives just trying to build da layer but D layers is very it's kind of complicated to build especially in permissionless way you have to acquire noes to inent identifies them to participate in your system keeping it honest but many of this applications at the end they want some exchange between the two parties and for that you can

always do that through the da layer but you can always do it uh like peer-to-peer like with fde for example if you want some training on your model you yeah you would uh send the data over to uh whatever trainer who will then train the model maybe prove to you in zero knowledge that they trained it correctly and then you want the result back so you can always go through the da layer to make sure that uh you know this exchange is happening but you can also do it peer-to-peer and it's much much simpler to build than building a whole day so for some applications like that I think FD is useful so on the quantum computer side like we actually already have some quantum computers they're just very impractical right to to solve any

of these real world problems do you think that people keep working on like okay like how far down the line of quantum computers do we have to get in terms of their practicality for people to stop caring about um postquantum Security in lses for example like do they have to be is the is the problem of if solving um lates versus like factoring of the same difficulty I guess it's like they're both polinomial time um but do we care about constants I guess is my way of asking this I think

we don't even really know enough about quantum computers and what their performance profile is going to be like to even reason about the constants today so yeah I think we're years to decades away from even knowing how to think about it but I mean it's definitely true that it might be that like you mentioned polinomial time it might be that you know from a theoretical point of view lates are broken by a quantum computer but they're actually much more secure given you know practical uh parameters than than you know other things like factoring so they they might you know that might also be another way that lates hold up is if it's just more more difficult even if it's polinomial time for a quantum computer but yeah that I don't know I'm

probably that's another way to nerd swipe cryptographers to just ask when they think quantum computers are going to arrive because nobody nobody knows but everybody has an opinion uh I'm probably like farther on the Spectrum than most that I think that they're like a very very many decades away from being here but um it's worth mentioning like even um sh's factoring algorithm saw a recent Improvement right it's polinomial time but like not a nice polinomial and they just improved the polom um and these questions are super relevant to how long will it be until there's a cryptographically relevant quantum computer which is basically one that can fact like today's um you know crypto systems um break their security

um so there there's a lot uh to play out and it's just so much guess work I mean I'm I'm with Joe that we're very far from a cryptographically relevant quantum computer and it's it I don't think it's like 10 years I think it's significantly more than that yeah there's a joke going around uh for the last 30 years quantum computers world with 10 years um away from us so I think we're we're 10 years away from being 10 years away yeah um I want J that um we still don't know as Joe was saying how how this will scale I guess because if if adding one cubit to un Cubit system is um not constant cost it can be like quadratic cost or a cubic cost and polinomial cost

then maybe you know you don't have such performant uh algorithms at the end just becomes too costly to grow the number of cubits that you can keep coherent um but um I think the worry is that even so our quantum computers are super small and Tiny and only toy uh examples can be run on them but uh the worry is that somebody will stumble on a technology that scales and then this will be like exponential growth and number of cubits you can support and that's really scary I mean maybe the progress right now like is very very slow but once you know scalable technology disco is discovered maybe it can go exponential ially fast

we don't know and uh maybe also um it will take another you know military conflict to to to incentivize everybody to really build this thing because so far there are no good kind of civil examples for quantum computers so most appealing application is breaking cryptography and that's uh of course you know doesn't motivate a lot of people until there is maybe a real need for that uh to happen so I don't know probably just um I think us is sponsoring a lot of quantum research and China as well and they're kind of competing with each other so having them kind of being a little afraid of each

other helps Advance this field if you like so let's uh go ahead and wrap up there thanks everybody [Music]