ZKStudyClub: Eli Ben-Sasson on Blockchains and Scalable ZKPs

Transcript

I'm really excited that you've all joined us. Uh this is going to be a bit of an experiment. This is the first time that we're using the Crowdcast platform. Um so do bear with us. We're learning as you are. Today we are actually going to be listening Ellie Benson talk about the story of how journal proofs and blockchain got together. And so I'm very excited to invite you Ellie. Just a quick note to everybody. You can see that there's like a chat in the sidebar. Feel free to add stuff there. And there's also this ask a question at the bottom. So in there you can ask a question and then people can like vote on it. And so this might be something fun for us to play with at the end.

Okay. Now I'm going to pass it on to you Ellie. Hi. So hello everyone. Can can you hear me? Um can someone say in the chat box if you can hear me? Okay great. Okay. [laughter] Thank you so much. So uh what I'm going to do is most of the time I'll just be talking and uh doodling on this here thingy which I hope you can also see shared. So like uh this thing and uh I have a very bad handwriting as you can see gets uh even worse when using this pad. But anyways I want to try it and I'll be doodling as I'm talking. So I um I'd like maybe for say hopefully half an hour or so uh tell uh my own personal

story which is a very you know it's just one tiny story about how you know my very theoretical research led me in a very gnarly way to end up doing things related to zero knowledge proofs and and actually be involved in in by now two startups. Um so it's uh it's this this personal story. I hope you'll enjoy it. Um and then um after these 30 minutes uh I'll leave like 15 minutes just to answer general questions and you know uh um talks and whatnot. So here we go. I guess for me the starting point was in uh basically in 2001 and it was through this thing called the

PCP theorem. So the PCP theorem actually um was discovered uh you know it's a sequence of works but it basically is attributed to uh you know Aurora and Sudan Aora and Safra and then this other paper it's called ALMs a mutani Sudan and all of this was in 1992 so this was way before my time um the PCP theorem was one of these marvelous things that actually came out uh from the um this whole marvelous area of interactive proofs and zero knowledge proofs that started about seven years earlier um with uh this uh model of interactive proofs and it comes

from this branch of of computer science and mathematics that's called complexity theory. It's this attempt to understand um how hard it is to compute c certain things and and what kind of uh languages or generic classes of problems you can solve in different models. And um the PCP theorem is till this very day hailed as this amazing uh uh and very surprising result. And the PCP theorem talks about the ability to check the correctness of a proof extremely efficiently. So um often it's uh it's explained in this sort of uh informal way that suppose you get this very long

proof of some very uh important theorem like uh you know the pankare conjecture or the reman hypothesis or something like that. It's really really long and and you don't want to you don't want to read all of it. So you would like to ask for some way to encode it so that um you know you can check it really really quickly by let's say flipping through the pages and just uh you know reading a very small number of uh symbols from it. And the PCP theorem gives this very generic um reduction that allows you to take any uh statement and uh ask for a specific encoding of its proof in such a way that you can read a small number of bits from that proof. And this number

can be made as small as three bits. And in general the number of bits that you need to read depends only on the error you are willing to tolerate and does not depend at all on the length of the theorem on the length of the proof. So even if the proof is a million pages long um if you want to be sure with uh you know certainty of uh at most uh you know 99.999% you only need to read something like uh 50 bits from from the proof and you you you will know with very high likelihood that the proof is correct. So this was at the time was an absolutely amazing revelation that you can sort of speed up the um um speed at which speed up the

the process of of checking the correctness of of proofs and you can do it for a very generic class of computations and um so this was before my time as I said and in 2001 I started my posttock um at Harvard and MIT and I uh went to two amazing professors at the time uh Salil Vadhan from Harvard and uh Madus Sudan from uh MIT um who now is at Harvard and I basically started my posttock with them and uh I came to them and said look I' I'd really like to you know do whatever you guys are doing um and uh one of the question was uh you know how question was like

how large is a PCP proof. So what we mean is suppose the suppose the standard proof you know the standard witness for your statement this is the original proof of the FMA theorem let's suppose its size is n and we know we can reduce it to this PCP proof that usually is denoted pi from which you can read you know three symbols and already know the answer but you know how large is pi what is its length in bits and it was already known that it is at most c to them to sorry is at most the length of the original witness raised to some

power. This power was a small constant something like roughly two to the two to the 100. I mean this is actually the constant was probably a little bit bigger. Uh but for the price of this you could actually get to read only three bits from the proof. So as you can imagine this sort of constant is a little bit too big for anyone's comfort. Even though as theoreticians everyone's sort of happy with any sort of constant as long as as it's a polomial everyone's happy but the question I was was asked was basically you know can you bring down this constant to something smaller and this was a question that we all worked on so you know with Salil Vadan and with Madus Sudan with many others uh

at the time over a number of years and uh we did bring it down so the main sort of result from that very theoretical work was that you can actually get the proof pi to be smaller than what's called um quasi linear in n and this was a long se sequence of work but this particular result was from my work with medus sudan in right roughly 200 five sort of um so this symbol means and now I hope I can you know go down a little bit or maybe all I can do is sort of just uh decrease this thing.

Ah, now I'm going to have a hard time. Uh oops. Okay, so this means um O of N times some log to power C of N. And this particular C wasn't too bad. It was like maybe a four or something like that. So this was uh you know a kind of nifty work in theory of computation but uh this was uh you know we were all very happy with this result back in the time. Um so this [clears throat] was 2001 then I guess if I could uh how do I move this thing down?

Nope. Never mind. Let me just uh I'll continue without this thing and maybe we'll later on add uh another Oh, okay. Here's the next page. So, that was 2001. Then around 2005. Oops. No, that's not what I want. Look, this is too complicated for me. So I'll just uh go back and uh and uh and and continue speaking and some other time I'll learn how to use this thing.

