Ethereum Foundation DevCon 6 - ZKPs: Privacy, Identity, Infrastructure & More Track, 13 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: ELI5: Zero Knowledge by Wanseob Lim | Devcon Bogotá

Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/eli5-zero-knowledge/

.

Speaker(s): Wanseob Lim
Skill level: Beginner
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: zero,knowledge

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers.
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

A

A

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.

A

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.

A

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.

A

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?

A

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.

A

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?

A

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.

A

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.

A

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?

A

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.

A

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?

A

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.

A

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?

A

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.

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

Everyone, so I'm once up from intern, Foundation, PSC team and I hope this session. Helped you a lot. Thank you. So much.