Peggy the prover and Victor the verifier In the world, Proofs often crop up. Think Zcash, Zerocoin. Blockchain Zero Knowledge But the problem with Zero Knowledge Proofs is that they are difficult to understand without getting into the nitty-gritty maths. So, I am gonna to describe a Zero Knowledge Proof protocol as a story of two friends, in an setting which we can all relate to. Zero knowledge proofs Like in any story, before we meet the protagonists, we have to set the scene. The backdrop of a zero knowledge proof story is the following. A that is difficult to solve. problem A of that problem. statement In this story, these are… : the Rubik’s cube. Problem : the Rubik’s cube in its current unsolved state. Statement of the problem Now we can introduce the main characters. Firstly, we have Peggy the prover. Peggy the prover Peggy the prover is always making . claims And, naturally, she wants people to believe her . She wants to prove to people that her are valid. However, this causes her an issue. She often doesn’t want to reveal the details that validate her , because that would give away her knowledge… and knowledge is power! claims claims claims One such that Peggy has made is the following. claim I know how to solve the Rubik’s cube (the problem) from its current unsolved state (the statement). …but naturally she doesn’t want to give away her knowledge of how to do it. Our second character is Victor the verifier. Victor the verifier He likes listening to Peggy the prover’s . They interest him. However, he just wants to always be sure that she is not making unfounded claims about what she knows, because he doesn’t want to look like a fool. claims For example, he would like to know if Peggy the prover can solve the Rubik’s cube. It would really impress him if she could. At this point, we have a from Peggy the prover of a solution to the Rubik’s cube (the ) in its current state (the ) which she wants to show off to Victor the verifier. And she really wants to let him know that she does indeed know of a solution that validates her , because she likes impressing Victor the verifier. claim problem statement claim Now, in a traditional proof (not a zero knowledge one), there is a very obvious way (or ) whereby Peggy the prover can impress Victor the verifier and prove her . They can meet up and she can solve the Rubik’s cube in front of him… and that is it. protocol claim In this case, Victor the verifier is 100% convinced that Peggy the prover was not lying when she made her . He is convinced that she is trustworthy. This is fantastic! Peggy the prover has been able to show off her knowledge and Victor the verifier is convinced that Peggy the prover hasn’t made a fool out of him. claim However, Peggy the prover isn’t happy with this approach….Victor the verifier may learn some information about how she solved the Rubik’s cube. Zero Knowledge What if Peggy the prover doesn’t trust Victor the verifier, or what if she doesn’t want to reveal her secrets? If Victor the verifier can also do the Rubik’s cube then it devalues her knowledge of the solution, and she certainly doesn’t want him to go off and solve the puzzle in front of all their mutual friends before she has done it. For Peggy the prover, this information (the solution) is valuable to her. She doesn’t want to reveal it… but she still really wants to prove to Victor the verifier that she knows a solution, because this is Peggy the prover, she is a show off. And so she thinks, is there a way in which I can still convince Victor the verifier that I can solve the Rubik’s cube (her ) but without revealing any information about how I solved it? claim So what is it that Peggy the prover needs to hide? Clearly, it is the set of moves she is going to make to the cube in between its current state (the ) and the solved state. She doesn’t want to reveal even a single move that she is going to make. Because, even if Victor the verifier sees one move in between these two states then she has given away some information about how she solved the cube. And Peggy the prover wants her proof to be a zero knowledge one, not a tiny-amount-of-knowledge one. statement And so she comes up with the following scheme (or ). protocol The zero knowledge proof protocol The Protocol Victor the verifier goes off and finds a black box and places it on a stool. He cuts a hole in the top and a hole on either side. He then places the unsolved Rubik’s cube inside. Peggy the prover then places her arms through the side holes and looks through the top hole. She solves the Rubik’s cube inside the box under the supervision of Victor the verifier. When she is finished she reveals the cube. Importantly, Victor the verifier cannot see the moves she makes inside the box. However, he can be sure that he is not being deceived because there is no way Peggy the prover could have fooled him. There is no way she could have had, say, a second cube, fresh out of the packet in its solved state, ready to sneakily reveal as a trick. He is confident that the scheme (or ) that they have agreed upon is secure enough for him to accept Peggy the prover’s as true (this property of the protocol is called in the literature) protocol claim soundness And what’s more, this satisfies Peggy the prover’s wishes: she has been able to convince Victor the verifier that she knows the solution (called in the literature) whilst revealing nothing about her method (called - in the literature). protocol completeness zero knowledge ness She has validated her of a solution to a of the Rubik’s cube in zero knowledge, a.k.a a zero knowledge proof! claim statement problem They are both happy with this protocol. Peggy the prover has shown off her knowledge and Victor the verifier is in awe of her. They decide to go for a drink afterwards and celebrate. In reality, the information that Peggy wants to hide could be her identity, her signature or some attributes she possesses. If you liked this story, please clap and check out my blog on Blockchain explained using Where’s Wally and a camera . Also, completely separately, please check out my company at www.pilcro.com . You will love what we are up to!
