ZK Workshop - PSE team

hello guys so my name is wisdom um The Talk today is an introduction to ZK so the goal of this talk is to basically give you an intuition for how ZK worked 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 math no very tiny math and um just a lot of intuition basically um don't worry I don't I don't need it's fine don't worry so um 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 do is a farmer and he basically makes apples okay so the idea is that John do 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 do to be able to figure out that his bag only contains green apples okay that's the problem that we care about and um okay so um what does Jo what 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 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 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 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 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 output that is right 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 Pro call 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 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 say some check so um so rather than checking all all the apples can we just check some okay so we are 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 um 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 right because we're just checking one right is is directly in the protocol so we're checking one but now what is our probability of detecting an error right if we're checking one we might just check location two right if we check location two it's green not red and then we're going to assume that the entire bag is green we take it to the market and it put us in jail right we don't want that to happen so um let's just what so how can we calculate probability um it's basically the number of um bad apples divided by the number of total apples so that's seven 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 50% chance we're going home with 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 one um divided by 14 * 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 so this make sense does this make sense Okay cool so what what you should see from this is that Randomness likes certain scenarios right so when we use this scenario Randomness likeed 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 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're 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 this is what ZK is so now let me pose it to you because of once I explain it you cannot recover right it's like it's a 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 reting a bad apple and this is what 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's 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 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 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 they not 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 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 [Music] 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,985 so we have a lot more Reds than we have greens and this is where Randomness likes to work so now we can sample one apple from from this set and we are 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 do is able to know that there exists an apple in the initial bag does this make sense 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 now how much work is done one 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 * 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 of 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 be 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 they 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 um 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's is the similar that a similar scenario actually okay yes so error amplification is going so 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 change a computation that normally takes let's say um one minute we have turned this into a computation that we're basically splitting the computation into two parts so the Prov is going to do one but the Prov will do let's say two minutes worth of work but then that means that the verifier canot do one millisecond water work does that make sense so the pr is going to do more work than normal because of 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 Prov go through the output and then blow it up based on the scenario and then if um the verifier will just like pick one and then that that's basically it does this make sense you see you you still feel like you have a question so just ask away yeah pres it yeah yeah so the P the main the main so the main idea behind ZK right one application of ZK is that you can have a I have comput like I want to do some computational work let's say I want to add up 500 number or I want to figure out like some very complicated function but then I'm just the phone right so I don't have that computational resource in order to do that but then I have someone else that has a super computer right 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 right he doesn't want to run that long competition he just wants to get money from me so there's no reason why the prover or the super computer is not going to just like 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 resource to do that I give it to you you have a super computer but then you could just tell me the answer is 146 right how will I know that you're 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 in 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 not afford me a way to check your work with very very tiny computational resource on my end does that make sense so so don't worry we we we'll talk more about this okay so um that's okay so the way you do that is is you can encode computation in things called pols right I can't go into too much detail now because of time and everything but um okay don't worry we'll get back to that and I'm still around so we can always like 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 right so if you do it I have to do it in order to verify are doing that's kind of like what is happening in like the blockchain space where um the validators or the nodes are redoing the computation in order to verify that you're actually did the work but now we are turning computation from being symmetric where two 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 Prov that does more work so I verify can do little work yeah yes so it's part of the protocol because you won't know that all apples are green in the first place right so it's the Prov that is going to do the error application it's going to say 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 going to know yes it's just if there's an error then it's not Amplified but if there's no error then you just blow it up does that make sense okay so this was the super computer thing so basically with this now you can have an army of superc computers lot of like a billion superc computers and you can get them to do work for you and be able to like verify that work so they cannot lie to you about the work that they have done even though you have like limited resources and then we basically use Randomness to attribute that so um I'm not sure I can go into this right now because of time but but a way to do error amplification is by using polinomial yes so there's something called polinomial interpolation polom interpolation you basically interpolate the apples and then if there's an error like so you know a polom you can evaluate a polinomial at an infinite number of points so that kind of like gives you a sense of the blow up right so but then you interpolate it with this initial um set of points I'm going to too much detail right now but see an example here where you have like red apples red apples red apples so because of his red you can see now that if we 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 so the polinomial is kind of like a suent way to represent this so the Prov is not checking the verifier just one yes you could so if you do one and you have a 99.

9% you can do two and then it basically adds more NES to the back so like 99.9999999% so the more checks you do the more um confidence you have as do check with the verifier and the verifier I think it's the verifier so the person that is doing the checks are there scenarios where yes so let us 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 blow factor or by checking multiple times any other question okay so that's basically summary right you were able to make the computation asymmetric and because of that the pr can do more work in order to afford the verifier doing less work so that that that's basically it so we have a a study group where we go into ZK like really really deep into ZK so um all this I did all what I did here was just like the high level um intuition but then talking about like the the math the the programming everything we have a group where um high and Francis where we take you from like knowing nothing to being able to like write out these protocols in code and um our stud group is um as stud group is made possible by the theum foundation privacy and scaling exploration so um they they are focused on like the application of um ZK in really really interesting ways you can um go to their website or join their Discord they have like this really cool application called um cive which um for events like this EV like this they apply ZK and FH 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 um when after the S you can go and meet um ELO and you will explain um how that works okay yeah so if you want to join the study group um 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 [Applause]