The 'Useless' Theory Behind Modern SNARKs (ft. Gödel Prize Winner Noam Nisan)

Transcript

If you have some kind of theoretical inclination, you always find really fascinating theoretical questions. The general idea was that interactive proof was just an interesting extension of an NP normal mathematical proof. You can't do a lot more, but there are interesting things that you can do more. >> It's amazing to me that the very first paper LFKN to surprisingly show the power of these interactive proofs had exactly the right protocol that we're still using today. You went from kind of zero to exactly the right thing. >> In computer science, whenever you can take two things and combine them into one problem that you continue, you're very glad. Any blockchain that wants to have a token and figures out how to handle this token. Does it need to mint

new tokens, burn new tokens, you can't really just use macroeconomics as far as I understand, but I think that's really important >> in a development that is extremely good for the blockchain space. What are you most excited about? So, [music] hi everyone and welcome to First Principles, a series by the team at A16Z Crypto. I'm Tim Ruffgarden. I'm the head of research at A6Z Crypto and today we're talking about what it means to verify a computation without having to redo it yourself and how that ability has led to a surprising line of work

that now underpins technologies like zero knowledge proofs and verifiable computation. We speak with Nom Nissan a Kuth prize and girdle prizewinning computer scientist at the Hebrew University of Jerusalem and a principal researcher at Starkware. His early work on algebraic methods for interactive proof systems helped establish the theoretical foundations on which modern snarks and verifiable computation are built. Along the way, he also co-founded the field of algorithmic game theory, a field I've been fortunate to make contributions to as well. And joining us is going to be Justin Thaylor, a research partner at A6Z crypto, also an associate professor in computer science at Georgetown University. He's the

author of the book Proofs, Arguments, and Zero Knowledge, one of the definitive references on Snarks, as well as a co-creator of Lasso and Jolt, two systems reshaping how zero knowledge virtual machines, aka ZKVMs, are designed and built. Together, we follow Dr. in Nissan's path from early work in computational complexity to foundational advances in interactive proofs, including the seemingly magical sum check protocol and the line of ideas that led to IP equals peace, which shows just how powerful interactive verification can be. We then trace through how these theoretical breakthroughs underpin modern blockchain

systems. Here's our conversation. >> Well, thanks so much for for joining us, Nom. Um, and >> thanks for having me. >> I wanted to start the conversation. So, your your career has been fascinating um, with lots of twists and turns. I'd say many more distinct chapters uh, than most research researchers have in their career. And in particular, I thought maybe we could start at I don't know if it was like 1996. I'm guessing it's around there, but a moment in time where on the one hand, you know, you were a leading complexity theorist sort of worldwide. You were famous for hardness versus randomness paradigms, you know, uh what else? Pseudor random generators for space computation, foyer analytic

approaches to pack learning, algebraic methods for interactive proof systems, which we'll talk more about later. And when you're leading a field, there are tremendous forces and incentives that encourage you to just keep doing what you're doing. Arguably, you have to be a little bit nuts to not just keep doing what you're doing when you're at the the front of a field like that. But my understanding is sort of b you know mid mid to late 90s there was perhaps a conscious decision to pivot away from what you had been doing computational complexity theory up to that point and explore other options. So I was wonder if you could just start by a little bit about you know was that a sudden decision was it a gradual thing was it scary how did you approach that you know what was what was that like at that time

so actually I have sort of a story so obviously the web basically hits the world something like around 95 everybody knew that the internet was like a major thing the web but no one in academia was really uh changing so people were very very slowly changing what they were doing because you know academia it's very slow to change. Big companies were already really all gung-ho on it and you know the world was already popular the internet but in academia things they kept on moving very slowly. So that sort of reminded me one of the things that I always made fun of my parents is that my father was doing a PhD in Chicago in 1967 in the middle of like you know all

the cultural shift all the student protest all the of everything but you know my father was there with three children and he really didn't notice it like this huge cultural change that was hanging going just around him and I always sort of vowed to myself that if I ever have that chance and I see something really huge going on, I will have to join it and will stop what I was doing and then I found myself in this situation where this huge thing the internet is going on am I just going to keep on doing what I did previously. It was really a conscious decision that I need to change. So at the beginning I really wanted to you know actually build systems and then I very slowly found out that it's very difficult to build systems but there are some interesting

theoretical questions that one should look at. So that was why I made the change and I have to tell you that our field theoretical computer science the field that I came from was amazingly accepting theoretical computer science as a community immediately embraced this new this new area and it was you know very easygoing. I have to admit one of the example was my father by that time was really worried you know until then I was doing like normal computer science very massy understood what that means but then I was playing with this economic kind of things you know popular culture kind of thing he was very suspicious of that so my parents lived next to a vigoron my father met a vigoron the renowned computer scientist

in the parking lot and sort of complained to him that his son was doing this you know completely useless kind of thing instead of doing serious math and avi actually told my father no this is a good field you'll see something really will come out of it so I think generally in a community my own university everybody just accepted it very easily >> that's and that's just yet another story and a victim looking out for us in more ways than we can possibly imagine [laughter] >> um that's that that's awesome I don't know a lot about the details of this period but you know I would love to really actually and also I think just I'd like to think a lot of theory scientists would be you know amazed at the number of different things you try

in a pretty short period of time so obviously there's sort of the complexity theory story that goes to the mid '90s you know algorithmic game theory specifically algorithmic mechanism design you know huge paper that came out in 99 I I assume the work was done in part in '98 but there's this little kind of interval in there where like I know maybe part of that led to you know writing the book about really sort of computer systems like from the round up. I think I heard you were teaching like intro programming classes or something like just tell me about some of the stuff that was going on at that time and and how did you approach you had to answer the question like how can I make an impact on this sort of new technology? So are there how did you go about doing that and you know any

lessons learned from how you went about it? >> So I started I thought that I would you know build systems everybody was building these things. It was sort of easier to build systems at that point in time because you finally had these new languages like Java where you know one person could do the GUI could do the communication you had very nice libraries everything was working really well. So I actually tried to build a little system with master students and I realized that it was not easy to build a real good system and once you build it and the master students graduates and you have no one to uh take care of the system anymore and also once you build a system if you have some kind of theoretical inclination you always find really fascinating theoretical questions

that oh I could have done this so much better had I figured this out and figured that out. So after basically a system that we built that was doing some kind of I don't know protocloud computing or something like a grid computing it was called then I believe I actually thought that the most interesting aspect was not all the systems kind of thing which already I figured out that I wasn't very good at but uh actually the the way you get people to cooperate over the internet even though they do not belong to one company or do not have one goal and that seemed really fascinating to me. is very completely different than anything that we previously looked at in computer science and I thought that was something interesting to look at and that's where

I actually went back to my theoretical booths and looked at that. >> Is the popcorn project part of this? >> Yeah, this is the popcorn project basically. >> This is the popcorn project >> cuz cuz what's amazing is that was a paper I just stumbled on completely accidentally. you know, I was out there uh you know, in Jerusalem a few years ago knowing to speak at your 60th conference and and I wanted to just sort of highlight some of your various works. So, I literally like went through your DBLP page just to remind myself cuz I was sure I was missing things, which I was. And I was like, what is this popcorn thing? And then I looked it up and I read the abstract and it kind of feels actually like halfway to a blockchain system. I kind of feel like there is this notion of like a shared

