Zero Knowledge Proof (with Avi Wigderson) - Numberphile
Вставка
- Опубліковано 15 чер 2024
- Featuring Avi Wigderson from the Institute for Advanced Study, Princeton.
More info and links below ↓↓↓
Avi's homepage: www.math.ias.edu/avi/home
And his free online book: www.math.ias.edu/avi/book
Fermat's Last Theorem: • Fermat's Last Theorem ...
Four Colour Map Theorem: • The Four Color Map The...
Gödel's Incompleteness Theorem: • Gödel's Incompleteness...
P v NP: • P vs NP on TV - Comput...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Video by Brady Haran
and Pete McPartlan
Support us on Patreon: / numberphile
Brady's videos subreddit: / bradyharan
A run-down of Brady's channels: www.bradyharan.com
Sign up for (occasional) emails: eepurl.com/YdjL9
Fermat's Last Theorem: ua-cam.com/video/qiNcEguuFSA/v-deo.html
Four Colour Map Theorem: ua-cam.com/video/NgbK43jB4rQ/v-deo.html
Gödel's Incompleteness Theorem: ua-cam.com/video/O4ndIDcDSGc/v-deo.html
P v NP: ua-cam.com/video/dJUEkjxylBw/v-deo.html
At 16:50 I'm pretty sure you were supposed to close all the envelopes belonging to the same column, not all reds
His claim that every mathematical statement can be converted to a graph that is 3-colorable iff the statement is true is wrong. For example, given some formula in first-order logic (i.e. something like "for all x there exists y such that x does not equal y"), the statement "the formula is always true" cannot possibly always be converted to a graph. This is because the question of whether an arbitrary formula is always true is known to be undecideable - there is no algorithm which can determine the answer. If his claim were correct, we would have an algorithm: simply convert it to a graph and then check whether the graph is 3-colorable.
Ah, I see what you are doing. Just throw enough amazing content at us and we'll get distracted and go away. Well we aren't fooled so easily! We want to see the conversion of a mathematical statement (or two) into a 3-color map! :D
@@rosekunkel4317 So you're claiming that checking whether an arbitrary graph is 3-colorable _is_ decidable? Why is this so? I don't think the resulting graphs need to be finite.
Why do I get the feeling that he disproved his own statement with the example of the three countries in a triangle rounded by a 4th one? That is not possible to be three-coloring, but still a valid configuration. Or what am I not getting?
/*edit*/ I made some drawings for myself and I can indeed color anything with in most cases 3 colors, but there are exceptions where I have to use 4. So if that is what is meant I find the name 'three-coloring' very confusing to use since it can be more. Maybe I'm just to logical as a computer-engineer.
Finished watching and I still have zero knowledge
Success
I was pretty sure the very first part of the conversation was him displaying the very example of the whole video lol
But you have to prove that
I scrolled down just to look for this comment, was not disappointed.
But can you prove it? :)
This video feels like a zero-knowledge proof of zero-knowledge proofs.
would be nice to see an example of translating of statement and proof to a map with coloring
I think the keywords to look for are SAT to 3-colorability. The steps in-between are turning a graph into a map, and turning a proof into a logic expression in the appropriate form.
Thanks kibrika
I typed “SAT A to colouring” into google images and was presented with humpty dumpty outlines 😂
@@kibrika thanks
That sounds like a video for numberphile2... Oh wait
Even for Numberphile, this video is just absolutely insane.
It's Numberphile2: double the difficulty.
@@rogerr4220 this video belongs on Numberphile²
@@rogerr4220 The basic concept isn't difficult to get. In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd do that in poker is beyond me, but the effect is the same - they believe you, despite not actually knowing what you've got.
This has to be the worst most unfulfilling Numberphile video I've ever seen. It's 33 minutes of my life I'll never get back again.
@@ArawnOfAnnwn That isn't a valid analogy because poker is a game where the objective is to persuade, not prove.
Somehow this 30 minute video gave me better understanding about zero-knowledge proofs than 2 hour-long lectures on the subject I had a few years ago.
I agree with others, we need a followup video with a practical example. This is interesting, but too abstract.
Bump.
monero the crypro is an interesting application
You have two pens of different colours. You want to prove to your friend who is colour blind the pens are different colours without revealing the colours. You say hold one in each hand, put them behind your back, either switch or don’t. If I guess if you switched or not right once the chance I was telling the truth about the difference in the pens is 50%. If we do this twice, 75% and so on until you’re sure enough the pens are different.
The key here is I’ve proven commenting about those pens to you without revealing anything about them. This is very valuable in cryptography
@@test-sc2iy thats a really helpful explanation! Thanks
What you need is two semesters of Computational Complexity.
please do a follow up on how to convert logical statements into a 3 colourable map
Please
+
You'd first need several college-level courses on set theory and formal logic to understand it first.
@@ObjectsInMotion Ah, too advanced then for Numberphile's UA-cam audience? I tend to think not. Just list the educational dependencies up front. No need to cover them in their entirety in the video.
From messing around on paper and reading a bit:
You start with a palette of F, T, and B.
This palette is just a triangle of nodes.
Whatever F is colored as means false.
Whatever T is colored as means true.
B is an auxiliary node.
You enforce the law of noncontradiction by connecting to B.
You encode a premise by connecting it to both B and F. This forces it to be true.
You encode a negation ~X by connecting it to both B and X.
You encode "X or Y" with another triangle.
One of the nodes of the triangle is T. Another node is connected to X. Another node is connected to Y.
The nodes that aren't T must be either BF or FB.
X - B - F - Y or X - F - B - Y
If X is F it forces the connected node to be B.
F - B - F - Y
And this forces Y to be T.
F - B - F - T
This works symmetrically.
You can construct any statement in propositional calculus from or and negation.
This means you can encode any Boolean satisfiability problem.
I'm not sure where to go from there.
the guy proving the existence of zero knowledge proofs was like: lemme prove that i have a proof that you can prove that you have a proof you don't want to tell
Great, so what's the proof?
-Won't tell you, but please take a look at this map of the statement...
I am at the stage of dealing with proofs in my maths study. Some are like trying to wrap your head around a pole while singing opera and messing with a rubiks cube.
Tonio Kettner I don't believe you. Prove it. But then you wouldn't believe that I don't believe you, wouldn't you?
@@ZandarKoad thanks for explainig me my own joke
@@toniokettner4821 Hey, a joke is always funnier the 2nd time you hear it!
It would be extremely helpful to see how to convert even a trivial statement into a map, as well as how to convert a 3-coloring of that map into a proof of that statement. Or at least a link to some paper where that process is explained, searching online returns no clear explanation.
Like he said, it’s using only formal proofs with symbols only, and a map would be huge for even a simple statement, so you would not really be able to translate it by hand or be able to comprehended if made by a computer. However, computers can communicate with each other in this language.
If I'm not mistaken, it takes a lot of definitions and tools, for example it probably goes through SAT and then through 3SAT to go to graph (map) colouring
@@TheKikou18 yes. Basically, no matter what branch of mathematics your statement is in, if first needs to be converted to pure logic. Even concepts as elementary as counting numbers and arithmetic are notoriously laborious to translate in this way (as evidenced e.g. by the lengths Whitehead and Russell had to go to just to show 1+1=2). I can scarcely imagine how hard it would be to encode concepts like arbitrary triangles in Euclidean geometry in this language.
@@varunachar87 I mean he said in the video that it can be explained even to a high school class, so I think that it would be an appropriate topic for Numberphile - there must be some explanation in between "its true" and "here's how to do it all out by hand."
@@elireville7206 I think this _is_ the high school-level explanation.
Congratulations to Avi for winning the Abel Prize!
I came to this video after I watch 2021 Abel Prize ceremony.
Proof of the four-color map theorem can be zero-knowledge verified using a three-color map.
I need a proof of that!
Interesting! Do you have a source for the proof?
So I could use zero-knowledge verification to prove that the three-color mapping of the four-color map theorem is a valid, but my trust in the zero-knowledge verification process is contingent upon my trust that the four-color map theorem is valid. Therefore the zero-knowledge verification is either redundant, because I already trust in the theorem it verifies, or ineffective, because I do not trust in one of the theorems it is based upon.
@@sk8rdman You are either joking or have missed the entire point of zero knowledge proofs.
@@Faladrin I don't know what you mean. Yes, this was sort of tongue in cheek, but I don't see what it is about zero knowledge proofs that you think I've missed.
I have been staring at this video for 30 minutes, and I have an urge to not erase anything for some reason.
I Once accidentally Proved The Collatz Conjecture in my dream. Now I know why I don't know anything about it.
I don't think I've ever understood any concept less in my life, but I still really enjoyed listening to Avi, and it's always interesting to see these complex mathematical ideas, even if they make my head hurt.
"I can prove X" -> "I know what keys open that door"
Whether X is true or false-> Whether the door opens or not
The mapping of the proof -> The key
Any statement can be a key, Only true statements/proofs open the door, however Party B does not know the internal mechanisms nor the keyshape. Party A has knowledge of the proof, can prove they have this knowledge by correctly identifying keys that open the door. They know whether the proof/statement they made is true and can be said to know the internal mechanisms.
Three parts make it zero knowledge. Completeness (Party B will be convinced that Party A has proof, the probability of Party A picking correctly approaches 100% ), Soundness (Party A cannot cheat if they do not have the proof/The probably of Party A picking correctly gets closer to 0% if the statement is false), and Zero-knowledge.
What makes it zero-knowledge is that Party B cannot look at the key. Party A looks at the key, Party B checks whether Party A picked correctly.
This process is repeated, since it is 50/50 for the first time and it gets progressively more unlikely that Party A is guessing as Party A correctly identifies valid keys.
The mapping is more like: The lock is the proof, the keys are the various different mappings, only true proofs have keys that open it. Both Party A and Party B can know how keys are made, but not necessarily how the lock functions. Since the method of key-making is known, you can't make false keys and there is no guessing.
In less precise language, you're basically proving to someone that the proof (of some problem or the other) you claim to have is legit, without actually revealing the proof itself. To use a poker analogy (this is really imprecise mind), it'd sorta be like convincing everyone at the table that your hand is the winner, without actually showing your cards. How you'd go about doing that in poker is beyond me, but the effect is the same - they have to believe you, despite not actually knowing what you've got.
@@ArawnOfAnnwn "How you'd go about doing that in poker is beyond me," why would you pick an example of which you don't know how to prove it? the whole point is knowing a way if how to do that...
@@sofia.eris.bauhaus "I don't think I've ever understood any concept less" - I explained the concept. You can feel free to explain the mechanism if you feel up to it.
It's like proving that you know the password to a computer by hiding the keyboard from view and typing in the password. Anyone can see that you unlocked the computer, so you must know the password, but that doesn't help anyone else figure out what the password is. The only new information they have is that they know you've proven you know the password.
-You know nothing.
-Correct.
However, now you know that you know nothing, therefore the statement is false and the fabric of reality is torn apart due to the paradox.
18:20 "Any formal mathematical statement can be converted into a map. And, I should stress, this conversion is efficient. There is a SIMPLE ALGORITHM KNOWN TO ALL..."
18:55 "Very simple, efficient, known to everybody"
Just had to laugh at these.
Known to all genius-level math wizkid
Known to everyone, minus everyone in the comments.
Yup, doesn't seem to be so easy as it sounds. If it were, we could check if Riemann's hypothesis is true (even if we can't build the formal proof).
@@AtanasNenov No? You'd still need to find a coloring of the map after converting the riemann hypothesis to a 3-coloring problem. But 3-coloring is hard, so you can't do it effectively.
@@AtanasNenov No. What we could do is generate the map only for the Riemann's hypothesis, which would be VERY HUGE. With that uncolored map, we learned nothing. Then, to prove the hypothesis is true, we'd have to color it with three colours. And doing *that*, specifically, is computationally unfeasible. Even though we have a simple algorithm that would eventually do it, if possible, the process would take more time than the age of the universe.
Plot twist, I didn't know what an envelope is so you teach me something
To summarize:
1) you can show a map can be 3 colouring without revealing information about the colouring
2) you can transform any statement into a map
3) if that statement is true, you can do a 3-colouring on that resulting map
C) you can do zero knowledge proofs for any statement
I am hoping that (3) is "If the statement is provable then you can do a 3-colouring on that resulting map", since otherwise this seems to conflict with Gõdel incompleteness.
@@anthonyberent4611 I'm not sure how Godel's factors into this at all? Eric's comment is perfectly correct.
To be even clearer: 2) you can transform any statement into a map and any proof of the statement into a coloring of the same map.
@@anthonyberent4611 Only NP statement's can be turned into maps, the unprovable statements guaranteed by the incompleteness theorem all lie outside that set.
There are short statements whose shortest proofs are arbitrarily long (in any axiomatic system able to interpret basic arithmetic). To get a map of fixed finite size, you need a fixed finite bound on the length of proof that you'll accept.
As for NP: "Statement X has a proof of length
@@RobinDSaunders So, are you saying that to create the map for a statement you need not just the statement, but also how large a proof you will accept for the statement? In that case, presumably, if the map you create is not three colourable, it doesn't tell you that there is no proof, simply that there is no proof shorter than your chosen N.
Knowing a property about a collection without knowing anything about the individual elements reminds me of quantum entanglement. I imagine there are interesting overlaps between NP completeness and quantum information theory.
Long story short: it's not a proof. It's evidence that a person *probably* knows a proof. NP-complete problems have a forward direction which is easy, and a reverse direction which is very difficult. The zero-knowledge "proof" is showing that you can do the reverse operation as many times as you like. Statistically you could be guessing the answer by chance but you repeatedly do this to increase confidence that you know how to do the reverse procedure, and therefore have a proof.
You can reduce the margin of uncertainty as much as you like. If you did an infinite number of checks, the probability of pure chance not being detected drops infinitely low, thus zero.
@@psicommander Not a finite proof, if you want to get technical.
@@wizard7314 I'm not sure. Isn't it a bit like Nyquist-Shannon, in which a finite number of discrete samples can amount to a continuous truth "within a frequency range" - ie. there has to be a number (and/or sequence) of tests that can in fact guarantee a proof, based on how many "countries" there are to color (the desired maximum frequency) ?
EDIT: I'm talking about a concrete threshold between "exceedingly unlikely to be wrong" and "proven" basically?
I still don't get how it was proven that all NP-complete problems have zero knowledge proofs.
Yes this is statistical in nature. You can never be 100% sure he isn't cheating. even if he threw random colors on the map there is a 2/3 chance every time that the 2 countries you pick are different colors. So after K iterations the chance he was cheating using a totally random coloring each time your "risk" would be of the order (2/3)^K which is always greater than 0.
This guy just won the Turing award!!! 🎉🎉🎉
18:20 I'd love to see an example of the smallest map that proves or disproves something, and a description of the theorem it proves. Great video.
Yes, this. A trivial or basic example would be great.
I'd love to know what "1 + 1 = 2" and "1 + 1 = 3" looks like.
@@Galakyllz Even those would probably be pretty big projects, just in formal logic alone, not to mention translating it into a map? idk
Unfortunately in general, these maps will be absolutely huge, even for the most simple proofs because the conversion consists of several steps (proof → formal proof → proof-checking turing machine → boolean expression in CNF → graph → planar graph). Every one of them will most likely turn its input into an even bigger output.
@@waldtrautwald8499 Are there pure logic statements that would produce graphs/maps that are small enough to understand?
Something like 1≠0? Or 0∈ {0,1,2}?
@@iveharzing You want a (somewhat short) boolean formula that is satisfiable iff your statement is true. This seems doable for your examples, depending on how you actually encode them.
The size of the corresponding graph is then linear in the length of the boolean formula (in CNF). So the graphs shouldn't be too large. The key step is the reduction from SAT to 3-COLOR. There are some great visualizations online.
This is way too awsome to be put on the second channel. Now I want to know, how a statement (even a very simple one) can be translated into a 3-coloring-map problem. Or is that also a zero knowledge thing?
Yeah I really wish he gave an example, no matter how simple.
A simplest mathematical statement will still correspond to a map of size 1,000 or more 🤣
I'm waiting for the followup. Even a simple description, name, or a link would suffice.
Should this video have been uploaded to the main channel?
What’s the difference? Why is there a “main” channel and a “sub” channel?
@@codycast Numberphile2, since the secondary channel.
@@codycast This channel is for the longer and more in depth bits that the main channel cuts for the sake of being more accessible.
@@biometrix_ yeah but what’s the point? Why not Numberphile 3, and 4, and 5, and...
''Fermat's Last Theorem follows as a corollary" is the perfect answer to "[...]a truly marvelous proof of this, which this margin is too narrow to contain." Fermat would be proud
I love this, but I understand why its not on the main channel. Its not a bite-sized digestible chunk, but I think this sort of thing is fascinating and maybe its worth learning about seriously if I think so.
Something he rather glosses over is just how quickly these maps grow with the complexity of the problem. Even an apparently “simple” proof, say that there are infinitely many primes, balloons to a very large number of strictly formal statements, and hence a very large map.
Who cares. Show us anyway.
Yes. You have to start with the absolute basics. You even have to construct natural numbers from scratch (see Peano arithmetic). I think he kind of misrepresented the complexity by saying converting statements to maps is a "simple" translation
This video makes sense for how zkps work in practice. Assuming large maps and then sampling that maps borders to get 99.99999999% confidence.
this is probably the best vid on zkps out there
This was a hard video to concretize but Avi just won the Abel prize partially for such work so I guess it makes sense that it's hard to bring down from the abstract :)
Someone who truly understands the material can break it down and reverse the process by which they came to understand it
Honestly I wish this video h ad been on the main channel. This is one of the most profound numberphile videos I've seen; so much so that I've just spent half an hour trying to remember where I saw it to rewatch it.
This was absolutely fascinating, thank you so much
This might be the greatest sleight of hand in mathematics. Brilliant.
Avi won the Abel Prize this week, and May sees the 50th anniversary of Stephen Cook's landmark 1971 paper which demonstrated NP-completeness.
I'm halfway through the video and already completely amazed! This is amazing!
The real question is what is the Zero Knowledge Proof of the Zero Knowledge Proof proof.
🤔😳🤯
First thing I thought when he said they proved it
This sentence is false.
As he first said, it's interactive. Can't be reduced to pure logic.
If you take the statement discussed in this video regarding the ability to convince a verifier (with as close to 100% certainty as you desire) that a map is 3-colorable, by only revealing random pairs of neighboring colors chosen from a random permutation of such a coloring, then that statement can be converted into a map.
And that map would be, according to the video, 3-colorable. And you could convincingly demonstrate that the map is 3-colorable without revealing any information, using the same method.
I believe this is what you're looking for.
Great video. Should this have been on the main channel?
I didn't even realize this wasn't on the main channel
Still can't wrap my head around that you can convert those proofs into those three color maps... gives me a headache
RIght? I'm so interested in the specifics. Like whats the simplest statement you can convert, and can you please draw it and explain how it captures the statement?
@@Android480 tattoo, the map for the statement that all statements can be expressed as maps.
@@Android480 i failed to find some sort of converting tool for that. i would really love to see some simple demonstration
There are things I didn't understand at first but I think figured out :
Say you have a map a and verifier that always pics the same country and ask to compare it to all the other ones, once the verifier has compared all the countries to the initial one, he will know for sure one of the colors. The verifier can then repeat the process with an other country with a different color from the first country, and he will the know for sure the exact three-coloring of the entire map.
-> I guess this issue doesn't exist if you're only allowed to probe neighbouring countries.
And one other thing:
What could prevent the prover from giving you two different colors at random for each query ?
-> This issue doesn't exist if the envelopes are real, meaning that the prover laid them before your query and you make your choice after that so that the prover can't generate the answer on the fly.
It means that the prover has to have a working 3-colored map to not be caught cheating eventually.
Yeah I think what would clear things up for me is an example of how verifier can catch a fake proof
It would be interesting to see a discussion of what proportion of published proofs are incorrect.
How do you verify that the map was actually generated from the proof algorithm and isn't some completely unrelated three-color map?
You as a verifier could generate the map yourself from the statement that is supposedly proven, then tell the prover to color it in. Or convert the map back to the statement and check they are identical. The map and the statement are the same thing in different forms and can be translated perfectly back and forth.
Then you can verify that the coloring is actually valid (only three colors used and no neighbors the same color), either by just looking at it and checking it, or alternatively if the prover is paranoid and don't want to let you steal the proof, by the zero knowledge (envelope) method. Then you know that the statement is true.
Same way you verify if a real infinite Penrose Tiling is not identical to another real infinite Penrose Tiling. xD
Do you think im going to spend 33 minutes in a math video?
Of course i am
Given that some people would spend that time...arguing with people on the internet who won't change their minds, watching so called reality TV, doing drugs, getting drunk, or reading 50 shade of grey, I think you can easily justify the 33 minutes vs those actions :)
You have 33 likes..I can't spoil that.
Amazing video, thanks Brady and Avi. I think I'll be falling down this rabbit hole!
One of the best numerphile videos I've ever seen.
I have the most wonderful proof of the zero knowledge proof, but it’s a bit too large to fit within this UA-cam comment.
I'll come back in 300 years
The humour in this comment is marginal
@@trueriver1950 yeah, it's a stale fermat.
HAHAHAHAHA Too accurate :,)
👌🏾👌🏾👌🏾 to all commenters.
Does anybody know what happens to undecidable statements when you construct their equivalent 3-color map? Whether a map is 3-colorable or not seems to me to be always either true or false, but Godels incompleteness theorem (also referenced) would seem to imply some maps are neither. This NP stuff on proving is super interesting but indeed the video left me with many more questions!
I THINK it works like this:
The colorings encode proofs of statements.
For a statement X and a map MX, the existence of a 3-coloring for MX is equivalent to a proof of X.
The negation ~X has a map M~X and a 3-coloring for M~X corresponds to a proof X is false.
If X is undecidable from your axioms that means there is no proof of X nor a proof of ~X. Equivalently there is no 3-coloring of MX nor a 3-coloring of M~X
Undecidable statements are not in NP so they cannot be converted into a map
Awesome video. Makes me want to learn about formal logic. Thank you!
Wonderful. I love this concept.
OMG! Avi! My favourite entropy extractor algorithm inventor.
Me when I have zero knowledge
Finished watching and I still have zero knowledge
Wonderful video about ZKPs, thank you so much Avi and Numberphile!
Loved this video. Please make more about Formal Systems
This has been the best numberphile in a long time.
You: I have a zero knowledge proof of this problem.
Hacker: Tricks you into opening NOT neighboring envelops in order to discover the whole map through finding envelops with the same color.
Oh dang! Permitting that kind of query would undermine the whole process.
Identity thief: changes the contents of the envelopes after you pick which pair to open.
Except...the color scheme can be shifted (1 of 6 variations I think was mentioned) randomly. You could repeatedly query until every 'country' on the map was revealed...and still not know what the final answer/3-coloring of the entire map is. Hence the term 'zero knowledge'.
@@ckshreve We're not interested in the colors themselves, any more than we care about whether we call a variable x or y. A given color is just an abstract label. What we are interested in is the structure of the coloration, which directly corresponds with the structure of the proof we want to find out.
Neat. This reminds me of the matchstick box idea wherein you can be confident the other matches are good after striking the previous ones randomly.
I like how they keep the child's drawing on the board, even in the animations
The warning "Do not erase on the board", proves that someone erased it.
+
So he says "simple" a lot. I'm not sure his idea of simple aligns with mine :)
It's moments like these when you feel the beauty of mathematics and formal logic. When it truly shines.
You can have a cake and eat it. Er... I mean, you can have a proof and not tell it in details. And it still works. *convincingly shows why*
"But I want to know the proof."
"You don't need to know the proof. Here's the proof you don't."
"I don't need to know the proof."
It has the beauty and style of a Jedi trick, only with a solid mathematical ground under it.
I think this was one of numberphile’s best videos. I thought he explained it very well.
What about Gödel’s Incompleteness Theorem? If that says that there are statements that cannot be proven to be either true or false, and NP completeness says that every statement can be converted into a map, there must then be maps where it is impossible to find a colouring, but also impossible to prove that there isn’t one. Would these maps be infinite, or how does this work?
I like this insight. I'm not sure if that is the correct analogy, but I'm also not sure that it isn't the correct analogy! Either way, I like it!
The way I believe it works is as follows.
Let's say you have a statement X.
There is a map called MX.
If there exists a proof of X then MX can be colored with 3 colors. A specific proof is a specific coloring.
If X is false then that means ~X ("not X") is true.
There is a map M~X. If there is a proof that X is false, i.e., a proof of ~X then there is a coloring of M~X.
If X is undecidable then there will not be a proof of X nor a proof of ~X and so neither MX nor M~X will have a 3-coloring.
These maps cannot actually tell you anything about the inherent "truth" of various mathematical statements. They can only encode the existence of proofs following from a specific set of axioms.
Gödels theorem then basically says that for any system (e.g. Peano arithmetic, or ZFC) there will be some statement X that can be encoded in that system, and thus for which we can construct a map MX, but for which both MX and M~X won't have a 3-coloring.
Sorry to clarify, there will be an X we BELIEVE to be TRUE that can be encoded in the system but for which there doesn't exist a proof (coloring) of X nor of ~X.
This was great! Should have been numberphile 1 content.
The only thing that really bothers me is that the zero knowledge proofs rely on inductive reasoning rather than on deduction (they are not “proofs” in the usual sense but rather provide “proof” in the sense of evidence). I guess the goal is just to attain “conviction” in the verifier but was anyone else bugged by this? Thanks I’d love to learn more
Regarding an example, I did zero knowledge proofs at University, and we did one example, which was graph isomorphism, which was really hard to wrap my head around. The lecturer then said every other example is vastly too complicated to be covered in the course. And because the only example within the scope of the course is graph isomorphism, it won't be on the exam haha.
import random
print(random.sample('rgb', 2))
It would be nice if he could come back and explain how they translate statements to maps
I conjecture the heart notation on the white board was key to his insight.
Excellent video from the master himself.
What does the three coloring of the four color theorem look like
nice idea for a tattoo
If "we tried to prove you wrong a buncha times, and couldn't" worked as a proof-of-proof, we can "prove" that someone has a proof to the Collatz Conjecture.
Imagine someone hands me a proof of the Collatz conjecture. There's 2 ways I could try to prove them wrong:
A) Shred the proof they handed me. I don't need that. Then guess a random number and run it through the Collatz function a bunch of times until I reach 1. Repeat many times.
B) Flip the proof open to a random page and check if the author made an error in reasoning on that page. Repeat many times.
I'll never be too certain that the Collatz conjecture is true by doing A. But if I do B, pretty quickly I'll have checked every page in the proof, and will be fairly certain that the proof is correct. (Or will have found an error if it is false.) Zero knowledge proofs look like B, not like A. (Just with weird-looking "encryption" of the proof.)
@@phillipb8765 ah, that makes more sense. Thank you.
This is awesome!! The whole field sounds cool
I didn't understand anything, but he proved to me it's an important video. No knowledge transfer happened!
"I have a zero knowledge proof of the goldbach conjecture! Just give me any even number you can write down and ill give you the two primes that sum to it."
okay give me the two primes that sum to 16. I am waiting.
@@AgentM124 13+3
@@davidwilsch4668 nice, my stupid brain was thinking about multiplication of 2 primes... Let me think of a new number. 2147483648
57653696942527439475647457428585475265326537654765964865453652643874659767486545364357654342531213214321432143765987685694
@anonymous dude 1+1 or 2+0 won't work and I don't think negative numbers can be prime either :) well done hehe.
If the algorithm is simple enough for high school, why didnt we go over it?
yeah that would have been nice, all the sources i could google were way beyond highschool
Because if everything that a high school student COULD learn, HAD to be learnt... you would NEVER leave high school lol
A dream for some, a nightmare for others.
@@fredblogs12345 i think he was referring to going over the algorithm in the video, not why he didnt have it in school
I remember having studied that during my university years. It was not too hard to follow, but I think you'd still need a couple hours in order to introduce the notations, definitions and whatnots needed to provide the proof itself. The Cook-Levin theorem proves the fact that the SAT problem is NP-complete, which is the tricky part, but the reduction of 3-colourability to SAT (and viceversa) is quite straightforward if i remember correctly.
Because High School isnt about learning anything but comply and obey. Follow the money. 💁🏽♂️
Absolutely brilliant
How is the secret envelope mechanism implemented in practice? I know you can use a cryptographic commitment scheme. To a casual viewer though, that's kind of an important detail. A lot of schemes are possible if you're allowed to assume magic.
Doesn't this mean that every mathematical statement is, in principle, provable or disprovable? Doesn't this contradict Gödel's incompleteness theorem?
in the subject's spirit: no
If I understood the video correctly, it is not. If you have an improvable statement and translate it to a map, the map wont have a three coloring. But if you have a non-3-colorable map and translate it to a statment, it will only tell you, that there is no prove to the statment, not that it is false.
@@tth-2507 so you could use it to prove there is no proof? (correct or not)
@@AbelShields I would say yes. But persumably thats hard ... mind that to show that it is unprovable you additionaly would have to show that you also cant disprove your statement.
@@tth-2507 Proving there is no three colouring is in principle easy (but slow); you just have to search all colourings. You can similarly show that the negation of the statement has no three colouring, and hence no proof.
This is so interesting, I feel like I get the main point but now I'm really interested in the algorithm that transforms proofs into maps and vice versa and *how/why* it works. these connections are so interesting and beautiful, it makes me want to become a mathematician
You should ! The topic is super interesting, I'm not sure how much they would teach it in math tho, as it is more central to more computer science things
mark van dijken You and everyone else too! I hope they eventually reference some course or lesson on the topic. I don't need a concise 30-min video. I'd gladly speed weeks getting into it.
I love that Brady asks questions a person with no knowledge would ask
I don't comprehend - in the example with the map I can fake a proof that I can color any map with just 2 colors. Because when the verifier ask me about any two neighboring countries, I'll always show two different "random" colors.
Ahh the legend wigderson!! Jealous of all my Princeton friends who have the pleasure to learn from him
This video is the first time I've seen him, and I'm not impressed.
Drinking game: take a shot every time he says proof
23:35 I'd play a Three Color Puzzle. It looks like there would be chains of logical deduction similar to Slither Link.
This would be really great to see done by computerphile for a different angle
Turns out they did!
I want to color a map in 3 colors and then find out what I just proved!
So does this imply that anyone, given enough time, should be able to prove any provable mathematical claim?
This is true regardless of the mapping theorem. If you have enough time you can type every possible document using every possible symbol, and that would include the proofs to every provable mathematical claim (and would also include my grandmother's telephone number or the number of ways a monkey can scratch its bottom)
@@TommasoGianiorio That's an interesting observation
Does that mean that every mathematical proposition can be simply brute-forced? And also, what would happen to non-probable statements? What would be their map and their colourings?
Seems like it, but brute-forced in super-polynomial time! (As long as P doesn't equal NP.)
Non-provable statements would have a map that is not 3-colourable. But that doesn't say anything about their being true or false, only that they don't have a proof.
I was thinking about whether I should give up half an hour to watch a mathematical video (I'm not a mathematician) and I should say that I do not regret my decision. The result is quite amazing.
How can be sure that the prover isn’t making up random colors?
Well, they can. But that’s why there’s the envelope-type system. The prover assigns the colours first. Then you open a pair of envelopes. Then the prover assigns another random permutation of the colours, and you open a pair of envelopes. The point is that the prover doesn’t know which envelopes you’re going to open, so they can’t just use random colours, because this envelope-switching-opening process can be iterated as many times as required for you to be convinced that it’s a proper three colour map. And if they just assigned random colours eventually you’d open a pair of envelopes with the same colour.
Not sure I explained it that well... did it help?
@@KusacUK Certainly. I would just like to add that the envelopes can be implemented as encrypted data, which the verifier requests keys for. This allows the prover to reject requests, and issue a new dataset to prevent consecutive queries.
@@KusacUK So this relies on the fact that the verifier can see that the colors in the envelopes don't change? i.e. he knows that there are fixed colors in the envelope and the colors in the envelopes just get permuted. Because if i would just ask someone without knowing there are fixed colors in the envelopes he could just tell me random colors and i could not spot a mistake.
@@bungeruwu Correct. Or think of it like evidence in a criminal case - physical evidence collected by forensics is bagged up, and there’s a whole chain of custody for that, and as long as the procedure has been followed properly everybody in court has a high level of confidence that any particular piece of physical evidence was found where they said it was. Of course, then you end up in discussions on what the evidence means, but that’s a different problem!
Ok, how do you convert a mathematical statement into a map? I think if you would have explained that then this video would have been a lot easier to understand. Can't find anything on google either, how can I find the algorithm?
Look at the idea of the proof for Gödel's incompleteness theorem. He basically invented a dictionary that allows you to encode all possible mathematical statements (including sentences in plain English) as mathematical objects that. What they do here is very similar. The general term for converting a problem to a problem of the same complexity class is called polynomial reduction.
Love this video.
This is at the border of computer-science-phile (unless you consider computer science as a branch of mathematics).
In practice, a zero-knowledge proof might be useful for example when you want to show that you are over 18, but without revealing your birthday or without showing your ID card (which contains even more personal information).
Another example might be if you want to show (prove) that you know the answer to a question, but without showing the answer.
I just love his accent! The way he pronounces pwoof has some nice charm to it.
His accent is not effective for an English speaking audience. He has a lot of trouble enunciating.
I think u did it, you zero knowledged proved the zero knowledge proof cause I walked away from this video with no new knowledge on the topic
What part didn‘t you understand? In short: every statement can be converted into a map. Every proof (true statement) is a 3-coloring of that map. If I show you a three coloring of the map I have given you a proof (indirectly), as everything can be converted back to mathematical statements. But wait because I showed you a specific coloring I also transmitted information. In order to make it zero knowledge you get to ask me 2 neighbouring countirss of the map, which I colored in before you asked. If they are opposite you‘re a little bit convinced. Now I color it again in a different way and let you ask me again. If they‘re opposite again you‘re be a little more convinced. Ok we repeat this until you‘re 99.999...% sure I really do always color the map with a 3 colors.
@@screwhalunderhill885 thank you for the "too smart/wordy didn't understand"
Feels like that's not even a proof because... You're getting information in the form of a limiting process...
Like when do you declare it's true - 75%? 99.99999%? Feels arbitrary
_i guess you gave me a no knowledge proof_
Great video.
Really interesting but so many questions.
An example would be awesome.
From what I understood:
1. Start with a hypothesis.
2. Prove the it.
3. Convert the proof into a 3 colored map.
4. The coloring can now be verified without revealing the solution.
Questions:
1. Is the "shape" of the uncolored map determined by the original hypothesis or by the proof?
If the proof determines the shape of the map, then:
A. Doesn't knowing the shape of the map give some information? (Therefore not Zero Knowledge Proof)
B. Would an alternate coloring (assuming one exists) be an alternate proof?
C. If I can color the map can would it mean that I also have a proof?
D. Assuming that I have verified the coloring in your supposed proof, how do I know that it links back to the original hypothesis as opposed to a random 3 colored map?
If the shape is determined by the hypothesis then i guess it answers most of the questions above.
2. Every finite map either can either be 3-colored or not. If yes then you have proved the hypothesis, if not then the hypothesis is false.
A. What about an unprovable hypothesis "Gödel's incompleteness"? Will it also have a map? If so will it be 3-colorable or not?
My professors always loved it when I turned in zero knowledge work.
I guess this type of work didn't get you any Turing prize, did it ?
Had a very hard time understanding what was being said
There are few papers that change an entire discipline, this one sure did!
Had to write some *proofs* for my home works. The task stated "show that..." But now I want to revise my solution and make my proof zero knowledge