Okay. [laughter] So that was 2001. We started with very theoretical work and then um around you know three years later there was someone um by the name a very uh um an excellent young researcher Alma Batachalia who's now a faculty member um and he as a summer project he took part of uh this result and and wrote code for it um as sort of a graduate project at MIT and he wrote code for this part that is related to uh um you read Solomon codes. So he wrote code for part of this uh project and uh you know first this looked very strange to me like why would anyone want

to encode this thing? Uh what use could could one have for this thing called the PCP theorem? But you know I guess students have to do summer projects. Anyways two years later I was teaching a course in theory. Um and then um I I just uh taught this theoretical result of the PCP theorem and uh three students came up. This was 2007. And they said, "We want to do a summer project uh at Techneon, which was where I was teaching at the time. Um, and I said, well, there there's this thing called the PCP theorem that by now we have pretty efficient proofs. Someone wrote code for it uh for one half of it for what's called the proximity testing, but no one wrote code for the other half, which is

sort of the arithmetization and the reduction from a computational problem to a problem about uh lowderee polomials. would you like to do it? And they said, "Yeah, why not?" So they did a summer project in which they took a um you know rewrote the code for the um part that talks about uh testing lowderee polomials and they added to that another part that does the reduction. Um and they submitted a student project and you know there it lay they they got like prizes at both the faculty of computer science and a technon for like best project of the year but uh you know wasn't published anywhere. We didn't do anything with it.

Um then uh another year later um so so you know I I I saw that as a theoretician as a as a mathematician I saw that you know folks could write code for these things. I had no idea why someone would want to do it but uh you know it it actually can be done. Um, a year later, um, I received this very sizable grant, uh, as a researcher from the, uh, um, European Research Council. And this grant was was almost 2 million euros. And that's a huge sum in any institution. And in in Israeli institution, it's way over what you can, you know, actually spend as a theoretician.

um you know because gradu grad students and postto salaries are only so much and you know you can't uh start employing the whole bunch of them. So I I I thought that maybe you know it might be a good idea to uh um actually write code for this uh you know for this thing and um I received the grant and right after that I I was asked actually um to go and meet Iran to who was a posttock at MIT um and uh you know discuss with him opportunities for him coming to work with us at Technon um and I just received this grant and told him, "Look, uh, you know, we have this, uh, nice

grant. Why, uh, why not sort of use it to work together on on proof systems?" He told me that he had just, uh, written a very nice paper with a young graduate student by the name of, uh, Alessandro Kza from MIT. So Eran was a posttock there and uh Alessandra was a you know a graduate student and they wrote something about like recursion of proofs and incrementally verifiable computation and um they thought that it might be a good idea to try and actually instantiate that thing with a real uh proof system that that uh might be useful. And I thought to myself, okay, there was already one project that

worked and um why not? So I was in Israel to was doing his job talks. We met uh you know someplace in Cesaria. I said look uh you know that's a reason for you to come to technon. He ended up going to Tel Aviv University. But I said look irrespective of that why don't we start working together. And he said yeah there's this uh really smart uh graduate student uh we'll all enjoy collaborating with him. So I said sure let's bring you know both of you over. So uh you know I started spending my grant by um inviting both Iran and Alessandro and at the same time I had another um graduate student who wasn't my graduate student but he

was at Technon by the name of Daniel Genkin um he's also a faculty member these days in the US and uh he was also interested in this stuff. So we started this uh collaboration that ended up being Skipper Lab and um we ended up hiring a number of uh programmers um who were actually undergraduates um at Techneon and asked them to sort of uh you know work with us together on encoding uh you know some PCP system for real computation including a compiler and uh and uh you know from from general CC code um you In hindsight, I think that was too big a thing to try and swallow, but you know, we thought that

it would uh be a short project. Um, took a very long time. Um, but we had a lot of fun. So, all this time we're writing this code uh for converting programs written in C into PCP um PCP [clears throat] systems. Okay. And we had this nagging feeling that um you know why would anyone use this? And I remember multiple discussions in different settings like why exactly are we doing this? And the best justification I had at the time was something like okay I have this huge grant to spend um you know why not worse comes to worse uh we'll write a bunch of

papers and we'll submit them. And then about the papers there's also a very interesting anecdote which is so as we're building the systems we're also specking them out and like writing in more details the reductions that take a general program to a proof and at this point so this was already going on for like a year or two and everyone was deeply involved and um you know I have to it's it's a funny story to recount but like I was at initially uh very opposed to publishing any papers before the code is ready and I remember this particular discussion with Alessandro was you know pushing for writing the papers and I said look it's not a good idea because this is such a simple

reduction that if we published a paper someone's just going to beat us to writing the code and also like who in the world would ever you know care about such reductions in papers about them and um um you know Alessandro was very persuasive and I sort of backed away and I said okay yeah let's these papers. So two things happened. I mean three things happened. It wasn't that easy to take uh those papers and actually convert them to code. Each one of the papers turned out to be like this very uh detailed uh you know with a lot of information, a lot of good insights that people all people are citing and using and building on till this day and it certainly took even us a large number of years like five or six years from those initial

papers to the uh you know to anything that resembles a system. Okay. So this whole time there there was this PCP track going on. Now um starting around 2008 there was this other so the PCP theorem is very complicated to implement because of this thing that is called um lowderee testing that that I'd be happy to talk about some other occasion but it's this like big big uh uh tough nut that that people try to avoid. And in 2008 there was a beautiful paper from from several colleagues of mine that initiated this other line of of attack that led to the you know to the snarks and many other constructions and it said well let's try

to use um additively homorphic encryption to bypass and sort of replace this uh tough nut of lowderee testing and uh this was an initial paper by Isai Kushi Levitroki and it led to a large number of uh improvements by G and Sahai and others that said, "Oh, you can use bilinear pairings to make it uh you know a publicly verifiable system." And this progressed very quickly and culminated in a in an amazing construction. uh G the GGPR um quadratic arithmetic program um construction that that is uh implemented in the Pinocchio paper which was the first you know implemented snark of uh you know the snarks that are as in Zcash

