ZK Series: Introduction to Zero Knowledge Proofs

Transcript

[Music] welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik finally an episode about zero knowledge on the zero knowledge podcast today Anna and I sit down to talk intro to zero knowledge proof so yeah today we're gonna be talking about your

knowledge proofs and it's very much like an introduction because none of us are experts i've never coded up a zero knowledge proof implementation of anything i've never even used to zero knowledge proof library the greatest extent of usage I've had is using Z cache so I think we're both noops in this area but we've been reading and we're trying to like break you down to a level that you can get an intuition for it at least and and we do hope you'll bear with us too we are trying to describe a pretty complicated concept in a podcast but we have we have really you know we've

thought about it I think we have some ideas on how to get this across cool so do you want to just do that what is a what's a zero knowledge proof sure it's a an area within cryptography really it's not a specific thing it's like a field of study and really a zero knowledge proof is a method by which a prover like party one approver can prove to another party the verifier that he or she knows some statement so they can either approve universal statements like there is a solution to this problem or they can prove some knowledge like I

know the solution to this problem but at the end of the day it's it's a proof about like the resulting thing is a 1-bit value it's a true or false so the answer that you're verifying is like it comes out as true true or false like I know this true or false this is true it's true true or false and they do this without revealing any knowledge about this like the background the statement so they should be able to say I know the solution to this problem and prove that they know the solution to this problem without showing the solution and that's actually so we asked I also asked around like a couple people and just to see if

I can get one liners and one of them was demonstrating that you know a secret without revealing yeah so you have a secret I want to know that you have a secret you can somehow prove to me that that secret exists but I have no idea what that secret is yeah okay so when we were first doing a lot of this research I had a for just a short while I was wondering if there was any relationship to what we had talked about when we were doing we were doing a podcast on hashing and proof of work because I know that proof of work is his concept where you get a hash which proves that work has been done and I was like okay so so is that potentially a form of zero knowledge proof I found out it isn't

maybe you can explain why that is so the the hashing proof of work does indeed prove that work has been done but not on its own so if you just get this hash you like you have no context to what it means or why it is what it is you don't know what has been hashed to produce this so it proves nothing alone so it really doesn't prove anything on its own yeah it only proves something within the context of the block so you need all of the knowledge of the block so you need the full block that has been hash and the hash so that you can rehash this block compare it to the hash that was

given and say okay the person actually did this work because improvement work like that the simplest version of it is you change a Ananse number just incrementing it by one all the time until you find some hash with a specific property and the only way to verify that is to have all the data and we calculate hash yourself so it's a proof but it it's a proof that requires full knowledge of the solution and the zero knowledge proof requires none of that yeah so the zero knowledge proof is an N root like there's a sort of result that allows you to decipher that like that this this activity has happened without any other information this activity or this question or this information exists without any other

information the comparison I guess to proof of work would be and like you it's an interesting thought I have never seen any idea around this I assume it doesn't exist but if you could have a zero knowledge proof of work it would be you know something that says I have produced work for this block without showing the block in the mock train you need to show the block regardless because everyone needs to have it so it's not super useful but there's there's other things and we'll get to that later in podcast that makes their knowledge was very useful for blocks and applications so zero knowledge proof have become sort of I mean first we actually French

mentioned this this is also the name of this podcast it is apparently a it is an a word that in the last few years has become very very popular at the field of research has become I mean I think it's always been there but it seems like it's become kind of cool or something yeah there definitely is some amount of hype around it after Z cache got launched yeah definitely saw an uptick in like people claiming to do zero knowledge stuff and but even before then I remember seeing like hack pads and various like login systems that claim time zero knowledge like identities in their systems and or like zero knowledge encryption of your contents and I don't

like I never really knew what that would mean like for the authentication system I can sort of get it but and it's so it's been around and it's been a bit high for a while but certainly since the launch of Z cash it's gotten more high but it's actually an older concept so it it comes from the 80s it was in 1985 that the like original paper on zero knowledge proof came out from MIT researchers Goldwater goldwasser actually how do you pronounce that in English I have no goldwasser gold vasa gold wasa McCauley and Rakoff yeah so that it actually has been around for a while and obviously its

