I'll try to explain what zero knowledge proofs are
and maybe why they are also useful. Well we can start with a proof - you know proof is the basis
of mathematics. The way we know that something is absolutely true is by proving it. Like
you know we know that every sum of angles in every triangle is 180 degrees and we can prove
it and then we know that this is true for every triangle we meet even some we didn't meet.
Proofs are what make us certain about certain mathematical facts. What makes it they're certain
about it is that they are convincing they follow this logic that, you know, any person wants to
verify the proof can just follow the steps of the proof and be convinced that it is indeed true. To
someone who didn't know it was true in advance - let's call this guy a verifier of the proof -
there's a way to check even if he didn't know a proof to check given a proof that it's
correct and usually it's much simpler than proving a theorem right. The prover,
the guy who proved it, may be a genius, one in life lifetime, like Wiles who
proved the Fermat's last theorem, but once he did it, you know, he wrote
down a proof and then people, you know, maybe with some amount of work, but not much need
for ingenuity, could verify that it's correct. So that's a proof. So what are zero knowledge
proofs? Zero knowledge proofs, by their name, they are proofs that reveal absolutely no information
to the verifier. So again we have a prover who knows some truth and some proof of it maybe
a mathematical theorem. There is some verifier, someone would want to maybe be convinced of that
truth but would not be fooled by any nonsense so it's the process in a zero knowledge proof
should be convincing on the one hand if the claim is true - should not be convincing if the claim
is false - so if I don't have a proof for it... So let's say it's me and I want to convince
you.. This conversation between us, at the end of it you know nothing more than you
knew before except that the claim I made was true. There's no information about the proof
in this conversation. There is no information about anything in fact that you didn't know...
and nevertheless there is no way to fool you and you will be convinced. I cannot trick you into
believing something incorrect or something I don't have a proof of... BRADY: You say that after
you've convinced me I have no new information except for the information that XYZ is true?
AVI: Yeah so maybe let's give an example. It's a story I like to tell even though it seems like
mathematicians may be paranoid. So it's you and I again, but say I'm a junior math professor and
you are my chairman... and maybe we are both number theorists and I come to you and say look
you know I just proved the Riemann Hypothesis. So for the audience this is maybe the most famous
problem in mathematics - it's the Holy Grail. And I come to you and I say look I proved it -
can I get tenure? - and you say sure if you did, show me how the proof goes, you know you are
also a number theorist... so I mean in a normal conversation between mathematicians you
know I'll start using the board or your brown paper or something and you know start
showing you the lemmas and the proofs and the whole sequence maybe it will take an hour, maybe
it will take a day or maybe it will take a year, but you know if I had the proof you'll be
convinced. And what's the problem in this process, I mean there's no problem,
that's how mathematicians work. But there are a few stories in the
history of mathematics - some of which you may know - that it didn't add quite as well
where the senior guy, having heard the proof, rushed and published it. BRADY: Stole it. AVI:
Yes you know so it happened.. it's not that it happened often, but it happened.
So maybe the junior guy, you know, me would like some protection. It would be much
better for me if I could convince you completely that I have a proof I know a proof of the Riemann
Hypothesis without giving you a shred of evidence besides the you know that it's true.
So that's the value for a zero knowledge proof. So that's an example, so now you should ask yourself
which mathematical statements, or which statements at all, have such proofs? Maybe some do maybe none
do, it seems counter-intuitive to say the least, because we somehow associate conviction with
information transfer... I mean there's nothing, if I didn't learn anything new and
I didn't know this was true... I need... yeah. It's another example - suppose
that we are both faced with some sudoku puzzle you know somehow it's, you know, it's too hard for
you but I know how to solve it and I tell you look Brady I can do this one and you say I
don't believe you. All right so one proof in this case is very simple, right, it's something...
I just fill in the blanks you check them it's a very simple type of proof. There's a way for me to
convince you completely that I can do it without you know writing any anything
it's a different process BRADY: So I don't know so your algorithm, but I know you were telling the truth?
AVI: You don't know the algorithm you don't know anything that you knew
before except that you now believe me that I I can fill it up and yeah. We are talking
about finite objects so the proof that the sudoku thing I can solve it is just the feeling of the
numbers proof that there are infinitely many primes I can write one down if I had the proof for
the Riemann Hypothesis I expect it would be finite and I could you know publish it right, so as I
said you can ask yourself what kind of statements at all can have such proofs? This question
was raised in the context of cryptography by Goldreich and Micali and Rackoff in the mid
80s about a year later Oded Golreich and Sylvio Micali, we proved that every statement...
every statement which has a proof has a zero knowledge proof, okay, every. So we can do it with
sudoku we can do it with the Riemann Hypothesis, every statement which has a proof also has a zero
knowledge proof. But I just want to say that this zero knowledge proof will be slightly different
than the, you know, so in a normal proof you just write it down - in a zero knowledge proof we need
to interact, you need to ask me questions and, you know, it's an interaction, okay, so zero
knowledge proofs are interactive. BRADY: How can I possibly interact with you without increasing my
knowledge? AVI: There are two separate questions. First of all you can interact with me
andI can refuse to answer any questions you like and then you will get no knowledge. Giving
proofs in an interactive settings is also you know natural.. you say, oh explain this to me I
didn't get it or show me an example or whatever. So interactive proofs is a natural object - how do
we even prove that something gave no information? I mean you could you can wonder about that. How
can one prove such a statement and the way to prove such a statement is that somebody else who
has no knowledge of the proof could have generated the conversation we just had. If somebody or you
yourself could have generated the conversation we had. If you yourself could have generated the
conversation we had you didn't need me - only use the knowledge the truth of the statement could
have generated the conversation we have - if you could that means you learn nothing. So that's
how you prove that something is zero knowledge. The way we prove that every statement has
a zero knowledge proof was in two parts: First we proved that a certain type of
statements, which is very pictorial, has a zero knowledge proof - okay this is a statement about
colouring maps which is, you know, relates to the famous problem - four colour theorem - so
maybe I'll mention it. So we proved that this type of statements about the ability to colour maps has
a zero knowledge proof okay - if you have a proof it has a zero knowledge proof - and then we appeal
to a general result about the NP completeness of this problem. I may talk about this is a very
important concept in computational complexity, to derive from that that every statement which
has a proof has a zero knowledge proof. So let me explain about map colouring some map you
know this is a map like in geographical map and you can think of the.. what we see are countries
so you would like to colour the country so that things that are neighbouring will have different
colours. So maybe we colour this one blue - if we colour this blue it means that we cannot colour
any of these guys blue - so maybe with the colour this one red - and this we cannot colour
red and blue - so this has to be some other colours - green - I guess
this has to be coloured red. Let's see if we can do it with three colours,
yeah because this we can colour red as well right - so only countries which share a
boundary, a border, cannot be coloured with the same colour - and then we can I guess
colour this green or blue, whatever you like. So this particular map can be coloured with
three colours. It's a very famous theorem in mathematics that every planar map like this one
can - no matter how many countries it has - can be coloured with four colours. Or if I need to
convince you that I can colour a planar map with four colours, you don't need any convincing
you know that there is a paper doing this for any planar map, however not every planar map can be
coloured with three colours this. This is a map yeah, so this is also a country, okay, so we have
four countries and they all touch each other they all have borders with each other, so this needs
four colours... not every map can be coloured by three colours. So now it's an interesting
thing to prove, you know I claim that some map can be coloured in three colours, right, suppose I
make this claim you don't trust me say I want the proof? Okay, I can give you the three colouring
like I gave it here, right, say, oh that's right I mean you check the boundaries and say okay
yeah that's that's legit, I believe you and the challenge is to provide now - the challenge is
to provide the zero knowledge proof. So the first part of our paper shows that claims of this type -
this map is three colourable - has zero knowledge proof. BRADY: But the only way I can
see that you could prove that is just by by doing it, by demonstrating it, by performing
the act. AVI: That's right - so that's not the only way... it's not the only way. Let's draw
again the same map. So I want to convince you that I know how to colour this map and instead
of telling you the colours which would reveal information that I don't want to reveal I instead
maybe these countries also have numbers and here instead of writing down the colour for you or
painting it, I will put an envelope. Okay so I tell you Brady this map is three colourable
and I have a three colouring for it and here's my proof - that I put the colour I need
for each country inside this envelope - each envelope is like a commitment once I put it on
the table - and they're real envelopes, think of it as real envelopes - I mean if we had them we
I can do it. There is envelopes and inside each is the name of the colour I'm going to
use for this country. BRADY: So if I open an envelope it will say red or blue.
AVI: Yeah, so first of all if you open an envelope - let's say the promise is not only that
it's three coloured but three coloured with these colours - red green and blue - so if you open an
envelope and you see purple you throw me away, you say I don't believe you, right. Again a normal
proof would be like I open all envelopes for you but that will reveal the colouring. What will
happen in the process of proof I will only let you ask me, Avi, you know, I don't believe you
so maybe I see that countries one and four are neighbouring, I challenge you open envelope
one and envelope four, and I open them and again if you see a colour that's not a red green
or blue, you throw me away. Also if you see the same colour in both you throw me away you
say I don't believe you and the process ends but you know it's possible and it will be if I
had the proof and we did it you know I was not trying to cheat you that you'll see two different
colours, of course this alone should not convince you very much that you know maybe the kind of
the map has a million countries. BRADY: You could have just gotten lucky. AVI: I could have
been lucky and so you want to be convinced convinced 99.99999 percent that I cannot cheat
you. 100 percent as I say often we don't have in our world so in fact in this sense it's not
completely like a mathematical iron clad as you mentioned before. You can achieve as high you know
confidence in the way for verification as you want but and it will be as close to 100 percent as you
want just by repeating this process but it will never be a hundred percent. Anyway so then you can
do it again because you want to gain confidence you do it again and I open again the two and then
you do it again I open again we do it as long as you like this cannot be it right because if I
really put in these envelopes the colouring that I had in mind then you'll eventually have
opened all of them and learned everything. So here is the trick, after you looked at two
envelopes of two neighbouring countries I put a different colour colouring in, okay?
BRADY: Same map different colouring? AVI: Same map different colour I'll explain
in which way it's different but since I have a colouring you don't
believe that there is any colouring I put a different colouring in then you
test me on two other and then the process continues - so now it's not clear why it should
be convincing, right, because I put a different colouring in and also it's still not clear why
it gives no information because it's not clear why maybe there's only one colouring - maybe there
are many - there are maps with one colouring. So I have to explain to you how both of there so
now I want to convince you the way I'll do it will reveal no information to you, okay, and for this
I have to explain how do I recover, how do I fill the envelopes again and again with the new
colours. It's enough if I do it in a map of just two countries - suppose this is a map you know it's
part of a bigger map Okay - so there are many more countries but we
will focus on two because you are going to quiz me on two - and suppose I had some colouring
of this map and in particular this was green and this was blue - and otherwise there were you
know some blues here, some blues here and reds you and so on if I have any three colouring
of a map - one - then I automatically have six. Why? I can always rename the colours - I mean
I could you know it's green right yeah BRADY: you could invert it? AVI: I could yeah I could permute them. If I have this colouring - I can just rename the colours and I call this this green and this red and this blue and yeah maybe I'll do all six - I don't know So if I had one colouring, I had six colourings
because I just renamed the I can rename it so the way I'm going to fill the envelopes each
round is by randomly picking one of these patterns and using it - so if I had one I had six. Now look
what will happen to a particular pair that you might quiz me on - in one colouring
it may have been green and blue but if you look at green and blue here and you see
what happens with random renaming - everything is possible and equally likely if I pick it randomly - so the point is that in this process if I had a proof you will not only see two different
colours, you'll see two random different colours you'll see just a random pair from this column, but
it's something you could have done yourself - you don't need me for this. If I had a proof you will
learn nothing because the process will just reveal reveal pairs of random colours. If I didn't have
a proof, you would catch me cheating - that's it. If we talk also about Andrew Wiles's paper - how
would I convert that to the zero knowledge proof - it turns out that the answer to both questions is the
same - and the answer is NP completeness. It's a one type of question that captures all mathematical
statements - so one particular and very favourite NP-complete problem is the problem does a
map have a three colouring? What do I mean by capture all mathematical statements - if we
have any mathematical statements - let's say the Fermat's Last Theorem - or that this number
is a product of two points - or the four colour theorem - any statement - also false statements. Maybe
there are finitely many primes - or the sum of angles in a triangle is 170 degrees - these are false
statements but any formal mathematical statement can be converted into a map and I should stress
this conversion is is efficient there is a simple algorithm known to all, it's a result from
the late 70s - a fundamental result by independently by Cook in the west and Levin in the
east - they basically prove that any mathematical statement of the type we just... any
mathematical statement that's formal can be written down can be converted into a map and this
translation between the statement to a map is very simple, efficient, known to everybody. So that's the first part of there and what do you want of this translation? You want two
things - that if the statement is - well we want three things actually, but let's start with two which
are the the most obvious one. We want that if the statement is true the map is three colourable - and
if the statement is false the map is not three colourable. So at this point we can translate any statement to
a statement about the three colourability of maps this result of Cook and Levin has an
additional property which is very important: If on top of the statement I
had the proof of the statement the same algorithm that translates it to a map
will also provide the three colouring of that map. If it was a true statement then I had the proof
of it, not only would I give you a map but I would also know a three colouring of it - okay so there
are these three properties if it's clear now that if Wiles wanted to prove to you in zero knowledge
that he has a proof of her Fermat's Last Theorem he could do it because he could translate - you could
both build the map because you know also the process just from the statement you could build a
map so now the proof of the Fermat's Last Theorem became that the three colourability of this map that
you know it's the map of Fermat right, it's the Fermat map, and then he would prove
you using what the envelopes I just showed he would prove to you that it's three colourable
and this is an equivalent statement - and if you learn nothing from this you learn nothing at all.
BRADY: This process you're telling me about from the 1970s was that where you can convert... it's almost like you can take any proof to it and like show it to a secret third party
and they'll just give you a token that says yeah you proved it like and then you can
just come and show me the token yeah I've got the token which means I proved it. AVI: no no no no no no - I mean you still have to be sure that... we just translated Fermat to three
colouring of map but you still would like to you know see the colouring it's not... we
don't trust anybody in this business right, I mean the verifier does not trust you know.
BRADY: We trust that algorithm, we trust the algorithm that creates. AVI: You don't need to trust it the proof is very simple you can read it I mean.
It's just we teach it to undergrads and
you can teach it in high schools it's this is a very very simple sense of an extremely powerful
statement but it's it's a fundamental result it's an absolutely cornerstone of my field - but this
does not require trust - okay, so things we've seen proofs of, we don't require trust and
this we've seen, yeah, so it's a simple statement BRADY: It's going through that filter of NP completeness that gives us the ability to do this AVI: You know, I possibly could have
done a trick with envelopes directly on Wiles's paper I mean I could - it would be less colourful. I could
have done one or directly on the product of two primes I could have done one but it's this
concept of NP completeness is extremely powerful and I'm not going to get into well I mean it's
my favourite topic also BRADY: Coming back to the product of two primes, when Avi's cryptography business came to Brady and said I want you to use me as my business and I promise
you I'm always multiplying two primes and I said to you prove it to me without giving away your
industry secrets, what would you have done? AVI: I would translate it to a map and given you a
zero knowledge proof that this map is three colourable. And you would know that this is an equivalent
statement to the statement that I have two prime numbers which multiply to this. BRADY: But you would
still have to do the zero knowledge on the map you couldn't you couldn't just show me the
map coloured with three colours and said look see the map's three coloured. AVI: That would reveal information... in fact the colouring will tell you the primes. You don't want that you want that,
yeah, I mean the whole point is that you will learn nothing from the process - if you know the
colouring of a three-coloured map that you didn't you know before. BRADY: The three coloured map here that we're creating from all our different proofs from Andrew Wiles, from our primes, that's
an analogy is it or is it can you actually is it actually... AVI: no no yeah absolutely yeah it's
it's real - I mean the maps will probably be humongous we'll have million or zillion
countries in it - at this point I'm not suggesting it as an efficient process although
people have worked and made efficient versions of it as like I said with digital currencies
it seems like it will be will be commercially available for some purposes
absolutely - it can be used but it will not be used for mathematical theorems in my... I mean actually
if you think about it, the way mathematical proofs are written they are not completely formal
right, they use English words they say oh in a similar manner we also deduce this or we
refer to another paper either read it or don't read it so they they have black boxes that are
not filled and you know may have some errors or anyway you you don't necessarily read. Formal
proofs are proofs with symbols like you know first order logic it's just pure symbols from the axioms
you state the axioms in the beginning and then you go through the chain of deductions. If Wiles wrote
his paper in this language which - that's what you would like to - then it would not be 500 pages as
it is now or 300 pages - it will be a million pages and it is this type of formal proof that would
be converted to maps right you know you need to be formal about it right - so that's not
the usual purpose of zero knowledge proofs, their main purpose is in cryptography and but I would
say you know certainly intellectually or for a it's sort of like an amazing thing it's an
impossible thing that cryptography can do and it's just one of many many many impossible things
you probably know about digital signatures and playing poker over the telephone - maybe
you don't - or you know digital currencies or you know elections electronic elections, lots of these
things you know are sort of impossible in a normal world and you need the axioms of cryptography and
the you know know-how of cryptography to make them work - zero knowledge is just is one example is you
know a favourite example because it's so striking that it's possible at all. This NP completeness is a fundamental point it's a it allows you when you want to prove a theorem
like zero knowledge proof for every statement and actually it occurs in in many other situations
in complexity theory having a particular problem with nice properties that captures all
other problems is very convenient - you notice that in what I just showed you the zero knowledge
proof for colouring maps I use properties of maps and I use properties of colourings... this
is not available in the Fermat Last Theorem it's not available in multiplication
of points so having an NP completeness having an NP complete problem so elegant so
nice and so combinatorially convenient was essential for us to devise this - to devise this
proof BRADY: So it's like a mathematical lingua franca in a way? AVI: Yes it's a language it's
absolutely it's a language which is extremely useful for demonstrating things that
in another context look impossible. The main use of NP Completeness is just a demonstration of
difficulty of this problem - basically what it says it captures all other problems it captures lots of
problems lots of optimization problems so we just show that finding three colourings of maps is as
hard as proving mathematical theorems in general if you had an efficient way of three colouring
maps you would not need Wiles for Fermat right, you could just run your you translate in
the same way and run your algorithm. So NP complete problems are problems which are expected to be
difficult - the previous NP question the major question of computer science is about does every
every such problem has an efficient algorithm - so in particular it is can be asked does every
you know that's proving mathematical theorem let's say within some limit of number of pages
is easy or not? We don't know that it's hard, it's possible, it's quite possible that there's a really
simple algorithm that you feed it a statement like Fermat and in a second it spits out the answer
it's true and even provides a proof - that's the P vs NP question BRADY: But you told me already
that every proof can be converted AVI: I said that if you had a proof or mathematical statement, well I told you two things every statement could be converted to a map in a way that preserves truth -
so it just says that three colouring maps captures every mathematical statement, right, so for this
reason proving mathematical theorems in general is as hard and as easy as just three colouring maps -
we don't know whether it's hard or is it just not I also showed you that if I have a proof for a
mathematical statement it can be translated to a three column of maps BRADY: So any statement becomes a map and if it's a proof it's a colouring AVI: Yeah if the statement is true any proof of
that statement becomes a three colouring of that map BRADY: So if I made a false statement
170 degrees in a triangle I would get a map but my colouring would be
AVI: There would be no no no there
will be no colouring no legal colouring absolutely yeah like there is no proof no legal colouring
it's a one-to-one translation yeah BRADY: That's an amazing machine AVI: It's an amazing machine this is
NP completeness it is an amazing machine it's like the fundamental you know yeah again the cook
Levin theorem it's from 70 BRADY: What does this machine look like? Is it a is it just a theoretical thing at
the moment or is it not... AVI: A brilliant part yeah no it's possible no it's an algo it's not
an equation it's an algorithm it's an algorithm it gives the first NP completeness result so
it proves that some problem not this problem BRADY: Is there like an online is it like an online
calculator or a program that you can go and put your statement or proof into and press
a button and it spits out. AVI: Yeah it is there you could program it and it will be easy it's
easy to program and it's easy to understand but you will tell you something about its
nature or what it relies on in order to have any result of this type you have to understand
what are mathematical statements what are proofs of mathematical statements what is the
verification problem process of a normal proof and the first thing to realize is that
verification is a central - it's really it's not the proof but the verification of proof
that is the main aspect of mathematics BRADY: And here verification was me opening the
envelope AVI: Or even before just you checking the colours if it's open right forget the zero
knowledges yeah - so the verification process in any proof system in mathematics is simply an
efficient computation it's a computation you check here you check that colours are different and if
it's written logically you check that you know if we proved a and we proved a implies b we
also proved b these kinds of things are they're all local simple things appreciate your
questions. BRADY: I'm thinking I'm thinking of this is a very simple thing but presumably
in reality these maps are ginormous and even spotting two coloured countries together
might be hard to spot. AVI: no no, but you pick two nice you you just pick two countries I mean it's very
simple I mean even if it has a zillion countries I pick you know 100,273 and another
one if they are not neighbouring I'm not going to answer you but if they are neighbouring I'll open
them it's simple it's simple even if it's a long number you just have to pick randomly the two
numbers and are open now this is easy but back to forget just a second the zero knowledge aspects
I mean just we are talking about NP completeness the verification of a proof of a normal proof
mathematical proof is a computational process is a computation is local it proceeds
by simple steps that check you know the very simple objects or if they you
know you know they just check that two things add up to a third or things of this this
type what Cook and Levin understood that you can take the verification process of proofs and convert them - the statement and the proof
and the process - convert them to this language let's say of three colouring maps that
are simple problems that capture all such processes and localities of computation is
what's essential in this translation so they start from an abstract verification of a proof and they
generate from it this map, okay, that's what the algorithm does - again it's simple once you know
what you want to do - it's a great idea and an amazingly powerful BRADY: Do these guys win
some prizes? AVI: Of course and they should win more MARCUS: yeah have a proof we might be quite difficult to
find like Fermat's Last Theorem took 350 years to before my colleague in Oxford Andrew Wiles
found the proof... SIMON: And of course because it's the last one that anyone can prove it's the most
precious one it's the one that's most desirable
Anyone know of a good explanation of the mathematical statement -> map coloring problem algorithm?