and then um when we learned of this we said oh look uh uh you know let's let's let's go and also implement this thing and again um I I I can confess that I was sorting um you know I I was a purist saying, "No, no, let's go and continue with the PCP um uh approach because we're almost there. It's like a month away. It's like, you know, we're just there and it's uh transparent and it's much better and postquantum secure." And yeah, it was uh mostly who brought on Mad Va another, you know, amazing collaborator and uh and then uh they said, "No, no, but this is a much faster approach. Let's go and implement it."

And I thought, "No, it's not much faster. It's a you know let's but but you know again I sort of came along for the journey and what a fun journey it was. So uh indeed that was much faster as we all know you know the snarks came out way before uh the Starks and um okay and now we started having so so we had like we had understandings in both worlds about arithmetizations and how do you do things in efficiently and we combine them in several ways that again we can leave to some technical discussion and now we had um the beginning of an inkling of something that that you could actually think of deploying. and they're showing a proof of concept. Okay. And this was already around 2013. So both in the Snark and in

the Stark world, there were things that that looked a little uh you know that you can start to talk about them. And um at that time I was uh in the uh in in the US for for a sbatical and I was just going to return home and I thought the systems weren't quite ready. Okay. But I thought as long as I'm here, why don't I, you know, and it's all local. I'll do like a tour among several universities and give talks and talk about this thing. So I started preparing a talk and I thought of some motivating examples right we've been for five years now since around 2008 sorry maybe 2010 sorry project started 2010 so for like more than three years uh multiple people have

been spending time writing code um and uh you know the question why like what are the applications for which someone will want this um were you know not something that we dealt with. So I remember you know sort of scrapping my head scratching my head and trying to think um what would be good examples. Uh so one example was that there was just this big debacle with a launch of a game. Uh I think it was Sim City 5 was launched and it immediately crashed because the game logic was all run on central servers and there were too many players who wanted to play the game was a centralized system. So the servers all crashed and actually the CEO

had to resign and the you know the stock dropped of that company. So I said oh the reason is uh here's one motivation. The reason is whole this whole thing happened is because the game company cannot rely on the players to sort of report what they did. There's no computational integrity. So they have to do everything. And this is the reason this crashes. And then I cooked up some weird examples about sort of uh you know internet of things style you know uh sensors reporting uh temperatures in a nuclear facility or things that didn't quite stick and this was 2013. So before that a number of times people have asked me uh you know what do you think about Bitcoin

because they assumed I you know I I I I do computers so maybe I understand something about Bitcoin. And my reaction to all those cases was, "Yeah, yeah, you know, it's it's nothing." And I actually didn't bother to go and read the paper or look anything up. Um yeah, you know, if I could have a time machine, I would go back and, you know, start mining or buy Bitcoin or something. But so, um, as I was trying to think of other examples, at some point I said, "Oh, you know, let's look at Bitcoin." And then it seemed like Bitcoin, which I didn't fully understand, was another good example for explaining why this thing that we're doing for three years now might be useful. Okay. So, I added that.

And then again, it was so Alessandro said, "Oh, you know, there's this Bitcoin guy coming to uh um speak at MIT um about Bitcoin." and I thought that I'd meet him, but I was just on my tour. So, I tried to reach out and I noticed that there's actually a Bitcoin conference in San Jose and I I I wrote to Gavin and said, "Could I, you know, I'm on my tour anyways. Could I come there and speak?" And they said, "Yeah, sure. Come and speak." So, um, I landed, uh, at the Bitcoin San Jose conference and, um, this was by far the most electrifying, uh, positively electrifying event I think I ever

attended. Uh, certainly in my sort of professional career, there was this sort of Woodstock messianic vibe in the air of, uh, we are now changing history um, for the better. Um and uh like it was amazing experience especially for someone who came always you know the only conferences I ever attended were ones of mathematicians with like a hundred uh you know smart mathematicians and not a lot of uh vibe and so on. So and and there I gave this talk that I also uh you know that that I shared uh the video still exists there. Um, and that was for me the watershed moment and

in hindsight the Eureka moment even though at the time I couldn't articulate what it was that that um that led to this. But in hindsight I think what happened was that um all the conventional examples um and conventional use cases we came up with you know banks would you like banks to use proofs ZKPs and prove that what they're doing is okay sure you would like but would they want to do this? No. like, you know, you need to trust them. They won't do that. Um, and so on and so forth. Would you like the government to prove to you something? Yeah, sure you would like, but the government is not going to prove to you anything. It's you're going to trust it. I mean, it's going to tell you you either trust me or you know, that's what the law says or something like that. So, whenever you

came to a conventional um, you know, business or enterprise and said, "Oh, we have this thing such as a ZKP. You can prove computational integrity with it. You can speed up verification." usually the kind of questions and and it's pretty much the same this day. The questions are okay, what exactly is this? Who exactly is proving what to whom and why would you do this? And do we really need it? Okay, you know what? Let's settle for a PC and and put it as a bullet uh you know on the presentation to the board. Um and in stark contrast in the world of blockchains, the reaction has and still is always the same. It's not, you know, what is this good for? it is where is the code? You know, here are five different use cases

that if the code is is is up to speed, we want to use it for it now. And and the reason is that in blockchains in decentralized blockchains you really really one of the core principles is that of um inclusive accountability and anyone should be able to check and verify that everything is correct without having any trust assumptions or minimal trust assumptions about the rest. So this was a um [clears throat] this was a like this you know watershed moment for me in hindsight sort of dragged me slowly into um um the world like this sort of merging proofs and blockchains

