Zero Knowledge Proofs

Watch over 2,400 documentaries for free for 30 days AND get a free Nebula account by signing up at curiositystream.com/upandatom and using the code "upandatom". Once you sign up you'll get an email about Nebula. If you don't get one, contact the curiosity stream support team and they will set you up with a free Nebula account right away. The name of the documentary I mentioned is Blockchain Revolution.
Nebula: watchnebula.com/
Hi! I'm Jade. If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
Visit the Up and Atom store
store.nebula.app/collections/...
Subscribe to Up and Atom for physics, math and computer science videos
/ upandatom
Follow me @upndatom
Up and Atom on Twitter: upndatom?lang=en
Up and Atom on Instagram: / upndatom
For a one time donation, head over to my PayPal :) www.paypal.me/upandatomshows
A big thank you to my AMAZING PATRONS!
Thomas Schmid,
Michael Seydel, Cy 'kkm' K'Nelson
, Rick DeWitt, Thorsten Auth
, Purple Penguin
, AndrewA, bpatb
, Chris Flynn
, Michael Martin, Scott Ready,
Izzy Ca
, John H. Austin, Jr.
, Brian Wilkins, David Johnston
,
Thomas Krause
, Yana Chernobilsky,
Lynn Shackelford, Ave Eva Thornton,
Andrew Pann,
Anne Tan
, OnlineBookClub.org, Aria Bend, James Matheson, Markus Herrmann (trekkie22), Robert A Sandberg, Kevin Anderson, Tim Ludwig, Alexander Del Toro Barba, Corey Girard, Justin Smith, Emily, A. Duncan, Mark Littlehale, Lucas Alexander, Jan Gallo, Tony T Flores,
Jeffrey Smith
, Brian Kent
, Alex Hackman
, Thomas V Lohmeier
, Joel Becane,
eris esoteric
, Michael Hunter
, Paul Barclay, 12tone,
Zhong Cheng Wang,
Sergey Ten, Damien Holloway,
Mikely Whiplash
, John Lakeman
, Jana Christine Saout
, Jeff Schwarz
, George Fletcher,
Louis Mashado,
Michael Dean
, Chris Amaris,
Matt G
, KhAnubis,
Broos Nemanic
, Dag-Erling Smørgrav
, John Shioli
, Joe Court
, Todd Loreman
, Susan Jones, Nico Papanicolaou, keine, Markus Lindström, CatInSpace, Jeffrey Melvin, Midnight Skeptic, Kyle Higgins, aeidolos, Mike Jepson, Dexter Scott, Potch, Robert Amling, Thomas P Taft, Indrajeet Sagar, Johannes Lindmark, Gil Chesterton, Alipasha Sadri, Pablo de Caffe, Alexander230, Taylor Hornby, Eric Van Oeveren, Mark Fisher, Phizz, Rudy Nyhoff, Colin Byrne, Nick H, Jesper de Jong, Loren Hart, Ari Prasetyo, Sofia Fredriksson, Phat Hoang, Spuddy, Sascha Bohemia, tesseract, Stephen Britt, Will Miller, Dagmawi Elehu, Hansjuerg Widmer, John Sigwald, Carlos Gonzalez, Jonathan Ansell, Thomas Kägi, James Palermo, Gary Leo Welz, Chris Teubert, Fran, Joe, Robert J Frey, The Doom Merchant, Wolfgang Ripken, Jeremy Bowkett, Vincent Karpinski, Nicolas Frias, Louis M, kadhonn, Moose Thompson, Austin Rose, Andrew, S, Sam Ross, Garrett Chomka, Bobby Butler, Rebecca Lashua, Pat Gunn, Luc Ritchie, Elze Kool, RobF, Frédéric Junod, Vincent Seguin, Shawn, Israel Shirk, Jesse Clark, Steven Wheeler, Philip Freeman, Jareth Arnold, Simon Barker, Dennis Haupt, Lou, amcnea, Simon Dargaville, and Magesh.
Creator - Jade Tan-Holmes
Script - Sheila Miller
Animations and Editing - Daniel Kouts danielkouts.com/

