Zero Knowledge Proofs



hello my name is Scott Twombly and I'm going to do a presentation today on zero knowledge proof so what is a zero knowledge proof well in cryptography a zero knowledge proof or zero knowledge protocol is a method by which 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 so why would you want to do that well what if you have a secret that you don't want to tell anyone but you want to prove that you know the secret and that's where zero knowledge proves could be so I want to start by talking about some very simple zkp riddles and these are a good way to get you to start thinking about zero knowledge and to see how they work and they're also just a lot of fun so first let's imagine that we're looking at a Where's Waldo book and you and a friend are looking at this book and you find Waldo and your friend doesn't believe you and he wants you to prove it so how do you prove to your friend that you know the location of Waldo but you can't reveal his actual location so you can't just point at the book and prove it to him another riddle is one of the Easter egg hunt so imagine you're in the Eastern continent very similar and the children are running around collecting eggs and there's one egg left and only you know where it is how do you prove to the children that there is in fact an egg left and that you know where it is how do you do that without revealing the location of the egg another one is a bit more far-fetched but bear with me so imagine you have a superpower where you can magically know how many leaves are on a tree you can look at a tree and you can just magically know the amount of leaves on it and you have a friend that you want to prove this to but he's not actually going to sit there and count to thousands of leaves on the tree to verify that you're telling the truth so how do you prove it without revealing the actual number of leaves or even talking about the exact number of leaves at all I'd like to talk now about the requirements for zero knowledge so let's have a person named Peggy be the prover in another Victor the verifier so the first requirement is completeness and it's a very simple condition saying that if Peggy is honest and does have a secret and she wants to prove it to Victor if Victor is also honest and everything will work in short as long as both proofer and verifier follow the protocol the zero knowledge proof will follow the second requirement is soundness and it's another condition saying that if Peggy were not honest if she didn't actually have a secret but still wanted to convince Victor that she knew the secret that this would be impossible now in reality most zero knowledge proof relaxed this requirement but they make it so Peggy's chances of successfully fooling Victor can be made arbitrarily low or in other words soundness arbitrarily high so these two requirements are for emptying any interactive proof what makes ckp special is the next one zero knowledge so if Peggy is honest Victor learns only that Peggy has a secret but not the secret itself and moreover anyone spying on Peggy and Victor have no way of verifying if this process is scripted or if it's genuine essentially Peggy can prove she knows a secret to Victor and only Victor so I want to talk now about a very common in a very intuitive example of a zero knowledge proof and this is one that's called the strange cave of Alibaba so in this scenario we have a Pei Victor and a Peggy and they have a cave where there's a door at one end of the cave and that door only opens when told the proper secret so Peggy wants to prove to Victor that she knows that secret so the protocol starts Victor waits outside the cave Peggy enters the cave and chooses either path a or path B she chooses that randomly so she walks around to the other side of the cave then Victor enters the cave and calls out which exit he wants Peggy to appear at Peggy appears at the correct exit and Victor is convinced but if this whole process this whole protocol is performed only once Victor should not be convinced it is possible that Peggy initially chose the B path got stuck at the door and got lucky when Victor chose for her to appear at that same B exit it should only be convincing to Victor if this test is repeated several times so say if it's only repeated 20 times the changes of Peggy lying about knowing the secret becomes – about one in a million so in this example all three zero knowledge requirements are met completeness is assured by Peggy and Victor following the protocol soundness is assured by repetitions of the protocol and zero knowledge is assured because Victor never learned the secret and any outside observer has no way of knowing if Peggy and Victor orchestrated the whole thing or that so to illustrate that last concept a bit more let's pretend that Victor is videotaping the whole process so the camera would show Peggy entering the cave but not which path she chooses it would show Victor approaching the mouth of the cave and shout in which exit exit he wants her to appear and finally Peggy appearing at the chosen exit and that's repeated let's say 20 times so by viewing the videotape any outsider reviewing the videotape it would be impossible for them to verify whether or not the protocol was being followed or whether or not Victor and Peggy planned the whole thing to trick others thus Peggy has proved knowledge of the password to Victor and only Victor so let's move on now to another example so in this example Peggy has a solution to a Sudoku puzzle and wants to prove it to victor without revealing anything about the actual solution so how would you go about doing this now this problem is interesting because this Sudoku problem in computational complexity theory is something called an NP problem which is a very large group of problems and solving it illustrates how one might solve many other problems so just a brief note if you've never played Sudoku before the objective of it is to fill this nine by nine grid so that each row column and block contain exactly one of each digit those did just being one through nine so let's say Peggy has the solution and she uploads that solution to a computer program and this program is verifiably honest like say it's open source and anyone can look at the code and verify that it does exactly what it advertises to do and what advertises to do is the following it encodes the given solution using a simple substitution cipher where it eats transmutation has an equal chance of appearing in other words the digit one has just as much of a chance of being transmuted into a three as it does a seven or a nine or a four or so on so next it is displayed the program displays to Victor as the following Victor has 28 choices he can reveal a row he can reveal a column he can reveal a block or he can reveal the original problem now he's allowed to choose multiple times but only one at a time and every time Victor makes a new choice that the program Riaan codes the solution with a brand new key so here's an example of what that might look like so in the first picture you see the computer program unmasked one row and Victor is looking to verify that it is valid that it's a valid Sudoku row that there's only one digit one of each digit in row likewise with the column and with the block and he can verify that it is in fact the original puzzle by looking at the encoded original puzzle you can easily map that to his original puzzle so he knows that this is a solution to his puzzle so let's discuss again the requirements for zero knowledge proof in this example completeness is ensured because of the verifiably honest computer program and the fact that Peggy and Victor are following the protocol honestly soundness is ensured because of the following if Peggy made up a solution and tricked Victor maybe Peggy just got lucky and Victor asked to reveal just a single row or a column or a block just so happened to fit the requirements of a Sudoku solution but he's allowed to repeat the choice as many times as he wants until he feels convinced so Peggy's chances of getting away with cheating if Victor chose only a single time are 27 out of 28 so they're pretty high but if Victor makes multiple choices at random let's say he chooses 150 times randomly Peggy's chances drop to less than a hack less than a half a percent the solution is also zero knowledge because since every permutation of the cell in the row column or block is equally likely victor learns nothing of the solution only that the encoded solution is valid so Victor is convinced that Peggy has a valid solution to the puzzle Victor has no knowledge of the solution itself and any outside observer can't separate the legitimate transcripts from this from any other sort of made up or false ones maybe Victor is intentionally not revealing the one row that would reveal Peggy as a liar there are many possible applications for zero knowledge proof currently there are almost none in the wild but the power of zero knowledge proof protocol and the growing need for privacy on the Internet ensures its eventual adaptation one exciting area for Zee KPS is in the field of enforcing honest behavior an example of such might be a cryptocurrency user imagine they want to prove that he or she is doing nothing illegal with their cryptocurrency without actually revealing what he or she is doing with it ie what they're spending it on another example is an electronic voting scheme where one person was to prove that he or she voted but not reveal any information about the actual vote and also a common example is one of proving identity such as the asymmetric public and private key digital signature scheme the future is bright for zero knowledge proof protocols in fact if you assume basic things like strong encryption it can be shown that all problems in piece space can be proven with an interactive proof now pspace is another one of those categories of computational complexity and it's even bigger than NP problems in fact it contains all NP problems it can likewise be shown that all problems can be proven with an interactive proof can also be proven with a zero knowledge interactive pretty P space holds an innumerable one numel amount of problems so that is a lot of possible uses for the zero knowledge proof protocol