um and um at the same conference even though I'm not sure we got to meet there I don't remember already but also Ian Meyers was at the very same conference presenting the zero coin paper which is this other beautiful result, right? the first uh use of you know some general purpose uh zero knowledge in the context of blockchains to to achieve some form of privacy. And uh shortly after we um you know sort of the the teams the John Hopkins team and uh our team that that uh you know the main characters that were involved in this particular effort at the time were Alessandro and Iran and Mad and myself. And we wrote this uh

zero cache paper that was an academic paper but also with a code implementation relied on the snark that that we built which was an improvement uh to the uh Pinocchio system and had some you know added benefits and and sort of we published that paper. Um okay. And um after that time we received a number of uh inquiries um uh about you know trying to do something commercial with this. Um most of these inquiries didn't sound too uh promising but one of them stood out and that was uh the one by uh Zuko uh who was and still is exactly you know the right person to

lead such an effort. uh all the right uh ideological and personality reasons. Um so um sort of the co-authors of that zero cache paper and uh Zuko's team uh I think initially was uh Zuko and uh Nathan and Derea but uh very quickly there were Shawn Bo and uh Taylor at the time and others uh we sort of joined forces um and uh the what is now called the Electrocoin Company uh was started which led to the Zcash uh cryptocurrency that you still a thing out there. Uh [snorts] I think a beautiful thing the amount of um tailwinds for adoption of zero knowledge

as a thing in the world. I think uh to a large extent is is a lot of the credit goes to uh uh you know Zuko and his and his amazing team of engineers that took what was uh first completely academic and then semi-academic you know the zero cache paper is sort of you know has some code implementation but then made it into a product um so that was uh Zcash. Now all of this sort of came out of this uh you know snark branch that even though it goes it still relies on PCP techniques. So, so this branch that uses um snarks comes from this, you know, from this sort of

older branch, this uh uh realization that you should use additive homorphic encryption to uh remove the hard parts of the PCP theorem and that paper is called I think like linear PCPs or without PCPs or something like that like let's remove the hard part and do things differently. But at least for me my passion was always um even just for puristic you know mathematical reasons uh it was sort of on the um what was now called start but back in the day and and still in some part of my mind I still think of it as like um PCP style uh proofs and by PCP style proofs one means proofs that have a lot of information

theoretic proofs to them. So there's a lot of math going into them, a lot of algebra and uh and uh probability and to prove that that you know that certain functions are lowderee polomials and there is rather minimal use of cryptography only to get a commitment scheme. Right? So you try to minimize the amount of crypto and the amount of cryptographic assumptions that you use and you maximize the amount of you know provable information. theoretic math.

Um, and and I have to admit that the main reason I still like this approach best first [snorts] and foremost is because of uh, you know, the mathematician side in me that likes this sort of pure, you know, it has more math and and and more proofs and and less cryptographic assumptions. So, but it also turns out to be because of these reasons turns out to be postquantum secure, have leaner cryptography, be transparent, no trusted setup and and you know faster arithmetic a whole bunch of other benefits but but uh again at least for me at least initially it came from this sort of you know puristic mathematical inclination. Um so we we continued along um this this

path of like uh what turned out to be Starks. Um at first they were called when they were first published it was called actually SAI which I think means succinct computational integrity. So they had no zero knowledge in them and uh they were way less efficient than than what we have now. Um by this time um two very important um additional team members um that I want to point out are Ariel actually three of them um Ido Bento that joined our team and he's also you know a big name in cryptocurrencies in general um Ariel Gabizon um who who was uh at the time working with us on

these things and and of course Michael Riyabv who started as a uh as an undergraduate, as a as a programmer, but sort of matured into a mathematician and and scientist who, you know, on top of doing amazing engineering also um is behind many of the you know, brilliant improvements that sort of bridge the gap between um you know, something that's very theoretical and not really efficient and something that's actually extremely efficient. things like the fry construction, the star construction, the use of interaction for uh you know merging together many constraints into something that's much faster. So um we worked together on this uh um you know

sigh thing that was again a publication and some open source code. Um and then um you know there was like one more thing that needed to be done and uh this was sort of making the proofs even shorter and and tighter and whatnot. So all of the first implementation relied very much on um this 2003 um uh result called the Benes on Sudan uh um PCP of proximity and it was it's pretty efficient theoretically but not so much in practice. So there was this uh um now

that construction actually uses this uh [sighs and gasps] analogy between um PCPs and this thing called fast forget transform because at some very deep level these things and by now we understand this much better than we have in the past and probably in 10 years we'll understand it even better uh you know with every year that passes we we we understand these things slightly more better. Um efficient PCPs and efficient proof systems have very deep connections to efficient uh for transforms and finite for transforms and this is a topic that I'd be very happy to dedicate a special talk to and just you know go

over fast for transform how to view it and how to see that you know it is very similar to proof systems and and the connections between them. So um in the benza Sudan paper and the constructions that are built on it there is this sort of a fast for transform but it it uses parameters in a very inefficient way and they are so inefficient that there are certain attacks on them. So back in the day with Ido and uh uh Ariel and Michael, we started analyzing the sort of uh security or the ways to attack PCP systems and we noticed pretty serious attacks. We even wrote a paper about it.

This paper we tried to submit it like five times. Um it got rejected from every possible venue. It's still out there. Uh you know we tried to improve the write up several different times. Um um I should say that along this route of theory to practice there was a very long period of time in which most of the papers that we wrote took a very long time to get accepted to uh you know even decent or semidecent uh academic conferences and I guess you know at the time it was frustrating um I mean like for instance the stark paper got rejected I think it was accepted on its fifth submission the fry paper was accepted on its third or fourth submission.

And you know it takes time for like this especially when like the theoreticians you know like one thing the practitioners like this other thing but as you're going this route they don't understand it and they don't understand it and neither one of them likes it. So sort of uh you know you sort of uh um it's it's it's it's a little bit like walking in the desert to the promised land but uh you know I think by now this is passed. So anyways there was this um we had this uh understanding that there are some things in the benzoson Sudan construction or the use of the FFT that is extremely inefficient and at the same time we already had a much better understanding of this uh new concept um

