How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser)

**Shafi Goldwasser** (0:00)
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.

**Justin Thaler** (0:24)
I've always kind of wondered why the notions of zero-knowledge and interactive proofs kind of came together.

**Shafi Goldwasser** (0:28)
The answer is privacy. The reason for introducing the interaction in the randomness was because this was the way to obtain privacy. And only later, this was a paper by Goldwasser, Micali and Richardson, where they showed that you could actually prove more using interaction and probabilism.

**Tim Roughgarden** (0:44)
Do you think cryptography currently is rigorous enough?

**Shafi Goldwasser** (0:48)
So in terms of the role of rigor, I think that...

**Tim Roughgarden** (1:00)
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 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 Micali and Charles Rackoff, 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 PSPACE 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 Snarks. 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, Micali, and Rackoff. And we'd love to just hear a little bit about 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?

**Shafi Goldwasser** (3:11)
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 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. If they were considering the following problem, there are people, 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 are they going to deal a deck of cards?
After the class, me and Silvio, we got 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 I came from nobody playing 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 an encrypted cards and how do you deal a card, and there was some interaction in it. There 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. 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 faced 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, 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 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.