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

**Noam Nisan** (0:00)
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.

**Justin Thaler** (0:17)
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 zero to exactly the right thing.

**Noam Nisan** (0:30)
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.

**Tim Roughgarden** (0:50)
In a development that is extremely good for the blockchain space, what are you most excited about?

**Noam Nisan** (0:56)
So.

**Tim Roughgarden** (1:06)
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. 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. 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. Nisan'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.

**Justin Thaler** (2:56)
Thank you for having me.

**Tim Roughgarden** (2:58)
I wanted to start the conversation. 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. In particular, I thought maybe we could start at 1996, I'm guessing it's around there, but a moment in time where on the one hand, you were a leading complexity theorist worldwide. You were famous for hardness versus randomness paradigms.
What else? Pseudo-random generators for space-mounted computation, Fourier analytic approaches to PAC learning, algebraic methods for interactive proof systems, which we'll talk more about later.
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 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. I was wondering if you could just start by a little bit about, was that a sudden decision? Was it a gradual thing? Was it scary? How did you approach that? What was that like at that time?

**Noam Nisan** (4:17)
Actually, I have a story. Obviously, the web basically hits the world. Something like around 95, everybody knew that the Internet was like a major thing. But no one in academia was really changing. People were very, very slowly changing what they were doing because academia is very slow to change. Big companies were already really all gung-ho on it, and the world was already popular, the Internet. But in academia things, they kept on moving very slowly.
That 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 all the cultural shift, all the student protests, of everything.