that was modeled I mean it was you know floating around in a large number of of of our papers um this notion of how to use interaction in oracles uh what was formulated as the interactive oracle proof model um in in this paper with uh Alessandro and and Nick [clears throat] Skooner uh who's another extremely influential uh researcher in in this in this effort along with Tom Gulu and and a few other of of uh you know from Alist's team. Um so in this model that you allow yourselves a lot more rounds of interaction, you can sort of um choose the way you do your sort of FFTs

very differently and this led to a much faster and more efficient in terms of proof size uh construction which is the Fry construction and with this sort of uh missing link. So, so this Fry uh protocol which is a cornerstone in Starks and many other efficient uh implementations along the Stark branch the sort of PCP based thing and and is you know a topic that I continue to be deeply interested in and along with you know many of the other folks at Starkware and and and others in our sort of academic uh u adviserss and and people in this in this team. um this was sort of the missing piece in order to

build something slightly more efficient which led to starts. Now all of this is still sort of uh research uh wise and so on but um I just want to mention sort of uh you know how sort of stark which was the second startup came along. So Zasha would describe it as you know we wrote an academic paper this amazing team came along right which was led uh by Zuko Nathan and Dara and uh basically you know we did some sort of handover uh um said we we were going to help as much as we can but uh you know our involvement was uh or my involvement at least I'll speak only for myself was not uh u as large you know um in this other case of of of Starks

um sort of already got the bug. Um and um for a long time whenever I had any question about um business, I had this uh good old friend from 30 years who was always my business adviser and all things by the name of UI. Um and and we spoke many many times on you know business related aspects around the formation of Zcash and other things. Um and but first and foremost we were just very good friends. So um at some point we sort of pop the question you know should we maybe work together and and and do this thing and uh um so when I say when I say we um by

this time it was uh it's clear to everyone that you know uh Michael Riabv my co-founder and chief architect at Starkware was you know deeply leading uh basically the Stark and Fry effort and Alessandro KZA longtime collaborator on all things ZKPs and proofs uh and uh and and we you know we sort of join teams get joined hands together um we had a lot of luck you know today we're in these [sighs] this right this corona virus and markets crashing and everything um um we started this effort in the fall of 2018 as the price of Bitcoin was going like this um So,

you know, we had we're very lucky with the timing and um yeah, that's how uh Starkore was uh founded. Um so, sort of to summarize I guess just this personal story that that again I I like what are the takeaways or like what happened? Um, I personally was drawn by pure math and never did I think that I'll be doing anything practical. [clears throat] Um at some point for reasons I don't fully understand um I got drawn into participating in implementation academic implementation

projects and then I would say that sort of a bitcoin happened to me in particular it was May 2013 and um yeah since then I was bitten with a bug and um [snorts] you know uh it's this uh amazingly unexpected story. Um so that's what I wanted to share. I see that uh according to the time like uh you know 40 minutes have passed but I think that like five or six we uh spoke.

So I I'll be very happy to uh answer questions and before that I want to say that uh so I haven't I haven't had time I was focusing on just uh speaking so I didn't read any of the comments but I just want to say that if there is interest in in maybe having another more math drill down into let's say this informal analogy between um fast for transforms and and certain kinds of uh proof systems transparent proof systems in relations to polomial commitment in schemes and you know open questions there and and the way the algorithms work. Uh I have nowhere to go right now and I think a whole lot of you have nowhere to go as well. Uh you know

unless you're in guess China, Singapore or Southeast Asia, right? So we could do uh you know another one uh maybe next week or something like that. an informal but but math uh dedicated so no more you know stories by the fire side. Okay. So I'll take questions if folks are interested in the comments. Hey Ellie, I'm going to rejoin now. So if you click on the bottom bar, it says ask a question.

Yeah, I see that. Click on that. And there's actually a few that have already been voted to the top. Yeah. Um, maybe I'll say them. I mean, I don't actually know how the video capture works on this, so I'll just say them out loud and then you can take them. So, the top one is, when do you think we'll see Zcape crew used outside of the blockchain market? Where will it be first? Okay, I mean, it's very hard to make predictions and especially in these days of the Corona virus, right? So, you know, so I have an excuse if this I would say that the first place outside of uh pure blockchains where we'll see

ZKPs really used in I would guess that that would be in the general gaming you know not blockchain related um because and I and I'll say why I think that in g first of all we see a lot of gaming coming closer to blockchains and it makes a lot of sense but even if blockchains weren't around games are already of immense economic value. Um you know uh the gaming the um digital gaming industry has is is larger than the music and and uh and movie industry combined. So and and that's not because of blockchains, right? Um and in

that world there sort of we are all transporting ourselves even and immersing ourselves even more and more in virtual reality and in this in this digital space. Now there's a lot of value there right you know there are certain people are making or spending uh um millions actually billions of of dollars on on various assets and things and and games that are all virtual in the in the digital world. So the notion of the need to sort of have proofs there and have computational integrity I think is a very big need. So I would guess that the first place outside of blockchains would be um the digital gaming space though it might actually

start from digital games somehow on blockchains and then sort of uh spin out to sort of uh general uh digital games. That would be my my first bit and I would say that like conventional finance and then uh government related stuff which is maybe most important you know having the government assert to us various things with computational integrity sadly I think that's going to be the last to come even though it's most needed there but okay that's my answer cool okay so next one was actually my question who from that early batch of students you mentioned like that first batch when

you guys just started working on it have gone on to work on um CKPS. Oh yeah. Yeah. So okay obviously I mean the the the the sort of ones most deeply invested are are very famous. So formally right when we started this work both Alessandro Kza and Mad Vilza were were students right and as was Ian Meyers and Christina Garmin who weren't you know involved in our side of the team but they're part of the zeroache paper they're all of them now you know they have uh pretty brilliant academic careers um there were uh the others that are sort of obvious candidates so the