18 thoughts on “Zero Knowledge Proofs”

  1. 1. At 10:54, you said 'Almost none "in the wild"' as far as ZKP application is concerned.
    2. Zcash was invented on 28 October 2016
    3. As of 23 Aug 2018, there are over 400 global patents relating to ZKP and the 1st patent application relating to ZPF was filed in 1998.

  2. Example one sucks Peggy could start by entering path A with victor watching and victor callus stay there and then Peggy could go around through the door to path B for 100% proof…

  3. I'm not a fan of Alibaba's Cave analogy. I know this isn't your fault since you didn't invent it, but still. All Peggy has to do is enter on one side and exit on the other to prove she had the key to the door. No need whatsoever for random picking, repetition, etc. But I suppose it has one property that is desirable, and that is it only Victor "must" believe her. If the video tape showed Peggy entering one side and exiting the other, then Peggy would have essentially verified her knowledge of the key to everyone, and not just victor.

  4. The sound quality is so bad, it is hard to watch. Good explanation. I would love to hear with better quality sound, as it made it difficult to follow the talk. Great contribution.

  5. i'm sorry. I still don't understand. Do regular blockchain tx's require the private key to be revealed? I don't believe so. Is the information being hidden the amount of coin being transacted?

  6. Since you use Symmetric encryption to ‘scramble‘ the proof sent to the verifier. What prevents the verifier to partially decode the solution? After asking randomly N times he will then be able to rebuild the solution that the prover tries to keep secret.

  7. This is the best presentation I have seen on zkp theory. could use a little more love when explaining the Sudoku example, but other than that, perfect.

Leave a Reply

Your email address will not be published. Required fields are marked *