ELI5: Zero Knowledge by Wanseob Lim | Devcon Bogotá

foreign [Music] if you are already familiar with the journal knowledge proof that I strongly recommend you to listen here this session the designing public goods using zkps which is running by the Rachel who is a super designer of the internal foundation's PSE team she have designed a lot she has designed in three years at the team and designed lots of zkp related user experiences and user interfaces so it might be very very inspiring oh yeah so let's start with uh about thinking about where the zkp is mostly used so we use zero knowledge proof when you'll want to prove a fact but you don't want to share the information I want to give you an example about uh more detail so uh let's think about some example at immigration at the airport let's assume that I'm a immigration officer here and this is an entrance here when when you go to the airport the immigration Officer says where are you from then uh I say like uh I'm from Korea I'm from Korea then immigration Officer says like North or South I definitely say I'm from South but unfortunately uh this immigration officer doesn't trust me that much so he says like um I really think you look like from North so give me your password this poor Korean guy wants to keep the freedom to keep my personal information so I said like oh that's my personal information I don't want to give my passport then okay what happens kick him out and this situation uh what should I have to do here what should I do what can I do here yeah actually we can I can show some password number I mean I can show my nationality or passport card um they cover but if we give a zero knowledge proof that I can prove that I'm a part of this South Korean yeah this is just an example which can be really happened in the future let's think about what happens here so we can call the immigration officer here as the verifier the entrant the poor South Korean as the prover and then the proverb prepares the witness using my passport which is which means like witness means I have some passport number here and I have my um I'm a male and my my number in Korea something like that the birthday Etc so and then generates a ZK proof and give it to the uh verifier which means the immigration officer here then the verifier the officer says okay I'm gonna verify this proof using the existing database we have actually this is pretty possible and we're gonna take a look at the details later about the how uh can how we can prove the membership of that I'm a part of this South Korean people let's see what is witness and what is informations we have to share here so there are some informations you can see here and maybe there's a password number that I want to that I don't want to share with the immigration officer actually it's probably doesn't make sense but so I we call these values uh as private inputs but I'm gonna just uh say I'm a part of the South Koreans I just opened my nationality this is the public input and to prove that I'm a part of the people I just culturally some mathematical values using the inputs there so uh we call this intermediate values including all the private inputs and the public inputs as witness here and this is just a basic model of how zero knowledge proving system works so we have private inputs and we have public inputs and also we have the circuit here the circuit is uh about the relations what was the relations here in the immigration situation it's like I don't reveal my passport number but my passport number is definitely a part of the registered existing database of the Korean people's passport number so it's kind of a membership oh there's a database and I don't want to share my information but this is definitely exists in the database so this relation is the what is is the circuit here and using all the private inputs and public inputs and circuits the approver uh makes this zero knowledge proof and then the verifier verifies this zero knowledge proof using the circuit using the same circuit using the given circuit uh to verify that I am a part of the Korean people okay then uh let's think about how and why it works uh yeah to start with it I think I should explain about what is ZK snark actually maybe I think some of uh people here in this room might be pretty familiar with what is the historic and some of uh some of us are not familiar with this so I'm gonna explain pretty in detail so sometimes it's not four or five years old kid I think so please understand uh I'm gonna start with the classic example maybe many of you have heard about when you just uh search Google what is zkp then you might see some example of Alibaba there then here's an example that here's a very extremely smart rhino and he's arguing that he knows the magic phrase of the Alibaba cave can you trust him can you believe it pretty hard to believe isn't it so we are we are the verifier and I by the way uh this argument that this rhino is doing is called the argument of knowledge because this rhino is arguing that he knows the magic phrase this is called the argument of knowledge uh by the way because this is pretty um hurry to believe the verifier comes up with an idea and says the writer that okay go to the cave and uh wait for me there then a rhino goes to the cave so you can see how the Alibaba cave looks like here so there is a uh gate at the between of the two gates then if the Rhino uh really knows the magic phrase do you know is there anyone who knows the magic phrase here yeah so if Ryan can say SAS can say the open sesame magic phrase then Rhino can just enter through the gate because it it'll get up and there the Rhino get into the cave so maybe it just depends on his choice he can go into the left gate or he can go go to the right gate there and the verifier comes here and says like Hey try to come come out from the right gate then to come out from the right gate Rhino goes to the door and says the open sesame and open the door and should come out from the right gate then we can think like oh I think Ryan really knows the magic phrase Maybe some of us uh realize there is some problem here um yeah so we're gonna ask about the left Keys uh situation in this case actually Rhino just went to the left gate at first then the verifier has come up from the late last gate and actually it doesn't need to say the magic phrase there yeah so actually you can you can think like this is very probabilistic this case is called false positive so the probability of the false positive here is 50 percent right then uh how about if you repeat this process uh as you said uh 10 times here then uh the probabilistic probability of the false positive becomes less than 0.1 percent like we can just repeat this like a thousand times then we can think okay this is pretty uh there might be the probability of the false positive is extremely low then we call this as the soundness the song this is a pretty important Concept in the historic and I'm gonna tell you about why it is important again later the verifier asks and the Rhino answers here and actually the the set of rhinos answers is the zkp how can we compute the size of zkp here it definitely depends on the reputation number right so if the proof size is very B then do we have the sum this there yes we have the soundness there if the proof is too small we cannot have the soundness like the false positive is too probably is the probability of the false positive is too high so the proof size is pretty important and here okay but uh imagine if we do this thousand times at immigration so Immigration Services okay just tell me you'll multiply something okay I actually it totally doesn't make sense so we need the non-interactive system here any idea how to make the non-interactive system okay let's go back to the Rhino case in this case uh this is very file uh try to make the random question every time but what if we generate some random set of questions uh before this proven uh proving happens like uh just like this left left right left right left what is the problem here yeah right right just using the dolly so we need to homomorphically encrypt those values actually today we got We're Not Gonna uh deal with the homomorphic concept here but um we should encrypt this uh in a very viable way by the before uh we go to the next slide I just want to say here this is called common reference string because verifier already make made this for the proofer so this string is shared between the proverb and the verifier so commonly shared string which is can be the reference for The Proven system so this is called common reference string by the way because we need to encrypt those values because we can get this increase maybe there might be a little people who can read this word but actually this is saying about go left and go right and if you go left and right go right twice something else so let's assume there is something that can interpret this encrypted common reference string so actually interpret is not a good explanation here in more detail let me assume that the five years old key understand hash function here we are adding assault and hashing the value and make a modular there so it's kind of a deterministic random stuff so uh the Rhino never can cheat on that if this rhino doesn't know the original reference string by the way these encrypted common reference string is not enough to be used publicly because this is okay when only we want to verify this rhino is smart what we want to build is some protocol that can be used publicly widely for everyone so for example we have a system that we can uh we can transfer some if using ZK proof then the ZK proof will include some information that I have enough balance and I can generate some signature and every information will be in the ZK probe but if if you can sit on that I just can move a lot in to my account without the correct information without the signature this is really important to make anyone no one knows the original reference string yes this is called the trusses setup to achieve this we have to do the trusses setup let me explain this one by one actually this is how a zkp system works with I mean the zika snark works with the common reference string so there is a common reference string made by the transit setup you share with the proverb and the verifier and the program verifier both does not know the seed original reference string here and then proofer picks a random salt and share it with the verifier and then also once the Proverbs picks the soul the Pervert can drive a set of questions because there is a reference string actually the verifier at first in the interactive system very final just gave the question to the writer but in this case Rhino can generate the questions by by himself and also the verifier can be can drive the answers right answers without knowing the exact questions uh if the verifier using the homomorphic feature homover characteristic of the reference string it can be a little bit um tricky but this is also a pretty important thing so I want to explain uh some multi-party computation thing here yeah actually this is pretty technical but uh not that difficult actually please uh by the way uh let's uh let me say why we why I'm explaining this more tea party computation here it's like do you guys know uh how the trusses that works why you need to join the ceremony that is share today's opening ceremony so I just want to share the how it works and why you need to join the kg transistor of ceremony here so let's go through actually this pretty for 15 years old kid but let's go so yeah um there is a homomorphic hiding G to the A is kind of a we can make some encrypted value using number a so actually that is a signature of the homorific hiding age but just think about that just as a hash function so to think about G to the a is something related to the hash of a actually it's kind of a homorphic hiding of a but um then there is a um characteristic that we can compute the G to the a using number a pretty easily but in contrast it's extremely difficult to to hit a from G to the a actually this is called the logarithmic discrete assumption here but Let's Escape there skip here and also if we have a g to the A and B we can also compute the G to the a b pretty easily okay this is a this is a um some key features of the homography hiding using the electric curve cryptography and uh let's see how the traces setup works so trust setup is creating a command reference string with uh and without anyone knows the original reference string so at first Alice joined the ceremony and picks the set of the questions the set of questions here is a b c d e here all the A and B and C the ND and E are numbers in a finite field so some numbers there are numbers and then we compute actually we did some encryption thing here you remember so so left left right left right left is a b c d e and this something already encrypted value G to the a g to the b g to C something so we can compute G to the HTTP C and G3 there and Alice shares this G to the A and G to the E values publicly P to the people then Bob joins this ceremony in this case uh Alice May uh Alice made this card the ABCDE value if Alice is Innocent but if Alice is Not Innocent maybe she's just uh store the ABCDE value in her computer by the way uh Alice uh didn't share the ABCD value with Bob yet okay then Bob also picks a set of questions again here there is fghij and then we're gonna create a new reference string using G to the a to the G to the E and the F G H I J only because we can compute G to the a f using G to the A and F together Bob can generate G to the AF G to the BG G to the CH without knowing the a b c d e value here call does the same thing here okay then um if any one of these three participants discarded and destroyed the randomly picked question values then uh maybe anyone might know the original reference string here AFK bgl chm and Etc because to know AFK you need all those values a and F and K so it means to just recover its reasonable value you need all the secrets from the older participants of the ceremony so it makes if any one of the participants that is called in and destroy the value then oh we are safe the best way to use this common reference string is actually not to trust anyone it means just go to the transistor of ceremony and his career see it there then you'll be safe at least by yourself if you just keep it discarding this destroyed right don't trust anyone this trust actually don't trust yourself too yeah just go to the tricep Ceremony this is the uh page uh that share today's opening ceremony so you can just go to ceremony.etherium.org then you can uh join the ceremony and actually uh you just saw that these should be conducted in a sequential manner because all I should do something and share and then Bob do something after something so there might be some cue but please don't lose your faith you you don't need please don't trust anyone so go into the queue and let's join the ceremony together um okay great uh then now I think I've explained almost every important concept of the historic then let's rebuild why this is called ZK snark using the concepts we just Explorer today okay so ZK snark is zero knowledge succinct non-interactive argument of knowledge first Journal knowledge means just hiding some information you remember that I just uh one I just wanted to hide my passport number here and but doesn't want it to prove something so this is called as the general knowledge if you want to hide some volume that can be called zero knowledge uh and uh to talk about succinct actually we have to talk about the soundness you remember if we have if we repeat only 10 times the proof will be pretty small but if we repeat the uh answering like 10 000 times the proof size will be larger is pretty important to keep the proof succinct while we keep the soundness so we need to find the gray balance there so succinct is used here for because of the soundness thing uh the non-instructive thing we can do that at the thousand times the immigration office right so we have we should have a non-interactive system and for the non-interactive system we should do some common reference string and because of that we need to do the trusted setup stuff all we all we we did all these things to prove argument of Knowledge from this rhino right so this is called ZK snork journalism non-interactive argument of knowledge so uh does everyone understand now gray I am pretty happy now okay so we're gonna go through the apply uh zkp stuff so where can I use dkp mostly people think like um I can hide something then uh it can be used for the Privacy definitely so uh the usages are mainly the privacy and scaling and there are a lot of undiscovered usages so let's go to the Privacy thing first um yeah and actually we already go through some difficult Concepts like multiple computation homomorphic hiding and logarithm um discrete assumption stuff so Let Me Assume again that our kids already knows this function and microprov and please let's remind how the ZK proving system works here again we have a circuit that represents the relations between witness including the public inputs and private inputs and the proverb creates a zkp and the verifier uh will verify the proof using the circuit together and in the miracle tree what we want to do here is proving that there is this a leaf in the Merkel tree uh uh without revealing any information about the leaf and The Sibling information which can reveal the path of the leaf which can be kind of a reference uh and here I'm gonna share the Mercury information between the both both the verifier and the program so this is where where do we use this thing at the immigration office yeah so this is proof I'm a member of this group but I don't want to reveal my identity here so this is the reason why we do this is marker proof using zkp actually we can compute the Merkel root using sibling values and The Sibling values also should be private input because if they are revealed then they can be some hint for about the leaf and then uh to generate the multiple proof we need to compute the intermediate nodes here right you need to compute the branch node of the marker tree when you compute the Mercury proof and these intermediate values are the witness actually um witness also includes the private and public all the values but uh I'm gonna say this is an witness and also this is the relation of the witness so the first let's see the first relation node one is Hash of sibling one and left one and node two is Hash of the Note 1 and sibling two node three node three is the hash of node 2 and sibling three and finally the computed node three uh should equal to the root value here this is the relation that we want to prove using the witness while we are not revealing the private information here Okay so we just put these values like this so there's a circle circuit uh the logic is a blue color and private input or the green color and public inputs are the red color here then we can generate ZK proof and the verifier can prove that okay you don't need to reveal the private inputs but I have the information about about this group which is the root value the public input red thing and also there is a relation logic between the witness here that is the marker proof uh and this members proofing also can be used for various usages actually first of all uh the Privacy protocol uh definitely and for the Privacy protocol uh we have the very good example for the identity um we are having the semaphore protocol which is the name of a um membership proof protocol that uh keeps your identity private but lets you vote on some agenda uh in an anonymous manner and also we can have some private transaction stuff uh Z cash and also Aztecs as xdk money and polygonite ball and PS team zero Pro and for later cash there are all the implementing the same logic with this members proof system uh and also this members proof system can be implemented in various ways uh definitely the first way is the method that I shared here the marker proof thing and actually recently uh people are exploring another methodology using the vector commitment which can let us express a set of values uh using a polynomial yeah so if you are interested in you can just uh Google this Cork and take a deep look at that by the way we have 10 more minutes so I'm gonna use 10 more minutes all over 10 10 minutes so the next example is a scaling you guys are pretty um familiar with the word roll up right actually the roll-up started um I guess it started from 2018 by Barry uh the our PSA teams leader and roll up started from the ZK roll up and I'm gonna explain uh what is the basic form of ZK roll up here uh okay so uh the first uh block is a just a normal some ethereum block let's assume that this is a normal ethernet block then there should be some transactions transaction from one changes two and for each transaction you every account external owned account should generate the ecdsa signature right so every transaction has its matching transaction and signature there and we finally we compute the block hash using some another values there but how if we uh make these signatures as private input what happens here we just remove the private inputs and we can replace that using a zkp this is just what the hero lab is and here are two advantages what are the two advantages here yeah definitely the data used and the another one because if we just compress all the signatures then we don't need to verify all the electric curve signatures so let's assume that if we have 10 thousands of signatures then the general launch proof can be much less than the 10 000 of the signatures so we can reduce the data size a lot and also we can skip the computation since using the cryptographical verifying system so we have a two advantages here the scaling of the computation and the scaling of the data usage so yeah so this is the reason why we are we are using ZK for scaling Solutions uh and actually there is a tutorial that you can implement the simple ZK roller by yourself so if you want to just uh Deep dive into how it really works then you can just go there and go to the tutorial okay it'll be very helpful for you to understand how it works okay and for the next uh I'm gonna share another fun examples Macy and rate living limiting nullifier Macy is a stat Macy stands for minimal anti-collision infrastructure which means actually have you try the CLR fund before using kitcoin fund quadratic fund Security fund in quadratic fund it is very useful to buy the vote because um the number of the participants is much important than the amount of diverts right in quadratic body so buying the word is pretty useful then how can we prevent both buying attack collecting all the Bots first and then the coordinator makes it and generate a new state tree then the voter cannot prove that I put it to this one then we can just prevent the vote buying attack so we can also use zkp here that the coordinator next the result without just modifying them correctly using zero knowledge probe so we are also doing the uh cr1 phone uh CLR fund for Defcon so you can go to the 8th columbia.co.