[@upandatom]

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!

[@karenjeandiez6331]

are u in instagram?

[@PranavGarg_]

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.

[@topdog5252]

Zero knowledge proofs r cool. Also ZKSnark or SKStark make me sound smart!

[@upandatom]

@@karenjeandiez6331 yeah @upndatom :)

[@cybmor1856]

@@PranavGarg_ agreed... this video has got me very curious as to how that's possible

[@johnchessant3012]

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.

[@kimberleemodel7182]

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.

[@seraphina985]

@@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.

[@jamesphillips2285]

@@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]

@@kimberleemodel7182 Are not all zero knowledge proofs multi-party?

[@JivanPal]

@@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.

[@abouttime5630]

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 :)

[@profskett]

Yarsss, give us some of that zero-proof knowledge!!

[@CyberMew]

Zero-knowledge proof?

[@MagicianOfFlame]

Has this been done? I am excited to know about it

[@yiravarga]

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.

[@proloycodes]

+1

[@dognip]

agree

[@Ikantspell4]

Gives a node to graphs....that was punny in theory

[@dutubsucks]

Yes please!!!

[@feefifofum6383]

Oh yeah!

[@martinellis38]

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

[@scottaseigel5715]

I agree. Your video is the best ZKP presentation I’ve seen to date.

[@kmatlockii]

Agreed. That was a great demonstration at the beginning.

[@Joachim1010]

I second that.

[@goldenalt3166]

Especially since "proof" doesn't seem to have the same meaning in those two phrases.

[@osmium6832]

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.

[@pasijutaulietuviuesas9174]

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!

[@upandatom]

;)

[@vigilantcosmicpenguin8721]

This method works incredibly well for videos like this. It's both sciencey and understandable.

[@AnirudhAjith]

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!

[@lux_incola4224]

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

[@scottaseigel5715]

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]

@@scottaseigel5715 did you just prove that a proof exist without actually giving us the proof ?

[@scottaseigel5715]

@@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.

[@chrisvienna11]

I agree. In particular proving that candies are of same color is impossible - at least not without giving away the secret.

[@mladenstific2459]

Jade, you are awesome! Such a simple, powerful and enabling explanation for this important concept!

[@macalmy6750]

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.

[@Zorgdub]

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.

[@pedrosantana1700]

This reminds me of encryption algorithms. Great video, as always! Would love to see the follow-up, as well.

[@nathanaelhahn4795]

Your videos are always so good. I'm learning a lot about how to teach clearly from you. Thanks!

[@mastibaji]

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!

[@words_infinite]

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.

[@agargamer6759]

This was fascinating, and yes I would love to see the follow up!

[@stevenwatchorn9816]

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.

[@JivanPal]

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...?"

[@generalfishcake]

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.

[@aaattteeennn]

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.

[@DouwedeJong]

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]

if I make a follow up! gotta gauge interest :)

[@domotheus]

@@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)

[@scottaseigel5715]

@@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.

[@shatterthemirror8563]

Yes, this is a very interesting subject. Just hearing these simple explanations makes me want to know more.

[@Agent-ic1pe]

@@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

[@gernblenstein1541]

Brilliant! Thanks also for putting the adverts at the end. Love you channel!

[@AaronJarecki]

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.

[@Necrotoxin44]

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!

[@JivanPal]

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).

[@cyclical2003]

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.

[@troyrose20078]

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.

[@JivanPal]

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.

[@lemonbread378]

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!!

[@peterbonnema8913]

Please make more video's like this!! This subject is amazing.

[@spencereckler]

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.

[@wernerviehhauser94]

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)

[@vigilantcosmicpenguin8721]

Ah, answering the age-old mathematical conundrum of, "Where's Waldo?"

[@zsi]

Fantastic :) thank you very much, looking forward to the graph theory video🤞

[@jemuelbjeroham1228]

Great Video, as always from you ! Thank you creating such.. Keep it up !!

[@alanmckinnon6791]

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 ;-)

[@maya20484]

Similarly I thought the video was going to be about private key cryptography. Instead I learned something new which is much better!