introduction into like crypto concepts like crypto token concepts is newer yeah so maybe we can I think it's I think we can sort of jump in now and start exploring what a zero knowledge proof really looks like and to do that we've identified a couple examples that we've heard used by presenters or on you know and videos or I've seen them documented in in papers there's some sort of easier to understand examples using real-life objects or you know rolls to try to explain what is your note proof is and the first one that we're gonna use is actually coming from a paper called

applied kid cryptography or how to convince your children you are not cheating as a paper and the example is a Where's Waldo not puzzle a Where's Waldo picture is that a universal thing I'm pretty sure it's a universal thing like Where's Waldo what's it called in Swedish I I don't know so like we never I've never seen like a proper Where's Waldo book when I was a kid but we had cereal boxes that were had like Where's Waldo pictures on the back of them and I don't know it was Waldo if it was like someone else but it was really exactly thanks for the concepts Waldo yes there is a German

version I think it's called like voice Valda or something like that but anyway Where's Waldo I'll describe what it is if people don't understand Where's Waldo is was a very popular book series where you'd have this very intricate drawing of a ton of like thousands of little people and one of those people is Waldo and he always looks exactly the same and as a kid you're supposed to just like look at this and then identify where Waldo is but anyway so the book is like a regular kind of like a kids book it's a little bit of a big book but anyway so the zero-knowledge idea or exercise here would be to have two people one has found Waldo the other has not found Waldo and the person who's found Waldo wants

to prove that they've found Waldo without giving away where Waldo is so we have this system with a prover and a verifier so there's there's one person that wants to prove that they found Waldo the other needs to verify whether or not the prover is telling the truth and Hennis actually found it and so what the prover there's a few different mechanisms that the prover could do to show that Waldo that he or she has really identified where well there is without revealing where well there is and I'll describe two of them so one is you get a giant piece of paper you cut out a little hole you hide the book underneath and it's a big enough paper that you can't tell where the book is and you figure out exactly where well does faces and you kind of show it

through the hole and so the verifier can look at a blank piece of paper in a little hole and see Waldo and know that you the prover has identified Waldo but not have any idea where Waldo is another example was that you would make a copy of it and then you could cut out Waldo and show that you found Waldo and get rid of all the other paper and the person would know that you'd actually found Waldo without showing where Waldo is so this is a very very basic example of a interactive zero knowledge proof our next example is going to be a far more common example well it's kind of a variation on a very common example

there's an example called the billiard balls and they'll have one billiard ball of one color and one of another we decided to switch it we're gonna call it red pill blue pill let's try to do this Frederick we're actually gonna play the roles here one of proofer want a verifier all right am i proving who's the colorblind one the verifier I think I want to be the verifier alright so the scenario here is one of us so I am not colorblind and Anna is colorblind and I want to prove to her that I am NOT colorblind I actually don't you want to prove to me that the pills are different colors

that's the same thing okay okay so we have two pills a red pill and a blue pill because of the nature of it we'll pretend we're in a rave in the matrix and one pill goes up and one pill goes down but I want to take two pills that will leave me right in the middle we need to have basically I will take both pills if possible as long as they're different but I'm colorblind and they look exactly the same to me and so Frederick how can you prove to me that they are actually different colors so I would I would ask you to put one pill in each hand put them behind your back yeah and then either shuffle them or don't shuffle them I do it in like I

can't see whether or not you're shuffling or not shuffling it's only a thing that you keep track of in your own head if you've shuffled or not shuffled so I always know like I know that like red pills in my left hand the blue pills in my right hand and then I can either just wait I can switch them you don't know which is in which hand true to me there's two purple pills in my hands but I do know if I've switched it or not yeah and so I asked you to either so it's gem or not switch them and then bring them out and show them to me and I'll say yes you switch them because I can see the colors like clearly I can see whether or not you switch them because like it's super

obvious to me then yeah like they're in the same place or they're not and so now I say yes you've switched them but with what only one example you could be lucky you could have just been like oh yeah they're both like in reality and so say they weren't different colors they're probably just a switch and I actually switched them you happen to be right yeah but now if you redo this if you again put it I put the pills behind my back I switched them again I pull them out if you are able to correctly call each time I switch or don't switch then I can I can then know that you're telling the truth so on the first attempt I would have a 50-50 chance of guessing the

