2:28 You can actually do this process with any amount of items and just make a thought experiment about putting them under cups and shuffling them first before letting the tester do it again to make the process keep going. Also you could do this with positive whole numbers and the distances between them by switching the numbers as part of a code.
Security wise, zero knowledge proofs don't stop fishing. I'm not doing all that modulo arithmetic in my head, its done on the computer. If all the banks use this protocol, all a scammer has to do is put in a password box, make it look like a bank website. But it just sends them the password, no zero knowledge proof used. Or play as middlemen, posing as bank and customer, passing messages back and forth until they log in.
From what I understand, there are subtle reasons why pretending to be the website would not work, which have to do with the specific protocol. Not all zero knowledge proof protocols would work, but there are ways to design it so that phishing is impossible. As for the man in the middle attack, I think you may be right. At least the attacker wouldn't learn your password, but I might have gone a but far to claim phishing is eliminated completely. I'll think about it some more.
if the bank is using the "zk proof", then it should never provide an interface where the user puts the password to log in, plus it should also educate the client that we will never ask for direct passwords. boom!! the client will always know to never put his password on a web page.
@@ShakeelKhan-pz6zl Ok. Lets say I know my password, how does the bank authorize me. I am (well at least most people are) unable to do modulo arithmetic in my head. All I can do is type the password, or maybe just some letters of it.
I have one more question, at 9:59 "if you don't know x, then you can choose to give C = g^r mod p, ...", what? Isn't that the prover should know x? If the prover doesn't know x, what is he trying to prove?
There's the difference between an honest prover and malicious prover. Honest provers know the secret, and malicious provers want to convince us they know the secret despite not knowing it. We want a protocol that honest provers can always pass, but malicious provers cannot.
@@alexonscience Ok, but you have already elaborate in your video in the first place (at 7:50) that when a prover knows x, he gives the verifier C = g^r mod p, but why later you state that if a "malicious" prover doesn't know x and also gives out C = g^r mod p? I am confused.
@@winkeesdigiland8905 Anyone can give g^r mod p, because r is only a random number. But only an honest prover can give g^x since only an honest prover knows x.
@@alexonscience Ok, so here is what I am understanding, if you are a dishonest prover, you either choose to give C = g^r mod p or C = (g^z)/y mod p to the verifier, and the verifier will randomly ask you what r or w (or z) is. and you can't always answer correctly. But if you are an honest prover, you can always answer correctly. Right? But if the verifier only asks for r, how does he verify that the prover knows x?
An awesome in-depth video 🥂 after I've watched a whole lot of simplified explanation videos while wondering about the implementation and application. I have one question tho: How can zero knowledge proof outperform biometrics validation? As to my understanding, we have to store "x" or the password in our devices, but they are more separable than our unique biometrics and are more vulnerable to theft and lost.
There are pros and cons of every authentication method; that's why two-factor is so popular. Biometrics cannot be changed if they are compromised, they inherently use private/sensitive information, can have false positives and negatives or even change over time, and are harder to implement.
This is a corollary of Fermat's little theorem. If you open en.m.wikipedia.org/wiki/Fermat%27s_little_theorem, under Generalizations, the second paragraph talks about this corollary. If you already know some modular arithmetic, you should try proving this corollary from FLT.
@@a2m2000 First page of www.cs.cornell.edu/courses/cs2800/2011fa/Lectures/lec_sept_26.pdf for a full proof. But the Wikipedia article already has a brief proof. It uses Euler's theorem instead of Fermat's last theorem, since Euler's theorem is a superset of FLT.
@@alexonscience Thanks.. I will go through it. on another note from this point on what do you recommend I study to understand zkp for projects such as Tornado cash on ethereum, do you have any suggestions for a path to understand this topic? thanks again (I liked, and Subscribed because you deserve it)
why is y * C mod p = g^x * g^ r mod p? since y = g^x mod p and C = g^r mod p, shouldn't it be y * C mod p = (g^x mod p) * (g^r mod p) mod p? how do you reduce to that?
There is a theorem: If a = b (mod n), and c = d (mod n), then a * c = b * d (mod n). If you want to prove it, you can use the definition that a = b (mod n) if and only if a - b = k * n for some integer k. Basically, there are two different ways you can use mod. One way is to treat it as an operator on integers, just like + and -. Another way is to treat it as a configuration on existing arithmetic. You may have heard this called an equivalence relation, or a finite ring or field. This second type of mod is easier to work with mathematically once you get used to it.
Hello, I did not write any code for the protocol in the video. This is more a toy example, and real zero knowledge proof protocols would use more efficient but more complicated algorithms. There are some libraries out there to do these protocols like libsnark (which I worked on for my research). But if you want the code for learning purposes, I encourage you to write it yourself (or maybe ask chatGPT).
Thank you for this video, this is realy interesting. But I have something I can't understand. When you choose the z number, I don't understand why when the verifier ask for "x+r", the result W are equal to z. So if someone can help me, it would be really appreciated.
Sorry I'm not sure what you're asking exactly. z is used when a malicious prover wants to convince the honest verifier that they know x, even though they don't. The prover generates a random z, and when the verifier asks for C, the prover sends C = g^z/y. And when the verifier asks for w = x + z, the prover sends z. The verifier will then check that yC = g^z. This is an equation that should be equal when the prover sends the correct x + r, but it will also be equal for the malicious prover's z. Fortunately, the verifier can combat this trick by asking for x + r only half the time, and asking for r the other half of the time.
I'm not sure how you'd prove that something is not a thing here. Like, say I had a nuke and I wanted to hide that fact. I'd recognize that thing as a nuke. In the flower example, I'd have two things, the nuke and not the nuke. I could have you switch them around a bunch, perhaps proving to you, that I can distinguish these two things. But that's all that's telling you. I could claim neither of the two objects is a nuke. There is no reason for you to trust me on that. The story is different, if *you* are the one trying to prove *to me* that what I have is, in fact, a nuke (and I happen to know you are right but I'm trying to lie to you), but don't want to give away how you can know this. But as long as the burden of proof is on me, I don't see how this helps at all for that particular problem.
(and worse, if you are trying to prove to me that you can tell that what I have is a nuke, at least with that switching problem, I could simply be dishonest about whether I flipped, insisting that your method doesn't work after all)
I guess one way out of at least the last part is to have an independent third party who truly can't tell the difference do the switching, and both you and the other person get to tell whether a switch occurred, leaving it up to the third party to say who is right. - But that also only works if you can guarantee the independence...
Sorry if I wasn't clear in the video. I didn't want to get too deep into the details. How the protocol works is that the party with nukes A produces two items: one that we already know is a nuke and one is an item that A claims is a nuke, which will be dismantled. The protocol then proves it the two items are identical (that is, produce the same number of tiny bubbles in a tube when neutrons are shot through it). The protocol does not take care of nukes that A never brought forward. The flower protocol I gave was just a toy example. No one actually uses that in real life. Practical protocols all run complicated mathematics with finite fields and polynomials on computers. I encourage you to read the original Princeton paper: www.princeton.edu/~aglaser/PU104-Philippe-Barak-Glaser-2015.pdf
@@alexonscience ah, using a reference nuke known to both parties to be a nuke changes things. So you are saying, for that sort of proof we are looking at the two-purple-flowers scenario rather than the one-purple-and-one-pink-flower scenario. That makes a lot of sense! Still requires at least one actual nuke to exist, which isn't great for the particular example of nukes, but that sounds far more useful for many other practical purposes. I know the flower example is just a toy experiment but I'd guess that, if there were such an obvious problem with that example, it'd be fairly likely that that same problem is somehow hidden in more complicated/practical variations.
@@Kram1032 but to use a zero knowledge proof in a real life situation like that would be comical like they know u have a nuke if you pull out the zero knowledge proofs XD
The problem with ZKP is that it over states it’s utility. There’s only limited use cases in the real world, without incurring more complexity in system design. Intellectually interesting. More hype than practical.
In my opinion ZKPs are still in their infancy, they have the potential to become faster and simpler over time, and we may discover more and more use cases. There are already a lot of use cases being researched, but it will take time to flesh them out, then convince people to adopt them. Besides, a lot of things we use right now are incredibly complex, including most cryptographic systems. If we hide the implementation details under a standard API it should be feasible to apply them more widely. Also, I wouldn't call their current status "hype," barely anyone has even heard of them outside of dedicated circles. Of course you have a good point too, and I'm excited to see how it plays out in the future.
@@alexonscience I think a video on a use case would be quite helpful. The thing for me is that adding complexity in system design only increases the risks of vulnerabilities and maintenance. For example, how does a person prove that he’s not a risk for AML. You can see how quickly the complexity can grow. At least I haven’t thought of an easy solution.
Hi, can you post a video explaining how zk-snark works? I have read a couple of articles and videos explaining zk-snark, but I can't connect how that differs from this one.
Huh I thought I responded to this comment already... Unfortunately I don't think I'll make a video on such an obscure and math-heavy topic, but I can briefly explain here. ZK-SNARK stands for zero knowledge succinct non-interactive argument of knowledge. A proof for a statement is a string that can only be created if the statement is true. For example, it can be the steps you take to derive the theorem from the axioms. An argument for a statement is a string that can only be created by a probabilistic polynomial time Turing machine if the statement is true. Proofs and arguments must have completeness (if it's true, you can prove it) and soundness (if it's false, you can't create a proof), but arguments have computational soundness. A proof or argument of knowledge is a proof or argument where the theorem you prove is that you know something. A zero knowledge proof or argument is a proof or argument where the verifier of the proof can learn nothing from the proof (other than the theorem is true). A non-interactive proof or argument is one where the prover just needs to send one message to the verifier instead of many interactions between them. A succinct non-interactive proof or argument is one where you can save on computation and proof size by adding a pre-computed reference string. TLDR: "Zero knowledge proof" is the general, imprecise term that I would use for a general audience. A ZK-SNARK is a very specific type of zero knowledge proof (argument) that is faster and more practical, that you would probably use for a real life use case. As for how ZKSNARKs work, something something math something something rank 1 constraint system polynomial commitment hashing sumcheck protocol finite fields
2:28 You can actually do this process with any amount of items and just make a thought experiment about putting them under cups and shuffling them first before letting the tester do it again to make the process keep going. Also you could do this with positive whole numbers and the distances between them by switching the numbers as part of a code.
This is the best presentation on ZKP.
This was epic. It's also very revealing. Of all the math I need to learn...
This channel needs more views!
Security wise, zero knowledge proofs don't stop fishing.
I'm not doing all that modulo arithmetic in my head, its done on the computer.
If all the banks use this protocol, all a scammer has to do is put in a password box, make it look like a bank website. But it just sends them the password, no zero knowledge proof used. Or play as middlemen, posing as bank and customer, passing messages back and forth until they log in.
From what I understand, there are subtle reasons why pretending to be the website would not work, which have to do with the specific protocol. Not all zero knowledge proof protocols would work, but there are ways to design it so that phishing is impossible. As for the man in the middle attack, I think you may be right. At least the attacker wouldn't learn your password, but I might have gone a but far to claim phishing is eliminated completely. I'll think about it some more.
if the bank is using the "zk proof", then it should never provide an interface where the user puts the password to log in, plus it should also educate the client that we will never ask for direct passwords. boom!! the client will always know to never put his password on a web page.
@@ShakeelKhan-pz6zl Ok. Lets say I know my password, how does the bank authorize me. I am (well at least most people are) unable to do modulo arithmetic in my head. All I can do is type the password, or maybe just some letters of it.
This is done by the computer program and offcourse in order to understand it, you must know the background knowledge.
@@donaldhobson8873 got it?
Enjoyed the Star Wars & Harry Potter references - this was really good!
General Kenobi! You are a bold one.
Nice informative video, I thoroughly enjoyed it!
Awesome explanation!
I have one more question, at 9:59 "if you don't know x, then you can choose to give C = g^r mod p, ...", what? Isn't that the prover should know x? If the prover doesn't know x, what is he trying to prove?
There's the difference between an honest prover and malicious prover. Honest provers know the secret, and malicious provers want to convince us they know the secret despite not knowing it. We want a protocol that honest provers can always pass, but malicious provers cannot.
@@alexonscience Ok, but you have already elaborate in your video in the first place (at 7:50) that when a prover knows x, he gives the verifier C = g^r mod p, but why later you state that if a "malicious" prover doesn't know x and also gives out C = g^r mod p? I am confused.
@@winkeesdigiland8905 Anyone can give g^r mod p, because r is only a random number. But only an honest prover can give g^x since only an honest prover knows x.
@@alexonscience Ok, so here is what I am understanding, if you are a dishonest prover, you either choose to give C = g^r mod p or C = (g^z)/y mod p to the verifier, and the verifier will randomly ask you what r or w (or z) is. and you can't always answer correctly. But if you are an honest prover, you can always answer correctly. Right? But if the verifier only asks for r, how does he verify that the prover knows x?
Can you give me some reference sources that might be useful for me to better understand the video? I am excited to this topic.
Greatly appreciated! How about a video on a non-interactive no more passwords zero knowledge proof.
Miss your videos! Hope you come back soon
Thanks! I've been busy but I'm currently working on a new video, stay tuned!
An awesome in-depth video 🥂 after I've watched a whole lot of simplified explanation videos while wondering about the implementation and application. I have one question tho:
How can zero knowledge proof outperform biometrics validation? As to my understanding, we have to store "x" or the password in our devices, but they are more separable than our unique biometrics and are more vulnerable to theft and lost.
There are pros and cons of every authentication method; that's why two-factor is so popular. Biometrics cannot be changed if they are compromised, they inherently use private/sensitive information, can have false positives and negatives or even change over time, and are harder to implement.
@@alexonscience Nice. Thanks for the information!
Really great video! Thanks :)
You're welcome
g^(x+y) mod p = g^(x+y mod (p-1)), I can’t understand it, is there any can explain it to me? Fermat is not like that 😅
This is a corollary of Fermat's little theorem. If you open en.m.wikipedia.org/wiki/Fermat%27s_little_theorem, under Generalizations, the second paragraph talks about this corollary. If you already know some modular arithmetic, you should try proving this corollary from FLT.
@@alexonscience thanks, but I didn’t see any connection between the equation and little Fermat theorem from that page
@@alexonscience, hi. I would appreciate if you show the proof, i cant figure it out either... thanks
@@a2m2000 First page of www.cs.cornell.edu/courses/cs2800/2011fa/Lectures/lec_sept_26.pdf for a full proof. But the Wikipedia article already has a brief proof. It uses Euler's theorem instead of Fermat's last theorem, since Euler's theorem is a superset of FLT.
@@alexonscience Thanks.. I will go through it. on another note from this point on what do you recommend I study to understand zkp for projects such as Tornado cash on ethereum, do you have any suggestions for a path to understand this topic? thanks again (I liked, and Subscribed because you deserve it)
Can you repost without the music please sir?
Here it is: ruclips.net/video/APKdinM2-ig/видео.html. Can I ask why?
@@alexonscience lmao the music is good
why is y * C mod p = g^x * g^ r mod p? since y = g^x mod p and C = g^r mod p, shouldn't it be y * C mod p = (g^x mod p) * (g^r mod p) mod p? how do you reduce to that?
There is a theorem:
If a = b (mod n), and c = d (mod n), then a * c = b * d (mod n).
If you want to prove it, you can use the definition that a = b (mod n) if and only if a - b = k * n for some integer k.
Basically, there are two different ways you can use mod. One way is to treat it as an operator on integers, just like + and -. Another way is to treat it as a configuration on existing arithmetic. You may have heard this called an equivalence relation, or a finite ring or field. This second type of mod is easier to work with mathematically once you get used to it.
@@alexonscience excellent, thanks!
Hi, do you have it's code implementation also?. If you have can you share, please?
Hello, I did not write any code for the protocol in the video. This is more a toy example, and real zero knowledge proof protocols would use more efficient but more complicated algorithms. There are some libraries out there to do these protocols like libsnark (which I worked on for my research). But if you want the code for learning purposes, I encourage you to write it yourself (or maybe ask chatGPT).
I was the 100th sub
That's amazing! Thank you all so much for your support
So in the future I could log into your email without knowing your email to send emails but have no access to reading your emails.
Not knowing your email password*
Amazing!!
amazing
why do you have to put such loud background music??
Thanks for the feedback, I'll tone it down next time. There are accurate captions if you are having trouble hearing what I'm saying
Thank you for this video, this is realy interesting. But I have something I can't understand. When you choose the z number, I don't understand why when the verifier ask for "x+r", the result W are equal to z. So if someone can help me, it would be really appreciated.
Sorry I'm not sure what you're asking exactly. z is used when a malicious prover wants to convince the honest verifier that they know x, even though they don't. The prover generates a random z, and when the verifier asks for C, the prover sends C = g^z/y. And when the verifier asks for w = x + z, the prover sends z. The verifier will then check that yC = g^z. This is an equation that should be equal when the prover sends the correct x + r, but it will also be equal for the malicious prover's z. Fortunately, the verifier can combat this trick by asking for x + r only half the time, and asking for r the other half of the time.
@@alexonscience Thank you for your (really quick) answer. And I have a better understanding
What part of science is this discussed in?
Zero knowledge proofs are a field in cryptography, which is theoretical computer science, which is arguably a subfield of mathematics
I'm not sure how you'd prove that something is not a thing here.
Like, say I had a nuke and I wanted to hide that fact.
I'd recognize that thing as a nuke.
In the flower example, I'd have two things, the nuke and not the nuke. I could have you switch them around a bunch, perhaps proving to you, that I can distinguish these two things. But that's all that's telling you. I could claim neither of the two objects is a nuke. There is no reason for you to trust me on that.
The story is different, if *you* are the one trying to prove *to me* that what I have is, in fact, a nuke (and I happen to know you are right but I'm trying to lie to you), but don't want to give away how you can know this. But as long as the burden of proof is on me, I don't see how this helps at all for that particular problem.
(and worse, if you are trying to prove to me that you can tell that what I have is a nuke, at least with that switching problem, I could simply be dishonest about whether I flipped, insisting that your method doesn't work after all)
I guess one way out of at least the last part is to have an independent third party who truly can't tell the difference do the switching, and both you and the other person get to tell whether a switch occurred, leaving it up to the third party to say who is right. - But that also only works if you can guarantee the independence...
Sorry if I wasn't clear in the video. I didn't want to get too deep into the details. How the protocol works is that the party with nukes A produces two items: one that we already know is a nuke and one is an item that A claims is a nuke, which will be dismantled. The protocol then proves it the two items are identical (that is, produce the same number of tiny bubbles in a tube when neutrons are shot through it). The protocol does not take care of nukes that A never brought forward.
The flower protocol I gave was just a toy example. No one actually uses that in real life. Practical protocols all run complicated mathematics with finite fields and polynomials on computers.
I encourage you to read the original Princeton paper: www.princeton.edu/~aglaser/PU104-Philippe-Barak-Glaser-2015.pdf
@@alexonscience ah, using a reference nuke known to both parties to be a nuke changes things. So you are saying, for that sort of proof we are looking at the two-purple-flowers scenario rather than the one-purple-and-one-pink-flower scenario. That makes a lot of sense! Still requires at least one actual nuke to exist, which isn't great for the particular example of nukes, but that sounds far more useful for many other practical purposes.
I know the flower example is just a toy experiment but I'd guess that, if there were such an obvious problem with that example, it'd be fairly likely that that same problem is somehow hidden in more complicated/practical variations.
@@Kram1032 but to use a zero knowledge proof in a real life situation like that would be comical like they know u have a nuke if you pull out the zero knowledge proofs XD
The problem with ZKP is that it over states it’s utility. There’s only limited use cases in the real world, without incurring more complexity in system design. Intellectually interesting. More hype than practical.
In my opinion ZKPs are still in their infancy, they have the potential to become faster and simpler over time, and we may discover more and more use cases. There are already a lot of use cases being researched, but it will take time to flesh them out, then convince people to adopt them. Besides, a lot of things we use right now are incredibly complex, including most cryptographic systems. If we hide the implementation details under a standard API it should be feasible to apply them more widely. Also, I wouldn't call their current status "hype," barely anyone has even heard of them outside of dedicated circles. Of course you have a good point too, and I'm excited to see how it plays out in the future.
@@alexonscience I think a video on a use case would be quite helpful. The thing for me is that adding complexity in system design only increases the risks of vulnerabilities and maintenance. For example, how does a person prove that he’s not a risk for AML. You can see how quickly the complexity can grow. At least I haven’t thought of an easy solution.
Hi, can you post a video explaining how zk-snark works? I have read a couple of articles and videos explaining zk-snark, but I can't connect how that differs from this one.
Huh I thought I responded to this comment already... Unfortunately I don't think I'll make a video on such an obscure and math-heavy topic, but I can briefly explain here. ZK-SNARK stands for zero knowledge succinct non-interactive argument of knowledge.
A proof for a statement is a string that can only be created if the statement is true. For example, it can be the steps you take to derive the theorem from the axioms. An argument for a statement is a string that can only be created by a probabilistic polynomial time Turing machine if the statement is true. Proofs and arguments must have completeness (if it's true, you can prove it) and soundness (if it's false, you can't create a proof), but arguments have computational soundness.
A proof or argument of knowledge is a proof or argument where the theorem you prove is that you know something. A zero knowledge proof or argument is a proof or argument where the verifier of the proof can learn nothing from the proof (other than the theorem is true). A non-interactive proof or argument is one where the prover just needs to send one message to the verifier instead of many interactions between them. A succinct non-interactive proof or argument is one where you can save on computation and proof size by adding a pre-computed reference string.
TLDR: "Zero knowledge proof" is the general, imprecise term that I would use for a general audience. A ZK-SNARK is a very specific type of zero knowledge proof (argument) that is faster and more practical, that you would probably use for a real life use case.
As for how ZKSNARKs work, something something math something something rank 1 constraint system polynomial commitment hashing sumcheck protocol finite fields