n to participate in the new round category funding round and the another really fun example is the rate limiting nullifier um this is pretty novel and maybe it is pretty hard to think about this concept from zkp because we can just we are just thinking about like only the privacy or scaling right then let's uh see what it is so there is a polynomial a one degree polynomial so it is y equals ax plus b and actually this polynomial is a polynomial that I just chose that I just chose and actually the value p is my secret key of ethereum then okay then I can show you some point on this line but if I share you more than two points what happens you can just compute this polynomial right because you have two points and this is one degree so you can just know the A and A and B then you can know my secret key so my secrets gets revealed so rate limiting lonely fire is using this actually this product is charmir's secret sharing protocol right limiting logifier is uh using this to prevent spam attack if I want to communicate with you I should revolve my points on on the polynomial to you so if I uh if I just send you too many messages that actually you can just recover my polynomial and just get all my it from the account right but here we have to use zkp that all these shared points are on the polynomial this is the only relation pretty simple right and we can use this for spam protection protocol we are doing a lot of experiments using this right limiting volume concept uh for the consensus layer and also the peer-to-peer networking okay so this is the last so from five years old key to a student I want to recommend this curriculum the first one is just write a ckp application using the tutorial thing I shared for the ZK roll up then it will let you it will help you understand how the KP works and how The Proven system works there and then you need to study and learn about the at first abstract algebra because in the proving system we are using a specific set of numbers and we need to understand how these numbers works and how the homographic hiding Works to understand this actually you need to understand the abstract algebra and the group Theory thing after that please study and learn about the elastic curve cryptography phrase and then after that please study about the pairing based cryptography then maybe some of you guys are heard about a plonk and kdg and inner product argument stop and they are all the uh kind of a things after you you have to you study about this pairing this cryptography and then a struggle German and extra so after you study these three things then please study about the punk which is arithmetization which means the converting your program into a polynomial then after then just go through the polynomial commitment schemes which is like how to make the questions and how to make the answers what we have done using the alibaba's case with the rightness actually the arithmetizations is pretty related to the polynomial scheme so you're going to study with some rncs arithmetization with growth 16 and you're going to study Planck arithmetization with kg or inner product argument uh thank you everyone so I'm once up from intern Foundation PSC team and I hope this session helped you a lot thank you so much