virtual machine. They're almost like the initial, you know, ideas that we now see manifesting in prover markets. I'm curious like does does that feel precient in hindsight at this point? >> It seems a little bit related. So you you immediately figured out that if you delegate pro work to someone, you sort of need to check it somehow at that point and and we definitely thought that oh there are various ways to check it. You could give it to a few people and see that they get the same result. You could actually have some kind of a proof like an NP like proof. So we already had these kind of ideas then but I think it's we were not thinking of course of anything like a blockchain kind of a system neither in terms of the the utility of it nor in terms of the

mechanics of it. It was more taking what was then very popular called network of workstations. Now you know how to lots of workstations together can actually cooperate and let each other use their resources but moving it to a web-based situation where not all the networks belong to the same company or the same university not all the workstations. So that was the basic idea that we tried to do there. But I agree that it's some kind of a distributed system. There are issues of trust. There are issues of incentives. you need to motivate people to participate. So some of it is is related really.

>> So 1999 as we discussed algorithmic mechanism design the paper with air ronin came out made a huge blast right away and that was you know part of a bunch of simultaneous beginnings of the field called now algorithmic game theory or computer science and economics. So help me just connect the dots a little bit. So you talked about how in working on the popcorn project, you know, the economic and coordination issues already were striking you as sort of the most scientifically fascinating parts of it. You've told me in the past that, you know, algorithmic mechanism design actually sort of started from air kind of walking into your office with a mechanism design paper and you were kind of like what is this? Am I remembering the story correctly or so? What was it like? Was you already thinking you wanted to work on some kind of more

economic problem and that was the right opportunity or >> I sort of wanted to work about incentives and computation. And I thought that was really interesting how to get different computers to cooperate. And I had no idea that there was this sub field of economics called mechanism design. So I did know that there was something called game theory. And I learned a little bit of game theory. And I you know Men came and I told him look this is very interesting. It's somewhat related to game theory. Maybe you can learn a little bit game theory. And [snorts] he got this big microeconomics mascul.

and he started reading it and telling me stuff and at certain point in time he realized that oh there isn't this kind of subfield of economics called mechanism design that seemed to be very related to what we were looking at and at that time did you know that um you know for example Elas Kupius and Christos Papadomitu were sort of thinking about game theory and computer science at that time or were those just sort of parallel simultaneous developments >> I was thinking about this and then it's about the same time I heard about Christos and Elas and I heard about your work with Eva. So I know that in some sense your work is a continuation of Papa Deto and Elas. But from my point of view there was this like three different threads because Papa Deto then was

looking at slightly other thing. I really was, you know, seeing what Eva and her students, for example, you were doing and the same thing about what Christos was doing. And we were all in the same space and I thought, oh, this means that, you know, we're on to something here because completely different people from completely different angles are looking at this general field. And I think for a few years there h there was this kind of thing that were maybe five universities giving courses in algorithmic game theory and economics and computation different names and all of us would always look at all the courses that the others were giving and basically steal from each other all the time. So it was really nice >> we we really were learning as a community together sort of in the open.

I agree and it's funny I think you know other fields like you know for example economics this is a bit foreign right the idea that you just start writing papers even though you don't totally know what you're doing yet and you kind of learn by doing and you get critique and then you get better the next time and by 2010 I felt like a lot of us actually knew what we were doing in 2000 felt very exploratory I thought [snorts] >> absolutely and I think so so one of the things that computer science gets a lot of criticism is that we write papers prematurely we don't really understand what we're doing, but we have something interesting, we write it in a paper. And you know, serious scientists would probably think about it another year or two and really figure out what's happening and write the whole thing

together. And we don't do that in computer science. We have something interesting like a popcorn kind of thing. You have an idea, write a paper, publish it in a conference. Maybe you have even a mistake, it doesn't really matter. You fix it next time. Maybe you can continue it. You will do that in the next conference proceedings. And I think that that's usually taken as a criticism, but I think it was amazingly effective for us because that's how I mean a lot of people got into into the same kind of spread of research and everybody knew what everybody was doing and everybody had new interesting problems and then interesting solutions and interesting techniques. So I think in the early 2000s that was amazingly useful for our sub field of algorithmic game theory.

>> Yeah, it really makes it almost a community effort, right? It's almost uh halfway to a polymath project or something, right? where everybody gets to work in kind of a common direction and learn from each other. I agree. I think it's a, you know, maybe it's not for everybody, but I think for those of us in the field, I think most of us view it as actually a strength, not a weakness. So, >> and I'm sure that for people just starting their career like you at that time, it was beautiful. I mean, you could always know what was everything in the world basically. >> Yeah. I mean, my, you know, I knew nothing at at that time. So my decision algorithm was pretty simple which was that like you know Christos Papitri Nom Nissan and Avataros are all like very excited about this field. If I know it's

good for me I think I'm going to [laughter] take advantage of being uh being in the right place at the right time. So just feel very lucky to to have had all of you as mentors very early on. So now let me suggest we rewind back to something that happened in the middle of um the complexity theory part of your career and something which has emerged to be very important in some of the design paradigms for snarks. And so I thought maybe to sort of set the stage Justin I was wondering if if you wanted to tell your own sort of personal story about how you found out about the sum check protocol. What did you think of it? How has it kind of followed you through your whole career since?

>> Yeah. Um so I first encountered the sumject protocol in a uh course I took in undergrad. A complexity theory taught by Joan Fogenbal. There was me and one other student in the class and uh Auroran Barack's complexity theory textbook draft had just come out. So we were walking through the draft and they had a whole chapter on interactive proofs and the the centerpiece is the sun protocol and the result from LFKN. Gnome's paper from 1990 or 1992 which is a an efficient interactive proof for sharpsat you know just falls right out of this beautiful simple protocol which you know came to me fully formed in already a textbook which is kind of

amazing that it was in a textbook then I just thought it was great and then I got to I started my PhD a couple years later cloud computing was just becoming uh you know the thing that all the academics were trying to be relevant for. And so people started looking at the combination of interactive proofs and algorithms for massive data sets, streaming algorithms with the idea that cloud computers were doing all this work and you know returning the answers to their users and the users were just trusting that the work was done correctly and should the users just trust or could they actually verify. So people started looking at interactive proofs in this sort of you know massive data sets cloud computing setting which

does feel a little bit like uh gnome your description of uh popcorn you know a distributed cloud already already back then and so you know I had this hammer from that I learned about in in Jones class and it turned out that everything was a nail for this hammer and so like all of these problems in the in the space uh and you know for algorithms for massive data sets the problems people care about are very very simple and clean and you could just kind of say for each of them use a sum check protocol use some check protocol and you get this like you know optimal protocol for for uh proving that an untrusted prover solve the problem correctly so that's how I understood his power and because there were streaming algorithms there

actually the the work had a lot to do with communication complexity so nome your your book with ya kushvitz was like instrumental in kind of my own development velment and career. So kind of the these two threads that seem unconnected the sum protocol and interactive proofs and communication complexity actually this was like a very very rich and fruitful lens to first encounter the protocol because you can prove unconditionally that it's it's optimal in some of these communication models. Then I learned about these very powerful interactive proofs like the GKR protocol uh from 2008 that were using the the sum protocol as a sub routine and started implementing it. Over time we realized that these interactive

