Basic Math Behind ZK s01 (By Milica)

Transcript

cooperation today we're so honored today we're so honored to have Malita here to give us some basic math knowledge behind Zeke's now let's welcome Melita thank you Kelly thank you okay Melissa here you go okay so can you hear me while everything is right yeah uh okay so um hi everyone I'm Melissa from Serbia and I'm a zika educator and basically what I do is um sharing my knowledge path publicly which is uh why I'm invited here on behalf of that learning and thank you

Kelly very much so uh let me see if we can use the whiteboards um from Zoom so that I can write and draw because that's what I like making uh draws so let's see okay yeah let me know if you see my whiteboard welcome it's awesome can you can you see my whiteboard

yes very clearly okay okay so let's try one of my favorite examples of Alibaba Kay so um usually we have um someone called Alice and Bob as actors so that's what we have uh usually in cryptography the two of those they're interacting and for the sake of referring to them as sometimes as a and b we call them Alice and Bob so um Alison bump uh are making um some sort of a game where Alice

proves to the Bob so she's sort of a pro that Bob that she has a key to the Secret Door and okay so um I'm starting usually when I when I'm explaining zero knowledge I'm usually starting with this more simple examples before we dive into more math uh because I want uh this everyone is on the same path uh and on the on the you know in the same page so let's um try to draw a path on on Alibaba cave so yeah I'm not really the best drawer

but let's say that this is the K and we have some Road inside and person that's standing somewhere here and entering the cave and let's say standing here cannot see the person uh that entered the cave already and there are some secret doors here okay so can you imagine there is some secret door here that um there is a key as well and uh Bob has no key so Bob has no key but Alice Alice claims she has a key indeed

so um Alice gets into let's let's say that this is Alice Alice gets into the cave and maybe she's here and uh Bob is coming and Bob wants to know if Alice has the key but Alice will not show the key to the Bob she will prove that she has the key deed if Alice takes a random pathway going back to Bob or that Bob orders the path to Alice for example if Alice is hiding I don't know somewhere here Bob obviously cannot see her so let's say

this is Bob Bob cannot see where Alice is but let's say let's let's call it left path and right parts so let's see Bob said like hey Alice can you hear me and Alice says yeah yeah I can hear you about and um Bob said like Alice take the last path I want you to take the left spot and maybe Alice is here and if she indeed has the key she is able to pass the Secret Door and take the left pad and then she comes to Bob like yeah you see I have the key I prove

this to you and Bob said like I'm still not convinced maybe you were accidentally uh on on the left side of the door and I want to once again to go into the cave and uh take some other parts so sometimes you would say left he would say right and uh if if Alice indeed has the key she would um she would be able to to cross around okay so um that was uh that was the the idea and that Bob actually approved every time because he saw Alice he saw the proof that that she's there like she was able

to pass to fast the gates uh okay and um let's say uh that um let's say that there are some other example as well and I didn't have uh the boluses that is the usual example but I do have arrows so do you still see me in front of the camera let's go to chat to see what people say so let's move from the white boards to to my camera can you guys see me yes

I'll call Echo so do you see that I'm holding arrows of different colors all right and um let's say I'm colorblind I cannot tell the difference between these two objects uh if I'm a colorblind person to me they are exactly physically the same but um there is probably some difference that I calibrated person cannot style and if you are a person that can tell the differences between the colors then you would always tell me the difference for example I can have them behind my back and then switching them and you

don't know like if I uh took the the red arrow um with my right hand and then switching them behind my back and tell you you can ask you like which is this color and if you repeat sorry and if you repeat that this is red again I would definitely say that you cannot have a difference between it you cannot make difference between these two objects but um yeah if you can tell the difference and I guess many of you and the school can uh you will always be able to tell me if I switch them or if I don't uh I might trick you and um you

