The One Question bounty closes Thursday 10 December.

Join in
We Them Media logo We Them Media Support us

ZK Workshop - PSE team

The picture loads from YouTube. The player loads only when you press Play. Turn on captions in the player if you need them.

A speaker gives a beginner talk on zero-knowledge proofs using a farmer with a bag of apples that must all be green. Checking every apple is safe but slow, checking one is fast but unreliable. Blowing up any error makes one random check enough, which is the idea behind a prover doing work so a verifier can do little. They also plug a study group.

Not by We Them Media Channel: Web3Bridge. Published Sunday 13 October 2024.

Titles are the owner’s. It plays from their channel.

Transcript

This transcript may contain errors. This video belongs to Web3Bridge. Letters mark each change of speaker.

These are the speakers’ own words. We have not checked their claims.

0:06 A: Hello guys. Hi. So my name is Wisdom. The talk today is an introduction to ZK. So the goal of this talk is to basically give you an intuition for how ZK works, right? I know all of us have heard ZK one way or the other and it might seem confusing, right? So the purpose of this talk is to give you a very beginner-friendly introduction to ZK without any maths. No, very tiny maths and just a lot of intuition basically. Don't worry, I don't need a clicker. It's fine. Don't worry. So we are starting with a problem, right? And then through solving this problem, we're going to rediscover some things about ZK. That's the structure of the talk. So the problem is we have this man, his name is John Doe. John Doe is a farmer and he basically makes apples. Okay? So the idea is that John Doe wants to sell a bag of apples to the market, but the market only accepts green apples, right? All the apples in the bag must be green, right? There must be no red apple. So, the question is, is there a way for John Doe to be able to figure out that his bag only contains green apples? Okay? That's the problem that we care about. And- okay. So, what does John- what are we trying to optimize here? So, this is the bag. It has 15 apples, right? All of them are green. So, what are we trying to optimize? We want to figure out- How many green apples are there? The amount of work that John would need to do in order to determine that all the apples are green. Okay? And then we also need to figure out if there is a bad apple in the line. So, can anyone suggest how, presented with this, how would you determine that all apples here are green? Just blot it out. You check each one of them, right? So, you check the first one, you check the second one, check the third one, fourth one, up to 15, right? If any of them is red, then you don't take that bag to the market, right? You disqualify that bag immediately. Does that make sense? Okay, cool. So, how much work needs to be done for that strategy? A lot. But in this case, where you have 15 apples, how many checks are you going to do? 15. 15. Okay. And will you be able to detect if there is a bad apple or not? Okay. Cool. So, total amount of work done is 15. And then if there's a bad apple, we'll be able to detect it with 100% probability, right? Because of- at some point, we are going to touch it and we're going to see that this is red. Does that make sense? Yes. Cool. Now, in this scenario, using the same strategy, how much work will be done? I think we're back. So, how much work would need to be done to determine if there's an apple that is red here with the same strategy? So, we want to check, yes. So, but in the worst-case scenario, 15, right? We'll still have to check each and every single one of them. Does that make sense? And if there's a red apple, are we going to be able to detect it? So 100% certainty, right? So it's still the same, 15 checks, 100% certainty. So we're good. But what's the problem with this protocol? It does too much work, right? If we had a bag that had 1,000 apples, we would have to do 1,000 checks. But then the good side of this protocol is that you will always have 100% certainty, right? So you're never going to take a bag that has a red apple by mistake to the market. You're always going to be able to detect that there is a red apple there. Does this make sense so far? Cool. So the question now is, can we reduce the amount of work that we have to do? How? He said sound check. So rather than checking all the apples, Can we just check some? Okay. So we're starting to get into how ZK really works. ZK is all about taking computation that is really expensive and then reducing the amount of work that you have to do to just like, to something really small. Okay. But let's explore from the Apple perspective first, and then we'll link it to how ZK really works. So, let's say we're just checking one apple. We need to figure out, can we still detect errors? Like if there's a bad apple in there, are we still going to be able to detect it? Okay. So, using the check one apple strategy, how many checks would we have to do here? Just one. Just one, right? Because we're just checking one, right? It's directly in the protocol. So, we're checking one. But now, what is our probability of detecting an error, right? If we're checking 1, we might just check location 2, right? If we check location 2, it's green, not red. And then we're going to assume that the entire bag is green. We take this to the market and they put us in jail, right? We don't want that to happen. So, um, let's just- So how can we calculate probability? It's basically the number of bad apples divided by the number of total apples. So that's 7 red apples divided by 14, which is a 50% probability. So if we just check one in this scenario, there's a 50% chance we're going to jail and there's a 50% chance we're going home with money. Does that make sense? So this is scary, but it's even worse. Imagine this was what the bag contained, right? Now it's only one that is red. So if we just randomly choose one slot, we are most likely going to get a green, right? So now our chances of going to jail is a lot higher. Does this make sense? So that's 1 divided by 14 times 100, which is a 7% chance that we take the money home. and a 93% chance that we go to jail. So this is not good. But the good thing is that the amount of work we did is really small, right? We just did one check, but then the probability is fluctuating. Does this make sense? Does this make sense? Yes. Okay, cool. So what, what you should see from this is that Randomness likes certain scenarios, right? So when we use this scenario, randomness liked it better than when we use this. Does that make sense? So the more red apples are there, the more randomness favors that, right? So we can do one check and we'll still be sure that, um, we're not going to jail. Does that make sense? So ZK is basically taking advantage of this idea that randomness likes certain scenarios and it doesn't like other scenarios. So we need to convert our problem into a scenario that randomness likes so that we can do less work. That is ZK in a nutshell. So we have been able to dramatically reduce the amount of work we are doing, but then we have a high probability of making errors. So this is the characteristics of this protocol. The first protocol is we did a lot of work, but then we never made an error. This one, we're doing little work, but we make errors a lot. So the question is, can we get the best of both worlds? This is what ZK is. So now let me pose it to you because once I explain it, you cannot recover. Right? It's like, it's like a magic trick. It should seem impossible right now. The question is, is there a way to only check once but have, let's say, 99.9% probability of detecting a bad apple? It doesn't seem possible, right? Like, it does not make sense. Like, how are you going to just check once and then have a 99.9% probability of detecting a bad apple? And this is what zk does. Okay, so this is the main idea- error amplification. Okay, so imagine we have a function that takes the apples. If there's an error in it, it's going to amplify it. If there is no error, everything is the same. Okay, but in order for us to do that, we need to increase the size of the apple. You know, we started with 15 or 14, but let's now make it 1,000 times. So let's say 14,000 or 15,000, but then we're going to increase it following a very specific protocol. So if all apples in the small sample- that's the initial bag- if everything is green, then the additional apples we're adding are also going to be green. Cool. So I'm going to give you a visual. So let's say this was the small bag. You can imagine that this is like 14, right? And then this is the big one. You can imagine that that's like 14K. You can see that everything is still green. Does this make sense? Now, if even a single one is red in the initial sample, we are going to add only reds, only reds. Does that make sense? So now in this scenario, one of them was red, one of them was green. We left the green, but then the rest were red. So now we have turned a situation whereby there was just one error to a situation whereby there are now a lot of errors. And that is something that randomness favors. So let's revisit the check one protocol where we're just doing one check. But before we do that, let's first of all blow it up. You know, this was the scenario that randomness didn't like, right? Because you are most likely going to pick one of the greens rather than the red. So we blow it up with the error amplification logic. Can you see this now? So now The number of greens still 13, but then the number of reds went from 1 to 13,987. So we have a lot more reds than we have greens, and this is where randomness likes to work. So now we can sample 1 apple from this set, and we're most likely going to land on a red. Before If we sampled one apple, we are most likely going to land on a green. So because of this error amplification, John Doe is able to know that there exists an apple in the initial bag. Does this make sense? Yes. You see how it works, right? This is what ZK is. This is literally what ZK is. So we'll look at that later. So now How much work is done? 1. Right, but the problem before was that the probability was bad. Now what is the new probability? Number of reds divided by total times 100. Number of reds now, 13,000 divided by 14K times 100 is 99.9%. Have you seen how we have gotten the best of both worlds? Now it is impossible to get 100% anymore because we have introduced randomness. The only way that you can get 100% is if you check every single one. We're now in a probabilistic system. So when you sample randomly, you are most likely going to- and there's still like a chance for error. It's just that you can reduce that chance for error to something like really, really tiny. This is like 0.01. And if you increase from 14K to let's say a million, when you're blowing up, then you're further reducing that error. Does this make sense? Any questions so far? So there's a chance you can pick the green one, but the chances are very, very low. So you imagine a scenario whereby I take a grain of sand, right? And I mark it, then I throw it in the beach. Then I ask someone that wasn't there to come and randomly pick one grain of sand. What are the chances that the person is going to pick that exact grain of sand that I marked? So that is the similar- that's a similar scenario. Actually, okay, yes. So error amplification is going to- you're saying that before, you know, we're saying it's just one check, right? That the work is now small. So in ZK, we have something called a prover and a verifier. The prover is the one that is going to do that work so that the verifier can do very little work. So we have changed a computation that normally takes, let's say, 1 minute. We have turned this into a computation that we're basically splitting the computation into 2 parts. So the prover is going to do one, but the prover will do, let's say, 2 minutes worth of work. But then that means that the verifier can now do 1 millisecond worth of work. Does that make sense? So the prover is going to do more work than normal because it has to amplify the error, right? But then because of that, the verifier will be able to do very, very little work. Does that make sense? Yes. Yes. Yeah, the prover will go through all the outputs and then blow it up based on the scenario. And then if the verifier will just like pick one and then Now that's basically it. Does this make sense? You still, you still feel like you have a question, so just ask away. Yeah, processing it. Yeah. Yeah, so the plural, the main, the main, so the main idea behind ZK, right? One application of ZK is that you can have a, I have compute, like I want to do some computational work. Let's say I want to add up 500 numbers or I want to figure out like some very complicated function, but then I'm just a phone. So I don't have that computational resource in order to do that. But then I have someone else that has a supercomputer. He now has the resource to do that. But then let's say I give him my work to do and then he doesn't want to pay electricity bill. He doesn't want to run that long computation. He just wants to get money from me. So there's no reason why the prover or the supercomputer is not going to just lie to me about what the result is. Does that make sense? So let's say I wanted to add a billion numbers. I don't have the resources to do that. I give it to you. You have a supercomputer. But then you could just tell me the answer is 146, right? How will I know that you are not lying to me? The only way is if I redo the work, right? But I never had the computational resource to do that in the first place. So instead of you to just add the numbers, You're going to add the numbers and you're also going to do some sort of error amplification. So that would now afford me a way to check your work with very, very tiny computational resources on my end. Does that make sense? So don't worry, we'll talk more about this. Okay. So that's- OK, so the way you do that is you can encode computation in things called polynomials. I can't go into too much detail now because of time and everything. But OK, don't worry. We'll get back to that. And I'm still around, so we can always talk. So we have moved computation from being symmetric to being asymmetric. So normally, what happens is that if you want to verify computation that has been done, you have to redo the computation. So if you do it, I have to do it in order to verify what you're doing. That's kind of like what's happening in the blockchain space where the validators or the nodes are redoing the computation in order to verify that you actually did the work. But now we are turning computation from being symmetric where 2 parties have to do the same work to being asymmetric where one party is going to do the work plus more so that another party can just do a very tiny piece of work in order to verify what has been done. So this is like, this is what we have been able to achieve technically. And this is all what ZK is. ZK has a prover that does more work so that a verifier can do less work. Yeah. Yes. So it's part of the protocol because you wouldn't know that all apples are green in the first place, right? So it's the prover that is going to do the error amplification. You're going to see that everything is green. then it's going to add up to- it's going to blow it up. And then verifier still just checks one, and most likely it's going to be green, right? So that's how the verifier is going to know that. Yes, it's just if there's an error, then it's now amplified. But if there's no error, then you just blow it up. Does that make sense? Okay, so this was the supercomputer thing. So basically with this now, you can have an army of supercomputers. Let's say like a billion supercomputers and you can get them to do work for you and be able to verify that work. So they cannot lie to you about the work that they have done even though you have limited resources. And then we basically use randomness to achieve that. So I'm not sure I can go into this right now because of time, but a way to do error amplification is by using Polynomials. Yes. So there's something called polynomial interpolation. Polynomial interpolation, you basically interpolate the apples. And then if there's an error, like, so, you know, a polynomial, you can evaluate a polynomial at an infinite number of points. So that kind of like gives you a sense of the blowup, right? So, but then you interpolate it with this initial set of points. I'm going into too much detail right now, but see an example here where you have like red apples, red apples, red apples. So because of this red, you can see now that if I evaluate it anywhere outside of the domain, it's going to be red. So this is red, that is red, and any other point outside 1 to 15 is going to be red. Does that make sense? Yeah. So the polynomial is kind of like a succinct way to represent this. So the provider is not checking. The verifier, just one, yes. You could- so if you do one and you have a 99.9%, you can do 2 and then it basically adds more 9s to the back. So like 99.9999999%. So the more checks you do, the more confidence you have. As to the checks with the verifier, and then the verifier, I think it's the verifier. So the person that's doing the checks, are there scenarios where- Yes. So let's say, um, one check gives you a 50% probability of being right, right? You can do multiple checks in order to increase that probability. So let's say you're not blowing it up a lot and you just, you just maybe like times 10 or times 100, then that means that the probability that you're going to- the confidence level for each check is lower. And in order to get like a high confidence level overall, you have to do multiple checks. So you can basically get your probability to any point, your confidence level to any point that you want. Either by increasing the blob factor or by checking multiple times. Any other question? Okay. So that's basically the summary, right? You have been able to make the computation asymmetric, and because of that, the prover can do more work in order to afford the verifier doing less work. So that's basically it. So we have a study group where we go into ZK, like really, really deep into ZK. So all this I did, all what I did here was just like the high-level intuition. But then talking about like the maths, the programming, everything, we have a group where- hi, I'm Francis- where we take you from like knowing nothing to being able to like write out these protocols in code. Cool. Our study group is made possible by the Ethereum Foundation Privacy and Scaling Exploration. So they are focused on like the application of ZK in really, really interesting ways. You can go to their website or join their Discord. They have like this really cool application called Cursive, which for events like this, For events like this, they apply ZK and FHE to the real world. So they have tags and then you can like tap the tags and basically be able to attest or prove certain statements about your presence in that event, which is really cool. So that, I think that's one of them. So when after the talk, you can go and meet Elo and he'll explain how that works. Okay. Yeah. So if you want to join the study group, this is it. We have one cohort running right now, But then we are going to start a new one very soon. And we'll keep you updated on the group. All right. Thank you very much. Thank you.

More from this hub

Something wrong, or a video you want off this page? Write to wethem.xyz@gmail.com and it is fixed or taken down within 48 hours.