proofs we were building were kind of half of a snark and you could combine them with uh commitment schemes and and boom you have your your snarks. And then these are basically the snarks now today that have the fastest prover. And that's kind of the key bottleneck, the key thing that's keeping snarks from sort of taking over the world is how fast or slow is the prover. So fast forward to 2025, there's this transition over to snarks that have the protocol at the very core. My expectation is this is how snarks will finally eventually in the coming years eat the world and you know affect how we deal with trust throughout all of our digital infrastructure. So that's my personal story coming to the sum protocol and you know it started

with two sort of independent feeling parts of your own career which is LFKN and communication complexity and all these things that felt unrelated turn out to come together. So, Noom, I wonder if if you know, maybe we should take a step back. So, now I kind of want to, >> you know, I want you to paint a picture of what things were like in, you know, ' 89, 90, whenever it was, you know, so interactive proofs at a high level, you know, what are they? Why were people thinking about them at that moment in time? You know, what kind of questions were they trying to answer with them?

And then maybe from there we can get to, you know, how did the sum protocol actually come about? So I think the story I mean from my point of view between I don't know 84 and ' 89 I would say this new idea of basically extending the notion of a proof came originally due to a few few people including Shafi including Gold including Mikalli Rakov and they said oh here's something that's like a proof but it's not like a mathematical proof like you know because it uses some kind of interaction and randomness. Turns out you need both interaction and randomness or otherwise if you only have one of the ingredients you don't get anything new and that was really I think mind-blowing for lots of

people in the community because people could see it sort of gives you what a proof is even though it's so very different than anything that we consider a mathematical proof and I think during these four or five years lots of work has been done on many variants of it the most famous variant is a zero knowledge kind of variant though usually people are so interested in the zero knowledge kind of aspect of it they forget that the really even more fundamental part is just the fact that you have an interactive proof that's more than a normal mathematical proof and in fact what we call ZK for zero knowledge proofs in the whole crypto world is not ZK really people are mostly not interested in the ZK aspect but just in

the fact that it's some kind of succinct interactive proof or non-interactive interactive proofs I would say so that was the first idea And lots of work has been done on it. People were looking at how many rounds of interaction and they figured out that there's a difference between any constant number of rounds which all of them were the same and many rounds and they were looking at zero knowledge and it turned out that lots of things can also have proofs that are in a zero knowledge kind of thing. And then there were a bunch of you know more exotic variants of interactive proofs with multiple provers with oracles and so on. I think that throughout that time the general idea was that interactive proof was just an interesting extension of a normal NP normal mathematical

proof. You can't do a lot more but there are interesting things that you can do more and that's basically how I think everyone definitely how I looked at it. So you're talking about sort of before before the sum check protocol right before the sum check protocol >> the thinking was that you could do more than NP with interactive proofs but you know maybe it was just some low level of the polinomial hierarchy or something >> even less that just a little bit more it's sort of like a randomized NP which is slightly more than NP I would say that was the normal way people looked at it >> okay >> and then for me uh the interesting point came when Lipton Richard Lipton had this uh interesting proof of what's called random self-reducibility or you know selfcorrection for the

permanent function for me I couldn't believe that he could do that and the reason I couldn't believe that he could do that because I knew that one if you can do some kind of random self-reducibility you could have some kind of interactive proof that's something that I proved in a much smaller much narrower sense a long time ago and then of course the permanent is known to a very difficult function. So my initial reaction was oh there must be a mistake there and I looked at it and of course there wasn't a mistake and I saw that yeah that's why my original proof didn't really extend to it because you know he has few things rather than one and so on but still it seemed to me that it

doesn't make sense because you could still get an interactive proof and then I could get some kind of an interactive proof. So, one of the more exotic kinds, not the vanilla type of interactive proof, but all the exotic ones were still considered to be just a little more than NP. And if you're interested in like what's called oracle results, what could be imaginary world where you separate classes in imaginary words, you shouldn't be able to prove anything like that also. So that basically took the same ideas but also now put them into an interactive proof kind of system and and wham you get a result that was surprising because suddenly you could prove something that's very in complexity terms that's a difficult function which previously no one thought

that you could do and that was the interesting thing about the LFKN paper that for the first time you had some kind of interactive proof for a difficult function >> and so are the are the roots of kind of the arithmetic ization technique. You would attribute that to the Liptin paper or >> so I think it goes even farther away than the Liptin paper. There was a paper I think of Bieber and Fenbound. So the ideas were in the air probably Manuel Blam is the person most responsible for having these ideas in the air a lot of places but each one of them was used in a little place and in some way it was always very very interesting for everyone. So everyone was trying to use it

>> but I think Lipton found a really convincing use of that technique and I think the interactive proofs are an even more convincing application. >> It's amazing to me that you know the very first paper LFKN to surprisingly show the power of these interactive proofs had exactly the right protocol that we're still using today like with no changes at all. It's like that that you went from kind of zero to exactly the right thing. And I don't know, maybe that's a statement about um the right hammer's the right hammer, but it just sort of came out all at once right there, even if it maybe took a little more time to, you know, work its way into uh actual systems or whatever.

>> So I, you know, I think the basic idea of, you know, you have two things and you need to prove only one, you know, intermediate point to prove two different points. That's a very general idea. I think in computer science whenever you can take two things and combine them into one problem that you continue you're very glad and if you have the algebraic technique which is what we are doing it's almost natural I would say I'm not sure that it's going to be the last word of course right but uh >> I actually have pretty strong confidence it uh it's here to stay uh in its current form even yeah >> so I guess there's two follow-ups I want to ask the first one this I mean this is a story that I think is well known to sort of um theory see us old-timers but

for the younger generations and for people in other fields um could you just talk through the history of you know LFK like email vacation these kinds of things. So >> the truth was that I I found the basic protocol with these kind of you know multiprover systems something like less than a week before I was due on a long trip to South America. I thought it was interesting because especially because it showed a result that was non-relativizing which is like very few of these. So, you know, I wrote it down. It was like one page and in email, not one page in Latte or anything like that. One page in email and sent it to maybe a dozen people, you

know, people I knew would be interested like Avi Bai. And then I went to South America and of course no internet then hardly phones. Phones were very expensive. So I could, you know, I had a phone call once in two weeks, let's say, with my parents. No, I had no idea what was going on. And apparently, you know, that point Babai and L for now who was there and a student at that time actually managed to get like normal interactive proofs rather than, you know, exotic ones. And then they wrote down a paper and then uh Adish Shamir managed to generalize it further to the right basically class which is bespace and all that happened when I had no idea what was going on and the only thing

that I knew that at one of my I don't know bi-weekly phone calls with my parents my mother told me I met a victin again at the parking lot you know an important parking lot and he told me to tell you and then she took out apparently some piece of paper that Abisha mere show that IP equals P space. [laughter] So that's what you know she just read this from a paper. I've been told to tell you that. [laughter] >> And what did you think when you heard that? >> I said, "Oh, wow. Great. Oh, this is such a nice extension of I I had no idea of course how we did it. And I didn't know even how they managed to get it down to normal interactive proofs rather than my Oracle proofs. So I thought that was amazingly nice. Had I been a more