[@kimberleemodel7182]

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.

[@Crystalmonkey124]

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

[@allantamm2185]

If he claimed that these hidden objects were visually different, that would be proof

[@Eldorado1239]

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.

[@saiganeshmanda4904]

Hey Jade! A wonderful video as always! Keep it up...

[@bobdinitto]

Fascinating concept. Thanks for your concise explanation. I'm subscribing to your channel and looking forward to learning more!

[@rajibalam9748]

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 :)

[@johnopalko5223]

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!

[@earthling_parth]

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.

[@rocaivan]

Thanks for all your fantastic work. Would be great to have a follow up video.

[@whoever6458]

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.

[@KuK137]

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...

[@jursamaj]

"…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.

[@whoever6458]

@@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.

[@gabrielionescu11]

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?

[@mrwensveen]

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.

[@MichaelFairhurst]

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.

[@RageXBlade]

@@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).

[@WatchingTokyo]

Yes please for the follow up video! Keep it up with the good work!

[@Franchifis]

OMG please make the follow up video, this is fascinating!

[@MaxArgent775]

Would enjoy the follow up. Interested to see more examples of how zero knowledge proofs can be used.

[@sylvainbougerel6272]

One of the best explanations of zero knowledge proof I've ever seen. Kudos simplifying this complex topic.

[@humptydumpty505]

Yes! Follow up video please. This was really awesome btw. Thanks!

[@christophersmith4850]

Always excited for your content!

[@rentedmule569]

More, please. I'd love to see an entire series on the evolution/uses of blockchain functionality, and how zero knowledge proofs apply.

[@Nohbdy_Ahtall]

Actual uses yes please, not stock-marketeering money manipulation games for hypercapitalist pursuits.

[@rentedmule569]

@@Nohbdy_Ahtall Yep, I’m more personally interested in its general use as a trusted audit trail.

[@LiborTinka]

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

[@seper159]

What if you have two of the same color and wanted to prove they are the same.

[@nikiweber4166]

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.

[@crushporter]

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 ♥

[@MrGreeneyes77]

Yes yes follow up video please! Very well done!

[@dscrive]

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!

[@Der1Metzler]

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! :)

[@loganmiat]

Jade should make a video about how cryptocurrencies are negative-sum games

[@ijiikieru]

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.

[@loganmiat]

@@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.

[@pupfriend]

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.

[@Vulioll]

Girl this was incredible, I NEED to know more about it!!

[@abhijitbarman4401]

You and your physics both are awesome! I love the way how you explain everything :)

[@VitaminGK]

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 😂😉

[@glenncurry3041]

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.

[@dealloc]

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]

@@dealloc It's either a valid analogy or it isn't.

[@RageXBlade]

@@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.

[@glenncurry3041]

@@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.

[@movelea]

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.

[@scottmarshall6766]

Fascinating subject. Yes on the follow up, and Thanks!

[@Hossak]

Wow this was a fantastic explanation! Thank you so much!

[@markuspfeifer8473]

I would definitely love to see a follow up on how every mathematical theorem has a zero knowledge proof! This is absolutely fascinating

[@markuspfeifer8473]

*reading* is it possible that this only applies to anything NP?

[@markuspfeifer8473]

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

[@markuspfeifer8473]

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.

[@masi416]

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.

[@nivekakninblarg8076]

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.

[@CharlieDraper]

The fact this seems so obvious after your explanation is testament to your powerful abilities as a communicator.

[@nawarelsabaa]

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 🙂

[@PenandPaperScience]

I find it incredibly interesting that every proof has a zero-knowledge proof. Excellent video, once again! :)

[@kevinmcfarlane2752]

Yes, first I’ve heard that. Interesting.

[@ZucchiZ]

Proof that using a zero knowledge proof

[@hughcaldwell1034]

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.

[@dragonfly.effect]

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".

[@hughcaldwell1034]

@@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.

[@leo1bueno1]

Excelent video Jade, you always make things easy to understand

[@sauceboss2367]

Love your videos. Please keep up the good work!

