Yes please! I'd love to see how to construct a zero knowledge proof from a proof of a proposition. An example of a more general case would be much appreciated.
Here's another cool example: Say a group of coworkers want to find the average salary of the group, but they each also want to keep their own salary secret. How can they do this? Answer: One person writes down a large random number, and adds their salary to it. They pass the sum to the next person who adds their salary to it and passes it on, etc. At the end the first person subtracts their random number, resulting in the sum of everyone's salaries. Finally they divide by the number of people to find the average. Because of the random number, no one in the group could have found out any information besides the average.
This is a cool example, but it's actually for multiparty computation, rather than zero knowledge. The parties compute a new result unknown to any of them, whilst hiding secrets from eachother.
@@kimberleemodel7182 Seems like that would be pretty handy in computing for collecting useful statistical data without having to insist on the usual strategy of demanding all your secrets are belong to us. A good way of collecting genuinely anonymous statistical insights on things like feature usage among customers etc. Currently so called anonymised data of this kind usually means their server applies some kind of theoretically one way hash algorithm to anything identifiable after you sent it eg the source IP and often not the strongest of hashes either. Using something based on this you could theoretically collect pretty detailed statistics on what functions get used the most or which produce the most errors for the average user without basically creating a potentially reidentifiable database of practically every click a user ever makes. More importantly though you could probably do so with a mechanism that could be relatively explainable to the user so they might actually believe you if you are genuinely doing it to improve the product by focusing on user needs as for that it is that statistical data you need more not per user data. Many companies do like to collect the latter as there are plenty of ways to fudge the legal and ethical lines between anonymity and identifiability for a tidy side profit, but it would be a cool tool if someone were inclined to put their money where their mouth was when claiming to respect user privacy etc.
@@seraphina985 Yahoo! did a password strength study that way once: by first re-hashing the data before passing it on to researchers. (could not find it in initial searching)
@@aaattteeennn , yes, but the example given is not a proof of anything, it is a computation of something without revealing certain information; a zero-knowledge computation, if you will.
Yes, please make a video about filling in colored graphs! I feel it would be very relevant for what I am mathematically working with! I feel you provided good and valuable context for this short topic! Much love.
On the poll, I expressed how the winning title is something people like me would instantly skip, but putting the losing title in the thumbnail is smart. This way, you're attracting both kinds of people. Well done!
I work in an area which zero knowledge proofs are critical. I think your presentation is nice and explains it beautifully. I especially like that whether the cups are swapped they were still moved, preventing answers from coming from lack of sound, etc. Any deviation like that should be watched carefully in real zero knowledge proofs, for example.
Assume video as usual. I'd heard of zero knowledge proofs before but never got them until now. Well done. I'd love to see a follow up on how mathematical proofs have zero knowledge proofs
When she was first explaining zero proofs I thought of a simple example that should apply. Say that I'm the only person who knows the trick for easily telling whether or not any number in decimal is divisible by 3. I could be tested by being given a set of really big numbers, some of which are primes and some are primes times 3. I could demonstrate that I can accurately pick out which is which without explaining how.
7:35 I would very much like a follow-up video about how graph coloring can be used to construct a zero-knowledge proof for any provable proposition. That's an insane claim!
Agreed, the two cups switching proof is just so simple and I can't figure out how to adapt this for other proofs, I understand what it is but can't apply it at all. I would love to be able to apply it to proving I know some secret linear functions and quadratic functions or something idk
The application would involve the number of skeptical proof-readers who are convinced. Every time a competent skeptic is convinced, this would increase the likelihood that the original proof is true. The whole thing suggests something like a blockchain confidence score. My issue has to do with the basic impossibility of ensuring competence AND skepticism. Academic fields are competitive (people want to “win”) but also authoritarian, dogmatic and insular (inherently biased toward those on the inside with a clear interest in keeping others out). That makes it incredibly hard to trust that A) critics will be adequately skeptical of renowned experts, and B) critics will be fair when dealing with outsiders or novices. Perhaps a pastiche of critic blockchain scores AND proof blockchain scores could enable a marketplace of sorts, but the managers of that market could always interfere with valuations. We might eventually be able to compare the quality of two proof claims: (hypothetically) “Fermat Is Proved” (99.997% likely) “Checkers is Solved” (99.999999992% likely) in which Paul Erdős (score 99.24% reliable) is cited [The preceding example is entirely speculative] In summary, ZKP offer a possible addition to the standard proof model which could express overall confidence and relieve many people of hundreds of hours of hard reading, but it’s certainly not a complete substitute. I do wonder if AI will advance to the point it can competently and skeptically read proofs…
@@romilgoel4191 perhaps. If so, that’s cool (I have a proof but it won’t fit into my brain all at once). It would really only be a “quasiproof.” It’s kinda like proving Schrödinger’s cat lives based on zero knowledge but some anecdotal evidence (Hey Theresa, is that cat hair on your jacket?) Such a quasiproof would be more statistical than the definitive, airtight, logical, formal proofs we read now. These might lead to a new class of proof-like assertions or confidence scores. It really is fascinating. TONS of the things we do outside of formal mathematics are explicitly or implicitly based on probability. Quite a lot of neuroscience indicates this may be the basic mode of learning across organisms.
I've studied graph colouring when I was a post-grad student, so I would most definitely be interested in seeing how it can be used to prove that a zero-knowledge proof can be built for any mathematical proof.
Great video! I've heard about zero knowledge proofs before, but the presentation veered between technical and hand-wavy. Your candy cloud example was a huge help. While I might not understand how to find a zero knowledge proof for a particular situation, I now feel like I at least get what it would involve.
Essentially this is why the Scientific method is so powerful. Testing predictions over and over reduces the probability you might be wrong, and gives us enough confidence to believe something is true. But a false prediction quickly increases the chances we might be wrong, even after many correct predictions.
Even more ironic is that, too, while a false prediction can be considered to be "wrong" it can still lead to a correct prediction reformulated down the line of inquiry.
I love the anecdote about the early paper being rejected multiple times. No one is immune from prejudices and biases, but evidence evnetually wins out (I hope :) ). The bit about pracitcal applications also goes to show how you never know where the next important practical idea will come from. So we should never stop exploring "knowledge for knowledge's sake," because you never know.
On the latter point, I always like to quote Feynman from a short spiel he gave on mathematics vs. physics. To paraphrase, the mathematician is only concerned with the purity of the logic, the abstract ideas, the axioms and the consequent results; whereas the physicist is only interested in reality and the ability to apply mathematical ideas. So when the mathematician says "here's how you handle such and such in N dimensions," the physicist says "but we live in three dimensions," to which the mathematician begrudgingly replies, "well then substitute N=3." The physicist goes about his business, only to sheepishly return 20 years later to ask: "Could you tell me about the case N=4 now...?"
I once explained a zero knowedge proof to 5th graders with a Waldo image and an oversized cardboard with a hole: I do know where Waldo is, and I proove it by putting the hole over Waldo, so you can see Waldo but nothing else of the image, you know that I know, but you don't learn where Waldo is (you knew he was in there beforehand)
As someone working in a computer science and engineering job, this satisfied a curiosity I didn't even know I had. Thank you Jade for such an informational and profound video.
I've been a fan of the channel for a while, and as someone with a fair amount of interest in blockchain technology, I gotta say you really nailed this video. This was fantastic, and anyone interested in understanding privacy coins should start with this video. I was unfamiliar with the concept that ZK proofs exist for every proposition that has a proof. I'd love to see another vid on it.
I think your example with the blockchain is sort of misleading. At least with Bitcoin, it's more that it's not particularly interested in your identity. What gets verified is that you know the private key associated with a particular "wallet"/public key which is a trivial thing with public/private key cryptography, and I think that verification qualifies as zero-knowledge. Whether or not we can figure out that Sue paid a hospital for cancer treatment with Bitcoin is a matter of whether or not Sue or the hospital have connected their identities to information that's public within the blockchain somehow. The hospital will probably make their wallets public for payment purposes, and anyone who's known Sue's address (maybe she created a GoFundMe for undisclosed medical expenses with her wallet in the description) is in on the secret of wallet addresses she's connected to. Someone sufficiently interested could figure out the broad strokes of what she paid for by parsing the chain. I only bring it up because it seems like you're testifying to a level of privacy that entirely public ledgers don't and can't guarantee. At least, everything I know about that's based on Bitcoin has similar weaknesses.
Zerocash aka Zerocoin unlike BitCoin does make extensive use of zero knowledge proofs for anonymous ledger entries, in the form of zksnarks. It's in their white paper.
You are right about Bitcoin, and that was also a gripe I had with the video. However, other cryptocurrencies have mitigated that, e.g. Monero uses ring signatures to obfuscate who signed a transaction, and uses encryption to hide details of transactions (sender, receiver, amount, UTXOs involved) from the public.
I love how succinctly you explained epsilon-delta proofs, too. I think that's what they're called? I just remember doing them a lot in my university courses (I thought maybe Complex Variables but I can't find my book ;-;), and so I perked up when I heard "this number isn't actually zero...[But] we can keep going until the odds that I'm lying are smaller than any non-zero number you choose" Honestly, this whole video was really great!
All that is being said in the video is that the limit of the probability of lying, p(x), as a function of the number of trials, x, goes to 0 in the limit as x goes to infinity. It was phrased ("we can bring this probability as close to zero as you like by doing sufficiently many trials") in the manner of the epsilon-delta definition of a limit, but the fact certainly wasn't proven rigorously using that epsilon-delta argument (thought not much extra is required to do that).
Thank you! There is com from me somewhere from one year ago saying it would be hard for me to find another angle than your great video above to cover this :) I've finally created my version on my channel, in French but you might appreciate the first protocol: a real-life ZKP for Sudoku. As the video progresses, the protocol is modified toward a dematerialized version, which might make the French more of a problem but the first protocol I guess the visuals are enough :)
Thank you very much for making this video. Apart from making a video about zero knowledge proofs on mathematical propositions, can you also explain how it is used in roll-ups and other solutions?
@@upandatom I'd love to see it! It's a really fascinating concept how you can take the result of a program that takes days for the prover to compute, but once they generate a succinct proof (snark), the verifier can be convinced of the result instantly without needing to run the program for days. (That snark proof can then trivially be made into a zero knowledge proof)
@@domotheus I think your *snark* suggests an entire new realm of epistemology. If I can persuade enough skeptical people of something can I regard that persuasion as proof? If so, hooray-no more reading hundreds of pages of quasi-comprehensible theory. If not, “WARNING WILL ROBINSON!” ZKP is profoundly amazing and philosophically deep. At present it seems like fairly technical finite math (AKA computational computer science) to me. When its application and understanding become part of social understanding, will humanity have advanced? Perhaps we are starting move this way by trusting in blockchain (which seems trustable to an increasing number of us). Should elections be safeguarded with blockchain technology? How can we persuade partisan players with a great deal to lose or gain to adopt a fair and far safer system that prevents almost every type of abuse. Perhaps if Vellayappa Ayyadurai Shiva, the brilliant inventor of email, were to devise such a system, people would try it. Too bad he’s vehemently opposed to so much that constitutes authority and political correctness. Accordingly, this man who has holds four degrees from the Massachusetts Institute of Technology (MIT), including a Ph.D. in biological engineering, and is a Fulbright grant recipient has been systematically marginalized and is now “known for” his pseudoscience, conspiracy theories and unfounded claims.
@@scottaseigel5715 I'm not sure if you understood the term SNARK - in this context, it refers to a Succinct Non-interactive ARgument of Knowledge: en.m.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof
For the example, wouldn't it be more true to say that the two pieces are in some way distinct from each other? If they were different shapes, but the same color, your example would still work the same way. Just a thought :D
Sounds it's kinda like this : P_ is a measurable property of both X,Y where X[ P_ ] =/= Y[ P_ ] Number of such properties is >=1 I know how to measure at least one of those properties, at least to the level that I will know with certainty whether the measured object cannot be X or cannot be Y. ie.: X and Y differ in wavelength and I can tell if two wavelengths are the same - BUT I might not know how to measure the exact wavelength nor do I have to know the exact wavelength of X and Y. If you sneak in a G with a wavelength that also differs from Y I will keep thinking it's still X and Y. We could successfully "play the game" with you sneaking in all kinds of other objects all the time, as long as you can predict what property am I using to discern X from Y and whether I actually know the property values of if I'm just able to tell the difference. Also, the fact you can "play the game arbitrarily long" doesn't equate to a proof I think. Either she simplified it too much (which I suspect is the case and that would be fine) or its technically true but practically not as you cannot "play the game" indefinitely in real life. It may get astronomically unlikely as fast as it wants but PI isn't "roughly" a halfturn.
Great video! Not only i understood what zero-knowledgeproof is about, but it also made me curios for more. However, this let me wonder: what if your statement is that both candies are the same color? How would you be able to prove that?
Thanks, I was looking for this comment. Q: are they switched? A: I dunno? x 1000 ? :) Normally, you could assume the claim is false, and when you fail to prove that you can assume the claim is true. But I don't see how you could apply that principle here.
Hard question, but here's my try. Assuming that there are a finite number of colors, proving the two candies are the same color is equivalent to proving both of your candies are different from the other n colors. In the simplest case, there are only two colors at all -- let's say red and green. And for a moment let's disregard the zero knowledge aspect a little bit. Proving that both are the same color means proving both are red, or both are green. We can do this by having the subject prove each candy is _not_ the same color as: a control piece of candy which is green, or a control piece of candy which is red. If the subject can always tell when either of their candies are switched with a green piece, then both of their candies are red. If they can tell when switched with red, both their candies are green. If the subject can't tell consistently for both pieces, then they're lying. Of course, you've gained extra information by doing this, if the subject is honest. Because now I know my subjects candies are both green, or both red. So this algorithm is not "zero knowledge." But we can fix that. Rather than us choosing a red or green piece as our comparison piece, we can ask our subject to choose one of them. If we don't know which, then we know both pieces are green OR red, but we don't know _which_ color. This works well for two colors. For more colors, we have to do more comparisons. For that reason, there may be a better algorithm than the one I just came up with. But yeah that's my attempt at it.
@@MichaelFairhurst Nice! In this situation, (identical information) the person obtaining the info (candy) should be able to see that there are identical elements to the swap. So, knowing that they are the same, replace one with a stand-in piece of information that is different. (Or maybe even for both) that way you can prove that you know but keep the original information safe (I.E. not expose that the information is identical).
My solution to to the problem in the beginning: I make a picture of them, in photoshop I randomly pick a hue transformation, resulting in a photo were it is still clear there are two different colored candies, without the information about the real colors. The other person can watch me take a picture and edit it as long as the image is not seen. EDIT: Easier method, the other person wears color changing glasses.
Jade, when I read the title I thought you were going to talk about asymmetric cryptography, which is also pretty neat - prove that you have something over an insecure channel without revealing the thing. But your topic was soooooo much bigger. Thanks, because now I have something new and fun to go find many books on ;-)
Asymmetric cryptography is largely orthogonal to zero knowledge. In asymmetric (or symmetric) the goal is to keep secrets from an eavesdropper. In zero knowledge, the goal is to keep secrets from the recipient of your communications. In the case of the differently colored candies, an eavesdropper would learn that the proof is about candies, but wouldn't learn the candies' colors (same as the verifier), and the eavesdropper wouldn't even be convinced that they're differently colored. Interestingly enough, ZK protocols can be "layered" behind transport cryptography, so that even the subject of the proof is hidden from an eavesdropper.
How could this not be the absolute BEST explanation of zero knowledge proofs? I watched a clip of Zooko explaining it and thought I understood it. He was good, mind, and I know he has put in immense work towards practically enginnering supporting infrastructure. But your presentation is phenominally good at explaining the concept. Thanks a million!
Love the video, but I have to say that I dislike cryptocurrencies to the point that I had to cringe when you switched from bitcoins to another topic with the words "another cool thing about zero knowledge proofs ...", implying that it was cool that zero knowledge proofs found an application in cryptocurrencies. Bitcoin & co. might be interesting from a technical point of view, but from a societal point of view, they are a neoliberal nightmare. I encourage anyone who is interested in a look at crypto from this perspective to go and watch "Line Goes Up" by Folding Ideas. But, politics aside, this video was really interesting on a conceptual level, and also very well executed! :)
After you watch that I recommend watching "This Machine Greens" by Swan Bitcoin. Edit: If you want a direct response to "Line Goes Up" I recommend watching "The ACTUAL problem with NFTs - A Response" by To The Point.
@@ijiikieru Just watched 'this machine greens', if you think there's a convincing argument there, sorry but you're in a cult. By being an energy sink, bitcoin is a negative sum game that relies on greater fools buying into the system to keep it functional. It leaks value through it's energy use. That documentary attempts to make the argument that it's valuable because of it's energy use and this flies in the face of thermodynamics.
Tried watching Line Goes Up... Had to stop when the Bitcoin section ended. He is either intellectually dishonest or uninformed. Calls into serious question whatever else was coming after. Gell-Mann Amnesia effect and all that.
This was really interesting and I would like to see you do more videos on this kind of proof. I like how you tied it into currency at the end because several things have bothered me about the notion of currency in and of itself. I remember adults having conversations about the wisdom of having taken US currency off of the gold standard. Since I was a really little kid and so the adults weren't going to include me in their conversation anyway, why what amounted to an exceptionally shiny rock would have any reason to be worth more or less than fancy paper or coinage with numbers, the name of the country, perhaps a Latin phrase or two on it, and some inexplicably odd artwork on it. I'm 42 now and this notion of currency has only seemed to become increasingly absurd to me. The only way that any sort of currency has value is if enough people agree to value it at a given level, which made me have to discard with the notion that anything really has value in and of itself. What your discussion of blockchain currency made me realize is that the point of currency is to organize the trading of one thing for another, whether that thing is one's labor or some actual item. So currency has no value in and of itself other than to be a placeholder for other things that people like to trade amongst each other. So the value is in being able to keep track of those trades.
You're right. But if currency is already imaginary thing, we can as well stop at fiat currency, cryptocurrency that is basically fiat plus wasting enough electricity to power medium sized country and fluctuates in worth so much you never know if a piece of bread will cost 1 coin, or 1000 next day, is comically stupid idea...
"…which made me have to discard with the notion that anything really has value in and of itself." "Value" is a judgement by a person. Nothing has objective value, because value is entirely subjective.
@@jursamaj I came to that conclusion as well but then I asked myself what the point of being a living being was at all and the only thing I could conclude was that, if there is any point to it at all, it is just to experience whatever ends up happening to us. It's a poor argument for meaning and it's not meant to be one, but when one asks the question of what they should do, I can only say that the answer is just to see what it's like to be you and to have that experience since that is the fundamental thing that all living beings have in common, whether they live long lives or die almost immediately after having come into being.
Yes, please make a sequel to this video explaining how it was proven that all hypotheses with a proof also have a zero-knowledge proof. Thank you for making this wonderful video :)
blockchain is simply a data structure, known in programming since 90s - cryptocurrency is basically the first good use of it, just like Merkle trees are good for hasing very large files but not good for hashing generally
I love Brady over on Numberphile and enjoyed his video on zero-knowledge proofs, but this video actually demonstrated a practical, easily understood actual example of a zero knowledge proof and now I understand them much better! Cheers!
Reading more about the topic, I think the general idea here is: - we need problems for which instances can efficiently be generated at random - the task must be to proof the existence of something, such that a single witness can be seen as proof - if the prover can somehow conjure up a single proof witness, all we need to do is to convince the verifier that whatever we have actually solves the problem without revealing the thing This technique cannot be applied if the proposition in question is of type „for all x“. Therefore, the mathematical examples you gave might actually not work
The whole thing boils down to „I can do card tricks, and I won’t show you how they work, but you can see that they do work.“ Those techniques have been around for quite a while, only now we found a way to certify that you can’t tell how the magician is doing it just from watching them do it. There are two categories now: 1. the magician has come up with some method to do his trick. In this case, you might be able to do it on your own. All that is guaranteed is that watching the magician do it won’t help you. 2. the volunteer on the stage works with the magician. The magician can do a fantastical magic trick for which there is no algorithmic explanation at all, but that is only because he solves an instance of the problem that is easy for him (but not for you). For cryptography, the latter is the interesting one. We’re interested in finding out that you have knowledge about a data point that you *cannot* have unless you have really seen the data point, i.e., there’s no way to algorithmically find the data point.
I appreciate the explanation. Very interesting concepts. But I have an issue with the test provided. The claim being "color" was being identified. But the two could have been the same color, but some noticeable difference in shape. The ability to detect ANY difference was all that was being tested. Not ONLY a color difference. But was even that being tested? What if a cup had been marked and what was tested was the ability to determine which CUP is which? The objects inside could be identical. What was tested was the ability to detect one set of objects from the other. Now looking through colored filters or using a colored light sources. Ask which is darker.
It was a simple real-world demonstration to show how it would work practically-the shape and kind of object is irrelevant. The color instead represent any secret. But rather than sharing the secret itself, you make propositions about it following different rules. This can be used for example in cryptography, where a secret has the potential of being intercepted by an attacker. Say for example a password. Rather than sending that password to the server, you instead prove that you know the password by answering the propositions put forward by the server, until it is satisfied.
@@glenncurry3041 Her demonstration is a valid example, you're getting hung up on the particulars of the physical demonstration. If it helps, imagine getting rid of the cups and candy entirely. Instead one person puts two identical squares of paper in front of the other person. The underside of the paper has identifying information on it. The outcome is the same. The cup game is a metaphor for explaining the much more complicated electronic equivalent.
@@RageXBlade So I am "getting hung up" on the example failing to do what it claims? And your suggestion is to then replace the entire example with a different example in order to prove the first example was OK? I understand that an attempt at a metaphor is being used. But a metaphor has to be correct in and of itself to be used. Rather than defending a bad one, using a correct one would seem far more scientifically correct and beneficial.
You're right. A real proof would involve taking out a single (unseen) candy of a third colour, then showing that there are 3 different coloured candies in your hand. They don't know which 2 colours the originals were, so that secret is preserved while undeniably proving the claim that you had 2 different colours at the start.
I swear I have watched a hundred videos about zero knowledge proof and never understood what it ACTUALLY meant due to the lack of demonstration, UNTIL NOW! so thank you sooooo much.
Good timing! Just the other day I was trying to explain zero knowledge proofs to a friend and not doing a very good job. I shall refer her to this video. Thanks again!
2:50 Since he never checked the cups, there "could" be a marking on one of the cups, this lets you "guess" correctly, even tough you're lying (same color). Or (in this specific case) she can hear how the cups are sliding on the table, to know if switched or not. (but this isn't about this specific physical example. this is more theory about HOW the proof can be done, especially in math. (at least hearing is much harder in math ;P ))
I don't get that example. You have proven only, that you know they are different, but not that you actually know the colors. And the fact that they are different have you given away. I heard an example that works better for me: Two rooms are connected by a door with a lock. You have the key and want to prove that you have the key without showing it. To do this you go into one of the rooms without the other person knowing which one. Now he calls you to come out of a specific room. There is a 50% chance that you don't have to use the key but by repeating this, the chance of you not having the key goes down. I also have never seen a cryptographic/mathematic example of a zero knowledge proof that I was able to understand, so I would like to see a follow up video.
You don't understand because the video shows an logical proof pretending to be zero knowledge. She proved that she knew that they were switch and that she has a method of knowing. Having rules to communicate the proposition automatically makes it a knowledge proof. Creating an entire language system just to say that you have a secret is the equivalent of these zero knowledge proofs. There is always a more abstract unit of data that is communicated.
just a couple of minutes in I was like "ahhh, that sounds a lot like a better explanation of blockchains as compared to the poor explanation I'd had earlier" haha thank you!
The term “secret” may cause some confusion regarding ZKPs. I (and probably anyone else) will certainly believe that you have secrets I don’t know without your needing to prove anything at all. You have to reveal part of the secret - that you have selected two different colors of candy in the example in the video - in order to apply the ZKP process for retaining to yourself the rest of the information. Yes, a video on the three-colorable map or the Sudoku examples of ZKPs would be interesting. Also, explaining the fact that for the application of ZKPs to the blockchain the proof needs to be non-interactive, which this video example and most other simple examples are not.
I also asked that myself , my solution would be: The other creates the pairs with all the possible combinations with 2 different colors and mixes them to the two of same colours. Then if you’re still always able to find out the correct one, the other can be pretty sure the ones you have are the same, because otherwise you would only be correct in 50% of the cases.
But wait a second. You could say they are different colors but they could be the same colors and just one of them have more sugaryness. Yes I made up that word just now. Or one could have a bigger left most lump etc. All you have verified is that you can tell the difference between whatever is under the cups. Or what if you just marked the inside of one of the cups. You havent proven they are different colors. Just that you know some way to tell if it has been switched or not.
5:12 Yes, I think Zero Knowledge Proofs can be practically applied as the only way for members within secret socieities to communicate safely in public.
Doesn’t “completeness” sorta destroys the whole point about “proving”? It presumes that you’re telling the truth in order to prove you’re telling the truth. How about the good old fashion “I swear” method? 😂
I love your Computer Science Videos. I just got my Bachelors Degree in Comuper Science and do know about a lot of what you are talking about, but you are making it so etertaining, it is like learing this stuff for a second time but with more fun. Love sis ♥
You are becoming one of my all-time favorite creators, Jade! Here's my vote for a follow-up video, maybe even a second follow-up video about the existence of a zero-knowledge proof to any proven proposition, if possible, though I would think YT algorithm wouldn't be so kind to that video 🙂
Actually, not all mathematical proofs have corresponding zero-knowledge proofs. ZK proofs exist for NP statements, which are efficiently verifiable; graph coloring is NP-complete, thus the existence of a graph coloring ZKP implies ZKPs exist for all of NP. However, there are complexity classes beyond NP, and some of those definitely do not have ZKPs. For example, EXPSPACE, the class of decision problems the require exponential space to solve, contains problems that do not have any ZKPs; this follows from the fact that IP=PSPACE and that EXPSPACE is a strict superset of PSPACE.
All mathematical proofs have corresponding zero-knowledge proofs _of corresponding lengths._ If the length of the mathematical proof happens to be exponential relative to the length of the problem statement, then the corresponding ZK-proof will also take exponential space and time. That will place it outside of IP (which stands for Interactive _Polynomial_ ), but it will still be a proof.
In 1986, Goldreich, MiCali and Wigderson proved that all languages with interactive proofs in NP have zero-knowledge interactive proofs. In 1990, Ben-Or et al. extended it to all languages with interactive proofs. Note that this only applies to statements which actually have interactive proofs. There are true propositions with no proof at all, not even an interactive proof, so they certainly don't have zero-knowledge interactive proofs.
0:16 I could use my spells against my teachers to prove that I am right in my arguments and bargain for better grades 😎 Wait!!! It is Mathematical?? I am outta here 😂😉
Thank you for this video! I think that there is a basic problem with the example you gave of the candy cloud game: After the first iteration, the person looking under the cups has gained knowledge about the candy clouds under the cups. She can base all of her subsequent statements on that first iteration. If she didn't really know that the clouds were two different colors, but they were two different colors, she can now correctly state whether the cups were switched or not on every turn. She can now satisfy all the requirements of the proof even though she didn't know the secret from the start.
The point that Jade is making is that if you didn't know the secret, you would not be able to correctly determine if the data was changed or not because you do not see it changed in the first place and the data is still a secret. You don't learn about what the data is, only the resulting data from the change. Switching cup is simplistic but that is the point of the demonstration. So that is why the probability is there and a large consistent prover/verifification process reduce the probabilty of false data to the point of near absolute certainty. If you did not know the secret, you would not be able to accurately determine if the data was changed or not correctly to the agreed difficulty probabilty of near absolute certainity.
With zero-knowledge proofs, one side has the full knowledge of whatever is in question. In this case, the person looking under the cups (Jade) picked the candy clouds from the jar and knows what color they are. The zero-knowledge aspect is with the person switching the cups, who never sees what the colors are, but can be convinced that the colors are different by Jade's consistently correct answers about whether the cups were switched or not.
Wonderful video, as always. If I remember rightly, another condition of ZKPs is that they only work for the verifier actively engaged. I.e. if you took a video of this whole procedure, there'd be no way for a third party to verify that it wasn't all staged, thus only the present verifier can be convinced. Oh, and if anyone wants more on the mathematics of the blockchain, I'd suggest 3Blue1Brown's video "But How Does Bitcoin Actually Work?". Anyone wanting a deep-dive into the ramifications of the technology should see "Line Goes Up" by Folding Ideas.
strongly agree w both 3B1B and LGU recommendations (though for 2 different reasons). also suggest a recent video by münecat (on her non-music channel) called "Web3.0: a libertarian dystopia".
@@dragonfly.effect Absolutely! I's thinking about recommending that one, too. It covers a lot of the same ground as Line Goes Up and is also pretty long, but it's got stuff that wasn't in there and is a good video in its own right.
Before i knew the idea of this, know I have the knowledge. It was like a light bulb being twisted while the light is on. Thank you so much. I work as a developer and this little tid bit you've shared is likely to accelerate my career.
In your example, additional information would be required to verify the "secret." As for the candy clouds, the verifier can see the jar and if different shapes as well as different colors exist, they would ask for the additional information. I'm fairly certain that would fall under the completeness category.
I'm still not convinced. At least with the example. You could tell me you put two different colors under the cups. But in reality you could put two different ANYTHINGS under the cops, as long as you could tell the difference. So you say you put two colored candies under them, when in fact you put an orange and an apple under the cups. The "proof" still works, but its false.
The proof is only demonstrating that she can distinguish the two items. In this thought experiment, the verifier already believes that the candies are under the cups but is skeptical whether they are distinguishable.
QUERY re cup example @1:00 onwards. If the colours are secret, and you put them in the cups then the cups are moved, you give complete control of the "secret" colours to the other party. If the other party is able to look at the colours,esp. if unknown to you, then what's the point in keeping them secret; viz-a-viz there is no need for this whole secrecy. If you do need to keep the colours secret then zero-proof as you explain it here can not be used in a cryptographic setting.
0:20 "without anyone telling what you are right about" Are you sure this phrasing is correct? You have to tell the validator what you are right about. You just don't have to tell him the actual value of what is being testet.
If you are familiar with the prisoner hat logic puzzle there is I think some logical crossover with that. The solution is based on an independent response outcome or rather lack of one that enables an assured knowledge response. It is a great logic puzzle that I would think has far deeper use.
Technically, in your candy cloud example- you could have just put two candy clouds of the same color under 1 cup or (if, say, the doubter could rattle the cups to make sure both had a candy cloud) picked two candy clouds of different shapes.
This by far the best video I have seen on Zero Knowledge proof. The best part is that you also brought in eves-dropping in this concept. Beautiful work! Thank you so much! :)
My mind was blown when you said there can be a zero knowledge proof for any proposition. Like what!?!?! Definitely looking forward to a follow up video!
This is one video, where I was basically lost and did not had enough background knowledge to understand. But, please keep more such videos coming. Edited: I watched the video second time and with attention. Now, I could understand most of what you said. And its still fascinating and very abstract.
5:10 Zero-knowledge proofs were used to verify binding government elections in Takoma Park, MD in 2009 and 2011, so real-world applications date back at least that far.
I'd like to spread an idea which often gets overlooked when talking about what's true: "True" and "Proof" only exist in the idea world(a.k.a math), zero knowledge proofs can exist there only because you can take that process to infinity. In reality everything is limited and has a probability attached to it, so saying "This is true because they proved it to me" can be very dangerous because what was proven may only work in a specific context or the "proof" 's probability may be not good enough for the listener who has stricter requirements. It's a lot more honest to talk like "I believe this because I saw that". Of course at some probability threshold everyone can agree so you get some things like "Law of Gravity" even though it might only work in just the part of the universe we see, or that tomorrow it can suddenly turn off.
For the candy cloud problem I would get someone else who is a trustworthy source (a friend or something) and show them the candy clouds and have them verify that they are different colors
Please make a follow up video. You only talked about the surface, but it's one of the most interesting things I've ever heard. I want to hear more real life examples to get an understanding. And maybe you could show how to prove that you know a prove of an easy mathematical proposition without explaining the actual prove.
as you were explaining the simple cup swapping example i felt my brain expand this is such an interesting concept, and i've always wondered about the 4 colour map theorem! This is my first video i've seen by this channel and im instantly interested, awesome video! informative, simple, and explaining real world links, love this!!
I would like to offer two arguments against this presentation of Zero Knowledge Proof. Let me begin by saying that, perhaps, the example given is intended to make a complex system of proof understandable by converting it into a simple, tangible format (ie: the candy-cloud example). Fair enough; unfortunately this simplification may have been oversimplified.
#1: The proposition that you can correctly tell if the cups have been switched indicates that you can tell the difference between the candy-clouds ONLY based on color. This ignores any other possible factors such as shape, size, etc.
#2: The requirement, at the start, that both parties are honest. If this is axiomatic, then proof is not necessary. You've said that you know that the two items are different colors, therefore it is so. If you are honest, no system of proof is needed; if you are not, the requirement is not met.
if i recall right, zero knowledge proofs are also the backbone of public key authentication mechanisms essentially you are trying to prove that you have the private key and therefore, that it is you who is talking to the server so the server sends you something thats encrypted with your public key and you decrypt it and then encrypt it with the servers public key and send it back and they can make that exchange as many times as they want, with any arbitrary verification messages, to establish each others identity to any arbitrary degree of certainty and at no point does either side ever reveal their private key
Mind blown. I love how you asked the question and said to think about it. I got stuck on if either of us is telling the truth. But, you added a 3rd part previously not revealed. I love these types of puzzles. I have one for you that follows a similar logic path of missing information. Trina and Zena were born within a few seconds of each other, same mother, same father, but they are not twins. Why not? If you don't know the answer, think about it. You didn't know about Tina, the 3rd child born. They are not twins because they are 2 of a set of triplets. Love your stuff Jade. Please keep making these and blowing my mind. Cheers!
I’m no mathematician or statistician so I hope you can clarify. When stating probability using the : symbol does it not imply an odds rather than a fraction? As in 1:2 != 1/2 Thanks
Should I make the follow up graph video? Like this comment if you want me to :)
Also 1:52 should be 1 : 7.89 x 10^31, my bad!
are u in instagram?
Yes please! I'd love to see how to construct a zero knowledge proof from a proof of a proposition. An example of a more general case would be much appreciated.
Zero knowledge proofs r cool. Also ZKSnark or SKStark make me sound smart!
@@karenjeandiez6331 yeah @upndatom :)
@@PranavGarg_ agreed... this video has got me very curious as to how that's possible
Here's another cool example: Say a group of coworkers want to find the average salary of the group, but they each also want to keep their own salary secret. How can they do this?
Answer: One person writes down a large random number, and adds their salary to it. They pass the sum to the next person who adds their salary to it and passes it on, etc. At the end the first person subtracts their random number, resulting in the sum of everyone's salaries. Finally they divide by the number of people to find the average. Because of the random number, no one in the group could have found out any information besides the average.
This is a cool example, but it's actually for multiparty computation, rather than zero knowledge. The parties compute a new result unknown to any of them, whilst hiding secrets from eachother.
@@kimberleemodel7182 Seems like that would be pretty handy in computing for collecting useful statistical data without having to insist on the usual strategy of demanding all your secrets are belong to us. A good way of collecting genuinely anonymous statistical insights on things like feature usage among customers etc. Currently so called anonymised data of this kind usually means their server applies some kind of theoretically one way hash algorithm to anything identifiable after you sent it eg the source IP and often not the strongest of hashes either. Using something based on this you could theoretically collect pretty detailed statistics on what functions get used the most or which produce the most errors for the average user without basically creating a potentially reidentifiable database of practically every click a user ever makes. More importantly though you could probably do so with a mechanism that could be relatively explainable to the user so they might actually believe you if you are genuinely doing it to improve the product by focusing on user needs as for that it is that statistical data you need more not per user data. Many companies do like to collect the latter as there are plenty of ways to fudge the legal and ethical lines between anonymity and identifiability for a tidy side profit, but it would be a cool tool if someone were inclined to put their money where their mouth was when claiming to respect user privacy etc.
@@seraphina985 Yahoo! did a password strength study that way once: by first re-hashing the data before passing it on to researchers. (could not find it in initial searching)
@@kimberleemodel7182 Are not all zero knowledge proofs multi-party?
@@aaattteeennn , yes, but the example given is not a proof of anything, it is a computation of something without revealing certain information; a zero-knowledge computation, if you will.
Yes Jade a follow-up video between zero-proof knowledge and the four color theorem is very much wanted! Thank you for the amazing content as usual :)
Yarsss, give us some of that zero-proof knowledge!!
Zero-knowledge proof?
Has this been done? I am excited to know about it
@@CyberMew Zero knowledge proof knowledge zero-knowledge proof. She can prove to us that she knows more about this without telling us what it is.
Yes, please make a video about filling in colored graphs! I feel it would be very relevant for what I am mathematically working with! I feel you provided good and valuable context for this short topic! Much love.
+1
agree
Gives a node to graphs....that was punny in theory
Yes please!!!
Oh yeah!
On the poll, I expressed how the winning title is something people like me would instantly skip, but putting the losing title in the thumbnail is smart. This way, you're attracting both kinds of people. Well done!
;)
This method works incredibly well for videos like this. It's both sciencey and understandable.
I work in an area which zero knowledge proofs are critical. I think your presentation is nice and explains it beautifully. I especially like that whether the cups are swapped they were still moved, preventing answers from coming from lack of sound, etc. Any deviation like that should be watched carefully in real zero knowledge proofs, for example.
Assume video as usual. I'd heard of zero knowledge proofs before but never got them until now. Well done. I'd love to see a follow up on how mathematical proofs have zero knowledge proofs
I agree. Your video is the best ZKP presentation I’ve seen to date.
Agreed. That was a great demonstration at the beginning.
I second that.
Especially since "proof" doesn't seem to have the same meaning in those two phrases.
When she was first explaining zero proofs I thought of a simple example that should apply. Say that I'm the only person who knows the trick for easily telling whether or not any number in decimal is divisible by 3. I could be tested by being given a set of really big numbers, some of which are primes and some are primes times 3. I could demonstrate that I can accurately pick out which is which without explaining how.
7:35 I would very much like a follow-up video about how graph coloring can be used to construct a zero-knowledge proof for any provable proposition. That's an insane claim!
Agreed, the two cups switching proof is just so simple and I can't figure out how to adapt this for other proofs, I understand what it is but can't apply it at all. I would love to be able to apply it to proving I know some secret linear functions and quadratic functions or something idk
The application would involve the number of skeptical proof-readers who are convinced. Every time a competent skeptic is convinced, this would increase the likelihood that the original proof is true. The whole thing suggests something like a blockchain confidence score. My issue has to do with the basic impossibility of ensuring competence AND skepticism. Academic fields are competitive (people want to “win”) but also authoritarian, dogmatic and insular (inherently biased toward those on the inside with a clear interest in keeping others out). That makes it incredibly hard to trust that A) critics will be adequately skeptical of renowned experts, and B) critics will be fair when dealing with outsiders or novices. Perhaps a pastiche of critic blockchain scores AND proof blockchain scores could enable a marketplace of sorts, but the managers of that market could always interfere with valuations.
We might eventually be able to compare the quality of two proof claims: (hypothetically)
“Fermat Is Proved” (99.997% likely)
“Checkers is Solved” (99.999999992% likely)
in which Paul Erdős (score 99.24% reliable) is cited
[The preceding example is entirely speculative]
In summary, ZKP offer a possible addition to the standard proof model which could express overall confidence and relieve many people of hundreds of hours of hard reading, but it’s certainly not a complete substitute. I do wonder if AI will advance to the point it can competently and skeptically read proofs…
@@scottaseigel5715 did you just prove that a proof exist without actually giving us the proof ?
@@romilgoel4191 perhaps. If so, that’s cool (I have a proof but it won’t fit into my brain all at once). It would really only be a “quasiproof.” It’s kinda like proving Schrödinger’s cat lives based on zero knowledge but some anecdotal evidence (Hey Theresa, is that cat hair on your jacket?)
Such a quasiproof would be more statistical than the definitive, airtight, logical, formal proofs we read now. These might lead to a new class of proof-like assertions or confidence scores. It really is fascinating. TONS of the things we do outside of formal mathematics are explicitly or implicitly based on probability. Quite a lot of neuroscience indicates this may be the basic mode of learning across organisms.
I agree. In particular proving that candies are of same color is impossible - at least not without giving away the secret.
I've studied graph colouring when I was a post-grad student, so I would most definitely be interested in seeing how it can be used to prove that a zero-knowledge proof can be built for any mathematical proof.
Great video! I've heard about zero knowledge proofs before, but the presentation veered between technical and hand-wavy. Your candy cloud example was a huge help. While I might not understand how to find a zero knowledge proof for a particular situation, I now feel like I at least get what it would involve.
Essentially this is why the Scientific method is so powerful. Testing predictions over and over reduces the probability you might be wrong, and gives us enough confidence to believe something is true. But a false prediction quickly increases the chances we might be wrong, even after many correct predictions.
Even more ironic is that, too, while a false prediction can be considered to be "wrong" it can still lead to a correct prediction reformulated down the line of inquiry.
I love the anecdote about the early paper being rejected multiple times. No one is immune from prejudices and biases, but evidence evnetually wins out (I hope :) ).
The bit about pracitcal applications also goes to show how you never know where the next important practical idea will come from. So we should never stop exploring "knowledge for knowledge's sake," because you never know.
On the latter point, I always like to quote Feynman from a short spiel he gave on mathematics vs. physics. To paraphrase, the mathematician is only concerned with the purity of the logic, the abstract ideas, the axioms and the consequent results; whereas the physicist is only interested in reality and the ability to apply mathematical ideas. So when the mathematician says "here's how you handle such and such in N dimensions," the physicist says "but we live in three dimensions," to which the mathematician begrudgingly replies, "well then substitute N=3." The physicist goes about his business, only to sheepishly return 20 years later to ask: "Could you tell me about the case N=4 now...?"
Jade, you are awesome! Such a simple, powerful and enabling explanation for this important concept!
I once explained a zero knowedge proof to 5th graders with a Waldo image and an oversized cardboard with a hole: I do know where Waldo is, and I proove it by putting the hole over Waldo, so you can see Waldo but nothing else of the image, you know that I know, but you don't learn where Waldo is (you knew he was in there beforehand)
Ah, answering the age-old mathematical conundrum of, "Where's Waldo?"
I can watch at most 2 of your videos per day as I need time to process and assimilate what I just learnt! :) Awesome content!
As someone working in a computer science and engineering job, this satisfied a curiosity I didn't even know I had. Thank you Jade for such an informational and profound video.
I've been a fan of the channel for a while, and as someone with a fair amount of interest in blockchain technology, I gotta say you really nailed this video. This was fantastic, and anyone interested in understanding privacy coins should start with this video. I was unfamiliar with the concept that ZK proofs exist for every proposition that has a proof. I'd love to see another vid on it.
I think your example with the blockchain is sort of misleading. At least with Bitcoin, it's more that it's not particularly interested in your identity. What gets verified is that you know the private key associated with a particular "wallet"/public key which is a trivial thing with public/private key cryptography, and I think that verification qualifies as zero-knowledge. Whether or not we can figure out that Sue paid a hospital for cancer treatment with Bitcoin is a matter of whether or not Sue or the hospital have connected their identities to information that's public within the blockchain somehow. The hospital will probably make their wallets public for payment purposes, and anyone who's known Sue's address (maybe she created a GoFundMe for undisclosed medical expenses with her wallet in the description) is in on the secret of wallet addresses she's connected to. Someone sufficiently interested could figure out the broad strokes of what she paid for by parsing the chain.
I only bring it up because it seems like you're testifying to a level of privacy that entirely public ledgers don't and can't guarantee. At least, everything I know about that's based on Bitcoin has similar weaknesses.
Zerocash aka Zerocoin unlike BitCoin does make extensive use of zero knowledge proofs for anonymous ledger entries, in the form of zksnarks. It's in their white paper.
You are right about Bitcoin, and that was also a gripe I had with the video. However, other cryptocurrencies have mitigated that, e.g. Monero uses ring signatures to obfuscate who signed a transaction, and uses encryption to hide details of transactions (sender, receiver, amount, UTXOs involved) from the public.
I love how succinctly you explained epsilon-delta proofs, too. I think that's what they're called? I just remember doing them a lot in my university courses (I thought maybe Complex Variables but I can't find my book ;-;), and so I perked up when I heard "this number isn't actually zero...[But] we can keep going until the odds that I'm lying are smaller than any non-zero number you choose" Honestly, this whole video was really great!
All that is being said in the video is that the limit of the probability of lying, p(x), as a function of the number of trials, x, goes to 0 in the limit as x goes to infinity. It was phrased ("we can bring this probability as close to zero as you like by doing sufficiently many trials") in the manner of the epsilon-delta definition of a limit, but the fact certainly wasn't proven rigorously using that epsilon-delta argument (thought not much extra is required to do that).
Thank you! There is com from me somewhere from one year ago saying it would be hard for me to find another angle than your great video above to cover this :) I've finally created my version on my channel, in French but you might appreciate the first protocol: a real-life ZKP for Sudoku. As the video progresses, the protocol is modified toward a dematerialized version, which might make the French more of a problem but the first protocol I guess the visuals are enough :)
Thank you very much for making this video.
Apart from making a video about zero knowledge proofs on mathematical propositions, can you also explain how it is used in roll-ups and other solutions?
if I make a follow up! gotta gauge interest :)
@@upandatom I'd love to see it! It's a really fascinating concept how you can take the result of a program that takes days for the prover to compute, but once they generate a succinct proof (snark), the verifier can be convinced of the result instantly without needing to run the program for days. (That snark proof can then trivially be made into a zero knowledge proof)
@@domotheus I think your *snark* suggests an entire new realm of epistemology. If I can persuade enough skeptical people of something can I regard that persuasion as proof? If so, hooray-no more reading hundreds of pages of quasi-comprehensible theory. If not, “WARNING WILL ROBINSON!”
ZKP is profoundly amazing and philosophically deep. At present it
seems like fairly technical finite math (AKA computational computer science) to me. When its application and understanding become part of social understanding, will humanity have advanced? Perhaps we are starting move this way by trusting in blockchain (which seems trustable to an increasing number of us). Should elections be safeguarded with blockchain technology? How can we persuade partisan players with a great deal to lose or gain to adopt a fair and far safer system that prevents almost every type of abuse. Perhaps if Vellayappa Ayyadurai Shiva, the brilliant inventor of email, were to devise such a system, people would try it. Too bad he’s vehemently opposed to so much that constitutes authority and political correctness. Accordingly, this man who has holds four degrees from the Massachusetts Institute of Technology (MIT), including a Ph.D. in biological engineering, and is a Fulbright grant recipient has been systematically marginalized and is now “known for” his pseudoscience, conspiracy theories and unfounded claims.
Yes, this is a very interesting subject. Just hearing these simple explanations makes me want to know more.
@@scottaseigel5715 I'm not sure if you understood the term SNARK - in this context, it refers to a Succinct Non-interactive ARgument of Knowledge: en.m.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof
Your videos are always so good. I'm learning a lot about how to teach clearly from you. Thanks!
This was fascinating, and yes I would love to see the follow up!
For the example, wouldn't it be more true to say that the two pieces are in some way distinct from each other? If they were different shapes, but the same color, your example would still work the same way. Just a thought :D
If he claimed that these hidden objects were visually different, that would be proof
Sounds it's kinda like this :
P_ is a measurable property of both X,Y where X[ P_ ] =/= Y[ P_ ]
Number of such properties is >=1
I know how to measure at least one of those properties, at least to the level that I will know with certainty whether the measured object cannot be X or cannot be Y.
ie.: X and Y differ in wavelength and I can tell if two wavelengths are the same - BUT I might not know how to measure the exact wavelength nor do I have to know the exact wavelength of X and Y. If you sneak in a G with a wavelength that also differs from Y I will keep thinking it's still X and Y.
We could successfully "play the game" with you sneaking in all kinds of other objects all the time, as long as you can predict what property am I using to discern X from Y and whether I actually know the property values of if I'm just able to tell the difference.
Also, the fact you can "play the game arbitrarily long" doesn't equate to a proof I think. Either she simplified it too much (which I suspect is the case and that would be fine) or its technically true but practically not as you cannot "play the game" indefinitely in real life. It may get astronomically unlikely as fast as it wants but PI isn't "roughly" a halfturn.
Great video! Not only i understood what zero-knowledgeproof is about, but it also made me curios for more. However, this let me wonder: what if your statement is that both candies are the same color? How would you be able to prove that?
Thanks, I was looking for this comment. Q: are they switched? A: I dunno? x 1000 ? :)
Normally, you could assume the claim is false, and when you fail to prove that you can assume the claim is true. But I don't see how you could apply that principle here.
Hard question, but here's my try.
Assuming that there are a finite number of colors, proving the two candies are the same color is equivalent to proving both of your candies are different from the other n colors. In the simplest case, there are only two colors at all -- let's say red and green. And for a moment let's disregard the zero knowledge aspect a little bit. Proving that both are the same color means proving both are red, or both are green. We can do this by having the subject prove each candy is _not_ the same color as: a control piece of candy which is green, or a control piece of candy which is red. If the subject can always tell when either of their candies are switched with a green piece, then both of their candies are red. If they can tell when switched with red, both their candies are green. If the subject can't tell consistently for both pieces, then they're lying.
Of course, you've gained extra information by doing this, if the subject is honest. Because now I know my subjects candies are both green, or both red. So this algorithm is not "zero knowledge."
But we can fix that. Rather than us choosing a red or green piece as our comparison piece, we can ask our subject to choose one of them. If we don't know which, then we know both pieces are green OR red, but we don't know _which_ color.
This works well for two colors. For more colors, we have to do more comparisons. For that reason, there may be a better algorithm than the one I just came up with.
But yeah that's my attempt at it.
@@MichaelFairhurst Nice! In this situation, (identical information) the person obtaining the info (candy) should be able to see that there are identical elements to the swap. So, knowing that they are the same, replace one with a stand-in piece of information that is different. (Or maybe even for both) that way you can prove that you know but keep the original information safe (I.E. not expose that the information is identical).
My solution to to the problem in the beginning: I make a picture of them, in photoshop I randomly pick a hue transformation, resulting in a photo were it is still clear there are two different colored candies, without the information about the real colors. The other person can watch me take a picture and edit it as long as the image is not seen.
EDIT: Easier method, the other person wears color changing glasses.
Jade, when I read the title I thought you were going to talk about asymmetric cryptography, which is also pretty neat - prove that you have something over an insecure channel without revealing the thing. But your topic was soooooo much bigger. Thanks, because now I have something new and fun to go find many books on ;-)
Similarly I thought the video was going to be about private key cryptography. Instead I learned something new which is much better!
Asymmetric cryptography is largely orthogonal to zero knowledge. In asymmetric (or symmetric) the goal is to keep secrets from an eavesdropper. In zero knowledge, the goal is to keep secrets from the recipient of your communications. In the case of the differently colored candies, an eavesdropper would learn that the proof is about candies, but wouldn't learn the candies' colors (same as the verifier), and the eavesdropper wouldn't even be convinced that they're differently colored.
Interestingly enough, ZK protocols can be "layered" behind transport cryptography, so that even the subject of the proof is hidden from an eavesdropper.
How could this not be the absolute BEST explanation of zero knowledge proofs? I watched a clip of Zooko explaining it and thought I understood it. He was good, mind, and I know he has put in immense work towards practically enginnering supporting infrastructure. But your presentation is phenominally good at explaining the concept. Thanks a million!
Love the video, but I have to say that I dislike cryptocurrencies to the point that I had to cringe when you switched from bitcoins to another topic with the words "another cool thing about zero knowledge proofs ...", implying that it was cool that zero knowledge proofs found an application in cryptocurrencies. Bitcoin & co. might be interesting from a technical point of view, but from a societal point of view, they are a neoliberal nightmare. I encourage anyone who is interested in a look at crypto from this perspective to go and watch "Line Goes Up" by Folding Ideas.
But, politics aside, this video was really interesting on a conceptual level, and also very well executed! :)
Jade should make a video about how cryptocurrencies are negative-sum games
After you watch that I recommend watching "This Machine Greens" by Swan Bitcoin.
Edit: If you want a direct response to "Line Goes Up" I recommend watching "The ACTUAL problem with NFTs - A Response" by To The Point.
@@ijiikieru Just watched 'this machine greens', if you think there's a convincing argument there, sorry but you're in a cult. By being an energy sink, bitcoin is a negative sum game that relies on greater fools buying into the system to keep it functional. It leaks value through it's energy use. That documentary attempts to make the argument that it's valuable because of it's energy use and this flies in the face of thermodynamics.
Tried watching Line Goes Up... Had to stop when the Bitcoin section ended. He is either intellectually dishonest or uninformed. Calls into serious question whatever else was coming after. Gell-Mann Amnesia effect and all that.
At 7:04 the letters "E" and "I" are swapped for the "Riemann hypothesis" as a zero-know-knowledge proof if someone is german ;-)
This was really interesting and I would like to see you do more videos on this kind of proof.
I like how you tied it into currency at the end because several things have bothered me about the notion of currency in and of itself. I remember adults having conversations about the wisdom of having taken US currency off of the gold standard. Since I was a really little kid and so the adults weren't going to include me in their conversation anyway, why what amounted to an exceptionally shiny rock would have any reason to be worth more or less than fancy paper or coinage with numbers, the name of the country, perhaps a Latin phrase or two on it, and some inexplicably odd artwork on it. I'm 42 now and this notion of currency has only seemed to become increasingly absurd to me. The only way that any sort of currency has value is if enough people agree to value it at a given level, which made me have to discard with the notion that anything really has value in and of itself.
What your discussion of blockchain currency made me realize is that the point of currency is to organize the trading of one thing for another, whether that thing is one's labor or some actual item. So currency has no value in and of itself other than to be a placeholder for other things that people like to trade amongst each other. So the value is in being able to keep track of those trades.
You're right. But if currency is already imaginary thing, we can as well stop at fiat currency, cryptocurrency that is basically fiat plus wasting enough electricity to power medium sized country and fluctuates in worth so much you never know if a piece of bread will cost 1 coin, or 1000 next day, is comically stupid idea...
"…which made me have to discard with the notion that anything really has value in and of itself."
"Value" is a judgement by a person. Nothing has objective value, because value is entirely subjective.
@@jursamaj I came to that conclusion as well but then I asked myself what the point of being a living being was at all and the only thing I could conclude was that, if there is any point to it at all, it is just to experience whatever ends up happening to us. It's a poor argument for meaning and it's not meant to be one, but when one asks the question of what they should do, I can only say that the answer is just to see what it's like to be you and to have that experience since that is the fundamental thing that all living beings have in common, whether they live long lives or die almost immediately after having come into being.
If the candy clouds are the same colour you can't see if the cups have been swapped or not...
Yes, please make a sequel to this video explaining how it was proven that all hypotheses with a proof also have a zero-knowledge proof.
Thank you for making this wonderful video :)
The fact this seems so obvious after your explanation is testament to your powerful abilities as a communicator.
One of the best explanations of zero knowledge proof I've ever seen. Kudos simplifying this complex topic.
5:56, Bitcoin doesn't do this, all it's transactions are public for anyone to see. Some cryptocurrencies that do actually do this are Monero and Zcash
More, please. I'd love to see an entire series on the evolution/uses of blockchain functionality, and how zero knowledge proofs apply.
Actual uses yes please, not stock-marketeering money manipulation games for hypercapitalist pursuits.
@@Nohbdy_Ahtall Yep, I’m more personally interested in its general use as a trusted audit trail.
blockchain is simply a data structure, known in programming since 90s - cryptocurrency is basically the first good use of it, just like Merkle trees are good for hasing very large files but not good for hashing generally
I love Brady over on Numberphile and enjoyed his video on zero-knowledge proofs, but this video actually demonstrated a practical, easily understood actual example of a zero knowledge proof and now I understand them much better! Cheers!
I would definitely love to see a follow up on how every mathematical theorem has a zero knowledge proof! This is absolutely fascinating
*reading* is it possible that this only applies to anything NP?
Reading more about the topic, I think the general idea here is:
- we need problems for which instances can efficiently be generated at random
- the task must be to proof the existence of something, such that a single witness can be seen as proof
- if the prover can somehow conjure up a single proof witness, all we need to do is to convince the verifier that whatever we have actually solves the problem without revealing the thing
This technique cannot be applied if the proposition in question is of type „for all x“. Therefore, the mathematical examples you gave might actually not work
The whole thing boils down to „I can do card tricks, and I won’t show you how they work, but you can see that they do work.“ Those techniques have been around for quite a while, only now we found a way to certify that you can’t tell how the magician is doing it just from watching them do it.
There are two categories now:
1. the magician has come up with some method to do his trick. In this case, you might be able to do it on your own. All that is guaranteed is that watching the magician do it won’t help you.
2. the volunteer on the stage works with the magician. The magician can do a fantastical magic trick for which there is no algorithmic explanation at all, but that is only because he solves an instance of the problem that is easy for him (but not for you).
For cryptography, the latter is the interesting one. We’re interested in finding out that you have knowledge about a data point that you *cannot* have unless you have really seen the data point, i.e., there’s no way to algorithmically find the data point.
That was exceptionally well delivered! You made it seem so obvious and simple,bhyt reading into the topic more, it's anything but. Well done.
I appreciate the explanation. Very interesting concepts. But I have an issue with the test provided. The claim being "color" was being identified. But the two could have been the same color, but some noticeable difference in shape. The ability to detect ANY difference was all that was being tested. Not ONLY a color difference.
But was even that being tested? What if a cup had been marked and what was tested was the ability to determine which CUP is which? The objects inside could be identical.
What was tested was the ability to detect one set of objects from the other.
Now looking through colored filters or using a colored light sources. Ask which is darker.
It was a simple real-world demonstration to show how it would work practically-the shape and kind of object is irrelevant. The color instead represent any secret. But rather than sharing the secret itself, you make propositions about it following different rules.
This can be used for example in cryptography, where a secret has the potential of being intercepted by an attacker. Say for example a password. Rather than sending that password to the server, you instead prove that you know the password by answering the propositions put forward by the server, until it is satisfied.
@@dealloc It's either a valid analogy or it isn't.
@@glenncurry3041 Her demonstration is a valid example, you're getting hung up on the particulars of the physical demonstration. If it helps, imagine getting rid of the cups and candy entirely. Instead one person puts two identical squares of paper in front of the other person. The underside of the paper has identifying information on it. The outcome is the same. The cup game is a metaphor for explaining the much more complicated electronic equivalent.
@@RageXBlade So I am "getting hung up" on the example failing to do what it claims?
And your suggestion is to then replace the entire example with a different example in order to prove the first example was OK?
I understand that an attempt at a metaphor is being used. But a metaphor has to be correct in and of itself to be used. Rather than defending a bad one, using a correct one would seem far more scientifically correct and beneficial.
You're right. A real proof would involve taking out a single (unseen) candy of a third colour, then showing that there are 3 different coloured candies in your hand. They don't know which 2 colours the originals were, so that secret is preserved while undeniably proving the claim that you had 2 different colours at the start.
I swear I have watched a hundred videos about zero knowledge proof and never understood what it ACTUALLY meant due to the lack of demonstration, UNTIL NOW! so thank you sooooo much.
Would enjoy the follow up. Interested to see more examples of how zero knowledge proofs can be used.
Brilliant! Thanks also for putting the adverts at the end. Love you channel!
Good timing! Just the other day I was trying to explain zero knowledge proofs to a friend and not doing a very good job. I shall refer her to this video. Thanks again!
2:50 Since he never checked the cups, there "could" be a marking on one of the cups, this lets you "guess" correctly, even tough you're lying (same color).
Or (in this specific case) she can hear how the cups are sliding on the table, to know if switched or not.
(but this isn't about this specific physical example. this is more theory about HOW the proof can be done, especially in math. (at least hearing is much harder in math ;P ))
I don't get that example. You have proven only, that you know they are different, but not that you actually know the colors. And the fact that they are different have you given away.
I heard an example that works better for me:
Two rooms are connected by a door with a lock. You have the key and want to prove that you have the key without showing it. To do this you go into one of the rooms without the other person knowing which one. Now he calls you to come out of a specific room. There is a 50% chance that you don't have to use the key but by repeating this, the chance of you not having the key goes down.
I also have never seen a cryptographic/mathematic example of a zero knowledge proof that I was able to understand, so I would like to see a follow up video.
You don't understand because the video shows an logical proof pretending to be zero knowledge. She proved that she knew that they were switch and that she has a method of knowing. Having rules to communicate the proposition automatically makes it a knowledge proof. Creating an entire language system just to say that you have a secret is the equivalent of these zero knowledge proofs. There is always a more abstract unit of data that is communicated.
I’d like to be able to prove to youtube that I’m old enough to watch a video without having reveal who I am.
just a couple of minutes in I was like "ahhh, that sounds a lot like a better explanation of blockchains as compared to the poor explanation I'd had earlier" haha thank you!
The term “secret” may cause some confusion regarding ZKPs. I (and probably anyone else) will certainly believe that you have secrets I don’t know without your needing to prove anything at all. You have to reveal part of the secret - that you have selected two different colors of candy in the example in the video - in order to apply the ZKP process for retaining to yourself the rest of the information. Yes, a video on the three-colorable map or the Sudoku examples of ZKPs would be interesting. Also, explaining the fact that for the application of ZKPs to the blockchain the proof needs to be non-interactive, which this video example and most other simple examples are not.
What if you have two of the same color and wanted to prove they are the same.
I also asked that myself , my solution would be:
The other creates the pairs with all the possible combinations with 2 different colors and mixes them to the two of same colours. Then if you’re still always able to find out the correct one, the other can be pretty sure the ones you have are the same, because otherwise you would only be correct in 50% of the cases.
It seems like your enthusiasm sparkles In the matters you discuss, which makes your work more fantastic...
But wait a second. You could say they are different colors but they could be the same colors and just one of them have more sugaryness. Yes I made up that word just now. Or one could have a bigger left most lump etc. All you have verified is that you can tell the difference between whatever is under the cups. Or what if you just marked the inside of one of the cups. You havent proven they are different colors. Just that you know some way to tell if it has been switched or not.
5:12 Yes, I think Zero Knowledge Proofs can be practically applied as the only way for members within secret socieities to communicate safely in public.
Doesn’t “completeness” sorta destroys the whole point about “proving”? It presumes that you’re telling the truth in order to prove you’re telling the truth. How about the good old fashion “I swear” method? 😂
I love your Computer Science Videos. I just got my Bachelors Degree in Comuper Science and do know about a lot of what you are talking about, but you are making it so etertaining, it is like learing this stuff for a second time but with more fun.
Love sis ♥
I find it incredibly interesting that every proof has a zero-knowledge proof. Excellent video, once again! :)
Yes, first I’ve heard that. Interesting.
Proof that using a zero knowledge proof
You are becoming one of my all-time favorite creators, Jade!
Here's my vote for a follow-up video, maybe even a second follow-up video about the existence of a zero-knowledge proof to any proven proposition, if possible, though I would think YT algorithm wouldn't be so kind to that video 🙂
Actually, not all mathematical proofs have corresponding zero-knowledge proofs. ZK proofs exist for NP statements, which are efficiently verifiable; graph coloring is NP-complete, thus the existence of a graph coloring ZKP implies ZKPs exist for all of NP. However, there are complexity classes beyond NP, and some of those definitely do not have ZKPs. For example, EXPSPACE, the class of decision problems the require exponential space to solve, contains problems that do not have any ZKPs; this follows from the fact that IP=PSPACE and that EXPSPACE is a strict superset of PSPACE.
All mathematical proofs have corresponding zero-knowledge proofs _of corresponding lengths._ If the length of the mathematical proof happens to be exponential relative to the length of the problem statement, then the corresponding ZK-proof will also take exponential space and time. That will place it outside of IP (which stands for Interactive _Polynomial_ ), but it will still be a proof.
In 1986, Goldreich, MiCali and Wigderson proved that all languages with interactive proofs in NP have zero-knowledge interactive proofs. In 1990, Ben-Or et al. extended it to all languages with interactive proofs.
Note that this only applies to statements which actually have interactive proofs. There are true propositions with no proof at all, not even an interactive proof, so they certainly don't have zero-knowledge interactive proofs.
I studied in Blockchain development and I could never explain it clearer. I love you and love your channel ❤
0:16 I could use my spells against my teachers to prove that I am right in my arguments and bargain for better grades 😎
Wait!!! It is Mathematical??
I am outta here 😂😉
Thank you for this video! I think that there is a basic problem with the example you gave of the candy cloud game: After the first iteration, the person looking under the cups has gained knowledge about the candy clouds under the cups. She can base all of her subsequent statements on that first iteration. If she didn't really know that the clouds were two different colors, but they were two different colors, she can now correctly state whether the cups were switched or not on every turn. She can now satisfy all the requirements of the proof even though she didn't know the secret from the start.
The point that Jade is making is that if you didn't know the secret, you would not be able to correctly determine if the data was changed or not because you do not see it changed in the first place and the data is still a secret. You don't learn about what the data is, only the resulting data from the change. Switching cup is simplistic but that is the point of the demonstration. So that is why the probability is there and a large consistent prover/verifification process reduce the probabilty of false data to the point of near absolute certainty. If you did not know the secret, you would not be able to accurately determine if the data was changed or not correctly to the agreed difficulty probabilty of near absolute certainity.
@@CSirce Thank you
With zero-knowledge proofs, one side has the full knowledge of whatever is in question. In this case, the person looking under the cups (Jade) picked the candy clouds from the jar and knows what color they are. The zero-knowledge aspect is with the person switching the cups, who never sees what the colors are, but can be convinced that the colors are different by Jade's consistently correct answers about whether the cups were switched or not.
Wonderful video, as always. If I remember rightly, another condition of ZKPs is that they only work for the verifier actively engaged. I.e. if you took a video of this whole procedure, there'd be no way for a third party to verify that it wasn't all staged, thus only the present verifier can be convinced. Oh, and if anyone wants more on the mathematics of the blockchain, I'd suggest 3Blue1Brown's video "But How Does Bitcoin Actually Work?". Anyone wanting a deep-dive into the ramifications of the technology should see "Line Goes Up" by Folding Ideas.
strongly agree w both 3B1B and LGU recommendations (though for 2 different reasons). also suggest a recent video by münecat (on her non-music channel) called "Web3.0: a libertarian dystopia".
@@dragonfly.effect Absolutely! I's thinking about recommending that one, too. It covers a lot of the same ground as Line Goes Up and is also pretty long, but it's got stuff that wasn't in there and is a good video in its own right.
Before i knew the idea of this, know I have the knowledge. It was like a light bulb being twisted while the light is on.
Thank you so much. I work as a developer and this little tid bit you've shared is likely to accelerate my career.
If the candy clouds were of sufficiently different shapes, or any other attributes, someone could "prove" a false secret.
I came here to say this
In your example, additional information would be required to verify the "secret." As for the candy clouds, the verifier can see the jar and if different shapes as well as different colors exist, they would ask for the additional information. I'm fairly certain that would fall under the completeness category.
I sometimes joke with my friends, I ask them 'Can you keep a secret ?'
They will say 'yes'
Then I say 'Good, so can I' and walk away.
I'm still not convinced. At least with the example. You could tell me you put two different colors under the cups. But in reality you could put two different ANYTHINGS under the cops, as long as you could tell the difference. So you say you put two colored candies under them, when in fact you put an orange and an apple under the cups. The "proof" still works, but its false.
Agreed. Neat concept but not really practical based on her explanation.
There could be even identical items under the cups, but the cups themselves are different.
You're not paying attention. Complete honesty by both parts is required, so you cannot put anything under the cups.
The proof is only demonstrating that she can distinguish the two items. In this thought experiment, the verifier already believes that the candies are under the cups but is skeptical whether they are distinguishable.
@@magilviamax8346 If complete honesty by both parties is required, then why would any proof be required?
QUERY re cup example @1:00 onwards.
If the colours are secret, and you put them in the cups then the cups are moved, you give complete control of the "secret" colours to the other party. If the other party is able to look at the colours,esp. if unknown to you, then what's the point in keeping them secret; viz-a-viz there is no need for this whole secrecy. If you do need to keep the colours secret then zero-proof as you explain it here can not be used in a cryptographic setting.
Yes! Follow up video please. This was really awesome btw. Thanks!
0:20 "without anyone telling what you are right about"
Are you sure this phrasing is correct? You have to tell the validator what you are right about. You just don't have to tell him the actual value of what is being testet.
If you are familiar with the prisoner hat logic puzzle there is I think some logical crossover with that. The solution is based on an independent response outcome or rather lack of one that enables an assured knowledge response. It is a great logic puzzle that I would think has far deeper use.
Technically, in your candy cloud example- you could have just put two candy clouds of the same color under 1 cup or (if, say, the doubter could rattle the cups to make sure both had a candy cloud) picked two candy clouds of different shapes.
That's why there is the "both sides are honest" requirement...
This by far the best video I have seen on Zero Knowledge proof. The best part is that you also brought in eves-dropping in this concept. Beautiful work! Thank you so much! :)
I just rewatched this. I think this is the most intereesting thing I have ever seen.
Excellent video Jade! And one small nitpicky thing: It's Riemann (not Reimann). Yes please to the follow up video!
My mind was blown when you said there can be a zero knowledge proof for any proposition. Like what!?!?! Definitely looking forward to a follow up video!
OMG please make the follow up video, this is fascinating!
This is one video, where I was basically lost and did not had enough background knowledge to understand.
But, please keep more such videos coming.
Edited:
I watched the video second time and with attention. Now, I could understand most of what you said. And its still fascinating and very abstract.
Yes please on the follow-up video. Just discovered this channel and already need more!
5:10 Zero-knowledge proofs were used to verify binding government elections in Takoma Park, MD in 2009 and 2011, so real-world applications date back at least that far.
For the first time, in a long time, the content is almost more interesting than Jade alone.
Please make more video's like this!! This subject is amazing.
I think this is your biggest hit Jade, thanks so much for this video.
This is the best explanation of Zero Knowledge Proofs I have come across so far. Thanks.
I'd like to spread an idea which often gets overlooked when talking about what's true:
"True" and "Proof" only exist in the idea world(a.k.a math), zero knowledge proofs can exist there only because you can take that process to infinity.
In reality everything is limited and has a probability attached to it, so saying "This is true because they proved it to me" can be very dangerous because what was proven may only work in a specific context or the "proof" 's probability may be not good enough for the listener who has stricter requirements.
It's a lot more honest to talk like "I believe this because I saw that".
Of course at some probability threshold everyone can agree so you get some things like "Law of Gravity" even though it might only work in just the part of the universe we see, or that tomorrow it can suddenly turn off.
1:48 Shouldn't that be a positive 31? The negative exponent inverts the ratio, making it super-likely.
yes you're right!
For the candy cloud problem I would get someone else who is a trustworthy source (a friend or something) and show them the candy clouds and have them verify that they are different colors
Please make a follow up video. You only talked about the surface, but it's one of the most interesting things I've ever heard. I want to hear more real life examples to get an understanding. And maybe you could show how to prove that you know a prove of an easy mathematical proposition without explaining the actual prove.
as you were explaining the simple cup swapping example i felt my brain expand
this is such an interesting concept, and i've always wondered about the 4 colour map theorem!
This is my first video i've seen by this channel and im instantly interested, awesome video! informative, simple, and explaining real world links, love this!!
Girl this was incredible, I NEED to know more about it!!
Yes, I'd also like a follow-up video on how arbitrary proofs can be converted to zero-knowledge proofs. Your videos are great!
Hey Jade! A wonderful video as always! Keep it up...
Yes yes follow up video please! Very well done!
I would like to offer two arguments against this presentation of Zero Knowledge Proof. Let me begin by saying that, perhaps, the example given is intended to make a complex system of proof understandable by converting it into a simple, tangible format (ie: the candy-cloud example). Fair enough; unfortunately this simplification may have been oversimplified.
#1: The proposition that you can correctly tell if the cups have been switched indicates that you can tell the difference between the candy-clouds ONLY based on color. This ignores any other possible factors such as shape, size, etc.
#2: The requirement, at the start, that both parties are honest. If this is axiomatic, then proof is not necessary. You've said that you know that the two items are different colors, therefore it is so. If you are honest, no system of proof is needed; if you are not, the requirement is not met.
Sorry for being pedantic.
After about 3 iterations, I would have forgotten which candy was under which cup...
if i recall right, zero knowledge proofs are also the backbone of public key authentication mechanisms
essentially you are trying to prove that you have the private key and therefore, that it is you who is talking to the server
so the server sends you something thats encrypted with your public key and you decrypt it and then encrypt it with the servers public key and send it back
and they can make that exchange as many times as they want, with any arbitrary verification messages, to establish each others identity to any arbitrary degree of certainty
and at no point does either side ever reveal their private key
Mind blown. I love how you asked the question and said to think about it. I got stuck on if either of us is telling the truth. But, you added a 3rd part previously not revealed. I love these types of puzzles. I have one for you that follows a similar logic path of missing information.
Trina and Zena were born within a few seconds of each other, same mother, same father, but they are not twins. Why not? If you don't know the answer, think about it.
You didn't know about Tina, the 3rd child born. They are not twins because they are 2 of a set of triplets.
Love your stuff Jade. Please keep making these and blowing my mind. Cheers!
The answer that came to my mind was they're both IVF babies, born to different surrogates.
I’m no mathematician or statistician so I hope you can clarify.
When stating probability using the : symbol does it not imply an odds rather than a fraction?
As in
1:2 != 1/2
Thanks
I do have the same impression.
Great video, as always! I'm curious about the posters you show in the background, where are they from?
displate.com
@@upandatom Thanks!
I'd just look under the cups when you weren't looking.