serious researcher and worked on it more, maybe I could have also done it. But I wasn't. Don't >> I wouldn't change I wouldn't change a thing. No. >> No. I mean things are going great. >> So with with all of the follow-up developments, the PCP theorem and all of that, were you following along? Did you think about continuing or were you had just moved on to communication complexity or or other things? >> So for a few years I was definitely following. So I was really interested in the PCP work and then definitely in the things that came before it and X work and so on but I just didn't have anything to contribute. So I did do other stuff at that time but you know I really would have liked to actually keep on doing you know everyone said oh you know I had all the techniques I was at

the right place why didn't I do that but you know other people did it right so >> well yeah >> I mean I another thing I would say um is as the focus moved to PCPs and hardness approximation the techniques moved away from the sum check protocol like the whole point of a PCP is it's non-interactive Right. And so the techniques, I mean, obviously they're still algebraic, but they did change and and so you had the right techniques for the interactive setting. I don't know, maybe uh maybe it was perfect. You you brought us the sum protocol with uh LFK and that's what we we needed.

>> You know, you try to do a lot of things. You succeed in only a tiny little fraction of them and you're happy and for with a tiny fraction succeeded, right? That's that's research. someone who doesn't accept the fact that he will usually fail in anything that he tries to prove is not going to be happy as a researcher. >> That's great advice. Justin, I wonder I wonder so getting back to snarks and the role of the sump protocol in them. I wonder if it might be good to do a little bit of background. So why in your opinion is the sum check protocol so uniquely suited um to practical snark implementations and then maybe kind of before that as background just we can talk a little bit about sort of what you know snarks are like what a little bit more formally or a little bit more in

detail do we mean by the interactive protocol and then what's the end in the snark for and then yeah maybe talk about some check >> so a a snark is a way to prove that you know some data where the proof is really short and fast to check. So the essence snark means succinct and succinct just means the the proof is really short and fast to check, right? And and what do I mean by short and fast to check? So there's always a trivial proof which is the data you're proving. You know, you could just send the data to the the verifier and the verifier can just check that the data satisfies the property you're claiming it satisfies. That's the trivial proof. I guess a concrete example here would be, you know, suppose you want to know the pre-image of something under a cryptographic hash

function, right? So >> I know I know a file that's a gigabyte in size. When I apply the Shaw hash to it, it spits out, you know, this particular value. >> The point is, if you if you send me the file, then I can just run the hash function myself and see if you're right. But the question, I guess, is is there anything shorter and easier to check than just that? >> That's exactly the point. A snark proof would be uh you think of it as as you know kind of compressing this this big file you're claiming to know down into something really tiny. You know maybe it's like a kilobyte instead of a gigabyte. You know you've both squished the giant file down to this tiny proof and checking the proof is much faster than you know had you actually sent the gigabyte file and and hashed it to check

it. So that that's what sickness means. The n in snark means non-interactive. So that means the the proof is just something you can write down uh you know post it on a website for someone to download. So SN ark the ARK just means that if the prover is cheating and lying and doesn't actually know the data it's claiming to know, it's not going to be able to to find a convincing proof of this false claim unless it can break a crypto system or something like that. >> So here here's what's kind of like feels ironic or confusing at this point, right? Okay, so it's a proof that some statement is correct or some witness.

Uh, and you talk about being non-interactive, like you could just, you know, post it on a blockchain or something like that or I guess like in a textbook. But then that was exactly the kind of proof that no one was talking about where interactive proofs allow you to do more interesting things. >> So, how come we started talking about interaction and now with snarks, we're just back to that same old [snorts] kind of non-act proof? Like, how do I how do I square the circle there? >> Yeah, let me try to try to explain that. So, um, the classical proof that is in a textbook, if you're trying to prove a false claim, there literally will not exist any convincing proof of the false claim. With a snark, there will exist a convincing proof of false claims, but they're almost impossible to find.

They'll take you millions and millions and millions of years to compute because that's what's required to break the crypto system that's, you know, security of the snark is based on. So, how do you actually build a snark? Okay, the short answer is you take an interactive proof like the sum protocol from Gnome's paper and you combine it with cryptography to get rid of the interaction and also to do some other stuff. Let's not worry about it. So an interactive proof is like a building block. It's like a component of a snark. Uh and you should think of interaction as a resource. So the other component of a snark is something called a commitment scheme.

This lets you um take a giant file like this gigabyte file you're claiming to know and rather than sending it in full to the verifier, you can kind of stuff it inside a a teeny box and just send like the teeny teeny box and you as soon as the verifier has that box, you can no longer change your mind about what the giant file is inside of it. >> So like we already mentioned like one very simple type of commitment which would just be you hash like you could take a big file and hash it down. Like that is a that is a type of commitment. In snarks, maybe you want commitments that have additional properties beyond that. But like that's a commitment, right?

>> Exactly. Exactly. The two components of a snark are basically an interactive proof and a commitment scheme. My best explanation for why the sum protocol is so useful in snark design is the following. Committing to data is expensive. You have to like do something like take all this data and hash it and that takes time. On top of that, after the untrusted prover commits to all that data, it then has to prove that the data inside the commitment is like the right data and not some garbage. So roughly speaking, the less data you commit to, the faster it is to commit to it and also the faster it is to prove that the data you commit to is good data and not garbage data. And so the subject protocol is a tool to minimize the

amount of data you commit to while still sort of keeping the verifier nice and fast. One other little piece of intuition which gets back to um I was commenting that the PCP direction kind of diverged a little from the sum protocol. So the way snarks historically were designed the very first snarks people took what's called a probabilistically checkable proof which is not an interactive proof. It's another kind of non-interactive proof and then they added some cryptography. They added these hashing based commitment schemes on top of it and that's how they got their snark. So it was not interactive proof plus commitment scheme. It was uh PCP plus commitment scheme. But when you put the the PCP and the commitment scheme

together initially you get interaction. This is called Killian's protocol. If you directly take a PCP and a commitment scheme and you do it you you get a succinct interactive argument. The commitment scheme brings back the interaction basically and then you have to remove the interaction with cryptography via something called the fiat transformation. >> Sorry Tim can can I try to say less? >> Yes. Yeah. [clears throat] So yeah, so so Dustin is I think talking about height how it sort of really works the way you get it. But I think at the top level one of the thing that you can get once you have the whole idea of interaction and randomness and allow for error and once you allow yourself some you know more exotic definition of what a proof means for example argument rather than proof. So you know it may be

possible to cheat you if you had infinite amount of computation. you get a different thing that you can gain by using all these new definitions of proof and that is the fact that you can have very very short proofs of long stuff. So normally if you're just looking at like normal notion of proof if you want to prove something about a gigabyte the proof will have to be at least a gigabyte long because you will have to look at each one of the bits and this kind of thing once you allow yourself the freedom of these exotic and more relaxed notions of proof but which are still definitely enough for anything you have in the real world then you can have a very very very succinct proof very short proofs and so you don't need all these gigabyte you need much less than that and that's a new thing that you

basically gain from these kind of proofs let's say and this world does come I think conceptually from the world of PCP which did itself come from the normal kind of interactive proofs but it took a little bit of turn as Justin said and I think that's the basic new thing that you get if you don't want to look how that is done internally it's very difficult to me to say why is check some so useful because I never thought of this as anything that could be practical by any stretch stretch of any mind, right? It was highly theoretical and I was sure it will never uh become useful.