[@benkreuter1902]

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.

[@user-qm4ev6jb7d]

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.

[@EebstertheGreat]

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.

[@punkdigerati]

If the candy clouds were of sufficiently different shapes, or any other attributes, someone could "prove" a false secret.

[@felix158]

I came here to say this

[@equesdeventusoccasus]

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.

[@rocknrolladube]

Really good video/channel! Thanks.

[@ngraner421]

I just rewatched this. I think this is the most intereesting thing I have ever seen.

[@TheGeekPub]

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.

[@robclaggy8620]

Agreed. Neat concept but not really practical based on her explanation.

[@Kris_M]

There could be even identical items under the cups, but the cups themselves are different.

[@magilviamax8346]

You're not paying attention. Complete honesty by both parts is required, so you cannot put anything under the cups.

[@tavern.keeper]

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.

[@Kris_M]

​@@magilviamax8346 If complete honesty by both parties is required, then why would any proof be required?

[@rahulchaudhary5257]

Loved the way you demonstrated. And you have a lovely voice!! Keep going!

[@sanjarcode]

Thanks a lot for making this, Jade.

[@SachinChauhan-ch6el]

Yes for the follow-up video!

[@QRSTUVWXYZ123ify]

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!

[@stoicc6510]

Yes please on the follow-up video. Just discovered this channel and already need more!

[@salvatoreceravolo1414]

Up and Ataom - great video on ZKPs. Also yes, please do a follow-up on ZKPs and the riemann hypothesis. Thanks.

[@nikhiljadhao9572]

Amazing video yet again, complex matter explained simply 🙌🏻🙌🏻

[@grandrapids57]

I've really enjoyed watching this channel grow- and it deserves it.

[@vladimir10]

Hi. I love your video and do want the video with coloring maps regarding Reinmann hypothesis!

[@bakerkawesa]

I needed to see this. Thank you.

[@survivordave]

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!

[@ranganathannandakumar4463]

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! :)

[@al-asadi]

Great video, I love the simple explanation!

[@snowballeffect7812]

Even though I've seen the graph coloring example, I'd love to see your take on it!

[@qzbnyv]

That was a great, easy-to-understand video about a topic that can be very easy for experienced people to slip into jargon when talking about. 👏 The graph follow-up video would be welcome :)

[@akshatgour2505]

It seems like your enthusiasm sparkles In the matters you discuss, which makes your work more fantastic...

[@johnroberts7529]

What a beautiful piece of logic. Thanks very much for this video. 🤗

[@epederson92]

Just subscribed! I'm binging your videos, they and you are brilliant. This video convinced me. I've been trying to find a realistic analogy on how zero-knowledge proofs work, and this is just so concise. I don't care if you found it somewhere else or came up with it yourself, either way you communicated it to me, and I'll always be grateful!

[@upandatom]

Welcome to the channel! :)

[@cisienx9764]

I love ur videos. The topics u pic are so new and interesting. U are one of my favourite educators. As a science educator I need ur guidance in a paper that I wrote. I have written a paper on defination of living thing and I don't know where to share it. can u take a look at it. And yes please make video on zero knowledge proof of riemann hypothesis❤.

[@TheZeedler]

You're awesome, Jade! Keep the great content coming!!!

[@kennys1881]

do further on this topic please!! more applications :)

[@Roter_Wolf]

Yes, please make the follow up Video!

[@Debraj1978]

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.

[@ArpanD]

Great! This is wonderful am inspired enough to learn more

[@jonahbranch5625]

This was really good! Thank you

[@northlangri]

Great video, as always! I'm curious about the posters you show in the background, where are they from?

[@upandatom]

displate.com

[@northlangri]

@@upandatom Thanks!

[@friedfish69]

You are really good at this. Thank you.

[@lvmbk3755]

Extremely interesting. I want to know lots more of it as it sounds really cracking a lot of fields

[@anasshaikhany9733]

I think this is your biggest hit Jade, thanks so much for this video.

[@TheHernanNoguera]

Yes, follow up episode!

[@bryanredd4654]

Great video! Thank you so much!