zkSummit - ZK0x01 - Zero knowledge proofs intro with Str4d (Zcash)

Transcript

so this is Strad from z cash and strat is going to be doing a very high-level introduction to zero knowledge proof s-- some of you might know this stuff some of you might not but i think this is a great way to start this event so thanks a lot oh there we go that's cool yeah so hi I'm Jack I'm from Z cash and I suck it cryptic crosswords I I just can't do

them to save my life sometimes I even wonder if they even have solutions so I fortunately have a friend who's really good at them but you know she likes to sort of tease me a bit so yeah I'll often ask her you know do you know the solution to some crossword that I am having struggled struggling with what sort of things could she tell me in response you could say yeah I know the solution well that's useful you know that's going to tell me okay if I believe her then then there's a solution but what if I don't trust her what if she's yanking my chain she could say here's the solution but it's no fun like you know now I now I have the solution I don't get to like bash my

head against it for the next three days what we really want is the ability for her to prove that she knows the solution to the crossword that I'm trying to solve without actually revealing it and so this is funny enough where zero knowledge proof scamming so the full definition of this was back in 1985 from God verse and McCauley and Rakoff and they better said that they looked into ever'time was essentially they were looking at soundness of proofs and essentially verifiers trying to ensure that provers couldn't lie to them and then they then flipped it on its head you know the the industry and with what happens if the verifier is malicious

you want to make a proof but not actually yeah giving you information away other than that they formally defined that to have what's called a zero knowledge proof it must have these certain properties specifically completeness so if the prover in this case my friend Alice hat is telling the truth she can eventually convince me like it might take some time it might take some bandwidth but eventually she can convince me that yes she does know the secret information it must have soundness which means that she can only convince me if she knows the valid solution so that means that if if she doesn't know the solution or if

she knows an invalid solution either I can easily detect that and check that and then finally she needs zero knowledge yes this is the what the papers calls it which is that I must learn absolutely nothing else other than she knows the solution or more generally that what him a statement that she is proving is true and that's it essentially the least amount of information you could possibly feel really can listen firm ation they know you know that's one bit of information of really can listen for mation it would go back to a zero usefulness proof so let's say okay how so how do these

things actually work in practice the simplest example I can probably go through in a reasonable amount of time is very simple example using billiard balls so imagine that my friend alice is has his billiard balls and she wants to prove to her friend Bob who is colorblind that the balls have different colors now obviously she can see them anyone who's not colorblind can trivially see that the that the balls have these colors but Bob can't to him they look the same they just know they have random spheres so we can design a protocol that enables Alice to prove to Bob that she knows that these have the

same color you simply Bob takes lols puts him behind his back and then shuffles him around a bit yeah essentially he he with 50% probability like he flips a coin in his head and if it lands on heads he swaps them and if it lands on tails he doesn't and he brings the mech out now to him he knows that he made some particular swap but he still can't see whether you know he still can't tell the difference between them but Alice can Alice can see not you didn't do anything to it so what goes huh it goes back does that's another permutation brings them back out oh yeah those were swaps and you know you repeat

this again and again and you end up with essentially a zero knowledge proof at a very coarse interactive level it has completeness so because it's a 50% probability obviously you you get compounding probabilities and so if you repeat this n times then the probability that that Alice could have just been having a lucky yes every single time go becomes essentially negligible you get soundness because Bob knows whether he swapped them or not so yeah he can easily check that and finally he gets zero knowledge miss ware yeah he's still cloud blind he still can't see that they are no they are distant colors but he

knows that to all intents and purposes they must be and I want to sort of touch on this a little bit further technically it's zero knowledge eNOS is slightly more complex than that so let's say so just going back to this point here so we have Bob he now has gone through this protocol and he is now convinced that Alice knows that they are different colors so let's say Charlie comes along and Charlie is also colorblind and Charlie want is saying to Bob how do you know wants to know if these are different colors and Bob goes yes they are Alice proved it to me well well now we're back at at a zero useful in this

Prout proof that doesn't actually prove anything to Charlie Charlie goes why might to believe you and Bob goes oh yes but you see what happened here is I videoed the whole thing so you can clearly see and from the sides you know you can see me swapping them or not talking you see me before my hands you can see that Alice can't see what I'm doing and you can see she you can hear her saying yes they you know yes they swapped or no they didn't and if you play the whole video through then you can see yep she got it right every time and Charlie goes aha but you could be lying to me you could have either pre-negotiated with Alice to say this is the order in which I'm gonna do things before you started recording the video and then the whole

