# Zero Knowledge Proofs and Blockchain Market Design

**Podcast:** web3 with a16z crypto
**Published:** 2026-08-13

## 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 to 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...
Hi, everyone, and welcome to First Principles, a series by the team at A16Z Crypto.
I'm Tim Roughgarden.
I'm the head of research at A16Z 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 Noam Nisan, a Knuth Prize and Gödel Prize winning 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 Thaler.
a research partner at A16Z Crypto, also an associate professor of 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.
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 PSPACE, 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 joining us, Noam.
Thank you for having me.
I wanted to start the conversation.
So your career has been fascinating with lots of twists and turns.
I'd say many more distinct chapters than most 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, what else?
Pseudorandom generators for space-bounded computation, Fourier analytic approaches to PAC 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 front of a field like that.
But my understanding is sort of, you know, 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 wondering 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 that like at that time?
So actually, I have sort of a story.
So obviously, the web basically hits the world something like around 1995.
Everybody knew that the internet was really like a major thing, the web.
But no one in academia was really 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 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 shifts, all the student protests, all the everything.
But, you know, my father was there with three children, and he really didn't notice even this huge cultural chain 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 we'll stop what I was doing.
And then I found myself in the 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 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 thing, this new area, and it was, you know, very easygoing, I have to admit.
One of the examples was, my father...
By that time, I was really worried.
Until then, I was doing normal computer science, very messy, understood what that means.
But then I was playing with this economic kind of thing, popular culture kind of thing.
He was very suspicious of that.
So my parents lived next to Avi Vigderson.
My father met Avi Vigderson, the renowned computer scientist, in the parking lot, and sort of complained to him that his son was doing this 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 the community, my own university, everybody just accepted it very easily.
And that's just a get another story and Avi Vigdrasen looking out for us in more ways than we can possibly imagine.
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 theoretical scientists would be 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 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 ground 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 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?
I started, I thought that I would 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 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 student graduates, then you have no one to 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, it was doing some kind of, I don't know, total cloud 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 actually, 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.
It's 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 story?
Yeah, this is the popcorn project, basically.
This is the popcorn project.
Because what's amazing is that was a paper I just stumbled on completely accidentally.
You know, I was out there, you know, in Jerusalem a few years ago, Noam, to speak at your 60th conference.
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 because 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 that feel prescient in hindsight at this point?
It seems a little bit related.
So you immediately figured out that if you delegate work to someone, you sort of need to check it somehow at that point.
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 can actually have some kind of a proof, like an NP-like proof.
So we already had these kind of ideas then.
But I think we're not thinking, of course, of anything like a blockchain kind of thing.
system, neither in terms of 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 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 related, really.
So in 1999, as we discussed, algorithmic mechanism design, the paper with Amir Ronan came out, made a huge splash 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 a mirror 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?
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?
I sort of wanted to work about incentives in computation.
I thought that was really interesting, how to get different computers to cooperate.
And I had no idea there was a subfield 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 Mironen came, and I told him, look, this is very interesting, somewhat related to game theory, maybe you can learn a little bit game theory.
And he got this big microeconomics, masculine et al-pay book, and he started reading it and telling me stuff.
And at a certain point in time, he realized that, oh, there is 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, you know, for example, Elias Koutsoupius and Christos Papadimitriou 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 Elias, and I heard about your work with Eva.
So I know that in some sense, your work is a continuation of Papadimitriou and Elias.
But from my point of view, there was this like three different threads.
because Papa Dimitri then was looking at a slightly other thing.
I really was 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 we're onto something here, because completely different people from completely different angles are looking at this general field.
And I think for a few years there, there was this kind of thing that were maybe five universities giving courses in algorithmic game theory or in economic to 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 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, it felt very exploratory, I thought.
Absolutely.
And I think, 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'll 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 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 south field of algorithmic game theory.
Yeah, it really makes it almost a community effort, right?
It's almost...
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.
Yeah.
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 that time.
So my decision algorithm was pretty simple, which was that, like, You know, Christos Papadimitriou, Noam Nisan, and Eva Tardos are all very excited about this field.
If I know it's good for me, I think I'm going to take advantage of being in the right place at the right time.
So I just feel very lucky 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 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 maybe to sort of set the stage, Justin, I was wondering if you wanted to tell your own sort of personal story about how you found out about the SumCheck protocol, what did you think of it, how has it kind of followed you through your whole career sense?
Yeah.
So I first encountered the SumCheck protocol in a course I took in undergrad, a complexity theory.
taught by Joan Feigenbaum.
There was me and one other student in the class, and Aurora and 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 centerpiece is the Sumcheck Protocol.
And the result from LFKN, so Gnome's paper from 1990 or 1992, which is 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, 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, Noam, your description of popcorn, you know, a distributed cloud already, already back then.
And so, you know, I had this hammer from that I learned about in Joan's class, and it turned out that everything was a nail for this hammer.
And so like all of these problems in the space 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 the SumCheck protocol, use SumCheck protocol, and you get this like, you know.
optimal protocol for proving that an untrusted prover solved the problem correctly.
So that's how I understood his power.
And because there were streaming algorithms there, actually, the work had a lot to do with communication complexity.
So Noam, your book with Yal Kushelevitz was like instrumental in kind of my own development and career.
So kind of these two threads that seem unconnected.
the SumCheck 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 optimal in some of these communication models.
Then I learned about these very powerful interactive proofs like the GKR protocol from 2008 that were using the SumCheck protocol as a subroutine 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 commitment schemes, and boom, you have 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 Sumcheck Protocol at the very core, my expectation is this is how SNARCs will finally, eventually in the coming years, eat the world and affect how we deal with trust throughout all of our digital infrastructure.
So that's my personal story coming to the Sumcheck Protocol.
And it started with two sort of independent feeling parts of your own career, which is LFKN and communication complexity.
And all of these things that felt unrelated.
turn out to come together.
So, Noam, I wonder 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 SumCheck 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 people, including Shafi, Goldreich, Mikali, Rakoff.
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 in many variants of it.
The most famous variant is a zero-knowledge kind of variant.
So usually people are so interested in the zero-knowledge kind of aspect of it, they forget that it's a 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 a 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 the SumCheck protocol, right?
Before the SumCheck protocol.
The thinking was that you could do more than NP with interactive proofs, but...
Maybe it was just some low level of the polynomial hierarchy or something like this?
Or even less than that, just a little bit more.
Sort of like a randomized NP, which is slightly more than NP.
I would say that was the normal way people looked at it.
And then for me, the interesting point came when Richard Lipton had this interesting proof of what's called random self-reducibility or self-correction 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 be 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 a 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 interactive proof.
So one of the more exotic kinds, not a 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 what's called Oracle results, what could be an 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 puts them into an interactive proof kind of system.
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 roots of kind of the arithmetization technique, you would attribute that to the Lipton?
So I think it goes even farther away than the Lipton paper.
There was a paper, I think, of Beaver and Seigenbaum.
So the ideas were in the air.
Probably Manuel Blum is the person most responsible for having these ideas in the air in lots 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 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...
work its way into actual systems or whatever.
So, you know, I think the basic idea of, you know, you have two things and you need to prove only one 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 were 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...
I actually have pretty strong confidence that it's here to stay in its current form, even.
So I guess there's two follow-ups I want to ask.
The first one, I mean, this is a story that I think is well known to sort of theory CS old timers, but for the younger generations and for people in other fields, could you just talk through the history of, you know, LFK and like email vacation, these kinds of things.
The truth was that I found the basic protocol with this kind of multiproover system, something like less than a week before I was due on a long trip to South America.
I thought it was interesting, especially because it showed results that were non-relativizing, which is very few of these.
So I wrote it down.
It was like one page.
and in email, not one page in Latinx 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, bye-bye.
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 with my parents.
No, I had no idea what was going on.
Apparently, at that point, Lassie Babay and Lance Forfnau, who was there, and a student at that time, actually managed to get normal interactive proofs rather than exotic ones.
Then they wrote down a paper, and then Adi Shamir managed to generalize it further to the right class, which is B-Space.
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 Avi Victor then 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 Adi Shamir showed that IP equals P-space.
So that's what, you know, she just read this from her paper.
Avi told to tell you that.
And what did you think when you heard that?
I said, oh, wow, great.
Oh, this is such a nice extension.
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.
I wouldn't change a thing, no.
No, I mean, it was very nice.
So 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 just moved on to communication complexity or other things?
So for a few years, I was definitely following.
So I was really interested in the PCP work and definitely in the things that came before it, NXP work and so on.
But I just didn't have anything to contribute, so I did do other stuff at that time.
But I really would have liked to actually keep on doing it.
Everyone says, oh, I had all the techniques.
I was at the right place.
Why didn't I do that?
But other people did it, right?
So, yeah.
Well, I mean, another thing I would say is as the focus moved to PCPs and hardness approximation, the techniques moved away from...
the SumCheck 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 so you had the right techniques for the interactive setting.
I don't know.
Maybe it was perfect.
You brought us the SumCheck protocol with LFK.
That's what 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 with a tiny fraction succeeded, right?
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, getting back to SNARKs and the role of the SumCheck protocol in them, I wonder if it might be good to do a little bit of background.
Why, in your opinion, is the SumCheck protocol so uniquely suited 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 N in the SNARK for?
And then maybe talk about SumCheck.
So 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 NARC means succinct, and succinct just means the proof is really short and fast to check.
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 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, suppose you want to know the pre-image of something under a cryptographic hash function, right?
Yeah.
I know a file that's a gigabyte in size.
When I apply the SHA hash to it, it spits out this particular value.
The point is, 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, you think of it as kind of compressing this big file you're claiming to know down into something really tiny.
Maybe it's like a kilobyte instead of a gigabyte.
You've both squished the giant file down to this tiny proof.
Checking the proof is much faster than, you know, had you actually sent the gigabyte file and hashed it to check it.
So that's what the sickness means.
The N in SNARK means non-interactive.
So that means the proof is just something you can write down, you know, post it on a website for someone to download.
So S-N-A-R-K.
The ARK just means that if the proofer is cheating and lying and doesn't actually know the data it's claiming to know, it's not going to be able to find a convincing proof of this false claim.
unless it can break a crypto system or something like that.
So here's what's kind of like feels ironic or confusing at this point, right?
Which, okay, so it's a proof that some statement is correct or some witness.
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 kind of non-anarchical proof.
Like, how do I square the circle there?
Yeah, let me try to explain that.
So 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 security of the snark is based on.
So how do you actually build a snark?
The short answer is you take an interactive proof, like the Sumcheck 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.
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 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 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 Sumcheck protocol is so useful in snark design is the following.
Committing to data is expensive.
You have to 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 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, not garbage data.
And so the Subcheck 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...
I was commenting that the PCP direction kind of diverged a little from the SumCheck protocol.
So the way SNARKs historically were designed, the very first SNARKs, people took what's called a probabilistically checkable proof, which is not 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 a PCP plus commitment scheme.
But when you put 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 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-Shimir transformation.
Sorry, Tim, can I try to say less?
Yes.
So Justin is talking about how it really works, the way you get it.
But I think at the top level, one of the things 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 definitions of what the 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 the 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 proof.
And so you don't need all these gigabytes.
You need much less than that.
And that's a new thing that you get basically gained from these kind of proofs, let's say.
And this world...
does come, I think, conceptually from the world of PCP, which did in 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 checksum so useful?
Because I never thought of this as anything that could be practical by any stretch of any mind, right?
It was highly theoretical, and I was sure it will never.
and become useful.
So when I was there, it was very, very difficult to just do RSA encryption.
I mean, you really have 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 to 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 in the way that you mean it?
Okay, so that now goes into the techniques of that, right?
The normal thing is, let's say, you want to sum some function up over all two to the n binary numbers.
So basically, that sum is, you sum for all the strings that start with zero, and then you sum for all the strings that start with one, and then you just need to add these two numbers.
right?
Now you have two subproblems rather than one original problem.
Now the nice thing about proof is you can take these two subproblems and combine them into one subproblem.
And the way you do that, once you have this kind of algebraic encoding, then you basically can take sort of like a random combination of these two subproblems and get one problem in that.
And there is this algebraic structure that gives you a guarantee that if you can solve this one subproblem correctly, then it must be true that the solutions that you provided for both original subproblems are correct.
And that's sort of a mystery how, you know, one piece of data suffices to actually attest for two subproblems, two different subproblems.
And that's like basically 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 The one way to think about a snark is you give up a little bit on sort of correctness, like 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 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 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 they do not worry 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 sum checks 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, Noam, 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, end rounds or what have you, 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 Chimera heuristic 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, I think there's some intuition for that.
The SumCheck protocol interactive proofs, they don't use cryptography at all.
They're information theoretically secure when you run them interactively.
You know, there's no cryptographic commitment scheme.
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 committing to using a lot of cryptography, the SUMCHEC 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 interaction and the very small probability that the verifier actually gets tricked.
So that's one piece of intuition.
And then, you know, the initial snarks, they went through PCPs.
But the challenge in building a PCP is the reason the SumCheck protocol doesn't give you the best PCPs.
PCPs are non-interactive.
So the hard thing about building a PCP is to kind of get the interaction out of the SumCheck protocol.
But then when you turn the PCP into a SNARK, interaction comes right back and you've 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.
You remove it to get the PCP.
And then you turn the PCP into a succinct argument, but now it's interactive, and you Fiat Shamir again.
Instead, you should just remove the interaction all in one shot.
So that means you should build your interactive thing with the SumCheck protocol and only apply Fiat Shamir once at the very end.
And I think that's where people are moving to today as the SumCheck protocol kind of takes off a little bit in the implementations.
Great.
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, 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, Noam, 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 can be made practical, anything can be made practical.
And I know that was part tongue-in-cheek, but there's still some truth to that.
So 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 Starkware, I was talking with Eli.
and I heard that they actually have a company that's actually building itself on these kind of stark snarks, and they were raising serious amounts of money, and Eli was a very serious scientist, and he had very serious business people working with him.
And I was hearing what they were doing, and I said, okay, I believe that.
I mean, I can see that they actually had 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 is like four years or something like that.
Not more than that, definitely.
And Justin, how about you?
Because correct me if I'm wrong, but I'm guessing, you know, your initial forays into thinking about sort of, you know, streaming verifiers.
I'm guessing the motivations there were primarily scientific.
Like this just seemed like an 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, 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 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 million fold 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 it would be practical, but 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, Sysignis is much less important than ZK, which is like for privacy.
But now today, most of the applications are more Sysignis-oriented than privacy-oriented, although the pendulum could swing back.
I hope it does at some point.
What really changed was...
blockchain applications and not the technology.
That was the big jump for me, was watching other people deploy these things.
And 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 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.
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 do that.
Yeah.
When people talk about things like, you know, a million fold overhead, I often like reframing it as like 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 in 1995, right?
It wasn't useless.
Right, and we take another couple orders of magnitude off that, and now we're talking about, you know, 2010 or something.
20 years or less.
Yeah, exactly.
Although I have to say that a million or a billion fault 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 number is like 10 to the 50 or something overhead.
So a lot of work has gone into technology making it not 10 to the 50, but 10 to the 20 or 10.
Yeah, it's been a long and productive road, I guess.
I feel like, Noam, you think that, you know, like 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 view is I'm sure they'll find 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 don't know if the constant factors are right, but like up to constant factors, the sum check 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 15 years or whatever.
Is it optimal in the sense of prover, verifier communication or?
Exactly.
Yeah.
So you got like Alice has X, Bob has Y.
Alice doesn't know Bob's input.
Bob doesn't know Alice, but you do have this untrusted Merlin who knows both and wants to convince them that F of X, Y is something.
And you can prove that in certain limited settings, the subcheck protocol gives.
the optimal trade-off between how much Alice talks to Bob and how much Merlin talks to Bob or whatever.
I find that very compelling evidence.
And I suspect that even 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, Noam, in a development that is extremely good.
for the blockchain space, you've been spending some of your time and 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 a dean.
I was looking for something new to do.
And Eli Ben Sasson came to me basically after you left him.
and suggested that I could also be of help, and came to me with some interesting questions.
The more I talked to him, the more interesting questions it seemed that were there.
One of the things that I very early understood that in all this thumb-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 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 things that I've often found, which always amazed me, is 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 more important than the 19 other ones.
And they just don't think that way.
I mean, we don't think that way, talking to myself as a programmer before I was looking at more of the game theory stuff.
So I was looking at more of the questions like, you know, fees, you know, 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 questions, just algorithmic questions about how to run it.
If you have multiple dimensions, now the algorithmic problems become really fascinating.
And should you even look at that and what's the incentive?
So lots of questions of this form.
I think there's another class of questions, which...
I'm really fascinated 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 tokenomics, I would say, like the macroeconomics of blockchains.
A lot of things there don't completely make sense from a macroeconomic point of view.
They have their own little 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 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 problems 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 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 the fees 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.
If memory serves, you wrote a nice kind of survey blog post around tokenomics 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 both the micro and the macro into the same kind of footing, the same kind of framework.
And I do agree with you.
I mean, 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're talking about earlier, it's 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 kinds of design decisions in our protocols.
Okay.
So you say like the fee stuff is less important, but still.
No, 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 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 way 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 of 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 really important.
You know, so in the work that I did around EIP-1559 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 of papers now.
that I think would make really, really nice contributions.
So that's in some sense analysis of an existing in-production 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 multidimensional 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 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 fantastic.
Okay, so let me start actually with your work.
I'll give you those $20 later, after we're done.
So this protocol that Ethereum used, the EIT-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 then, you know, we'll figure out what's going on.
And then after your paper that actually analyzed it and showed what was good with it, the kind of collusion necessary and so on, I said, oh, well, 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.
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 there.
So I find that really fascinating that, you know, it's a good protocol, a 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 going to the multidimensional stuff.
So multidimensional 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 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 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, from my point of view, in doing the correct thing without previous analysis.
Maybe there is 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 simple example of multidimensional 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 be a 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?
Because the work that you did with Moshi Babayoff, 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, pre-EIP-1559, they all had the same size, you know, 15 million gas or whatever.
And then one of the innovations introduced in EIP-1559 was allow 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.
And my understanding was always that the primary reason that you would allow blocks of various sizes would be to provide on-chain feedback into a price controller, into sort of a local search algorithm trying to find the market-clearing price.
And 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 Noam and his co-author Moshe Babayoff show is that actually, in some sense, the reason that EFP 1559 does guarantee near optimal welfare is exactly because of this flexibility.
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 variable size blocks.
I just thought that was super cool.
Your earlier complexity theory work, presumably very loosely motivated by reality and applications or whatever, but then your AGT work, it sounds like first order phenomenon was 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 don't feel that I ever...
You know, looked at complexity that I didn't feel was connected to actually a 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?
That's super cool.
I mean, that's the power of our field, I guess.
Even if the connection to reality is tenuous, it's 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...
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 Rabin's original work on factoring numbers, finding if a number is primed by some sophisticated mathematical properties rather than what you would expect if you studied elementary school.
And it seems like number theory will never be practical for anything, completely theoretical.
And then it's not only practical, but it's like the basis of billions of dollars everywhere, almost from armies to companies to people, everything.
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 that was such a huge part of the economy.
And I think that's not like 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 slash 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 had asked even the most obvious questions.
You know, of course, 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 Silvio and Avi.
had the world in front of them and everything was already finished behind the times we got there.
And I suppose that every, you know, every cohort of graduate students will feel the same forever.
But, you know, again, but being close to technology, I mean, there are always new ways of technology, right?
And pretty reliably, they require, in some cases, completely new subfields, 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 said, I feel very lucky to have that.
Assuming that AIs will do everything for us starting from tomorrow, right?
That was a possibility, yeah.
Take it day by day, you know?
Exactly.
No, it was great talking to you.
Okay, very nice talking to you, Justin.
And Tim.
The big thing I learned is I really have to figure out where this parking lot in Jerusalem is, because that sounds like a pretty special place.
Thanks so much for doing this.
We love having you on here.
It's fantastic.
Thank you.
It was really nice.
All right.
So we talked to Noam about a lot of things.
One thing, just this idea of arithmetization, which is sort of crucial in the SunCheck 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 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 Gnome came up with SumCheck 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 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, zero one, very binary, it would seem.
But then to, you know, have this kind of algebraic sort of polynomial approach to it just seems like conceptually a huge breakthrough.
Yeah, absolutely.
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 polynomials.
What you really need is an error-correcting code with a certain property called multiplication property.
And polynomials are just one example.
What's the multiplication property?
It means you can take two code words and multiply them together coordinate-wise, and you get another code word.
if not in the same code, then a closely related code.
And as you apply the SumCheck protocol to a product of at least two things.
And so if there's not a product of things, the whole thing is trivial, basically.
phrase it in that abstract way, 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 an error correcting code is.
So at that level, sort of I get it.
But, you know, again, that's with the power of hindsight.
It's still amazing to me that this particular error correcting code from the polynomials that we started with in 1990 or whatever is still 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 still focused on those polynomials.
And another thing that I thought was interesting, so for Noam, 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 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 the subject 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 for years studying and using the protocol.
Where that view became clear was there are all these other protocols that we use in snark design.
Every snark sort of has two components, one we often call.
a polynomial IOP, the details don't matter, but just think that's the sum check protocol.
And the other part we call a commitment scheme or a polynomial commitment scheme.
And that people think of as something else.
There's cryptography there, like hash functions and stuff where there isn't any in the sum check protocol part.
And so people gave all these commitment schemes where there was very clear, like you were taking, splitting things into two pieces and munging 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 SumCheck protocol, just sort of the technical term would be like run underneath cryptography.
But let's just say, you know, the SumCheck protocol kind of reimagined in a slightly different way.
So you're saying the SumCheck protocol arises both in the polynomial IOP part and in the polynomial commitment scheme part, or at least if you have a suitably.
general definition of what you mean by the SumCheck protocol.
Yes, that's exactly right.
And in fact, I'm putting out a little survey soon titled, like, SumCheck is all you need.
And the point is not only when you're just...
Just to be clear, by little, you mean 33 pages, right?
Yeah.
Well, relative to the number and page count in the papers, it's summarizing it.
Okay, fair enough.
So, you know, the point is, like, not only is SumCheck the right tool, and you can wield it in very sophisticated and non-trivial ways in this, you know, PIOP component.
It is also the right tool in the other components.
And so the whole snark is really just sum check.
All right.
So finally, the interview touched upon the possible optimality or suboptimality of the sum check protocol.
And what Noam said about it, I was reminded of one of my favorite quotes, which is, there's this old, really old now, algorithms book, I think 1974, so before even I was born, by Aho, Hopcroft, and Ullman, which really just put down the blueprint of how every algorithms textbook, 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 in Noam'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 have pretty high conviction that there is not something better.
Firstly, let me say, you know, it's not obvious when you just take the SumCheck protocol exactly how powerful it can be, right?
There's highly sophisticated ways you can apply it.
So there's a lot of work to be done, even if it is optimal, figuring out like the right ways to apply it.
There are also, as I mentioned to Noam, like specific limited settings where we know unconditionally you...
can't do better other than like constant factors.
And even in like snark land, you know, where we don't know for sure that the subject protocol is like optimal 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 take 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 were doing all kinds of stuff.
So.
Obviously, you'd rather have a 2025 computer, but if you have verifiability 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 check protocol itself.
It will be like how it's wielded.
I would even go so far as to say, we know you can use any error correcting code with the multiplication property.
It doesn't have to be low degree polynomials.
I think we will keep using low degree polynomials even.
I'm a little less confident in that.
And what we'll just see is more and more clever ways of finding nails for this hammer or, you know, just ways to wield the hammer.
So you asked Noam, like, you know, you did this, you came up with this amazing proof.
There is this, you know, sequence of papers leading up to the IP equal PSPACE paper that was definitely like first ballot Hall of Fame results in theory CS.
Like, why didn't you keep working on that?
And he actually talked about how, you know, the PCP, probabilistic checkable proofs work, he kind of followed along, but just like he didn't himself have the breakthrough in that window.
And then, but really at some point he moved on 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 Thaler, Noam Nisan, using the SunCheck protocol in some devilishly clever way to hit some new nails.
That's what I would like to see.
So get to work on it, Justin.
We'll have to pull Noam back away from the economics.
Yeah, yeah.
You should be able to snark-pill him, I think.
Okay, all right.
Challenge accepted.
All right, excellent.