So when I was there, it was very very difficult to just do RSA encryption. I mean, you really had to work a lot to optimize your C code. So you get something that worked within I don't know a minute or something. So it was very difficult. But I think the basic idea that allows you take one for two. So you take two pieces of data and you combine them into one piece of data. That's a very useful building block. So you know it's better to combine three to one but usually it takes you more effort. >> Yeah. No I mean so what's the simplest sort of example of two for one the way that you mean it.

>> Okay. So so that now goes into the techniques of that right. The normal thing is let's say you want to sum function up over all 2 to the n binary numbers. So basically that sum is you sum for all the the strings that start with zero and then you sum for all the string that start with one and then you just need to add these two numbers. Right now you have two sub problems rather than one original problem. Now the nice thing about proofs you can take these two sub problems and combine them into one sub problem. And the way you do that once you have this kind of algebraic encoding then you basically can take sort of a like a random combination of these two subpros and get one problem in that and there is this

algebraic structure that gives you a guarantee that if you can solve this one sub problem correctly then it must be true that the solution that you provided for both original sub problems are correct. And that's sort of a mystery how you know one piece of data is suffices to actually attest for two subpros two different sub problems. And that's like basically the the mystery or the beauty of this algebraic properties that it actually does work that way. >> And one thing I love about that explanation is you know you mentioned earlier that one way to think about a snark is you give up a little bit on sort of correctness like on the on having a foolproof proof. You accept a kind of, you know, for all practical purposes negligible chance that you are

incorrectly tricked by a false proof in exchange for something you could never do otherwise, right? These very short proofs of sort of long statements. And in that random combination argument you gave, you can already see where the kind of relaxation of correctness comes in because if you get very unlucky with a particular random combination that you choose, maybe everything becomes zero. I don't know, something like that. then all of a sudden maybe there are ways that you get sort of tricked um by combining the problems in that way. Is that right? >> Yeah, that's exactly right. So the algebraic miracle that we talked about that if you're correct on this one piece of combined data, you must be correct on the two original ones. That's not 100% true. That's true up to some very small probability of error which you need to

always take care of. Whenever you have a real system, you need to make sure that the error becomes small enough that you're not worried it will happen in real life ever. But that's already a point where once you actually follow the proof you see ah there is a probability of error just here >> and now Justin to finish talking more about why is some check so uniquely suited in your view >> for the snark design. So you referenced the idea of treating interaction as a resource and so my understanding is that you know the sum check protocol is in some sense the most voracious consumer of that resource of everything out there right so you know nom I think you referenced this idea that with a constant number of rounds interaction and randomness doesn't buy you that much but then the sum check protocol shows

that if you have as many rounds as you could possibly want in effect right n rounds or what have you that then actually that's when magical things happen so Justin, should I think of it that as it turns out with other cryptographic techniques, you know, like the fiat shame heristic you mentioned for kind of flattening interaction and non-interaction given the existence of that toolbox, interaction is a relatively cheap resource and then am I understanding correct that in exchange for using more interaction so why is it that then you wind up having to commit less because of that? Is there intuition for a fundamental trade-off between commitment costs and sort of interaction costs if you like?

>> Yeah. Uh I think there's some intuition for that. The sum check protocol interactive proofs they don't use cryptography at all. Their information theoretically secure when you run them interactively. You know there's no cryptographic commitment scheme. It's it's nothing. And so you could think of it as like an extreme case of a proof system using no cryptography. Whereas cryptographic commitments are expensive cryptography. Right? So if your goal was to kind of prove something to a verifier, keep the verifier cheap, nice and fast without uh committing to using a lot of cryptography, the subject protocol is exactly what you want to use, right? It's at this extreme end.

It's information theoretically secured. It has no cryptography, but it's very powerful. Why is it so powerful? It's because of the the interaction and the very small probability that the verifier actually gets tricked. So that's that's one piece of intuition. And then you know the initial snarks they went through PCPs right but the challenge in building a PCP is the reason the sun protocol doesn't give you the best PCPs PCPs are not interactive right so the hard thing about building a PCP is to like kind of get the interaction out of the sun protocol but then when you turn the PCP into a snark interaction comes right back and you got to apply fiat shamir so if you're going to use fiat shamir anyway there's no reason to you're removing the interaction twice if you go through a PCP right you remove

to get the PCP and then you turn the PCP into a succinct argument but now it's interactive and you fiat again you should just remove the interaction all in one shot so that means you should build your interactive thing with the protocol and only apply fiat shmeir once at the very end and I think that's where people are moving to today as the protocol kind of um takes off a little bit in the implementations >> great so so let me use that as a launching pad just the sort of theory to practice arc that we've seen with snarks which I think all of us find sort of pretty remarkable. No, I think your viewpoint was I would imagine the common one certainly through the 20th century and even well into the 21st that these were a you know fascinating but sort of theoretical construction. So kind of the

same question for both of you. I'd love to hear both of your thoughts. So what was the point at which you were like oh my goodness this might actually be like real like no I remember we were on a panel together not that long ago. I don't know if you remember saying this, but you said like if snarks could be made practical, anything could be made practical. [laughter] And I know that was part tongue and cheek, but there is still some truth to that. So when when did it become clear to you that this maybe was actually going to be important technology? To me, I have to admit that no sooner than when I started working for Stark Wear. I was talking with Ellie and I heard that they actually have a company that actually building itself on these kind of Starks Nar and they were raising serious

amounts of money and you know and Ellie was very serious scientist and he has very serious business people working with him and I was hearing what they were doing and I said okay I believed it. I mean I can see that they actually had like a system working already putting stuff on Ethereum and I said okay it works. I see that it works. I was amazed that it works. Definitely before that I did not believe that it could be made practical. Definitely not in a way that anyone would put his money into it. So for me this like four years or something like that. Not more than that definitely. [laughter] And and Justin, how about you? Because correct me if I'm wrong, but I'm guessing, you know, your initial foray into thinking about sort of, you know,

streaming verifiers. I'm guessing the motivations there were primarily scientific like this just seemed like a important theory question. You might have had your own arc sort of realizing that this work and in particular your work could really have a big impact on practice. >> Yeah. Yeah. That uh it was it was a journey. So the streaming stuff it's like those protocols were practical but they're for such specific problems you know no one's going to bother to use this right and then the general purpose stuff this GKR implementation um during my PhD and things you know the story we told at the time was like Amazon cloud computing is going to return a proof so that people don't have to trust it and I knew like that's just a story we write in our papers because nobody's going to pay for like the millionfold overhead it

was worse than that at the time you know to get that proof right they're not going to make their cloud computing bill a million times bigger and you know there were some very specific things like matrix multiplication or something where you know would be practical but that's it's like too specific right so the change happened with Zcash in particular was kind of the first blockchain related deployment actually interestingly there sickness is much less important than ZK which is like for privacy but now today most of the applications are more sicknessoriented than privacy oriented although the pendulum could swing back I hope it does have some point what really changed was blockchain applications and and not the technology. That was the big jump for me