thing's a sham or it could have been a honest attempt and Alice failed a few times and you edited the video to remove the times that she fails now to all intents and purposes that looks the same as a valid run the protocol where Alice could tell the balls apart and this sort of gets at the core of what it means to have zero knowledge proof if if you imagine the real protocol as a real recording of going through and you're seeing the you see Alice you know makes us distinguish and that all happens and

then you put next to it a video that is entirely fabricated that you know either by one of those two strategies they look I indistinguishable essentially so if you now imagine I have some machine learning algorithm that I can apply to the video and it extracts out the secret knowledge in in this in this world everything everyone is colorblind including algorithms except Alice yeah just pushing the metaphor a little bit farther if I have that algorithm and you know so that I can extract information out of the out of the real run and the two runs are indistinguishable then I should also be able to extract

information out of the simulated run but by definition the simulated run contains no knowledge because it was a fake run there was there was no hidden input that was being proven which means that if if if all I can extract out of the simulated run is nothing then therefore I cannot extract anything out of the real runner and that is that is what we mean by zero knowledge so that that's the magic part that just is like so exciting and yeah it's it's it's so cool so it's actually useful for so let's say okay we now have a zero knowledge prima system it's

actually a really cool result which shows that if you have a zero knowledge equivalent system like billiard balls you can convert it into any other zero logic proven system so you could it really really really inefficient but you could use that to to prove anything you want to do so you know we want the best place for these kinds of things is where you have some system where you have private information or you have some information that you want to publicly verify where have we seen one of those before it's as the gaudiest image I could find on the Internet it's yeah blockchain is a very good example of a case where we want to we require in fact public verification of the system but we would very much like

to obscure most of properties and so you know I'm sure most people here know how a Bitcoin transaction looks but you know that's essentially the Edda block at a high level the you know you have some inputs to reveal the values and you have outputs and then those outputs then change the inputs of new transactions and that chaining is the problem that's the that's the part where you leaking your transaction graph and we can quite simply I say simply it's not quite that simple as someone who bash the head against this for this part of a year with six other engineers but the you can essentially replace the outputs of your transaction which previously were a

value in an address with essentially a commitment to a to some private information and then in your next transaction when you spend it you provide a zero knowledge proof that proves knowledge of that private information and also that all satisfies the consensus rules of the chain there are other talks I could go into they get more in detail about that but I will leave it at that for now yeah there are many other uses of of this kind of thing and verify auctions for instance so people contributing private bids and then you want the whole thing you want obviously that the winner to come out without necessarily revealing to to other parties who was actually doing bids verifiable voting you can

imagine uses for that in governments and general voting voting systems smart contracts I think a few of you might have applications there and even authentication mechanisms your basic you submit a password to a website yeah you don't want to give them your password and you can think of you know proving a pre-image of a hash is a very basic in a way kind of kind of proof you know plenty other things supporting you I'm sure that leave you and how these things actually work in practice unfortunately that's that's that's not my problem with this talk what I will do here is give you some references so this first one is a really nice paper by Keith Carter and tell who they explained it in terms of

Ali Baba's cave so you know you know the the tale of going in you know the cave with magic password and essentially you know you can escape the thieves because you know the secret to get through the backdoor whereas other people can't and essentially improving knowledge of that secret without revealing the secret to anyone likewise Matt Green has a really nice Illustrated primer using the graph coloring problem tiny bowler hats and time machines so it's really it's really worth the read and to explains the same thing I've gone through here and finally if you're actually looking for a place to sort of find resources on Anzio knowledge proofs I've started up a

website Zika P dot science right at the moment it's just sort of a grab bag of all the zero knowledge proven systems I can find and implementations and DSL xand things eventually I'm having to get certain you know start getting like benchmarks of different systems on the different low so people who are implementing these things can actually start making decisions of like what trade-offs they want in their proven systems and other things like that yeah leave leave it there if he knows got any questions then otherwise thank you does anybody have any questions assume you want to do some Q&A there

we'll just in in general yes they so like the comical example of a which you may have heard of as EK snark this it's the snark stands for succinct non interactive argument of knowledge so it's it's specifically a probabilistic proof I'm not aware of any proof systems that that are incontrovertible for the simple reason that you know you could essentially with a with a patio infinitely powerful computer you could

you could generate a proof string that happens to validate the system the yes there's that's why since you can tune these two you can tune that level essentially to to what you require there's there's some really nice stuff about ZK snacks which I which mean that you actually don't need that many things in order for it to be effectively circular but yes essentially its letters one of the things that you essentially are sort of giving up when you're trying to do this kind of thing because yeah you you can't ever be absolutely certain but they're like you can't ever be absolutely certain that AES isn't broken it's just like very very very unlikely all right so we actually I'll just jump

back on the stage thank you so much for this talk by the way