very very first batch there were so Ara Batachariah is a faculty member I can find a place but he's doing theory he's doing amazing theory these days but he's not involved in ZKPS um that was the very first I had three students uh who just did the summer project uh none of them is involved in ZKPS these days even though um you know I I can tell you that that I they have an open invitation to sort of uh come and join Starkwin each one of these students these programmer students when they were there I I always tried to you know have them stay continue. Um okay so that was those were the very early ones. Then there were two other

students Arnono Gv and Wad Balta. They're sort of you know moved on to other spaces even though Wahad Balta has now returned to Technon is doing a uh I think a master's with uh Yuvali Shai on I think on ZKP so he might return. Um Daniel Yenkin is a faculty member in the US. I I I forgot the exact place. Um but but that was the early and then of course Michaelv is my co-founder chief architect. Doentov is involved in many many blockchain projects you know Litecoin foundation um he's in the uh uh space mesh and a whole bunch of other things. And another

one is Shahul. He was not in the first batch. She's I think CTO of Digital Assets um holdings which is a New York based company that's uh using blockchain technology for uh traditional financial world. Cool. Let's keep going. There's a bunch of more questions. Okay. [laughter] All right. I'm gonna close that one. Okay. Snarks and Starks are both incredible breakthroughs. What is the next improvement from a theoretical perspective that needs to be tackled?

Example, proof size security. What about from an engineering perspective? For example, usability performance. H I would say so. So okay like proof size first of all for snarks there's there's not that I mean it's you know it's it's what we would often call epsilonics like you know you're already at 200 bytes like you know it's not going to be less than one bite at 100 so so I think for snarks proof size is not uh that interesting I mean one question that is um not so much I think practically interesting but sort of kind

of cool is can you get the best This is a good question always to ask. Can you get the best of all worlds? Can you get the speed, scalability, transparency, postquantum security, uh you know, all the good things of a stark with the proof size of uh of a graph 16 snark? Um that's a I think that's a very cool theoretical question. But I think that even if tomorrow you have the answer to that and the answer is yes, here it is. um it doesn't matter that much in terms of uh uh you know real world applications because and I can I could go into that so but that's so I even though this is a question a lot of people are looking at including myself I don't think it's the um you know the breakthrough I I do want to mention this

so there are huge breakthroughs happening all the time in this huge branch of proof systems we just had this amazing breakthrough occur it has currently nothing to do with you know zks or anything. Um it's this amazing result that the quantum version of multiple prover IP which is basically the PCP model the quantum version of that has a complexity class that basically all of the computation that can be this is an amazing uh you know breakthrough and it's completely unexpected. Um it's causing a lot of waves. I urge everyone to read about it. there's a beautiful quanta uh article. So, you know, that's

the kind of breakthroughs that I uh applaud. Um it's it's uh it's it's really a spectacular result. You can search for MIP star and just you know you'll get a whole bunch of uh it curiously it actually uses a bunch of results that we did in the PCP context but you know then it does you know it builds a whole new level of innovation on them. It's it's good to know that some of the stuff that we did for those very different contexts are used there. So I would say the big breakthroughs are the unexpected stuff that we actually don't quite see the the you know the reducing uh making things more efficient that's extremely important practically but from a science

theory point of view it's it's less important. Um yeah cool. Uh so should we keep going? Do you have time to go over a little? Yeah. Okay. Look, I I you know, I'm in quarantine. I can go nowhere. [laughter] All right. So, just so everyone knows on that ask a question on the lower bar. Click on that because then you can like vote on these questions as well so that you get kind of the next the next one you want to hear further up in the in the list. All right. So, I'm just going to ask the next one.

I think it's this one. Which feature of stars do you see as being more relevant for business zero knowledge or scalability? Again, the one I see Oh. Oh, wait. The one I see um Yeah, it moves around a little bit, but okay. Okay, now I see it. Which feature of starts do you see as being more relevant for businesses, zero knowledge or scalability? So, I would sequence them. I think that initially scalability uh is definitely the more important one but I think that after that it's going to be scalability with privacy. Now uh first of all this is what we see when we try to interact with businesses. Partly uh and this is also you know an

explanation why starter for now is focusing mostly on scalability and not privacy. Part of the reason is that we have, you know, pretty darn good alternative solutions for privacy like, you know, uh, snarks and bulletproofs and, you know, the whole bunch of other things that if you don't care about extreme scalability belt, you know, larger and larger throughput and very efficient proofers, they are uh they are they are, you know, very good for for for use and they are actually deployed. But still I think that that uh first we need scalability um which is best delivered by by you know these sort of u symmetric starks what we call that are based only on

symmetric crypto but then you'll also want scalability with privacy. Oh this one I like. Why were the papers rejected primarily? Oh man I I could speak about this for five hours. Uh why? Because the PC are a bunch of idiots. That's why. No. Okay. Uh, PC means program committee. No, don't quote me on that. [laughter] You're only live. I'm kidding. Look, anyone who has uh written any paper in in the academic worlds can give you a whole uh lecture on on why they were rejected and how it's always the uh program committee in the community that doesn't uh that just doesn't understand uh the greatness. I I

don't think it matters that much. Um you know I no it's actually you know it's funny and at the time it was very frustrating to to read this and say oh man can't they see this blah blah blah but uh it's part of the process no I mean you know uh look if something is uh like unexpected and or if uh you know you take something that is in one context like let's say the PCP theorem and you try to import it to this other universe and world of let's say realw world cryptography that doesn't really do that stuff or understand it. So now both worlds are unhappy. We're all, you know, myself included, we're sort of conservative and like the things that we know in the past. So when we see something that's