always tell me like aha this this is this is definitely rad and I can show you this and you can tell that yeah this is green so you will always be able to tell me that there is some sort of difference which I as a color blinded uh verify I cannot tell so how do I verify so if I switch them behind my back like every time or every other time I would say like I switched them and they notice the difference this is good like it must be that they're not a liar so if we switch to the Whiteboard and yeah by the way if someone wants to try

and try out the game or here on the call I'll be happy uh to to play the prover and the verifier game if there are some volunteers yeah um so um let's say that let's please switch to the white boy I want uh to explain the percentages behind uh these interactive proofs so there are like two types they're interactive and non-interactive proofs um so let's go back to the Whiteboard and let's say like first time if you were not an honest very far you

will have like 50 chance that you will uh that you would um uh that you would convince me and every time there's less and less chance that you will be so so lucky that you will always be able to convince me uh that that you can differentiate between the colors so this is how it looks like sir first time there is half half uh see there is like um half chance like that you would uh convince me that something is uh did some statement that is false is true and next time

so it's a quarter right so it's quarter like if we have uh if we do this two times it's quarter right sorry for the bad line if we do this three times it's um it's uh one through eight and if we do this ten times so what would it be it would be uh one divided by two the to the power of 10.

which is one through two thousand and uh sorry yeah it's it's not 2000 it's rather uh so let me see okay okay it's one through one thousand and 24 which correlates to somewhere 0.1 percent so something like it so it's even less because it's not one divided by one thousand so it's less than uh zero point one percent if we repeat this experiment

uh 10 times so you can imagine like what happens after repeating a hundred times so it's less and less every time we repeated it halves so um these were like these were the example of interactive um zero knowledge proofs because uh I would for example not be able to tell that you can make a difference uh between the the colors and you you will you would uh to say Bob did not see the key uh that Alice had to open the Secret Door and uh yeah so there are there are

others um as well there are uh interactive ones which are usually um so the most there is uh out there like there are ZK snarks and ziki Starks and um basically uh if we take the popular term of the kbms usually if you scratch under the surface or pretty much any zkvm nowadays you would see uh that it's powered by either ziki Stark or ziki Stark and in the future I would I'll be creating a lesson on on that as well but uh for now um I can tell that for example even the

ziki snarks are having a small proofs and are faster we have zika stocks that have no trusted setup and that are for now Quantum proof we always think photography for now because you know give us a time and something will be breakable in the future so there is nothing that's uh practically guaranteed uh for good and forever um so um what else is there to to say about bathing things behind the case is possibly the principles behind it so there are like three principles behind

the case and their completenessantis and zero knowledge so I will write them uh here so let me see yeah cool this can move cool so it's completeness yeah so first one is completeness so that means that um if the statement is true an honest verifier will be able to convince the prover on the statement so if something is true it will always be true and Anonymous verify will be always able to convince the

prover that something is true indeed so um if that is not the case we don't have the completeness so the second thing as um second thing is sadness so the sound is what does that mean so the sentence means the following that if the statement as for example false that no cheating mechanism uh no cheating prover can convince an honest verify that the statement is true except for the very small percentage

like we had like we had here like that is 0.1 and less and less and let's say that we have um 100 rounds of those it would be almost impossible because we would have uh one divided by two two to the power of hundred and that's like insanely big number and um so the third one is zero knowledge so what does it mean it means that you um

the verifier does not reveal uh it's it's uh knowledge so um the poorer had zero knowledge on how to verify and how to verify knew something so you never reveal your your uh secrets for example uh like um that the Alice she never revealed her key to Bob right so Alice kept her her key to herself and that contributes to the zero knowledge and um yes so if you guys have any sort of questions and um

if you do not uh if you do not remember if you cannot come with some uh now you can always refer to my Twitter uh Xerox me let's say is the handle and I'll be happy to to um write on this topic or on to the topic that you propose and um yeah for for the next lesson I'm planning on explaining a modular arithmetics and um so will be announcing when that will be on air as well okay is there someone has questions

or if there's no and very thank you Monica uh for give for give us a very wonderful lesson thank you Stan thank you good afternoon for having me okay I'll stop the recording