uh was watching other people deploy these things. And you know, I like to say blockchain is like the perfect setting for this technology because number one, you need the adversarial security guarantees because everyone in the world has billions of dollars of incentive to like cheat the blockchain and, you know, convince the the world computer they have billions of dollars of tokens when they don't. And two, the statements you ultimately often want to prove in blockchain settings are so simple that even when these provers are millions of times slower than you know running the computation with no proof, you can still run the provers in a reasonable amount of time. So that combination was just remarkable and it's exactly what this technology needed to actually make its way out into the world and it will ultimately give it enough

time it'll spill over to other things as well. It'll just get fast enough to to do that. >> Yeah. When people talk about things like, you know, millionfold overhead, I often like reframing it as like uh 30 years of Moore's law, I don't know if those numbers are exactly right, but that's sort of ballpark, right? Which means like, okay, as long as you're comfortable using a 1995 computer, like you can actually prove it with a 2025 computer, right? And it's like, you know, computers are obviously way better than 95, but like I was doing some useful stuff with computers like [laughter] 95, right? [clears throat] Was it wasn't useless. So, >> right. And we we take another couple orders of magnitude off that and now we're talking about you know 20 years or something. Exactly. Exactly.

>> Although I have to say that a million or a billion fold sounds optimistic to me if I'm looking at it from the eyes of like 20 30 years back. It would seem to me that the numbers like 10 to the 50 or something [laughter] over it. So so a lot of work has gone into the technology making it not 10 to the 50 but 10 to the 20 or or 10. >> Yeah. It's been a it's been a long [clears throat] long and productive road. I guess [laughter] you know may I feel like Gnome you you think that you know like the the phenomenon that subject is based on is like so clean that maybe there's clearly a right way to use it and of course it would come out from the very first paper like fully formed and perfect. Actually my my view is I'm sure though fans is

something better. So I mean there's no way that this is the last word. I mean right maybe it will have some of the ingredients you know two for one is a common ingredient algebraic is a good ingredient but they will find something better >> Justin aren't you proving optimality of it in various senses these days >> yeah so in this communication complexity setting certain like very limited communication models you can actually prove I I don't know if the constant factors are right but like up to constant factors the sum protocol is optimal that to me is actually pretty strong evidence besides my personal you know journey of having just used this thing over and over again for for 15 years or whatever >> is optimal in the sense of proverifier communication or >> exactly yeah so you got like Alice has X

Bob has Y Alice doesn't know Bob's input uh Bob doesn't know Alice but you do have this untrusted Merlin who knows both and wants to convince them that f ofxy is something and and you can prove that in certain limited settings the subject protocol gives the optimal trade-off between how much Alice talks to Bob and how much Merlin talks to Bob or or whatever I find that very compelling uh evidence and I suspect that even in in you know without limiting the model so much it actually is still optimal but you'd have to make breakthroughs in communication complexity to show that. So I think it's just the right thing in a cosmic sense.

That is my take. Yes. >> I wanted to talk a little bit just about what you've been up to more recently. Gnome in a development that is extremely good for the blockchain space. you've been spending some of your time in cycles thinking about scientific problems that come up. So, you know, I'd love to hear just a little bit about how you got into the space and sort of what are you most excited about of the different work you've been doing in it over the past sort of two or three years. >> So, I have to admit I probably got into it by accident. So, you know, I finished being Gadine. I was looking for something new to do and El Sason came to me basically after you left them and suggested that I could also be of help and came to me with some you know

interesting questions and the more I talked to him the more interesting question it seemed that they were there. So one of the things that I very early understood that in all this uh some check stuff cryptography stuff I'm 30 years behind and they have lots of people who are amazingly good at this so I sort of did not get into any of the more you know proof oriented stuff there but as you said my new work is basically economics and computation and as usual many companies don't have people who come from that field so somehow one of the thing that I've often uh found which always amazed me that you have these brilliant programmers and they have 20

different parameters and they don't really take it to their hearts that one parameter which is price is sort of more important than the 19 other ones and and they just don't think that way. I mean we don't think that way you know talking at myself as a programmer before I was looking at the more of the game series stuff. So I was looking at more of the questions like you know fees you know how how much money do you take from the transactions when they compete for block space what's the right way to do that and of course you look into that there are amazing questions in game theory amazing question just algorithmic questions about how to run it if you have multiple dimension now the algorithmic problems become really fascinating and should you even look at that and what's the incentives so lots

of questions of this four I think there's another class of questions which I'm really fascinated ated with although I can't say that I have any success in really solving them but I think someone who at least thinks about them is really important for a company and that's like the whole tokconomics I would say like the macroeconomics of blockchain a lot of things there don't completely make sense from a macroeconomic point of view they have their own little you know way of looking at things in their own world and we must understand that and macroeconomics by itself by the way is not like a science like microeconomics that we've studied and we know how to use and it's very, you know, very clear and very clear how to apply it to new situations. Microeconomics is still

somewhat of a voodoo kind of thing. You don't know what the right models are. You don't know how that really relates to inflation, to employment, to stuff, to growth, to stuff like that. And when you try to apply that to the kind of problem that you know any blockchain that wants to have a token and figures out how to handle this token does it need to mint new tokens burn new tokens what does it mean in a macroeconomic sense you can't really just use macroeconomics as far as I understand and unfortunately I don't know enough of macroeconomics but it doesn't seem that the more that I'm learning the more that I can actually help and figure out what to do but I think that's really important because somehow at the end of the day this is what is going to affect

society before actually the details of you know the fees and and how do we handle congestion and so on I find that currently the most fascinating stuff even though that's the stuff that I have least to say to actually tell anyone except trying to organize things and putting them in a methodological way that is not like new research because everyone either agrees with it or already knows it or doesn't agree with it. >> No, I think that's a great point. You, if memory serves, you wrote a nice kind of survey blog post around kind of tokconomics and how you were thinking about it maybe a year plus ago.

>> That's true. Yes. >> Yeah. So, I would recommend that to listeners. >> So, I tried to put it both the micro and the macro into the same kind of footing, the same kind of framework. >> And and I do agree with you. I mean, I I think for those of us that care a lot about this technology, my guess is like the macroeconomists are not coming to save us in the sense that like I really think we kind of have to do it or redo it ourselves, which as we were talking about earlier is kind of what we do in computer science anyways. We kind of just plunge forward and do some reinventing of the wheel. But then eventually, you know, we start doing some novel stuff. At the very least like as you say we just I think we have some work to do just having clear guidance

about how to make these kind of design decisions in our protocols. >> Okay. So you say like the fee stuff is less important but still >> no still it's very important. you have to have a functioning market for things to work right and it's it's not less important but I think we sort of understand it now in the sense that the details may be less important at this point right so there's still lots of questions about what kind of efficiency you get what kind of incentives you give you know how good everything is but it's not whether it will you know make or break anymore I think we sort of have some kind of reasonably good idea how things work a lot of it because of some of your work Tim that basically took the very smart ways that let's say protocols in Ethereum were designed and put them

into kind of language and notions and ways of thinking that we can think about scientifically and abstractly and I think that was really useful. >> Well, thanks for the kind words. I mean, you've done a couple things that I did not do since then which I'd love to give you a chance to just talk a little bit about that I think are are really important. you know, so in the work that I did around EIP559 and Ethereum transaction pricing, I just looked at the sort of incentive properties and I did not really try to articulate, you know, is this doing an efficient allocation of block space. So I didn't do any welfare considerations which you have a couple papers now that I think would make really really nice contributions. So that's in some sense analysis of an existing inproduction system which is very important. But then