right answer and then I you know the probability goes down maybe after 10 guesses it's so pretty like it's unlikely that I guessed correctly 10 times in a row yeah but after a hundred times or a thousand times or a million times surely I know for sure that there are different colors and which color is which and I can then trust that you have in fact been telling the truth that there are two pills with two different colors and it's zero knowledge because I don't actually have to tell you which color is which I like the only information I reveal is whether or not you have switched them which you already know so I don't actually have to

tell you anything about their colors and there's no information exchange or other than the fact that okay fine you now know that I can see them as different colors maybe we can we can sort of use this example to talk a little bit about like the features of zero knowledge proof because those are quite well defined so in this example in all your knowledge examples you should be able to prove three main things this is like the definition of a zero knowledge proof is these three properties so zero knowledge proof must have soundness completeness and zero knowledge Ness which is a real

like if something if field like you in academia or something makes up a word does that make it a real world or is it a made-up word still it's on Wikipedia yeah okay so how is this sound so the definition of soundness is if the statement is false no cheating prover can convince the honest verify that it is true except with some small probability but more simply only if it is true will I be able to prove that it's true so basically I can't construct a proof that lies and like in this example because Frederic was correct each time the basically it it would have

been impossible if I was lying and was actually colorblind I would I would guess wrongly at some points exactly so there is this probability aspect of it there is to my knowledge I don't know if there can be a zero knowledge proof that doesn't have a probability aspect to it I think that this is clear here because it says except for some small probability so essentially like in this example we only know with some probability like the probability gets smaller and smaller than more tests we do but like you can choose your how comfortable you are with what probability so the next feature as

mentioned was completeness if the statement is true the honest verifier can convict an will be convinced by this fact by an honest prover so it's the way I would kind of think about this and it sounds very similar to the previous one because it actually kind of Asst but only if I have the knowledge will I be able to prove it so in the previous one I said like only if it's true will I be able to prove it and now it's like if I only if I have that knowledge will I be able to prove it so I can't prove something like even if it exists like even if it is true but I don't know it I

can't prove it so in the blue pill red pill example like I have that knowledge of what which colors which but maybe like if I was if I could see color but wasn't looking at the situation as I still couldn't construct a proof like even if the property that lets me construct a proof exists but I don't have the knowledge I can't construct it so sound soundness is sort of approver can't cheat and completeness is that the verifier will be convinced by an honest prove er and

the last of the three core features so we've caught we've covered soundness and completeness so far it's zero knowledge eNOS felt different with zero knowledge nasira knowledge 'no siz if the statement is true no verifier learns anything other than the fact that the statement is true and so actually in this case I didn't know which one was red or which one was blue I only knew that they were different yeah so the the statement that were proving in this example is they are different it's not this is blue or this is red and that might not be information that I want to divulge so I'm that's the only thing I'm proving and I'm not giving you any more information than that so that's the zero

knowledge miss zero knowledge this actually means that Europe you're giving one bit of information so it's not zero bits but because that would be completely useless it means that you don't give more than one bit of information this is interesting too because I think zero knowledge miss also covers the fact that a third party or someone every verify or anyone else is this true could actually also somehow verify it yeah so in we'll get to this but there's interactive and non interactive proofs in an interactive proof you it's two parties playing a role and like talking to each other I mean a non interactive proof you could publish this proof and then anyone can verify it without

gaining any information so I that certainly the zero knowledge miss is inherent property of zero knowledge proof but it also means that you can construct proofs that you can distribute freely without sharing information and maybe we can give so we're gonna give one more example in a bit more detail where we can actually show and non interactive this is a this is a bit more complicated but I think it's really it's a really good one and we will be sharing some links in the show notes for this episode because sometimes it is really good to also look at the visuals but Fredrik do you want to do you want to go ahead with Sudoku yeah non interactive example so I think

that this this example is useful to bring up because it's an example of a non interactive proof so I said yeah interactiveness means there's two parties that need to talk to each other there's a sort of challenge response mechanism going on and any zero knowledge proof we always need this challenge response mechanism but we can sort of generate challenges and then reply with all the responses at once and then the verifier can just take all this data and verify it on their own so that's what a non interactive zero knowledge proof is so the Sudoku example yes I will assume that everyone knows how Sudoku works but there's rows

