Computer Scientist Explains One Concept in 5 Levels of Difficulty | WIRED

hi my name is amit sahai and i'm a professor of computer science at the ucla samueli school of engineering today i've been asked to explain zero knowledge proofs in five levels of increasing complexity a zero knowledge proof is a way for approver to convince a verifier that some statement is true and yet reveal no additional information beyond the fact that the statement is true zero knowledge proofs are being used in blockchains and cryptocurrencies so cryptographers are excited about zero knowledge because of its amazing mathematical properties but also because of its incredible applicability to so many different scenarios [Music] what's your favorite subject i'd say math some of these small problems can actually be really big and complicated it's like a puzzle i love math for the same reason today i'm going to tell you about a thing called zero knowledge proof so in the zero knowledge proof there are two people there's approver and a verifier and i want to prove that something is true to you but the weird thing is i want to prove to you that it's true without telling you any reasons why i remember when i first heard about it i was like wait what how could that possibly be right yeah so what do you see in this photo a lot of penguins yeah hidden among all these penguins is a puffin do you want to try to look for it do you see where it is hmm i know where it is but i don't want to tell you do you believe me you're not sure to believe me right yeah but what if i could prove to you that i know where the puffin is without revealing to you where it is let me show you i took that photo that we showed you and i put it behind this poster here why don't you go take a look through that hole i see the puffiness so when you look at this board we don't know where the photo was right was the photo like with the corner here in which case the puffin would be all the way at this side or was the photo with the corner here because the buffing would be on the other side so this is a really simple example of a zero knowledge proof i convinced you that i knew where the puffin was but you didn't learn anything else why do you study zero knowledge proof when i first learned about them i just thought they were so cool but it turns out they're also really useful not just for finding like puffins if you just type in your password and the hacker hacks into the computer they can just get your password right yeah what if instead we could somehow use a zero knowledge proof to log in you would just be able to prove that hey i'm chelsea without revealing anything to them if you could do that then it would be amazing right yeah because then even if the hacker hacked into the computer he wouldn't learn anything because even the computer doesn't learn anything so chelsea in your own words what is azure knowledge proof zero knowledge proof is proof to a statement you don't show them why or what you just show them a tiny segment or just do some sort of weird magic trick that's not really a magic trick and they will be convinced and you didn't show them why or anything like that so have you ever heard the term zero knowledge proof before i have not no right it's a way for approver to convince a verifier that something is true without revealing anything about why it's true which sounds totally bizarre right like how can that possibly be what i want to do is prove to you that i know this combination without revealing the combination to you and what you could do is you could write a little note a secret that i definitely wouldn't know fold it up stick it in here and then if i know the combination i should be able to open it and tell you what you wrote all right there we go all right so my dog is named doug did you figure out what the combination was no so nowhere in this interaction did you see any information that you didn't already know and yet i convinced you that i know the combination right yeah so what's the exact purpose of azure knowledge proof is it like proving something but without giving enough information that could endanger whatever it is you're proving so you're asking like why shouldn't i just share my secrets with somebody people don't trust each other and if i was able to prove that i've done something correctly to someone without having to reveal my secrets then that person would trust me more how does this relate to computer technology like do you type it into a computer and somebody else receives it or is it an in-person interaction suppose you wanted to exchange messages with someone that you knew what would you guys do you'd probably first get together and like figure out some secret code right and then like write messages to each other in that code but what if you've never met the person before what if you want to exchange secret messages with me and we've never met each other before how could we possibly do that i have no idea it sounds impossible but it does but it's not we wouldn't use like a physical lock or a physical box we would instead use mathematics to do these kinds of things you could take a message and encrypt it using mathematics and then i could prove to you that i know the key i could open it up and send it back to you that way i would be proving to you that i know the mathematical key to the mathematical lock box so based on what we've discussed today in your own words what is a zero knowledge proof it's like if you have this really important secret that you want somebody to know about but you don't want to tell them everything you can use as your knowledge proof to prove to them that secret but not give away all of it [Music] what are you studying i'm a first-year computer science student at usc viterbi i'm interested in all things like data and internet and blockchain and cryptocurrency have you ever heard of zero knowledge proofs only in passing so actually in the blockchain space is one of the spaces where we are seeing zero knowledge proofs being implemented and uh and i think it's just the beginning let's talk about zero knowledge proofs at its core a zero knowledge proof is an interaction between two people then i should be able to convince you that some statement is true but you won't have any idea why it's true well like understand that it's true because like you know the operations performed in the proof are like of a certain like you know they have like certain attributes that would make them true what you're basically asking me is wait what right right so this is what makes cyrano's proof so fascinating and so counterintuitive and i think the best way i can i can explain it to you is by by means of an example but before we do that i have to decide what i'm going to prove to you in a with a zero-knowledge proof and the way we're going to approach this is through something called np completeness what an np-complete problem is it's a problem that's really hard to solve but if you can solve it you can solve any problem that's in the class np and that includes a vast number of problems and what we're going to do is we're going to use an np complete problem to actually prove an incredible variety of statements through a zero knowledge proof and the specific and complete problem that we're going to be looking at is called map three coloring okay so here we have a map okay and these are a bunch of countries and we've arranged them so that no countries that have the same color share a border that's what makes a map like this validly colored and now you might think well why should we care it turns out that whether or not a map can be three-colored in this way is an example of an np-complete problem and it turns out that you know maybe what you really want to do is you want to give a zero-knowledge proof that you have at least point three bitcoins right that would be cool yeah without revealing what the address is of your of your account it turns out i can take that statement that i have at least point two bitcoins and convert it into a map of countries and that map of countries will be three colorable like this only if you have at least point two bitcoins how would we turn something like this into a zero knowledge proof of course the first step is we have to erase all the colors what i've done is i've put a color inside each of these envelopes now how do you know that it's a valid coloring you don't right you have to pick any two neighboring countries you can pick them however you like at random can i get these two these two all right sounds good right here we have green right and over here we have blue okay and as you can see there are two different colors right so you have a little bit of confidence right that i have managed to color this correctly but not that much confidence because i've only shown you two of the countries yeah right so now of course one way to get more confidence is to open up more of them for you but that would be revealing information to you i don't want to do that so instead i'm going to ask you to please turn around and now let's change up these colors can you pick two countries at random and we'll reveal to the colors again okay this one and this one nice and they're smart of you to check with the same one of the ones you already had right but as you will see now it's not green it's blue and this one on the other hand is three okay the colors i showed you last time don't work with these new colors right this wouldn't have worked yeah because of this one right exactly right but it works for this coloring that i'm showing you right now so what we've done is we've made it impossible for you to put the pieces together and if you do this let's say a thousand times and if i correctly showed you different colors each thousand times you'd be really convinced and that's it that's the entire zero knowledge proof oh okay so is it like there's no like actual like explicit like step one step two step three it's just like a probabilistic yeah in actual implementations we wouldn't use envelopes we would use encryption right but it's really this is the protocol so what are the broader implications of like zero knowledge proofs are they supposed to be like more practical for like implementation and are they supposed to like structurally prove something it's not about making something more efficient it's about doing things that we just didn't know how to do before i can actually prove to you without revealing to you any of my secrets that i use to behave honestly right i could prove to you that i signed some encrypted document correctly right without revealing to you what that secret document was that ability to change the game like really just change what we can do is what zero knowledge brings to the table where do you think we could build like more trust using like zero knowledge proofs and like its implementations one great example is like in elections if you could prove that an election was correctly conducted that every vote was counted and it all added up to one person winning with a particular total in zero knowledge then you don't have to give up the actual votes of any person and yet everyone could see that hey yeah it was done correctly it's so great to have you here and talk with you eli um can you tell me a little bit about your research my research is in cryptography specifically i'm working on some various multi-party computation protocols the one i'm working on right now is a system for computing aggregate statistics so that service providers like google chrome or tesla can collect those statistics without learning anything about individual users data that's awesome i as a user don't have to let firefox know that my favorite website is mylittlepony.com but they can know how many users go to mylittlepony.com every day that's near and dear to my heart not a party competition obviously zero knowledge proofs are about proving things to another person without revealing the details of what it is that you're proving but you know in my mind zero knowledge actually goes even further beyond that it's like this overarching concept that you can see a lot in multi-party computation where you want to accomplish some sort of task without revealing anything more than exactly what you need to accomplish that task right and it allows you to prove that you've been behaving honestly without revealing any of the secrets involved that you used to actually behave honestly so we of course know that zero knowledge proofs for np complete languages play such a huge role in cryptography i'm curious what was your first experience with empty completeness like yes so my first encounter with np completeness was in my very first algorithms class that i took as an undergraduate so that was my first introduction is that an np complete language is this amazing problem that not only tells you about itself but solving this problem can actually tell you about an entire class of really interesting problems we first started thinking about proofs as an interactive game where we're talking to each other that made journalists possible absolutely right yeah and and the idea that randomness could be useful for proving something again seems so counter-intuitive if we think about this platonic ideal of a proof right there's no randomness there's no non-determinism that's present there and it has to do with you know this whole idea of flipping a proof on its head you know in an old classical proof randomness is specifically against the goal of what you're trying to do right because you're trying to make everything obvious and you're trying to reveal the flow of information indeed but once you flip that on its head and you're no longer trying to do that suddenly all of the bad properties of randomness become good exactly right because randomness is unpredictable and that's what we want right we want that unpredictability randomness to be utilized to actually hide the information that we want to hide how have you used your knowledge in the projects you've worked on what are the challenges that you find in my experience usually the hardest part is figuring out exactly where the best place is to use it i've written some papers in the past that have used zero knowledge in a more theoretical way but when it comes to applications some of the most exciting applications that i've seen so far have been in the blockchain space so what are some of the efficiency bottlenecks that you find in terms of efficiency uh one of the coolest things about zero knowledge proofs is that there's so many kinds i like to call them flavors i think that in general when you're using zero knowledge proofs in application the main bottleneck tends to lie on the approver can you take the provers job and split it up into lots of parallel computations right that's such a fun question it's such a great question and yeah i think i think we still don't know the answer to that as a field one of the coolest things i've seen over the past you know three or four years when i've been working on this kind of stuff is the transition from theoretical to applied and seeing all of these amazing systems that people thought of in the past 30 years start to actually get efficient enough to be actually made no doubt and especially with cloud computing exploiting the power of the cloud to enable zero knowledge proofs and to make use of journal electricity would be amazing right and also in the blockchain space for example if you want to speed up the generation of proofs if that could be done in a distributed way then that would be great one of the hopes that i have is that the power of multi-party computation is about bringing people together who are mutually distrustful yeah right so can we take that power that's there in the cryptography and use it to somehow help with the tremendous level of mistrust that exists in society right now in helping to bring groups of people together i think that's one of the reasons that i was so drawn to multi-party computation in the first place in my mind one of the most important problems in the world is the fact that so many people don't trust each other and to be able to actually use math to create technology that can allow people to work together without having to trust each other is a really cool and awesome mission i think it's so great to see you again i think last time we met was in 2017 or something like that i think we zoomed once during the pandemic but it's good to see you in person right absolutely and actually in 86 i was taking a crypto class with professor edelman the a of rsa and he assigned me the paper by uh god of wasabi charlie redkov zero knowledge proof so that's indeed my first ever presentation ever in this country it was about zero knowledge that's what's up on zero knowledge yes such a almost hypnotic concept it's also an interesting um way how mathematically to formulate those concepts right for example we have data then eventually we said that from data like data mining you can get the information and then you have this word called knowledge right right so knowledge has been long debated even in philosophy what is knowledge but here is in a very fascinating way mathematicians or computer scientists right want to somehow capture knowledge they didn't say zero information proof right so so what's your take on why knowledge is rather than information or zero data proof clearly this data there so can't be zero data absolutely i don't think we still have a completely satisfactory answer to that question what was so such a beautiful insight as i'm sure you know is that the idea of zero knowledge being something that you can already predict right if you can already predict the answer then you must not be gaining any knowledge by that interaction this insight of being able to predict the future accurately and that being an evidence of a lack of new knowledge was such a beautiful insight such an amazing insight why not zero information here fundamentally i uh clearly from computing perspective security perspective it's a how much knowledge you gain i guess more than how much information you gain and how much data you have right so that big data doesn't immediately imply a knowledge but people can sometimes right sometimes i mean for example in medical research how amazing would it be right to be able to have a drug and be able to prove that my drug works in this model and yet not have to actually reveal the structure of the compound what uh currently you think it would be the next directions in one of these next big things yeah this concept of zero knowledge programs would allow you to carry out completely arbitrary computations in a zero knowledge way without any interaction right i can just take the program convert it to a zero knowledge program or an obfuscated program and then just send it to you right and then you can run it and gain the benefit of that computation without having to talk to me anymore that's right there's non-interactive nature the non-interactive nature but with verification verifiability in it sometimes when for example when you have multi-protocol exchange that's it you know just like random numbers showed up you have to enter the random number as a participation authentication right now yeah clearly i think in blockchain they also began to incorporate more uh their knowledge proof in the ledger we're definitely at this moment now where zero knowledge is going to be used more and more there's so many uh conferences and meetings that that occur in the zero knowledge space where you and i are not invited because it's for the people who are who are developing it the people who are programming not as mathematicians yes yes and i think that's a sign that's a sign that our baby has grown up and you know it's time for it to be developed i think profoundly the students often also ask me what are the future direction both in terms of crypto zero knowledge proof in the real world and how mathematically you see in computing it's a great question i know i wish i could see the future i i can't actually but let me try the part of that that i'm the most comfortable answering is of course the mathematical side i think that there is you know we've done so much in cryptography over the last few decades but we understand so little you know even today we understand so little and i think the most fundamental aspect of that is understanding hardness how do we get hard problems how do we actually build mathematically hard problems so that we can then use them to build efficient zero-knowledge programs and efficient or knowledge proofs right i guess also with quantum computing you need even harder problems indeed absolutely you know now that we have we have the specter of quantum computing coming at us and we all know that quantum computers can break a lot of cryptographics that's profound challenge it's a profound challenge so can we find new sources of hardness that are quantum resistant even quantum computers can't break and that's something i've been working on for the last several years but i'd be very excited to see what happens in that in that space but i'm sure they will motivate beautiful mathematics yes that's right you know one of the great things about the real world is that people in the real world have demands and those demands often sound impossible and that's where we come in it's our job to make the impossible possible

2022-01-19 21:05

Other news