like really new, I mean this is very true. Satoshi's paper would have been rejected from any uh conference in any journal in the world flat out, right? No one would have accepted it. And you can name 50 different um reasons why it would have been rejected. And it doesn't matter. It's still, you know, probably one of the most amazing papers in computer science and beyond that in economics to have uh appeared. So, all right, which is the next one there? So, this doesn't update as quickly as the votes come in. I don't know if you see that there's a there's one with six votes.

I toggle down. Yeah. Yeah. Oh, it it jumped up. Ah, not for me, not yet. What do you see here now? What do you see as the strengths weaknesses of lowderee texting, te text testing, proximity proof methods versus homorphic encryption techniques? More tentatively, do both techniques have a long-term future or one set of methods dominate? Okay, I'll answer the first question first. I think the um lowderee testing proximity proofs will will dominate. Um first of all if most of the efficient homorphic encryption stuff um are based uh on some kind of [clears throat] some of them are based

on things like number theoretic assumptions or they require them uh additively homorphic encryption. So that whole thing falls down. There might be alternatives that are based on lises but they'll be less efficient. So just based on that I think that um long-term uh they won't survive. They're also less efficient. um in the midterm I think we might I mean another analogy is what you see let's say in in uh in encryption so yes we do use uh number theoretic constructions for instance in SSL handshakes but we use them for the minimal amount of time that we can and you know to to to agree on a key and then we move to this more efficient form so I think that in the long term even if uh quantum computers and attacks aren't

there and and I do believe that we will find attacks in some of these constructives um you would still want to minimize your use of them to the particular things they're they're good at. um the this the weakness of lowderee testing with respect to the other methods there's I know of one weakness which is that the proofs that you get are larger by roughly two orders of magnitude from the fastest you know the shortest snarks and one order from some other constructions but that's the only disadvantage I'm aware of everything else are advantages they have greater speed fewer assumptions uh they're more agile in terms of uh you know the kind constraint systems you can write with them and so

on so forth. So great question. Where are we now? Shall we do this one? The one at the top now. Is there an efficiency the PCP toughen out right? So I I this is an amazing question and uh it's the one question I probably spent most of my career thinking about like getting even better PCPs. Um there's I you know if I I had known a very good approach I would have pursued it. I don't know uh I'm not aware of of ongoing promising work but I'm sure um that that others are also thinking and

someday we'll have much better u just plain old PCPs but for now um there is a semi-efficient uh you know the sort of the benesis on construction you could uh make it work and in certain settings you would get something on which your computer won't be exhausted while it's proving but uh it's just uh vastly less efficient than the um what you can do with an interactive uh oracle proof model an IOP is a pairing based NARC a PCP is it an IOP okay so a PCP it is okay a PCP is a very uh okay

the PCP model is a very clean but unrealistic model it is a model in which you are given you know the prover generates a very long proof to which the verifier has oracle access to. Okay. Now um a pairing based snark is not a PCP formally. Um so the the answer to the first question is no. It is not in this model. Is it but is it an IOP? So the IOP model is one of the most general model there are. So the IOP model contains within it PCPs and IPS and so on and so forth. So it is a special case of an IOP but an

IOP allows you like much more strength than what you need in a in a snark. So the answer to the second question is formally yes it is some form of IOP but uh I wouldn't call it that because uh an IOP allows you a lot more strength and sort of you don't need that when you're building a pairing based snark. Cool. I wanted to try something. I want to make this the bigger screen. I'm curious what happens for everybody because it's just a bigger screen. All right. [laughter] What's next? Here we go. We've moved from theory to practice. How has this move been? What are you personally

working on at Starkware? Okay, so these are great questions. Um, for me, this move has been uh and especially uh Starkware uh is so I I I love academics and I loved my my work uh when I was a professor at Techneon. Um but uh which I am no more these days but uh like I'm having the time of my life uh at at Starware um and uh this has many reasons like you know there's

have a great team a lot of good old friends a lot of good new friends um just a lot of fun now what am I personally working on at Starkware. Um so a little bit of everything I guess. So um um I have a list of science related projects that keep getting postponed. Um and uh I feel really bad about that. And then I'm involved in a lot of uh the other stuff, you know, the strategy, the um the uh some of the product discussions. uh by now I think I I can't really say that I'm deeply involved in in low-level engineering or uh you know um or in uh I mean as things grow bigger

and bigger there's only so much you could sort of uh actually do part of it is actually they don't know the code so you know [snorts] right next one regarding the PCP theorem What do you mean? What do you mean with only three bits need to be read? Is that to get a soundness of 1/2? What would the amplitude to get arbitrarily high soundness? Excellent question.

Not surprising. So formally what happens that's that's a really great question. Formally what happens is that when you look at the PCP theorem and you care about um uh deducing inapproximability results which is the main thing PC the PCP theorem has been used um in theory not in practice. So you really care about two parameters. You want to minimize the number of queries and you want to make the kind of query as simple as possible while minimizing at the same time the soundness error. Okay. And what I meant was there's this stellar result, you know, one of the most famous about the PCP theorem. It's called Hastad's uh PCP. Um you can all look it up. It's I

think the title is some inapproximability results by Johan Hostad. Um and there what he shows is that irrespective of the proof length sorry irrespective of the original witness length you can transform it into a PCP. So that with the price of three queries and moreover making the kind of query you read these three bits and what you do is compute their sour uh they're exclusive or it's very important that you do that. Um then you every correct statement you can accept with probability.999%.

Sorry.999 and your error probability is at most uh you know 0.500001 and uh you can't do better than half. So this is nearly optimal. And then if you want to amplify it, so if you want to have your error probability smaller than 2 to the 120, you're going to need to read 360 bits. And actually you can do a little bit better than that. There are other papers that show you can do slightly better than even reading 300 three time sorry three times the security parameter.