there's columns and there's sections so in each section like in a solved Sudoku puzzle each row is numbers one through nine each columns and rough numbers one through nine and each section is numbers one through nine and you want to prove that you have a solution to this puzzle but you don't want to give the solution away like maybe you want to sell this solution or something and so what you can do is you take cards with numbers on them one through nine you need 243 of these cards it's nine times nine times three because there's there's three like categories there's

rows columns and sections so on each square you either know the value and like its printed on the puzzle or you don't and for the known ones you put like that number three times three of that card on top for the other numbers you put the cards face down and then to construct the proof that you have a solution you take the top card from all of the rows strengths nine piles of cards from them you take you have nine rows like all the rows have piles with them and each one of those piles will have the number one through nine yeah in it so then you take

all of the columns the top card from every square in the column create nine piles of cards out of them and then you create nine piles of cards with the last ones remaining from each section so you have 27 piles and you shuffle each of these piles and then you send them all to the verifier now the verifier you keep you keep all of these separate so you're keeping like each each row you had nine cards you can shuffle them so the order is totally out of whack but it's still nine cards exactly each pile is shuffled but then you send them like here's Row one pile here's a row to pile here's column one pile here section one

pile etc so they can go through each of these piles in turn and and look through them and they'll only see numbers one if this solution is correct they'll find the numbers one through nine in each pile and then after having gone through all the piles and verified that the numbers 1 through 9 are H and each all are in each of the piles they can be assured that I actually had the solution to this and this is a non-interactive proof because anyone any third party person who wasn't even witnessed to like the sharing of this information at all or the cards or the anything can come and look at those piles and actually see

the same thing and be able to verify the same thing so to verify this you need to have some trusts that the prover has followed this protocol that they're not just friend like they're not just putting piles together with kind of next to it so that's where the zero knowledge proof bits get difficult it's like how do you prove that someone is following this protocol and in this case there is like we can't go into detail but there's like you could have some commit schemes where you basically tag each of these cards with some identifier and then pre

commit to saying you know it should be in this order and then you hash that and you share that as well well there's like a way that you could trip to cryptographically secure that they're following the protocol so they need that along with the piles to be assured that they're not lying and that's where the hash comes back in yeah hashes are are kind of everywhere in cryptography and they're a very important part of our world I love this example but I have this one question which is like why why would you actually need to have any cards face up or face down if in the end you're getting piles of like cards one through nine all shuffle like shuffled

so I mean I just I don't understand why that actually is part of this yeah so I think that's part of the proof that someone is actually following the protocol and in how you deal with these like commit schemes but essentially if you imagine this as an interactive protocol where there's a the person you want to prove that you have the solution to standing next to you you placed out the face-up cards to prove that you have this solution to the puzzle that they gave you that is not a solution to just any random puzzle because any random puzzle would produce the same sort of outcome so the face-up ones are important to show that you're solving this particular puzzle okay cool

as I said the this Sudoku example actually has an interactive end a non interactive version and that's usually the case like if you're reading online about their knowledge proofs and you'll very often come across these interactive examples because that's the easiest way to explain these things and it's how they first like we're first developed so like if once you start digging into this a little bit deeper but like still scratching the surface but you'll dig into this problem of like graph coloring in transforming problems onto graph colouring problems and how you can construct their knowledge proofs for that etc but in in sometimes as well in

the eighties there was a method developed that let let you transform interactive proofs into non interactive proofs so by having cryptographically secure hash function you basically use a hash function to generate randomness or to like creates like to pick challenges in this protocol so you still have this like interactive aspects but you're generating challenges by yourself on your own side so then you send all of the challenges and all of the responses at the same time to the verifier and this is how you like if you publish that

and then anyone can verify it not just the one that was interacting which role here though is the hash function actually taking this is the input information so this is let's like maybe let's go back to one of the examples like on the Sudoku one the hash would produce produce basically like random numbers or what what would it be yeah so like in the interactive version of the Sudoku one you have like if Alice and Bob are standing next to each other Alice is trying to prove that she has the solution Bob will go like give me the third row give me the fourth column give me the first section and in between all of