you know also one of the superpowers about being a theoretician is you really can reason formally about systems that don't exist yet. And so you have some other work on multi-dimensional fees which you know there's a little bit of an example in Ethereum where kind of you know normal transactions and blobs have their own independent fee markets but for the most part >> the way blockchain protocols um work is they kind of just smush everything down into just one notion of gas and just price gas. And so you I think have one of the more illuminating papers around the pros and cons of actually you know do you want to actually do a single dimension or do you want to do multiple dimensions? So if you're up for it a little bit of an elevator pitch on each of those two lines of work I think would

be would be fantastic. >> Okay. So so let me start actually with your work. >> I'll give you those $20 later [laughter] after after we're done. >> So so this protocol that Ethereum used the EIP 1559 is really an interesting protocol. It combines a lot of stuff there in a sort of elegant way. I have to admit that the first time that I saw the definition of it, I saw all these amateurs, they should really give it to us, the AGT kind of people and uh and then you know we'll figure out what's going on. And then after your paper that actually analyzed it and show what was good with it, the kind of collusion necessary and so on, I said, "Oh, wow.

Actually, they knew what they were doing." And I think that people from the academic side are really a little bit baffled about how did they know what to do. So obviously they had amazingly good intuition and obviously they read lots of simulations and obviously there are very smart people there but still they definitely did not do let's say the kind of analysis that you did regarding incentives. Now similarly in one of the papers that you mentioned that I did we tried to analyze you know does it even really allocate block space well and it turns out that it does and it turned out that some of the things that it actually uses are sort of necessary for it and that was the second time that I got the same kind of impression okay so they

really did something clever how did they know how to do it because you know it's not trivial neither the incentive stuff that you have nor the efficiency analysis that I took but still the intuition of plus simulations plus discussions of enough smart people apparently managed to get that so I find that really fascinating that you know it's a good protocol really good protocol and how did they know how to do it now I'm less sure about that by the way once we're say going to the multi-dimensional stuff so multi-dimensional is difficult I don't think we completely understand it so we're getting more and more papers that understand it more and for example one of the things that I'm really not sure.

I'm not sure what type of efficiency you get with, you know, this two-dimensional thing, blobs versus just normal gas. Does it even work or not? It's not clear to me. So, that's one of the things that I'd really like to to to figure out. So, we know some senses that it works, but really I think the more interesting senses you take time into account, you take some kind of worst case into account. We don't know what's going on. So they succeeded twice let's say in from my point of view in doing the cle the correct thing without previous analysis maybe there's one thing that analysis can tell them to do how to do better or maybe not or maybe they got this right too I mean let's see it's a great point that even just the the the simple example of multi-dimensional

pricing that is in production now even that one we really don't understand from sort of a formal perspective so graduate students and other aspiring researchers out there could Nice problem. Nice problem to look at. >> And yeah, maybe just to add a little color to the second example you mentioned about how did they know that it was going to be so well cuz like the the the work that you did with Moshi Baboff, this also really surprised me for the Ethereum nerds in the audience. So Ethereum block can have variable sizes, right? So back in the old days preip 1559, they all had the same size, you know, 15 million gas or whatever.

And then one of the innovations introduced in EIP559 was allow to blocks to be bigger by a bounded amount or smaller than some target. So 15 million gas would be the target say but you could go up to 30 or be as small as zero. [snorts] And my understanding was always that the primary reason that you would allow blocks of various sizes would be to provide onchain feedback into a price controller into sort of a you know local search algorithm trying to find the market clearing price. And you know if you could somehow magically know the market clearing price maybe you would keep the blocks a fixed size because you don't need to do the learning. But then what Nom and his his co-author Moshi Bababov show is that actually in some sense the reason that

EIP559 does guarantee near optimal welfare is exactly because of this flexibility. [snorts] So back at the time I was doing that work I was basically just like lurking in like Ethereum Discord R&D chats basically. And as you say, there's a lot of like super smart people there. And there was speculation that like this would also probably help smooth out sort of variations in demand, but I don't actually think that was the main reason that you have the variable size blocks. So that's one thing that was so cool about your paper was like you get the welfare guarantee and by the way, you wouldn't have it but for these variableiz blocks. So I just thought that was that was super cool. your earlier complexity theory work um presumably very loosely motivated by

reality and and applications or whatever but then your AGT work it sounds like first order phenomenon was you know the internet stuff happening in the real world were you always of kind of both minds and you know both flavors of motivations for your work or did that do you feel that that has shifted over time >> no I believe that I always so I really think that at heart I'm a computer scientist. I'm not a mathematician. I really have the application of computer science. I definitely have the instinct to look at the theoretical aspects where you need it. But I I don't feel that I ever you know looked at complexity that I didn't feel was connected to actually real system. My bringing is not as

mathematics but a computer science. I you know I like to program and so on. That's always been my point of view. And you know sometimes you need to actually do stuff. Sometimes you have more interesting theoretical things and then you do need to go down the wormhole, right? >> No, that's super cool. I mean that's uh the power of our our field, I guess. Even if the the connection to reality is tenuous, it's still still there. We're looking at computation that's like a phenomenon that exists in the physical world. You know, you can be at different ends of the spectrum and still just be doing, you know, great theory work that eventually finds its way into practice.

It might be 30 years. But um no >> I agree Justin it almost feels like cheating being a theoretical computer scientist sometimes where like you both you know if you want you can actually really have a big impact on technology on the other hand you also get to work in sort of these deep beautiful subfields of mathematics at the same time. >> Yeah. So the example that I always try to give people is like Raven's original work on factoring number finding if a number is prime by some sophisticated mathematical properties rather than what you would expect if you know if you studied elementary school. And it seems like number theory completely will never be practical for anything completely theoretical and then it's not only practical but it's like the basis of you know billions of dollars everywhere and almost you know from armies to companies

to people everything and and that's really amazing to think that something that was after I was born was the first time that people start thinking about it in completely theoretical ways and now it's such a huge part of the economy and I think that's not like you know an isolated incident all the time. We see that in theoretical computer science and that's really I think probably we are sort of lucky to be in the right generation for this in the right area. >> Yeah. And actually especially you know for doing work in you know the blockchain/web3 world. I mean this feels like a very special window to me. It's just very easy to imagine students 20 years from now being angry at us saying everything was so easy back when you worked in the field. No one no one had

asked even the most obvious questions. You know, of course, there there's a unique set of challenges when you do work in a very immature area as well, right? It's a different set of challenges. >> That always reminds me as a graduate student, I think the general feeling about graduate students my age was that the people three years just ahead of us, in front of us, you know, people like Shafi and Sylvio and Avi had the world in front of them and everything was already finished by the time that we got there. [laughter] And I suppose that every you know every cohort of graduate students will feel the same forever. [laughter] >> But yeah again but being close to technology I mean there are always new ways of technology right and pretty reliably they require in some case completely new sub fields right of

