Zero Knowledge Proof (with Avi Wigderson) - Numberphile

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

Anyone know of a good explanation of the mathematical statement -> map coloring problem algorithm?

👍︎︎ 2 👤︎︎ u/Mr_Smartypants 📅︎︎ Feb 09 2021 🗫︎ replies
Captions
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
Info
Channel: Numberphile2
Views: 146,078
Rating: 4.8634572 out of 5
Keywords:
Id: 5ovdoxnfFVc
Channel Id: undefined
Length: 33min 37sec (2017 seconds)
Published: Tue Feb 09 2021
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.