these Alice would like replace all the cards but if you don't want to do this you could like take all of the cards and their positions and and everything hash that then you get a number out of that you transform that number into like on to like the board saying like numbers between 1 & 9 are sections numbers after that blah blah and then you can use the output of this hash function to choose your first challenge and then you respond you hash the response then you get a new suit random-number use that as the challenge for the next input and so on and

eventually you'll have like a long challenge response cycle that you can send off to someone so it's essentially a way to generate random numbers and you don't need then like the verifier like the prover is an algorithm it's just the hash like it's not a person anymore the verifier still somehow needs to exist yeah but then once and they can just like parse through all the data and verify everything at once we've still really just scratched the surface of your knowledge proofs this is like very introductory we're just trying to get some of the concepts sort of clear for ourselves we will be in future episodes

going deeper on a lot of these things but I think in this episode we can at least touch on like some of the use cases of these things so what these zero knowledge proof have existed since 1985 they've been used we know they're being used in blockchain technology but what else are they being used in yeah I mean to me I will often learn by looking at real world examples are like yeah getting my hands dirty working on something and they have been in use for a long time in various areas before blockchain I think the most obvious one is like authentication systems that use these schemes so when you log into

whatever Facebook you actually send your password in plain texts to Facebook then on their side they're hashing that password and comparing it to the hash that's stored in their database so they don't at least don't store your well presumably because we can't know but they presumably don't store your password in plain text but they still get it like their servers are still getting it so if you don't want to share your password at all I mean one way would be to hash it around the client side and then send that hash to them but sending hash the hash to them for something that's as small as the password is actually still done like giving them quite a lot of

information like they can brute force that hash pretty easily so if you don't want to give them anything more than one bit of information like I have the password to this account that's where you need a zero knowledge proof and what else could you use your knowledge proof for I think the most useful ones that I've seen at least again I'm a noob in this area I don't like look for this stuff daily but another one another useful example that I came across is if you want to prove that you have the private key of a public key so like public private key encryption is everywhere usually like with PGP was intended to be like the public private

key encryption of email and it's never really taken on because like part of it is like if you send me a public key do I know that that's your sum like I can encrypt something with it and be ensured that only the person with the private key can read it but it's still like can I tie an identity to this not really so these all these like key servers have spawned up and that kind of tried to tie an identity to the key and stuff like that but you could actually use a zero knowledge proof to say I have the private key for this public key and thereby like proving your identity together with your public key and yeah exactly how this is used in real life

today I'm not actually sure it would have also have to be like an interactive zero knowledge proof because if it if you send it out non interactively then you'd then you're back to the same position where it's some of its public knowledge and anyone can copy it so it's only useful in the interactive sense and then it's serves your knowledge proofs if then obviously also become part of a lot of blockchain projects or concepts the most notable I mean there's a whole there's actually like a whole history of zero knowledge in blockchain which I don't think we're ready to do in this podcast and I want to I really do want

to bring on I think we talked about this bringing on some people who like have actually lived through some of this know these people and have like seeing the developments of you know things like zero coin D cash and that's for future episodes but we are seeing I mean we do see zero knowledge pop up more and more in like with blockchain projects I know that I mean obviously the most notable is the cash which is a token built like with zero knowledge proof Slyke inherently built into its protocol and I know that they're doing tons of research to actually you know make from what I understood like doing the real zero knowledge actually you can maybe help me

with this but I think doing the real like the the real proofs can be quite CPU intensive really very it takes up a lot of yeah it's it's resource intensive in general but especially like memory intensive is the biggest like that's why you you can't really send a shielded transaction Anzhi cash from a mobile phone for instance because your your phone doesn't have that much RAM so even like if it was just CPU then you could just let it run for a long time but because you don't actually have that much RAM it's it's literally impossible on most phones Wow so yeah they're doing a ton of stuff there and like trying to make it like improve the UX improve the speed improve the resource resources

