# Zero Knowledge Proofs Power Privacy And Blockchain

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

## Transcript

The definition of zero knowledge is in some sense that at the end you will believe what I claim, but you will discover nothing else.
In the beginning when we were trying to define these interactive proofs, we wanted to make sure that we talked about the prover is all powerful.
And over the years, the prover was assumed to actually not have much computational power.
Part of the reason why he knew he couldn't cheat you.
is because he wasn't smart enough to do so, because it was computationally limited.
I've always kind of wondered why the notions of zero knowledge and interactive proofs kind of came together.
The answer is privacy.
The reason for introducing the interaction and the randomness was because this was the way to obtain privacy.
And only later, this was a paper by Goldracht, Mikhailin, Vilderson, where they showed that you could actually prove more using interaction and probabilism.
Do you think cryptography currently is rigorous enough?
So in terms of the role of rigor, I think that...
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 A16Z Crypto.
And today we're talking about a fundamental breakthrough in cryptography, how you can prove something is true without revealing why it's true.
So this insight gave rise to zero-knowledge proofs, one of theoretical computer science's most powerful concepts.
What began...
as a theoretical advance, is now one of the fastest moving areas in crypto, powering everything from privacy-preserving systems to roll-ups to verifiable computation.
Our guest today is Shafi Goldwasser, a Turing Award-winning cryptographer who, along with Silvio Macaulay and Charles Ratkoff, invented zero-knowledge proofs.
Joining us is Justin Thaler, A16Z crypto research partner and associate professor of computer science at Georgetown University.
Together, we explore how seemingly toy problems like mental poker led Dr.
Goldwasser and her co-authors to define interactive proofs and zero knowledge and how that work in turn opened the door to deeper results about what can be efficiently verified, including surprising theorems like IP equal p-space and probabilistically checkable proofs, which show that complex computations can be checked.
by inspecting just a few random locations of a proof.
And ultimately, we'll talk about modern blockchain systems powered by snorcks.
Here's our conversation.
So Shafi, welcome and thanks so much for taking some time to speak with us today.
So there's two things you hear a lot about when people discuss blockchain technology these days are, on the one hand, snarks, and on the other hand, privacy in the sense of zero knowledge.
These two ideas share, to a large extent, the same intellectual roots, which is work on interactive proof systems.
And so I thought maybe that would be a good place to start the conversation.
So, for example, there's the famous GMR paper, Goldwasser, Macaulay, and Rakoff.
And we'd love to just hear a little bit about, you know, what was the milieu like at that time?
Like, why ask those questions?
Why work on those problems?
How you came to them and how it came about?
So certainly there were no snarks.
There were no contracts or blockchains or clouds or even worldwide web.
I was a graduate student at Berkeley, and my advisor gave a talk, a class actually, on cryptography and number theory.
And it was mostly about number theory, and the last two lectures were about cryptography.
And he talked about the RSA, which is public encryption scheme at the time was essentially the only one.
And he also talked about this paper, which was how to play mental poker, which was essentially by the same RSA guys, maybe in a different order.
They were considering the following problem.
There are two people sitting in different parts of the world.
And over the phone, they were going to play cards, but they didn't have any cards.
So how were they going to do that?
How were they going to deal a deck of cards?
And after that class, you know, me and Silvio, we got kind of excited about this question.
I don't know why, because I don't think either one of us was much of a card player.
The truth is I didn't even know there were 52 cards.
Because where I came from, nobody played cards at the time, at least.
What does this have to do with zero knowledge and with interactive proofs?
So there was an idea for protocol.
for how you define encrypted cards and how do you deal a card, and there was some interaction in it.
It was a nice protocol, there were definitions of what it means to play securely and according to the rules of mental poker, but the way that you verified at the end that you followed the rules was that both players had to open everything up.
So they show what they really encrypted, each move, the messages they sent, what do they correspond to in the real game, and so forth.
And then somebody told us that that's not really the way poker is played, that in a sense you play, but nobody knows necessarily when the cards were face down, what was going on.
So the question came up, how do you prove that you've done the right thing, even though you don't reveal the cards?
So how do you prove that you're dealing cards properly, even though you haven't, in some sense, revealed everything about what you've encrypted and the randomness used to encrypt and so forth?
So we came up with a protocol.
for a very specific problem, which was to prove that the card was properly open and that used number theory, so it wasn't like a general showing that everything can be done in zero knowledge.
But there was a specific language, you know, a specific problem.
But in order to do that, we realized that, first of all, we needed interaction in order to be able to prove something without revealing everything.
We needed to allow probability of error.
So there was some sort of randomness involved both in encrypting the cards and in proving to you that something was done properly.
So there was some chance that I was going to cheat you.
We accepted that because the probability was very small.
And so we needed to modify the notion of proof, that a proof could be interactive.
There would be sort of a prover and a verifier.
Prover is convincing a verifier of something.
Second of all, the verifier was willing to accept a small chance of error.
And that enabled not revealing everything.
But we had a definition of what does it mean not to reveal everything.
We need to define what it later became.
as the definition of zero knowledge.
So all these aspects were to show something that in retrospect may seem esoteric.
Then it was our entire life because this was our paper to be.
Okay, then it started getting generalized because the question was, can you do more than one example?
Okay, one, can you have something that doesn't...
really sort of very strong, sort of perfect zero knowledge.
And the definition of zero knowledge is in some sense that at the end, you will believe what I claim, but you will discover nothing else.
Okay, how do you define nothing else?
There's sort of an operational definition, which is everything you could have done before we engaged in this interaction where I'm proving you a statement, you could do afterwards.
And the way to show that everything you could have done...
computationally before is what you could have done after, is something called the simulation paradigm.
You have to show that whatever knowledge this verifier has afterwards, you can simulate that even without the prover and the interaction.
So this is a mouthful, I realized.
But in any case, this was the beginning.
And did it all, did it come together quickly?
Were there parts that were sticking points for months?
Or tell me a little bit more about just the process of getting from the question as posed by your advisor to what we all read in the published paper.
So the advisor didn't exactly pose the question as we solved it.
It was, there was this mental poker paper.
And then he showed that there was another paper, actually, by Lipton, who showed that there's a bug in it, that there's one bit of information about the cards that can be revealed.
So then he was, OK, how do you do it without that bit of information?
There was a problem in the mental poker solution.
And it was, in some sense, in retrospect, an act of really divine spark to realize that it was all about how do you...
Encrypt a single bit of information and how do you prove that that bit is, you know, let's say zero or one without revealing anything else?
Were there bumps in the road?
That was your question.
It was very exciting because ideas just came one after the other and we managed to come up with an interesting definition and prove it.
But of course you've got, you know, if a graduate student is looking at this, you've got an advisor, right?
And they ask you questions, well, how about this and how about that?
And then you realize you haven't thought about it and you do more.
We started this whole thing that was just a mental poker paper, but then we generalized it to this idea of zero-knowledge proofs more generally, and we wrote it.
We were very excited.
This paper was submitted like six times, and we kept getting rejected.
Then we got to this zero-knowledge interactive proofs with Charlie Rakoff also.
So there were certainly bumps, but we were very determined.
I'm a lot less determined now.
My people get rejected once or twice.
But then he was like, no, we have the right definition.
This is very interesting, and we were going to...
It was like a war in some sense.
That's a terrible thing to say.
I think there's lessons for, you know, the next generation of PhD students around tenacity being a very important part of one's trajectory, right?
Absolutely.
I don't know if you experienced it, or you, Justin, or maybe think life was easier.
It wasn't life was difficult, but every time you get a rejection, if you assume that the people are rejecting you, they know all.
Then you can't go further.
But somehow we didn't assume that.
And I got to give a little credit to my co-author, to Silvio, who's also very competitive.
So it was like, hold on.
Yeah.
Yeah.
Something tells me the situation remains similar today.
One thing that I find fascinating here, a traditional metaphor to kind of explain the notion of interactive proofs to people is...
You know, one mathematician is claiming some theorem is true to another mathematician.
And rather than writing out like a 50-page proof on the board right there, you know, they have a conversation.
So that feels like a less frivolous, more formal kind of application than poker, maybe, depending on your taste, I guess.
But then there's no notion of private or secret information.
I've always kind of wondered why the notions of zero knowledge and interactive proofs kind of came together.
It seems like the answer might be poker.
No, the answer is privacy.
It's because the reason for introducing the interaction and the randomness, you know, the probability of error, was because this was the way to obtain privacy, which was, you know, the poker example.
But then, more generally, you ask, can you prove, for example, that a composite number is a product of two primes that are of a particular format without just giving the factorization?
So doing some sort of interaction.
And only later...
we realized that we can actually prove statements.
And this was a paper by Goldracht, Mikhailin, Vildursen, where they showed that you could convince someone that two graphs were not isomorphic to each other, which is a problem.
At the time, we didn't know any other way to do it.
We didn't know how to put a short proof, just proof.
But there was no zero knowledge involved.
So the realization that you can actually prove more using interaction and probabilism came after the zero knowledge.
example.
And I just want to say one more thing is that you're right that it's natural to think of one mathematician proving a statement to another mathematician.
But the mathematicians didn't like this notion.
So when you talk about interactive proofs of mathematicians now, we're talking many, many years later, they accept it.
But at the time when I gave a talk, I remember some colloquiums, and I called this an interactive proof, they said, this is not a proof.
Because a proof is something that has zero error.
Now, of course, in reality, many proofs that mathematicians write, sometimes they're completely incorrect in the sense that the statement that they prove is incorrect.
But often they have mistakes.
I mean, these are just very long proofs.
It's a complex theorem, and it's very difficult to pinpoint the error.
So I think that it couldn't have come as a way to propose to mathematicians, hey, here's an interesting new way to define.
You had to have a justification for it, which was privacy, and then, ah, you can actually convince.
of more difficult theorems, which we don't know how to do with the standard proof.
Yeah, it's fascinating.
I mean, my personal journey to interactive proofs, you know, started with, forget zero knowledge, right?
IP equals PSPACE and all of that.
And it's fascinating to hear that.
You know, you wouldn't have come up with that notion of interactive proofs without privacy and zero knowledge being like kind of the first order consideration.
So there is another proof system, which came a few years after us, but we got published at the same time because we got rejected all the time, called Arthur Merlin proofs.
And Arthur Merlin was really a one round.
It was a verifier and then a prover.
A verifier was Arthur and a prover was Merlin.
But it was a simpler notion, both that it wasn't considering lots of rounds, and second of all, that it didn't talk about privacy.
And third of all, that...
Arthur was just someone who was tossing coins, where for zero knowledge, often the verifier tosses coins maybe, but then they send a message where the prover doesn't know what the coins are.
And that, in a sense, is the power of the verifier.
So he checks to see whether the prover will do the right thing.
So I just want to say one more thing.
We're talking about proving that a theorem is correct.
Much of the, as far as I understand, the applications are more that the prover knows something that the verifier doesn't.
So for example, I prove that I know a password, or I prove that I've signed a contract and I have the signature key.
So it's not so much that necessarily that some theorem is correct, but it is that I know the proof of that theorem.
But by me knowing the proof of that theorem means the proof exists.
Another thing is that...
Okay, let's say it started with zero-knowledge interactive proofs.
It had both interaction and probabilism and zero-knowledge.
But then the research kind of split into different directions.
There were all the complexity theory people who didn't care about privacy.
They got very excited about this idea that this interaction allows you to prove harder and harder statements, which correspond to more and more complexity classes from standard complexity theory.
And then it went even in a much more interesting direction where people said, okay, do we actually need interaction?
And it turned out that it is possible to sort of take a standard non-interactive proof, like just a standard proof, no zero knowledge, no randomness, no nothing, and to rewrite it in a different, sort of in a, using some sort of error correcting code, so that now, if there was an error in the original proof, the standard classical math type proof, there would be lots of errors in the new one.
And the reason that that was good was it meant that you could sort of just probe this proof in a random location and you would land on an error if there was any error at all.
You know, that opened a whole new dimension to sort of a new notion of a proof where you could do local checks, you could just poke it in a random place and you could talk about how much you read, which is a lot less than reading the entire proof and what is the probability of error.
And I think, you know, it was an object that was...
easier to study for traditional combinatorialists, computer scientists, and so forth.
And that actually leads to snarks, right?
Because you've got this long proof.
It's too long, okay?
And if you want to really talk back in the world of applications, where is that long proof sitting?
You know, it doesn't sit anywhere.
You'd like to be able to somehow compress it and send it and still have the verified be able to poke in it and find the error.
And now we go to this world where...
We have hash functions and we have these Merkle trees, very complex hash functions where these proofs can be compressed.
And yet you are able to kind of poke at them and discover an error with high probability if there was an error in the original uncompressed version.
So that's a great summary of sort of many, many years of research by the computer science community.
Let me rewind a little bit.
You mentioned about how there was this branch.
which took a purely complexity theoretic view of interactive proofs.
And just like Justin, that was the first way I encountered it, right?
It was, you know, probably the complexity theory book of Aurora and Barack or something like that.
You know, the proof of IP equals p-space and so on.
And so I'd love to get your thoughts.
You know, in particular, the SUMJEC protocol, which shows up in those proofs, is one of the main paradigms that's being used today to build SNARKs.
And so...
I'd love to just hear, where were you when you heard about whether it was IP equal PSPACE or one of the precursors, when you heard about sort of the SUMCHEC protocol?
Were you surprised that interactive proofs were as powerful as they turned out to be?
Or just, again, take me back to sort of that moment in time for you.
So we knew it was more powerful than standard proofs.
There's an intermediate segue a little bit, and that was we had one prover, and then there was work that I was involved in where we said, okay, what other proof?
systems are there.
So we said, okay, how about if there are two provers?
So there are two people who have written a proof together, and there's one verifier.
We had the story, and that is they're like suspects of a crime, the crime being that there's an error in the proof.
And they're sitting in different rooms, and you ask questions from one to give you answers, and you ask a randomized question from the other to give you answers, and somehow you can check the consistency between them in order to verify that they're not cheap.
It was this paradigm, and the question was, is it more powerful than one prover or not?
And then Noam Nisan, he was a postdoc at MIT, I was a professor at MIT, and he came up with a protocol to show that the permanent problem, which is a well-known problem that is hard and it's close to p-space, complete.
He showed how to use two provers and sort of a sum-check protocol to prove that a prover could prove.
to verify the value of the permanent.
And a lot of the ideas of the subject are in that protocol.
But there were two provers.
And I think then he went off to travel in Brazil or something.
I don't know, somewhere.
And while he was gone, the rest of those guys, Fortnau, Karloff, and Lund, so the paper is FKLN, they figured out how to make that two prover into one proof.
And it was for the permanent.
And this is all happening all, it's kind of very quickly.
Once they got that and everybody knew about it, then Adi Shamir from Weizmann managed to take it to the last stage, which was IP equal to PSPACE.
So I was at MIT.
We had a seminar on these things.
It was surprising because these ideas are not immediate at all.
They are complex.
They are beautiful.
They're still used today, as you say, in concrete protocols for blockchains and so forth.
But I was not removed from it because it was all happening.
The same group of people were postdocs, Princeton, Berkeley, MIT.
But it was surprising.
But when you start hearing things one step at a time, you sort of break that barrier of thinking that you just are barely scratching the surface.
And then it seems that there's a lot more.
I mean, what is really surprising to me is that you guys are actually using it.
Justin, do you want to talk a little bit about that?
Like at a high level, what's sort of unique about SumCheck for the purposes of concretely performance snarks?
Yeah.
So this path, the historical path, I always find fascinating, right?
That Shafi just recounted, right?
It went single prover interactive proofs from Shafi's paper and then multi-prover interactive proofs and then PCPs and then snarks were, you know, kind of first built out of PCPs.
But, you know, from a present day perspective, that path is especially...
curious because, you know, we have something called the Fiat Shamir transformation, which there are open theoretical questions about its security.
But, you know, practitioners are sort of happy to use it.
It's just a generic way to get interaction out of protocols, which means if you want to build a SNARK, you don't have to go through PCPs necessarily.
That's just the historical route, right?
And in fact, it's sort of...
It doesn't make sense to go through PCPs because PCPs are non-interactive, but then when you compile those into a succinct argument, the interaction comes right back and then you fiat-shamir, right?
And so what really makes sense from the present-day perspective is to start with something like an interactive proof or a two-prover interactive proof, never go through PCPs, and just remove the interaction once at the end of the day with fiat-shamir.
This has been my personal path to, you know, starting working on SumCheck and finding it to be a beautiful, simple protocol and useful for really simple problems.
And over, you know, years figuring out, it's sort of like the perfect hammer that actually applies to everything out there.
So I always find that route fascinating.
It seems like the PCPs just like grab people, like you mentioned, and were somehow easier to think about.
But then if your end goal is the snark, it's actually, you know, like a stepping stone you just don't need.
And so to answer Tim's question briefly, the SumCheck protocol has a lot of rounds of interaction in it.
And it just seems to be a very good tool for forcing the prover to actually do work so the verifier doesn't have to do the work without paying a lot of overheads.
My personal intuition is, you know, cryptography is expensive.
You know, if you need to commit to a lot of data, you're going to be doing a lot of, you know, hashing or group operations or what have you.
You need to commit to some data to keep the verifier nice and fast and succinct, the proof short.
But you'd like to kind of use that sparingly.
You commit to more data, it means it takes longer to commit to.
It also means you separately have to prove that the data you committed to is like not random garbage.
So that takes even more time.
And so the SumCheck protocol just uses interaction to the extreme to use that cryptography, those commitments, really, really sparingly.
The historical route has just been fascinating.
PCPs, they typically use like univariate polynomials in their guts.
The reason is it lets you keep the proof short even when there's no interaction to help you out.
But then if you have a lot of interaction, like multivariate polynomials are really nice because you can kind of have one round of interaction per variable.
And so, I don't know, this PCP route just took the community towards certain techniques and we've now sort of come full circle back to the beginning.
To me, what's really fascinating about this development is the power of abstraction.
As you said, why would we be talking about zero-knowledge interactive groups early on?
And the poker is just a curiosity.
But after that, you know, really the understanding that there's something fundamental that's going on here and asking, do you need interaction?
How much interaction do you need?
How do you get to do it without interaction?
And also, even with a sum check, so you think about it as it's efficient, it's good.
You know, as you were describing it, it's a good way to do things.
But if abstractly speaking, where does that come from?
Where it comes from is that if we generalize from poker and then proving that you know a password, proving that a contract is a valid contract, more generally, we talk about proving that a computation was done correctly.
So there's some algorithm or train machine or whatever, and then it takes some input and then it provides some output.
And you want to convince someone that the output was correct without having them to repeat the computation themselves.
And the thumb check, in some sense, you can...
So there's this abstraction that everything is a computation.
And now really the question is, how do you prove to someone else that computation was done properly?
And then you realize that if you look at the rules of the algorithm or the rules of the machine that the algorithm is running on, you can express the rules sort of like step by step as a sort of algebraic formula that each rule was computed from the data from before you did some computation.
Next.
piece of data, computation, next piece of data.
And this can be expressed already as, as you say, with polynomials, okay, on variables where the variables actually have value, which is the data.
So there is something you needed to think about computation of a Turing machine or a circuit in order to even lay down this thing that later will become a sum check.
So what were you summing?
You were summing this formula and over all the steps of the computation.
And it's fabulous in my mind that it's this going to that abstraction that you would like to summarize computation as an algebraic formula that at the end actually is also the right thing to do for a specific concrete application.
I agree completely, right?
It's like...
If you're looking at the, quote, sharp-sat problem, that is counting the numbers satisfying assignments to a formula, it's like sum check is the perfect fit.
Because the sum is you're just summing over all possible assignments of, you know, does this satisfy the formula or not, right?
And when, you know, I read about sum check in Aurora and Barack's textbook, I was like blown away.
It's so beautiful, right?
But you might think, oh, we moved away from that.
That was just a clean abstraction.
But actually, one of the prevailing trends in snark design today is to...
do exactly what you just described of writing out a computation transcript step by step by step using a virtual machine abstract, like a simple CPU, and then applying SumCheck to prove that every single step was done correctly.
Now, the way we apply SumCheck doesn't look like the same kind of thing as summing up all satisfying assignments of a formula.
But otherwise, it's literally exactly what you said, which was the way of thinking when this stuff was worked out in the, you know, late 80s, early 90s.
So the similarities and like the small deviations are fascinating and complement each other.
I have a question to you.
So can I?
Yeah, of course.
As you say, it started both about the interaction, probabilism, and privacy at the same time.
And then the succinctness came in.
and eliminating the interaction.
But from what I understand, they call ZK snarks, but there is no zero knowledge there.
So the privacy is kind of gone, is not interesting or it's just cost so much or it's going to come back.
What is it?
You're talking to two of the people in the world that are most annoyed on a daily basis about this particular terminological error.
Yeah, yeah, yeah.
Snark community, whatever name you want to give to the community, today uses ZK basically to mean succinct, like you say, possibly with actual zero knowledge, you know, with like, you know, privacy, possibly not.
Some applications need the privacy and some don't.
Some of the kind of most popular applications today don't need it.
And that's a big reason why you see a lot of these snarks that people call ZK Proust not actually being ZK, right?
So if you want to just like scale blockchain, so untrusted parties that exist off-chain are posting Proust to the blockchain that they did a bunch of computation correctly so that, you know, all the blockchain nodes only have to check the proof and don't have to do the work from scratch.
There's no privacy necessarily needed there, right?
You know, but if you talk about like Zcash, you know, private currency transfers, now you do need privacy.
And of course, they are using something that is ZK.
Now you can ask, well, like the snarks people like to use, can they be made ZK and people just aren't bothering?
That's a little bit nuanced.
I think the short answer is they all can be made ZK in principle.
Some of them would experience more performance overhead if you made them ZK than others.
So I think, you know, two things will happen is my prediction.
One is the privacy applications will kind of become more important again over time.
Zcash was early and then privacy became less of a focus and it'll come back.
And so then everything will have to be ZK.
And two, I think the sort of the techniques that will kind of win out will just magically be ZK without the overheads.
So that's how I think it's going to go.
I want to say one other thing that I think is kind of an interesting development over the years.
And that is that in the beginning, when we were trying to define these interactive proofs, we wanted to make sure that we talked about the prover as all-powerful.
We showed that these proofs are correct or a very small probability of error, regardless of how strong the prover is.
And over the years, you know, there was, first it was Crepeau, Chaum, and Broussard, where they had this notion of an argument.
where it was an interactive, but not proof, interactive argument where the prover was assumed to actually not have much computational power.
Part of the reason why he knew he couldn't cheat you is because he wasn't smart enough to do so, because it was computationally limited.
And then Sylvie did the same in order to get to the snark idea.
Conceptually, it's fascinating.
So it might be that the theorem is wrong, okay, that you're proving.
But what convinces you that it's okay...
is that there is no prover that can convince you of the opposite.
So in some sense, one thing is to start with the mathematician.
The proof has to be 100% correct, okay?
Then we said, you know what, there's this probability of a mistake, but we can quantify it and we can show that it's one in Avogadro's number.
You know, it's extremely small.
And then we say, it's correct with respect to anybody that can work in a reasonable amount of time.
So there's no one who can point to, in some sense, a mistake, you know?
As far as we are concerned, it's good enough as correct.
So that's kind of a conceptually interesting concept.
The fact that a reality is indistinguishable from a correct reality with the computational resources we have, and therefore it's good enough to think of it as correct, is a paradigm which has led to a lot of efficiency and a lot of improvements.
But it is definitely not the same as a assumption.
Yeah.
Convincing proofs of false statements exist, but nobody can find them.
I mean, I was pretty far along in my own career when I started looking at proof systems for these statements where solutions trivially always exist, but they're presumably hard to find.
And yet you were looking at such things, I guess, from day one for, you know, proving knowledge of RSA secret keys or something.
This is one more step.
It's not that their proof is hard to find.
Maybe it's not even correct.
Yeah, it's like layers of an onion, right?
Do you care about problems where the solutions always exist, but the question is, does the prover actually know a solution?
And then there's, are you going to let convincing proofs of false statements exist, but no one can find it, so it's okay?
It's just, yeah, different flavors and layers.
I guess that's what leads to a beautiful theory.
So it's interesting to me that it hasn't really gone into the algorithms world.
Okay, so worst case.
You say an algorithm will run in a certain amount of time means that in the worst case.
But people talk about, of course, that with respect to certain probability distribution, it might be much faster.
In some sense, there's a similarity there.
If you can't find instances where you could talk about not being able to find an instance where this algorithm runs more than a certain amount of time.
And it's probably true in practice for many problems that the instances you run into are all going to be okay.
So as a cryptographer, I immediately think this is a question of playing with an adversary.
The adversary is trying to tell you, no, your algorithm runs slower than you say.
But if the adversary is bounded and you can never do that, what's the difference between having an algorithm that runs quickly, except in some very bad cases, which no one can ever come up with, versus a much more complex algorithm whose worst case running time is slow?
So it's interesting.
That's sort of very natural for a cryptographer because there's an adversary.
And the adversary has some computational powers, and you're fighting that adversary.
And if you can win against that adversary, whether it is convince them something's correct, maintain privacy, all is fine.
Whereas, you know, that kind of thinking could be adopted in other fields, but it hasn't.
Yeah, the closest analog I can think about that comes to mind is smooth analysis.
That's true.
Which is not a computational concept.
It's more of a statistical concept that says that the instances for which, say, the simplex algorithm is slow are, you know, measure zero or sort of very rare.
That's right.
And, you know, in practice, it's kind of...
a little bit hard for humans to come up with those instances.
Like someone like Mahalas Yannakakis will write like a brilliant paper, sort of, you know, giving the bad examples where local search takes an exponential amount of time.
But I've never seen a computational treatment of it.
So that would be fascinating.
So maybe a couple of reflections on this great conversation so far.
So one would be just the kind of non-linearity of the ideas.
So, you know, when you read a textbook, right, all the concepts are presented in this very logical manner, and it's as if it could have just been discovered in that exact same way.
And so one thing we've heard from, you know, your story about interactive proof, zero knowledge, succinctness, all of this, is that the way it's written down in the textbook is generally not the way it was discovered.
Absolutely.
But then even more fundamentally than that, the ideas are not even linearizable.
I mean, it's really sort of a web of concepts that are connected to each other in very rich ways.
You know, even things that were discovered together by you originally, Shafi, you know, they seemed like they went together at the moment.
Maybe it wasn't clear why they had to go together, but over time they keep reoccurring sort of in the same room, if you will.
So this idea that there's many, many ideas that are connected to each other and that the discovery process, I don't want to call it a random walk, but it may not be the same path of discovery, which is the one that you tell later in the textbook.
And then the second reflection is about this interplay, let's say, between the specific and the general, or even maybe I'd say the toy example and the general theory.
And it's funny because Chris Dixon, who's a managing partner here at A16C Crypto, he likes to talk about the next technology is going to look like a toy.
So this idea that something that's a toy is what's actually going to become something very general and powerful.
I think you see that theme again in talking, for example, about poker.
But then a big part of our job, you know, as researchers, as theoreticians, is to say fundamentally, what is this really about?
And at the same time, so you can think simultaneously about very toy examples and very general theories.
And indeed, you know, the notions of reduction and completeness and complexity theory, arguably, is about exactly this.
The idea that a single problem can stand in for an infinite class of problems.
And I will finish this with a question, Shafi, just about sort of how you think about.
this interplay, because I don't know about your experience, but when I talk about what I do to people who, you know, are far from what we do, far from being mathematicians or theoreticians, they're always shocked when I talk about it being an extremely creative endeavor.
So, you know, I compare it, you know, more to, I don't know, someone who's writing music or designing a sculpture or art or something like this, as opposed to being some kind of very, you know, clinical, goal-driven activity.
And so I just...
Here's your thoughts, Shafi, about like, is there a role for, is there an importance to kind of playfulness of toy examples in the process of working on, you know, in your case, sort of very deep and fundamental theories?
That's a very interesting question.
First of all, I think that researchers are different.
Different researchers are different.
Some people cannot make any progress without seeing an example.
So if you're going to tell them that there's this thing called interactive proof and their randomness and rounds, they don't know what you're talking about unless you show them a particular Question like, is 15 equal to 3 times 5 without giving you 3 and 5?
For me specifically, if that's part of the question, I need a narrative.
We'll get to the creativity in a minute, but the question is also for motivation.
What makes you work?
And underlying in your question about creativity is that maybe people, when they think of mathematicians or theoreticians, is that they have a problem and they know a whole bunch of mathematics and then they try to apply the...
the mathematics and they have somehow superior skills, technical skills, and they're able to apply it and solve the problem.
What makes more sense to me and what has been my experience is there has to be, first of all, a story in your head.
I definitely need that.
And so it's not just there is this problem I need to solve.
The problem is more of a narrative, and now you can attach to it a specific math problem.
So a narrative being maybe that you want to play poker.
There's this famous story that Manuel Blamos told us.
There's Alice and Bob, and they live in different cities, and they have a dog, and the question is, who gets the dog?
They have to flip a coin.
How do you flip a coin over the telephone?
So there was a story.
There are these two people.
They want to flip a coin over the telephone.
And now you can start thinking, how do you do that?
So for me, a narrative is very important, and I would assume that in the blockchain space, there's definitely the narrative, which is...
You have this ledger, you want to post things, you want to be able to have smart contracts or whatever.
That's a narrative also.
But that's not a math problem.
From this, you can define a math problem and now you can talk about techniques to find it.
Now, the question of creative process, how do you solve it, right?
Obviously, it's creative.
I mean, how are you going to do it otherwise?
I mean, it's the usual thing, right?
If everybody can do it, there would be no need for us, no...
way to get our papers published and no ways probably to make a business that's profitable.
If everyone can do it, then there's no extra.
So that's creativity.
For me, I need to be in a space where nobody, you know, somehow your mind can wander.
For me, that's seminars where people talking about their work and at some point you're there, you can't go anywhere else.
Your mind wanders.
And probably there's some idea that has been described that touches on your own.
you know, web of thoughts.
I don't know what it is for you, but it's definitely created.
So changing topics a little bit, a question that Justin and I wanted to ask you was, do you think cryptography currently is rigorous enough?
And I ask that because I went back to your Turing Award citation today, and one of the things you're credited with, along with everything we've been talking about so far, is foundations of cryptography.
So in effect, adding rigor, rigorous foundations to cryptography.
Ever since, we've seen this constant back and forth between what assumptions you're willing to make and what conclusions you're willing to achieve.
Justin earlier referred to the Fiat-Gamir transform, and there remains open questions about the security of that transform in different contexts.
So we'd love to hear a little bit about your thoughts on the role of rigor, on the role of assumptions of varying plausibility in cryptography as a field.
Yeah, so in terms of the role of rigor, I think that...
We were very much into defining things precisely and coming up with proof methods to prove things.
And I think that helped the field because rigor means usually that the definitions are shorter and easy to explain because they're equivalent to other notions and that enables the field to go forward because you can build on very firm foundations.
Is it as rigorous now?
On one hand, yes, because we have a sort of a recipe.
book of how to define cryptographic security.
So we usually have to sort of model an adversary.
That's the acceptable way.
And that is to come up with that if you come up with a cryptographic primitive, you have to prove that it's secure in presence of this adversary.
You have to define secure also for the primitive.
And usually these proofs are reductions.
There's a reduction from this is all going to be secure if factoring is hard, if some other assumption.
holds.
Maybe that two players don't interact with each other, you know, in a multi-party computation.
But it has to be a tight proof.
You know, so in other words, if somebody comes and breaks the protocol, that will translate to a fast algorithm for factoring, or it will translate to some leakage on the secret key or something like that, okay?
So we do have this recipe, which means that hopefully the students you train and people who work in the field follow it when they design a new protocol.
Now, of course, the field has become much larger and there's a lot more people.
So I'm not sure everybody checks everybody else's work.
When we were a small field and everybody read each other's works, it was feasible.
And also because there's a lot more applications, obviously you want to cut corners because you'd like it to be efficient.
And that's another incentive for not to satisfy these proof paradigm, you know, these reductions from assumption to primitive.
Each case, you know, should be valued separately.
About assumptions.
So I mentioned the factoring assumption, and I think everybody here knows that, in principle, quantum computers can factor.
I think it's much less in principle than it used to be.
So people are working on actually coming up with, you know, quantum devices.
that can address factorization, and they're starting to talk about constants and how many qubits are involved and so forth.
So we have moved from the factoring assumption to these lattice-based assumptions, which, as far as we know, quantum computers cannot solve in polynomial time.
Of course, again, those lattice-based assumptions might not be as efficient as you want for the blockchain space.
So for the blockchain space, you might want something that's...
based on, I don't know, by linear pairs or whatever the favorite assumption is right now, which is, in principle, attackable by classical computers.
And people also invent new assumptions because they seem to be true, and they would make your protocol much more efficient.
Like the only way, knowledge extraction and so forth, the only way to solve a problem is a particular way, and you would utilize that in order to get a very efficient scheme.
In my mind, as long as they can state their assumption precisely and show, indeed, that protocol is equipped...
security is equivalent to this assumption, we're in this win-win paradigm.
Somebody comes along, breaks the protocol, might be bad for AZ-16, but it will be good for mathematics, we'll discover something new.
And it also makes it less likely.
But it's sort of the natural course of events, right?
You want things to be efficient, you have to pay in maybe not taking the most ancient assumption out there that people feel confident.
So, you know, we've been talking a lot about, in effect, ancient history, at least by computer science standards.
But you've been super active for your entire career, including the last many years.
So in general, we'd love to talk about your more recent work, last five to 10 years.
One idea would be your work related to machine learning and related to law.
And certainly one thing I'd be particularly interested in is just.
Was working in these application areas, was it a pivot for you intellectually?
Or to what extent did the same mindset that you could use in your work in cryptography and complexity theory, did that still port over pretty well to these other application domains?
So I'll tell you two things that are related to what you brought up.
So first of all, the law aspect.
I was in Berkeley.
I was the director of the Simons Institute and I had some law colleagues.
I spent a year at Radcliffe and I had some interaction with Martha Minow that was just coming off being the law school dean.
And we had an idea of teaching a course on law and cryptography or law and algorithms.
Because it seemed like the whole, again, going back to the narrative, the idea of trying to convince a judge of your innocence, you could think of that as a proof.
Of course, in law, you really try to avoid.
putting precise numbers and probabilities on likelihood of something being true.
Because once you put a number, one can sort of show that it's incorrect.
And the notion of evidence is not the same as a proof.
But it was interesting to talk to lawyers and to understand how they think.
And that brought us to this place where we showed that even...
If you think about legal applications, one of the first works that I was involved in was about this question of wiretapping.
So let's say there's a wiretap order.
The police is allowed or the FBI is allowed to tap some phones.
And it turns out that after the warrant is taken away, they have something like 90 days to sort of open the files.
So the question was, how do you really scrutinize all these wiretaps if...
There's no public access to it.
We came up with some paper where we said, let's bring together encryption, zero knowledge, actually blockchains, where you would think of having all these wiretaps on the blockchain encrypted so that privacy is maintained until a time in the future where all of a sudden automatically it should be open.
So the cryptographic tools that we had seemed to be relevant to that question.
Another place was...
Let's say the FBI discovered some sort of pornography ring or something using some software.
And the software is proprietary and secret.
And then they come to court and they claim in front of the judge that they have a lot of evidence that this person was engaged in illegal activity on the internet.
Then the side representing the accused could ask to see the software.
But once they see the software, the FBI cannot use the software anymore.
So there was a question, how do you prove that you use a specific...
software without revealing the software.
So that was really proofs and zero knowledge, you know.
Can you sort of convince another side that you use the software without revealing the software?
So something very natural about using this in the realm of law.
So that's story one.
Story two, just about the machine learning.
Today, that's all the rave, you know, besides blockchains.
And there's real fantastic questions there.
Why should you believe when, you know...
chat box, whether it is OpenAI or Google or Meta or whatever, gives you an answer to a question.
And when I say question, I mean, let's say it's a math question.
You know, there's a prompt, which is a math question, and they give you an answer.
Why would you believe it?
In fact, we know that you shouldn't really believe it for the particular question you ask.
On the average, you should believe it.
Let's say 90% of the time.
So can a chat box provide a proof, a mathematical proof, for the particular prompt you ask?
that the answer is correct.
And so this is actually work with a student of mine, Oral Paradise and Guy Rothblum and Olga Amit, where we propose to take the notion of interactive proofs and adapt it to the machine learning setting, where you would actually be training a chat box not only to produce answers, which are correctly, say, 90% of the time, but for every answer to also teach them how to produce proof.
not only learn how to solve problems, but learn how to come up with proofs.
And it's been, there's an algorithm, and it's been successful in some cases for some real language models.
So I think that there's a lot of future to the notion of proofs.
Also zero-knowledge proofs maybe in the future, because you'd like to prove without really the training data.
I mean, you can go lots of places there, and I think it's fascinating.
You know, I was talking to a friend.
who's also a seasoned computer scientist.
And then they expressed skepticism about machine learning.
And I was like, you know what?
We're so lucky that it's happening now rather than in 15 years, where we can still use the things we know to make a difference.
You know, why are you skeptical?
Just go with it.
Well, I think that was sort of my motivation.
I think that's great.
I mean, there's frustrations in being early to a technology.
There's a lot of moving parts and the models aren't.
sort of agreed upon yet.
But on the other hand, you know, the impact you can have, like you say, while there's still time to make a difference with the trajectory of technology is pretty amazing.
It's one of the privileges of being a computer scientist, honestly, where it's just sort of new waves of technology and applications come up every, you know, decade.
And every time that happens, it's a new opportunity for all of us.
Totally.
And also, you know, maybe the particular chat box or the particular, it won't be language models, it'll be something else, will change.
But the idea that you should prove your answers, if you can.
That should remain because we shouldn't believe everything we're told.
So I came to that also narrative.
I saw some talk somewhere that I could use some chat box as my financial advisor.
So I was very excited.
I came home and I had this whole big new plan of how to invest.
And then it turned out it was all predicated on the wrong understanding of some rule.
It's like, what?
And I had to go to lawyers and spend like $5,000, $6,000 just to realize, because I said, do this.
He said, no, it's wrong.
I said, no, it's right.
Judge Petit told me.
Oh, my goodness.
Well, you're definitely an early adopter, Shafi.
I'll give you that.
I tried.
All the perils therein.
Then I guess the lesson of the story is it all comes back again to proofs and knowledge, right?
Yeah.
I think that proofs are very fundamental.
Fantastic.
Well, thank you so much, Safi.
Really appreciate the time.
Bye-bye.
Have a good day.
theory.
So, I don't know.
I mean, what do you think?
Is sort of playfulness and sort of toy examples kind of an important part of research for you?
For me personally, I'd say yes in a different flavor.
My work with the Sumcheck Protocol and recognizing how it's sort of the hammer for which everything is a nail in non-obvious ways came about from using it to solve like the simplest problems computer scientists study.
The Sumcheck Protocol kind of...
directly solves them in interesting ways.
And making the protocol run fast takes insights, even in those simple settings.
And then it turned out that those exact same algorithms and ideas actually are completely general.
And now we use those same techniques to prove arbitrary computations, right?
So the power of theory is like generalizability and abstraction.
And often the right thing to study is kind of the cleanest, simplest.
which feels like a toy, and then it unlocks, you know, like, the whole world of computation.
I think poker is especially interesting because there's something sort of playful, almost frivolous about it.
In fact, it's very complicated.
I think, especially in computer science, there's a long history of sort of, you know, playful topics that might not feel super important or deep, sort of unlocking notions or ideas that then become core to the whole field.
And one thing that, you know, we talked a little bit about sort of playfulness and toys, and you even used the word frivolous, but it's something that I think is not quite the same, but related.
And two things we hear about a ton in crypto, right, are memes and narratives.
And, you know, I often kind of say, like, there'll be like a famous sort of research paper, but actually what everybody knows is sort of the simple example.
on page two right so like there's one thousand times as many people that know the example on page two as have read more deeply into the paper this is before my time but i i wonder if like you know the graph coloring zero knowledge protocol would be like an example that turned that theory into kind of a something that became a meme that could sort of travel in effect quickly at least relative to how ideas um traveled in the 1980s so i think that's also important you know you can prove results you can develop a theory but For the theory to be successful, you also have to communicate it to others.
Other people have to get it.
Other people have to be excited about it and want to build on it.
And so I think, you know, starting from sort of simple examples, I actually think can be powerful also in that way and just helping communicate the essence of what the general theory is about.
And then I was also kind of amused to hear Shafi literally talk about narratives being important for her in thinking about her research.
The idea that you'd start with, you know, say the narrative of two people trying to jointly flip a coin over the phone, sort of a problem basically given to her by her advisor at Berkeley, Manuel Blum.
Or, you know, in more modern times, she said, you know, like the idea of a global, you know, distributed ledger being a narrative, right?
And then the sort of the role of the researcher, a certain type of researcher anyways, is really turning that into something formal, into mathematics, having mathematical definitions, articulating.
you know, what problem you're solving, what properties you want, and then, you know, formal protocols or theorems or guarantees.
So, you know, and as much as we, you know, talk a lot sort of in industry about sort of narrative being important for, you know, projects to succeed, I essentially see that come up also for Shafi and sort of how theories, how theories can succeed.
Yeah, somehow these clean goals can be very clarifying.
The interactive proof model was sort of introduced as a interesting model in its own right.
And We had the same notion of what is a mathematical proof for 2,000 years dating to the ancient Greeks.
You know, you write your proof in a book and someone can check it step by step.
And this was sort of a natural generalization of it that at the time, mathematicians, Shafi said, hated.
Because, you know, even though mathematicians do have conversations with each other in the, you know, in the real world to convince each other of something being true or not, they ultimately, you know, prize these written formal proofs.
And so the model came out, a natural model, but just...
There's the model.
Some protocol is originally given, but nothing like this sum check protocol that Gnome told us about, right?
And so somehow the right model leads to the right protocol leads to all sorts of other stuff.
And it's the stories along the way, right?
Without the right model, you just don't get the sum check protocol, right?
Without the sum check protocol coming from a complexity theorist, you don't get the practical snarks that will ultimately underlie the world's digital infrastructure.
And you're right.
And there's often like a back and forth.
Like maybe the first thing someone comes up with is an algorithm.
And only then do you step back and be like, wait a minute, this is a cool algorithm, but like, what's the problem we're solving?
And like, why do I think it's cool?
What are those properties?
And then when you write those down, you're like, okay, now let's start from a clean slate.
If I think about any algorithm that might have those properties, there's something even better than the one I came up with in the first place.
Yeah.
And I guess points to the power of abstraction, but, you know, without.
clarity and narratives or clear goals, you don't know what abstractions are the right ones and things like that.
You know, maybe the final thing to talk about around Shave's interview.
So she told a story or she alluded to the fact and you alluded to the fact that the GMR paper was rejected multiple times before it's accepted.
For people in the audience that, you know, aren't themselves researchers, right, it may look like all these classic results just sort of fall from the sky, fully formed, right?
It must have been famous sort of from day one.
But there's really...
a process that goes on behind that.
I think both on the part of the inventors or the authors in sharpening the clarity with which they explain their ideas and maybe coming up with more examples and, you know, having memes in effect to illustrate it.
But then also, it just feels like, you know, new ideas just take time to be absorbed.
So why do you think that is?
Like, why are kind of really good new ideas hard for even the most seasoned experts to sort of, you know, recognize the first time they see it?
So I think one of the issues is experts always want to understand how something relates to what came before.
I think if you look at the GMR paper, they have a whole bunch of explanations.
of how these notions, zero-knowledge proofs and interactive proofs, relate to other things that they're just not related to at all.
And it's clearly reviewers were like, wait, how do these things relate?
Something's totally new, and the fact that it's totally new almost works against it because you can't point to, oh, this is a clear step forward relative to something that came previously.
Yeah, the easiest thing to understand is here's a problem you already know and a result that improves in an agreed-upon way over the state of the art, right?
Yeah, yeah.
completely new definition that no one's ever thought about, then people struggle.
Like, is this an interesting definition?
Is this a trivial definition?
And of course, as you know, theoreticians, their biggest fear is sort of accepting a paper that turns out to be like trivial in some sense.
So, you know, to minimize errors of that form, you often wind up perhaps being a little too negative on works that you don't fully understand yet.
And again, like, it took...
Five years from publication, almost maybe a decade from when they actually just came up with the model to see the full power of it with the Sumcheck Protocol unlocking that.
So we're very bad at predicting the implications of new things and what's to come.
And the nature of research is it's fundamentally unpredictable or wouldn't be research.
I mean, at one point, Shafi said, you know, how do you solve the problem?
Well, it's creative.
Of course it's creative.
It's creative.
Someone would have done it already.
I thought that was great.
Yeah, yeah.