computer science and theoretical computer science. So even if you're too late on one wave of new technology there will be more in your career. So um like you say feel very lucky to have that. So >> assuming that AI will do everything for us starting from tomorrow, right? So [laughter] >> well that was a possibility. Yeah. But take it day by day, you know. So >> exactly. >> No, it was great talking to you. >> Okay. Very nice talking to you, Justin. And >> the big thing I learned is I really have to figure out where this parking lot in Jerusalem is. [laughter] That sounds like a pretty special place. So >> thanks so much for doing this. We love having you on here. It's fantastic. So >> thank you. It was It was really nice.

All right. So, we talked to Nom about a lot of things. One thing just this idea of um arithmetization which is sort of crucial in the subject protocol and that being sort of in the air and one thing you and I do have experience with but if you're not in research maybe you don't have this as much where there is there's just like a sometimes a moment in time where you can just feel that a certain idea or a certain technique is about to find like a killer application and you do find lots of experts in the area all simultaneously trying to figure out exactly what it's going to unlock. It sounds like that was sort of, you know, that moment in time for that idea when Nome came up with some check protocol because that's definitely one of those ideas where I'm just like how did anyone

ever think of this in the first place. It's like once once once you write it down you're like oh wow that feels really powerful but like just coming from a computer science perspective it's very sort of you know 01 very binary it would seem but then to you know have this kind of algebraic sort of polinomial approach to it just seems like a conceptually a huge breakthrough. Yeah, absolutely. And and you know we now sort of have abstracted out what this technique is like really doing and you know we know that technically you don't really need polomials. What you really need is an error correcting code with a certain property called multiplication property and polomials are just one example.

>> What's the multiplication property? Uh it means you can um take two code words and multiply them together coordinate-wise and you get another code word if not in the same code than a closely related code. And so you apply the sum protocol you know to a product of at least two things. And so if there's not a product of things the whole thing is trivial. Uh, basically if you phrase it in that abstract way, uh, then it makes more intuitive sense to me, right? It's like the whole point of snark verifiers versus sync verifiers is any little teeny thing the prover did wrong needs to be detected by the verifier. So you need this sort of distance amplification property that you know one tiny mistake gets blown up to

something easily detectable. How do you do that? Error correcting code. I mean that's literally what what an error correcting code is. So at that level sort of I get it. But uh you know again that's with the power of hindsight. It's still amazing to me that this particular error correcting code from the polomials that we started with in 1990 or whatever is still the basically the best we know. There have been some papers bringing in some other codes but actually everything that's deployed in practice today is is still focused on on those polomials. And another thing that I thought was interesting, so for Nom, he boiled down the subject protocol into like one phrase, which was you can turn two into one. And he said something to the fact

like once I once it was clear you could turn two into one, then the whole thing became clear. >> What did you think of that summary as someone who's thought about this check protocol for a very very long time? >> Yeah, I think that's exactly right. And it's sort of amazing that that insight was there at the start. You know, I don't even think I had that view. uh for years studying and using the protocol where that that view became clear was there are all these other protocols that we use in in snark design every snark sort of has two components uh one we often call a polomial IOP the details don't matter but just think that's the sum protocol and the other part we call a commitment scheme or a polomial commitment scheme and that people think of as as something else there's

cryptography there like hash functions and stuff where there isn't any in the in the sun protocol part And so people gave all these commitment schemes where there there it was very clear like you were taking splitting things into two pieces and and munching the two pieces together into one. So now you have one piece sort of half the size you originally started and then only later did the snark people realize those other protocols are themselves the sum protocol just sort of the technical term would be like run underneath cryptography but let's just say you know the protocol kind of re reimagined in a slightly different way. So you're saying the subject protocol arises both in the polinomial IOP part and in the polinomial commitment scheme part or at least if you have a suitably general definition of what you mean by the sum

protocol. >> Yes, that's exactly right. And in fact I'm putting out a little survey soon uh titled like some check is all you need. And the point is not not only when >> just to be clear by little you mean 33 pages, right? So [laughter] >> well relative to uh the the number and and page count in the papers it's it's summarizing it. Fair enough. So you know the point is like not only is some check the right tool and you can wield it in very sophisticated non-trivial ways in this you know pop component it is also the right tool in the other components and so the whole snark is really just just sum check >> all right so so finally the interview touched upon the possible optimality or suboptimality of the sum protocol and whatnome said about it I was I was

reminded of one of my favorite quotes which is uh there's this old really old now algorithms book I think 1974 so before even I was born by Ajo Hopcraft and Olman which really just put down the blueprint of how every algorithms textbook you know including mine has ever been written since then and very early in that book there's a quote that says the most important property of an algorithm designer is that they are never content so you're always asking yourself you know can we do better right and I felt the spirit of that innome's comment where he's like this is just this protocol I just came up with right I mean there's always something better. So surely there should be something better than this. We're now 35 years later. So what do you think?

>> I mean I uh have pretty high conviction that there is not something better. Uh firstly let me say you know it's not obvious when you just take the sum protocol exactly how powerful it can be right there's highly sophisticated ways you you can apply it. Uh so there's a lot of work to be done even if it is optimal figuring out like the the right ways to apply it. There are also as I mentioned to gnome like specific limited settings where we know unconditionally you can't do better other than like constant factors and even even in like snark land you know where we don't know for sure that the subject protocol is like optimal in in any certain sense we can't be too far off from optimal for

trivial reasons right and you know if you look concretely right a snark prover that's proving it ran a computer program correctly like today it's under 100,000 times slower than just running the program with no proof of correctness, which 100,000 is still a big number, right? But like you can only take a factor 10 off that a couple more times before like there's just no way you're going to [laughter] take any any more factors off. And even what I like to say is, you know, these numbers sound big, but Moore's law has been like very impressive, you know, exponential compounding over the years, too. So, I prefer saying something like, "Oh, it's as fast as like a 1995 computer." Which to a lot of our audience that probably just feels like the stone age, but like I was using computers in 1995 for lots of, you know, good purposes and the web

existed and we're doing all kinds of stuff. So, obviously you'd rather have a 2025 computer, but if you have verifiability and the and the computational power of, you know, 30 years ago, it's actually not so bad. >> Yeah. So, there's already some applications where the 100,000 is okay. And as that number goes lower, we'll just see more and more applications kind of opened up. Again, I do think we'll keep seeing improvements, but I suspect it will not be in the sum protocol itself. It will be like how it's wielded. I would even go so far as to say we we know you can use any error correcting code with the multiplication property. It doesn't have to be lowderee polomials. I think we will keep using lowderee polomials. Even I'm a little less confident in that. And what what we'll just see is more and more clever

ways of finding nails for this hammer or you know um just ways to to wield the the hammer. So you asked Noom like like you know you did this you came up with this amazing proof there's this you know sequence of papers leading up to the IPL pspace paper that was definitely like first ballot hall of fame results in theorycs like why didn't you keep working on that and he he actually talked about how you know the PCP probability checkable proofs work he kind of followed along but just like he didn't himself have the breakthrough in that window and then but at some point he moved on to to other things. So what I would love to see is like a full circle. I want to see a paper where two of the authors are Justin Thaylor nom Nissan using the Sumcheck protocol in

some devilishly clever way to to hit some new nails. That's what that's that's what I would like to see. So get to work on it. >> We'll have to pull Nome back away from the economics. >> Yeah. [laughter] Yeah. He you might be able to you might be able you should be able to snark Bill. >> Okay. All right. Challenge accepted. >> All right. Excellent.