necessary so the next version they have upcoming they've been saying that they have it so efficient now that you could generate a shield a transaction on a on a phone so yeah there's tons of stuff and active research in this area and then some of the words that are often brought up are things like the CK snarks and sometimes we hear about Starks which is apparently the future future version yeah pure theory at this point this not pure theory there I've seen conference talks where they actually show off some some examples himself but like the one talk I saw by one of the researchers working on this it was a great talking

if I can find it again I'll put it in the show no show notes but it was quite a while ago but he was showing some example program so snarks is just like zero knowledge non interactive arguments of knowledge something's something along those lines what it stands for which is really like any zero knowledge proof I'm not exactly sure what the difference is or why making this separate distinction but Starks are like you can prove the result of a computation so you can like give someone a program and then prove that this is the result of running the program and you can be you can verify

that this is the result of running the program without running it yourself which is super like useful and the blockchain contexts like massively so but they the input program was something stupidly simple and it took like 200 gigs of RAM or something to prove it was just like you're not it's not feasible right now to use this for anything but it's still like it exists it's a thing well just needs to be improved and then we've also seen like zero knowledge library tour like actually more like ZK snark libraries so that like these are basically just like taking CK snark it's usually Z okay snarks right yeah

yeah like I don't know if maybe snarks is the new way of Z or sayings they're not groups or just like it's that it's a specific subset of zero knowledge proof that are useful like an interactive Zehra knowledge proof is not actually all that useful usually at least you need it to be non interactive so then like that is a smart essentially a non-interactive zero knowledge proof but we do see people building libraries that people can then use to implement your knowledge proof or snarks into their blockchain projects or into any project so at the ZK summits the events we held a couple weeks ago there was a

presentation by Howard Wu on Lib snark which is a C++ library for snarks and it's a great library just like has a wide API covering all kinds of snarks and how to use them and I have I haven't dug into that library and like which languages have bindings to it or whatever it's something that I wanted to do but certainly like with this librarian hand you can you can use this today like there's no issue here you don't have to go in and know what ton of stuff you can just like use this library you don't have to re-implement the world here cool well I think I mean we've covered a lot of ground in this episode do you have any last thoughts on zero

knowledge proof project I think there's huge potential and I think it's really like the the area is really cool it's like new to a lot of people but it's also like old to a lot of people so I think the more across work we can get haired the better like actually like to me this is almost a way to involve real cryptographers in cryptocurrencies and it has a huge potential for a lot of stuff like I I was at this charting summit and we were talking about using

their knowledge proofs as a means to compress a like merkel free path so if you go this is a whole podcast episode in itself but there's a thing called stateless clients in the stateless client model you need witnesses for transactions basically saying i this is a valid transaction so usually like send a witness with it but these witnesses can be really long like their their series of hashes that point to a specific place in a Merkel tree and you can actually use the zero knowledge proof to say that like this is proof that this transaction reference is only this path in the

goal tree so you compressed the whole tree into like one zero knowledge proof which is much smaller so it's like a compression mechanism and yeah they're there's tons of applications and I'm excited to see where all of this goes um I have a last thought on zero knowledge as well we do I do want to sort of admit something about the name of this podcast I can we didn't originally named the podcast CEO knowledge the idea came up Bank Jack suggested it and we thought it was kind of cool sort of a double entendre there's like you're not fruits and then there's like we don't know anything zero knowledge the podcast hosts have zero knowledge the podcast hoes have zero knowledge but I think what's really cool about it is it's

actually has put us very much in the face-to-face with the zero knowledge community and the academics and the groups that are doing work on this and it's extremely exciting and it's a really cool it's a really cool sort of theme or concept to if you want to look across a ton of different blockchain projects and not necessarily get caught up with some of the sort of groupings that we see happening in the ecosystem your knowledge is actually a really cool way to do it because there's a lot of different groups who are playing with it in different ways and it's turned out to be like yeah it's just kind of a cool that's kind of cool coincidence or cool whatever cool turn of events that we

happen to to sort of pick that name and then actually find just [ __ ] awesome and find this great community around it anyway thanks I'm gonna say a big thank you for listening if you've made it this far this was a denser episode than most it's it's funny because like it's we've never taken such an introductory point of view on anything like going basics as much as this and yet it's probably one of the densest episodes this kind of goes to show how much stuff there actually is to learn on this this topic totally so yeah thanks for listening thanks for listening [Music]