Oh yeah, for sure. Would you care to comment on Ben Sison's law of the reasonable complexity for natural problems? Yeah. Well, okay. Yeah, this is something I researched very extensively and I have very strong opinions on. So, uh I hope you uh I mean I can't I hope I can hear the smirks going on. Um, what I meant to say is that I mean the the reason I tweeted it that day that there was actually one part of our construction that has a you know an exponent of 13 in it and and my initial reaction so it's in one of our papers and my initial reaction to that thing was look there's no uh there's no result ever that actually has an exponent of 13

in it and and you know that is the correct answer. So I thought uh I'd I'd uh I'd you know throw it out as a as a taunting tweet but to this particular thing you know the point counting on genus3 hyperlive curves I guess but for the o log P to the 14 and the word algorithm I don't understand anything about the rest so I don't know what point counting means genus three hypertic curves so I'm qualified just as anyone else to say I would say there's room for improve improvement, right?

That's what I would say. You can skip over the one that's from me there because it was actually answered underneath it. Okay. Um there's three more. Do you want to just pick one? Yeah. Who are the authors of the pino? I can Google them up. Uh but Oh, yeah. No, it's answered underneath actually. Okay. that's already there. That's why I just skipped that guy.

Okay. What have been the biggest challenges switching from a research role to an executive role? How did you try to solve these challenges? Um, that's a great question. So, luckily, as I said, I have uh all of these great um friends and co-founders and so on. I mean, they're more qualified to answer [laughter] this question. Some some of them might say that till this day I haven't completed the transition from a researcher to a you know responsible adult. I mean I I confess that statement but uh I guess the biggest challenge I remember very early on like we just started the company and we sit at this

meeting and our excellent VP of engineering who's also a 30 year old you know we are friends back 30 years in cuts says okay let's have a three-month program and at the time like uh you know this was like I was you know there were very few people who understood what's going on Right. Uh we have these engineers coming on. So people also look at me and I I remember coming back home and saying you know this is amazing. There are people out there who can actually plan for 3 months into the future and like you know think about what they're going to do in these various it was like complete revelation.

So I would say that uh to quote the Beatles I get by with a little help from my friends. So anyone thinking about doing this thing, I you know get some good friends who can help you along this transition. It's good. Okay. Snarkstarks for scaling often require batching of transactions adding a non-custodial but centralized operator. How do you reconcile this with the decentralized goals of the blockchain in the future? Do you see all validators running stock stark software to decentralize the batching? Amazing question. Okay, there are two answers to

this, right? So, so let me let me restate it. I mean, this is the this is the problem that I think Koda is actually trying to to solve uh headon very soon. So, so and and you know, we're all watching in anticipation to see how they deal with it because let's restate the problem. You want a lot of people, let's say, you know, just a lot of people to send their transactions, shielded or unshielded, and then you would like to have a prover somehow, you know, batch and compress all of them uh to one thing, right? That that's something that we're going to need. Now, this is a problem of coordination, right? You could do this in some roundroin fashion. You could rely on a centralized service. Having a centralized service is is not so bad.

And I'll explain why. because that centralized service cannot uh you know cannot cheat. It could censor so it's you know it's not ideal but it's not as bad as a fully right there's a limit to what that centralized service could do. Um now there's this amazing research question that I have not invested any time in. I think it's highly interesting um but they don't know how to solve it which is what is the right way to throw in um you know game theoretic or economic incentives along with uh the correct sort of partitioning of labor in order to get a decentralized and efficient uh you know batching of of of of a proof. Um I I don't I don't know.

This is a great science question that I don't know to solve. I wonder if um you know Koda might be a good team to ask because they're trying to solve it. Do you want to do the one with three votes there? Yeah. Yeah. Yeah. So what is the status of the uh Stark friendly hash function work? Is there a leading candidate in your mind? That's a great question. So um yes there there there the there there is a leading candidate that um we are getting more and more comfortable with uh that that seems to be rescue. We're not you know completely sure about it.

We're waiting for one very last piece of uh symmetric cryp analytic work. Um and uh um we are um making a lot of progress on writing the code. It's I hope that within two to three months uh it will be stable enough to do two things. Send it to external auditors and this is something we publicized a large number of times. We want to run a workshop for developers who want to start building on it. This is going to be open source code high performance C++ prover and verifier. We already committed to it running at a at a rate of uh at least uh 600

a proof of 600 hashes per second per core. So on a quad core more than 2400 um and uh you know we thought of doing this workshop in Israel like with actual teams now this corona virus thing is up in the air but uh uh and that's another topic that we'd be very happy um to to speak about. Cool. Right when you said that Allen parade in the chat when you said rescue. Anyway, so the last one, what is the current state of paper and how involved are you in this project?

So, uh there's a website on which uh I think uh folks are updating um from time to time uh research. Um I am not involved anymore in it. I believe that so I think definitely Alessandro and his team are involved in it and um I don't know who else I could look at the website again but uh yeah so my involvement right now with the skipper project is uh zero.

So I I just want to say so I guess I think uh um I I want to say this um I enjoyed it a lot and as I said I have nowhere to go and I could say that um you know I really would like to um give another talk on like you know math uh or math intuition about let's say PCP fry deep fry and FFTs and maybe also bring you know some of uh uh my friends you know researchers and and uh collaborators both from starkware and outside to sort of opine and and explain this stuff. So uh uh really good.

Yeah. And and I don't know if we can Okay, Anna, we'll discuss this later. Either we'll do it through your channel if uh you know we can sort of hijack all of it or otherwise we'll find some other means. But um yeah, and I want to thank uh everyone. I'm going to read now all the comments and see because I I I couldn't read it uh while focusing on this thing. But very cool. All right. So, I think that's wraps up the first crowdcast that we're doing the ZK study club as. Thank you [clears throat] so much for coming. This is super interesting. Um, I think this link will still actually have this video on it, so we'll share this after. Watch it.