Zero Knowledge Proofs - Computerphile
HTML-код
- Опубликовано: 6 июн 2024
- How do you prove something without giving away all your data? Zero Knowledge Proofs could hold the answer. Alberto Sonnino, Research Student at UCL explains.
EXTRA BITS: • EXTRA BITS: More on Ze...
Computing Limits: • Computing Limit - Comp...
UCL Link: bit.ly/C_UCL-people
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
A simple example of a Zero Knowledge proof ist this: Say there is circular hallway, separated by a locked door. To prove that I know how to unlock the door, I don't need to give you the key, nor do I need to show you how I unlock the door. We'd just start at the opposite side of the hallway (where the door isn't visible) and I'd go down the hallway to the left and I'll come back on the right side. I couldn't have pulled it off if I didn't know how to open the door.
This is the way some protocols on the internet work. You will encrypt something and send it to me. I will decrypt it, and will tell you something about the content (like a checksum, or a task that I need to solve). An eavesdropper will only see and encrypted message and a checksum (or the result of the task), never will he see the message (the task), nor will he see the key, nor will he know what I did. In this case I have proven to be the person I claim to be (the one you exchanged a key with over another channel at a different time) without revealing anything to an eavesdropper.
With secure asymmetric encryption (key pairs, where one key is public and one is private) this can be achieved without exchanging a secret key over another channel. You could encrypt something with my public key (that everyone may have) and ask me to tell you something about the content you just sent. If I can pull that off, I have proven to you, that I have the private key, with no one but me having any knowledge of the private key itself and no eavesdropper having knowledge about the actual content, the key or the challenge.
A zero knowledge proof is basically giving someone a challenge that they could not solve without having a required knowledge, not revealing the required knowledge itself.
The pen example was the best one to refer to this. The envelope example was just to unclear. Thanks for clearing this up a bit more.
I honestly think you explained this better than the video, thank you.
Isn't your example the same as the Ali Baba cave?
@@boyabundabasketball4988 Yes, it is also known as the Ali Baba cave.
@@brixomatic However, this gives you a 100% guarantee that you have the key. If for example you were to walk down the hallway and I asked you to come down the left hallway, I can with 50% certainty say you have the key (if you went right and went through the locked door and came to left VS you were already left and didn't need the key) and repeating the experiment many many times can give me confidence.
He proves he knows about the subject but gives us zero knowledge.
That was the point right?
LOL
i was about writing a similar comment but yours is just appealing XD
IM DYING 😂😭💀
It's like when you and a friend have a secret, and you're in public and he says a keyword for that secret topic, and you're like "ayyyy"
wrgg
I literally just had an exam on this... Next time please upload this one day earlier thank you
But the timing of this video's release has nothing to do with the timing of your exam.
IdeallyYours ... do people here need to state /s as for sarcasm for you?
zero chance of that happening !
Kevin North security
Yeah, but now they can reveal everything you got wrong ....or right lol haha
I did not expect the video to end so abruptly. I was expecting him to have a chance to explain the tallying of the votes.
When he first said secret, I totally thought he said cigarette
Me too. Plus I've never smoked.
It's very frustrating that almost all such videos do a perfectly good job of explaining the abstraction, but then do literally nothing to explain the actual implementation. I had about 499 good abstractions, and now I have 500. Still don't know how it's actually done.
Accurate observation.
Read vitalik's blog on it, where he references the original zk-SNARKs paper
This explanation was easier to understand and more straightforward than all of the explanations offered in Wired’s “explained at 5 level of difficulty” video on ZKP!
Great video to convey the intuition of zero knowledge proofs, which I didn't know already. It'd be really helpful to see a basic encryption example to take the intuition another step towards full understanding. Thanks for the great content!
Vote Red Pen! Crooked Blue Pen is supported by Big Ink! Draw a wall! Draw a wall!
All pens are corrupted. Vote for a pencil instead ✏️
All forms of writing are bogus. Don't endorse the broken system. Don't vote.
Fake ink!
The peniarchy will fall
Blood Bath and Beyond. This pen is RRR...RRR....BLUE!
While this does explain the concept very well, I don't understand how the encrypted votes will be counted without revealing their content. Surely a voter has to decrypt their two envelopes before any protocol can add their votes to the totals, right? So why wouldn't that reveal what they voted?
Finally a topic that is well presented without being common knowledge already. Best video of the year on this channel IMO!
I believe that most of the stuff they post on this channel is not common knowledge. Common knowledge is something known by most people.
The problem with e-voting is not the algorithm or the protocol behind it, it's the implementation of it. It doesn't matter if you have plans to build a perfect system if people keep making mistakes trying to build it.
well the protocol is also a problem.
Even before we get to the impossible implementation problem I'm yet to see even a vaguely valid algorithm that lets citizens vote anonymously while retaining the simplicity of invigilated paper votes and restricting vote tampering. It would also have to let the citizens verify their their vote was counted and not discarded or modified. Each step is easy but combining encryption with hashing with signatures while maintaining anonymity in a function voting system has yet to come to my attention.
@@recklessroges Even with paper votes, how do you truly know your vote was "not discarded or modified"? It all comes down to trust.
Any advancements in this area?
I can only understand this as a high level overview about the concept which ultimately requires the actual algorythm/crypto to be really understood.
This reminds me of the way cryptographic keys are exchanged in WPA - what is actually exchanged is a key generated from some odd bits of data like the time, so you only prove that you know the key, without broadcasting it over wireless
I ended the video with zero knowledge too. Great Presentation. It is really insightful and well explained. Thank you
This video gives zero knowledge about how zero knowledge works.
because how it woeks depends on where you use it. It is only to show what it is.
...but hopefully it gives you knowledge about what it is and what its uses are. I’m sure there are well explained videos for specific ZKPs elsewhere...
He just tell us enough to prove us he knows.
aspie96 voting? Did you not watch to the end?
@dosmastrify, voting example does not tell you how it works. I.e. it does not explain how to use zero knowledge proofs to prove that I know who I voted for in e-election. It merely states in broad terms that it is possible. I think the explanation could have been more... in-depth.
Ok, I just saw this same "demo," but with candy clouds instead of pens. My immediate thought was, "What if the pens ARE the same color, and that's what we want to prove?" Suddenly the swap test fails. So it feels like a particularly trivial example is being chosen. I want to see a deep dive demo into how this idea ACTUALLY WORKS - something that would give me some shot at being able to apply it to anything I wanted to apply it to.
1 you could have distinguished the pens based on some other distinguishable aspect about the pens and not the color that only you are aware of...2 the pen need not be blue, some other color perhaps(may be it is green) hence still distinguishable from the red
5:04 - Tom Scott will disagree with you!
The details left unstated in this video about electronic voting using zero knowledge proofs could fill a decent size book. It presumes that methods exist without describing how they might work. On top of which, the example isn't valid in an election where you may vote for nobody.
The ability to vote for nobody is trivially accounted for though.
since by definition 'nobody' represents a singular option. (there's only one possible way to vote for nobody) this just means that 'nobody' is conceptually the same as a single candidate.
So it still means you can vote for 'one' candidate, but that 'nobody' is considered a valid choice of candidate. (you voted for a single candidate, which happens to be the null candidate - eg. None of the actual candidates.)
Why do don't do electric voting is because someone can hold a gun to someone's head.
Same reason why you are not allowed to take photos of your ballot before you seal the envelope.
Also: It is easier to trust physical paper than an electronic machine. Computers are inherently untrutwearthy if you don't know exactly how it does thing. And fraud is much easier when you only need to log in with your electronic ID and such.
I wonder how zero knowledge would solve the most fundamental issue of e-voting.
Imagine a well working paper system: You can stand in the voting room all day, watching people put envelopes in the voting box, taking note of who put one in and how many people put one in. After that you can watch the box opened, every envelope opened and the counting. Thereby you can prove to yourself a lot of things without knowing who voted for what option:
- the total number of envelopes is the total number of actual unique people. There were no envelopes in the box before the voting began.
- each envelope contains only one vote or its invalid - therefore you can derive each unique person voted just once
- each vote represents the genuine free decision of a unique person: The voter could decide freely because he wasn't watched, his vote will be in the box because he put it there and the position where he made his mark wasn't changed
While some part of this may be proven by zero knowledge prove, what prevents a voting machine from having some "votes in the box" beforehand and silently discarding the same number of real votes? Or what prevents a voting machine changing a vote before it was encrypted?
There are actually Zero Knowledge proofs for this as well. Imagine a system, where you encrypt your vote and publish it on a website specifically designed for this election. Then you (and every other voter) can check for themselves, that their vote is actually present there.
After the election closes, the votes are shuffeled, aggregated and the aggregate is opened. For every step, you can give a zero knowledge proof, that this step was performed honestly (assuming that a large enough number of officials who supervise the election are actually honest). These zero knowledge proofs have to be published together with the election results, so everyone can see that the counting wasn't rigged.
Of course I omitted a whole lot of stuff, e.g. how you know that everyone only votes once, but these protocols are way to complex to explain them completely in one comment.
Encryption - It's said in the video that it's not part of scope, but I think it's essential. Who does the encryption when you put into envelope? I find it hard to "believe" that there would be a magic algorithm which would decrypt if and only if elections are finished and all envelopes are in hands of "good guys".
I came here after watching about ZNP from wired and get a bit confused. But this video cleared all my confusions and now I get the hang of it.
What encryption technique does zkp use, I know it isn't in the scope of the video but I really want to know???
By what method is it possible to irreversibly encrypt packets of single digit binary data where only the sum of those packets is then ascertainable?
Man, that pen trick is so much clearer and more informative than the parable of Ali Baba's Cave that I've usually seen used to describe zero knowledge proofs.
Really? I read the Ali Baba cave parable on Wikipedia before watching this video and found it was a lot easier to understand.
I don't know if someone has mentioned this before but wouldn't I have to show you that I indeed have a full deck of cards before proceeding? Or is that already assumed? Let's say it's not. How could we ensure that I have a fair and full deck of cards before proceeding
I've been applying this method (sort of) my entire life without even knowing I realise now.
awesome intuitive examples!
I don't get the 3rd,optional proof. You copy it and vote on top of it. What does that mean and how does it proof anything? Can Somebody explain?
After listening to this guy for 3 minutes, I rediscovered a so called "hit single" by an artist known as Loona, titled: "Latino Lover". It was a feint memory in my brain from my childhood and it came back alive... I'm not sure I'm thankful.
This is just an example of how ZKP can work, but it doesn't explain how it works! Could we get a video with more mathematical explanation?
I don't get the part around 7:16 ~ 7:48.
I have trouble understanding both the speaker's English and the substance. Could someone enlighten me?
What problem was he trying to solve and how do "copy and pasting someone else's ballot" and "voting on top" factor into it?
Scott Tsai He's explaining that you also need a proof that the voter knows what they're voting, so that someone can't just give them an envelope and tell them to submit that
That makes sense. Thanks!
I had a Linear Algebra exam today. This video title about sums it up..
Nice examples. For those who feel that the accent is confusing, just view the subtitles... Google seems to be able to understand his accent just fine!
I've learned about zkp on the example of the Alibaba door while learning about smart-contracts, i find this example far more simple that the example used in the video. if someone could enlighten me about non-interactive zero knowledge I would be thankful
You were way ahead of the curve man!
Good explanations. I finally understand this. Thanks :-)
Alberto Sonnino is a good teacher.
So zero knowledge proof is basically guessing on data? Like say for instance you are able to determine that the data that is being stored may or may not be used for third parties?
Can you make a video on Strings and Pattern Matching?
Im a bit confused. What exactly would the proofs be that the sum is one, the inputs are binary, and that I know whats inside?
Excellent explanation ! Tks
*The video description says "proove" [sic].* Just wanted to let you know...
+3ICE thanks, I'd fixed it but it's taking a while to propogate... >Sean
@@Computerphile Haha I love you guys
You take the blue pen and you forget about everything you've learnt you remain a part of the matrix, you take the red pen you stay in wonderland a bit longer, you go down the rabbit hole. What do you choose?
Wow. I totally didn't understand a thing about this subject before. And now, I think that I know even less. Perhaps you could do a follow up with a better explanation and some real practical examples.
I'm not sure I understand how in the voting example there is a difference between "knowing the content of the vote" and knowing that 1) the votes are binary, 2) they sum up to 1, and 3) that you know what you're voting for
I had zero knowledge about this before I watched this.
A part I don't think was entirely clear was the following:
Given that the secrets/data are assumed to be encrypted, how can they prove something about information that's, by definition, not accessible (e.g. that each individual vote met the criteria of being binary, etc.)?
Apparently, there exists encryption methods that do allow for operations such as summing.. I know.... i had to dig thru comments to get that "small" detail..
How does one sum up encrypted votes if they are encrypted?
So what's the difference between this and zk-snarks?
So what if I write a virus for your e-voting system that tells the user they are voting for the blue pen, but the software submits a vote for the red pen instead?
Yeah ok i sort of get it, to start of with i thought this was for web searches or to hide a trace of searches or page visits, i guess it could be. But then thought you are relying on encryption, and if the encryption couldn't be broke in the first place then why bother with what you have just said, or am i missing the point??
But how would you sum the encripted numbers? Isn't decripting them to sum them up giving away information?
There are ways to encrypt data such that you can still apply operators (like addition) on them. For addition, you'd have to build an encryption scheme for which the following holds: encrypt(A + B) = encrypt(A) + encrypt(B)
This would've been super helpful if that was mentioned. To me it was all about "we have envelopes and then we use what is inside to calculate a sum", meaning that he has to open it. Using a special envelope that allows to do math really did not come anywhere in that demonstration.
Cool thx :D It's just my curiosity, but aren't these types of encryption inherently worse than other forms of encryption? Also if you have an example I'd be ecstatic.
It was not well explained. See my comment at the top.
klemen kobau generally yes because once you have relations between encrypted values that can be used to break the encryption. For example there are encryption schemes that make comparison possible. But in this special use case I believe this is fine because we only have 0 or 1 as encrypted values that always should add up to 1.
A problem with a lot of e-voting schemes is that even if you can't decrypt the vote individually, you can still copy the vote to a separate pile, add dummy votes until you can decrypt it, then count the difference from the dummy votes.
One way you can mitigate this problem is to have some randomness to it. Say you have a 33% chance to vote for the other candidate. You hand over 3 votes, do a zero knowledge proof that all 3 votes aren't the same, then the voting booth chooses one at random. The more voters you have the less likely it is that the randomness will affect the outcome, however the risk of it happening does increase if it's a close election. Yet for an individual it's unlikely they would face any consequences if someone reads it, with the high risk of it being incorrect.
About e-voting:
Is it possible for the voter to check his vote has been registered and counted correctly, WITHOUT the voter being able to proof to anyone how he voted(necessary for voter secret)?
Not that I've managed to create or find, (and I've been searching for years.)
Sadly, being able to retain and exploit the extra information used in a typical transaction is viewed by the data aggregators not as a bug, but as a feature.
Please guys, make a video about OPUS audio codec, it is quite interesting how it saves space
You said that you present 26 cards, either red or black(depending upon the color you have) from the deck. Isn't that's also some knoweldge that you are providing it to the person in front ?
The point is to prove that the card is red without revealing any other details about the card (suit or number). You can easily do this by showing the person all 26 black cards from the deck. This works since a deck only has 26 cards of red and 26 of black. By showing you all 26 black, then the other secret card must be red. You've proven it is red, but the person still doesn't know the suit (diamond or heart) nor do they know the number. Do remember that basic ZPK really only works when all parties involved are honest. In this example, the deck must be only 52 cards consisting of 26 red and 26 black and the person with the cards did not alter the deck in any way. Also, the person who picked the card must have picked a single card from that deck.
> watches computer science video
> comments are about pen politics
The example of the red card is great but I still cannot understand how could I prove something like "I have more than 10k dollars in my bank account" without revealing how much money I do exactly have.
The red card is related to the other 51 by some rules (there are exactly 26 card for each color, and so on), so I can give informations about the other variables related to my card, but the amount of money I have is not related to anything...
How do you restrict one user to vote only once with anonymity ?
Wouldn’t the card example not be a true zero knowledge proof due to info leakage? As an observer would also gain info that the card is red
Is this a zero knowledge proof or a proof by contradiction? What is the difference?
Good video!
So what are the proofs for evoting? Tell us!
Isn't it just homogeneous encryption (voting)?
Couldn't you tell the number of the card by seeing which number is missing?
more please!!!
thanks! after watching this video, i feel like i have gained zero knowledge.
Rules need to be in place as to how to play the game, and answer is constrained. It sounds out of the world because it is new but will become obvious and something people have been using it in the past albeit not applied to computers.
hi~ this video was such an eye candy. however I'd love to see subtitles. I can say I understood pretty much but subtitles speed up the learning process. But! it was a such a great and informing video. I'm looking forward more on provable security by Antonio on YT.
7:15 can someone explain the third ZKP
isn't this basically data validation? I mean this is boundary checking is it not?
I don't understand one thing, he is color blinded, how he can know that you tell truth he shifted pens or not?
You should consider using a trepied.
Handles cards like a magician :)
How can one possibly learn about zero knowledge proofs?
I cant wait for zksnarks.
John Snow knows math. I'm glad.
Does anyone else agree that the opportunity for a matrix pun was missed by Computerphile?
He seems happy
It's like cracking enigma, you know it can't be x if you observe y. But you still don't know z
I have to admit that some brain sparks happened when I watched this video, but in the end I still didn't really understood it :/
How do we prove that a milk colored sky is not blue?
Privace Anansi Technologies...?
But one thing about the cards example. This gives me a 100% certainty about you having a red card right?
Don't ZKP have some probability in them? As you have to repeat the experiment many many times to gain enough confidence that person A knows a secret?
yes, zero knowledge proofs arent actual proofs in a sense that there's always a chance that they guessed it. think about that pen example, there is the chance that i just guessed whether they had a or b all say x rounds. those a s and b s are represented by bits 1 or 0. usually virtually all cryptographic protocols have sizes, meaning they can be 32 bit, 64 bit or 2048 and so on. the number of key size digits defines key size and entropy, that is how many possible variants of 1 s and 0 s orders are there. in zpk s the times of rounds they repeat the challenge is related to the concept above, they gonna repeat the challenge number of times respective to those key sizes and then hardness of breaking the zpk translates into rsa-2048 or aes-256, which are moderns cryptosystems used for passwords in general anyway that neither can you crack (solve the order of pens) nor can you guess (chance that you accidentally name that order).
@@dropagemonem Sure. But the card example is different. As you know in a single round for 100% certainty that the card is red (given the deck is 26 red and 26 black). So is this still a ZKP or not.
Sean you need a tripod for this camera
What kind of real-world thing would you prove with the pen example?
He hired three people to do this video lol
is there an implementation example? programming language doesnt matter.
He looks like "Steven Strait" from Expanse
What stops someone to agregate a single vote with a bunch of known votes to read it?
computerphile is unique
So how do I zero knowledge prove that my vote was binary and the sum was 1 ?
0:51 I quit smoking 3 days ago and now I'm like *"TELL ME ABOUT THE CIGARETTE! I WANT TO KNOW"*
I can't watch Quentin Tarantino movies now and now cigarettes took this channel from me too??? WHAT ELSE DO I HAVE TO DO TO QUIT???
on a nearly future i want to make a machine able to proof just verifying. no way to know how to proof.
cough zksnarks
kibichi Altair Cough ethereum
No matter which pen you vote for the stationary industrial complex still wins.
I don't know how to "proove" something without data [ See Description ]
I still don't understand it...
But you're convinced that it works, right? That's Zero Knowledge Proof.
I know that zSNARKs exist, but I don't understand how to apply them to real world problems...
That's why it's called zero knowledge , isn't that a proof ?
one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.
Simple example. There are 2 people, A and B. Now A has told B that he knows B's password for the safe, B's thinks A is lying and tells A to prove that he knows B's password. Now A could just tell B the password, but there are other people in the room and A doesn't want them to overhear, so instead A open's B's safe with the password. Now B is convinced that A knows the password even though A never told B the password, by opening the safe.
The zero knowledge part is that A never has to reveal to B what the password is to prove that A has the password.
Jack Kraken Thank you, that made it entirely clear.
Has anyone told this guy that he looks like John Krasinski?
More from Signor Sonnino please.
Doesn't matter what, I could listen all day. :)