How To Explain Zero-knowledge Protocols To Your Children

On YouTube (23 min) Calculator scientist Amit Sahai, PhD, is asked to explain the concept of zero-cognition proofs to 5 different people; a child, a teen, a college pupil, a grad student, and an expert. Using a variety of techniques, Amit breaks downwardly what aught-noesis proofs are and why it's and then exciting in the globe of cryptography. Amit Sahai, PhD, is a professor of estimator science at UCLA Samueli School of Applied science. From S1 E16 of Estimator Scientist Explains One Concept in five Levels of Difficulty | WIRED https://youtu.be/fOGdb1CTu5c

Jacques Patarin[i], my cryptography teacher at university introduced us with zip-knowledge proofs with a simple real-life naught knowledge scheme. All you demand is five cards, 3 identical red and two identical blacks. You lot give ane black and i cherry to each person (Alice and Bob), and keep the concluding red. The scheme is the following: Alice will puts her ii cards ON Acme of the remaining cherry card: to say yes, she puts her blackness card on tiptop of her carmine menu, to say no she does the opposite (red on pinnacle of black). Bob will put his pair of cards Beneath the remaining ruby-red menu, and to say yeah he puts his black card at the lesser, with his red menu in between, and to say no he does the opposite. And so you cutting the deck enough times to obfuscate who've done what, and yous know that they've both day yeah if you have the two blacks cards next to each other (or both at each ends of the deck). If anyone (or both of them) said no, you'd take black cards separated by one ruby-red menu. [i] https://fr.wikipedia.org/wiki/Jacques_Patarin

I have designed i of such bill of fare decks and released information technology under an open up source license at DKC - Dining Child-Cryptographers [0]. This was done equally part of an European union Hackathon at Google, Belgium. [0] Dining Kid-Cryptographers, https://github.com/secYOUre/DKC

How-do-you-do. Could you add a section that explains what this is about? The linked repo does not explain what the objective of the game is supposed to be. I empathize that the game is related to "the dining cryptographers", but I haven't memorized that piece. I read it in one case? I tin probably observe it on Wikipedia? I recommend making your game a self-contained work that does non rely on at least i of the players remembering some details most a very specific idea experiment.

How-do-you-do! Thanks for your feedback, this is appreciated. While there is no background information well-nigh the game in the DKC repository at the moment, the game comes with a set of cards where the equipment, rules, and finishing criteria are described [1]. If there is interested for that, I volition add more context on the game and its contribution towards understanding secure multi-party computations for the youngest. I may withal have the slide deck I used to present this work at the cease of the hackathon, which may provide some farther introductory material. [1] DKC's rules https://github.com/secYOUre/DKC/tree/principal/self-print/300-d...

What does "cut the deck" mean hither, precisely? I feel like this word is fuzzy & can mean several things.

You split the cards stack in two and put the top function at the bottom of the other part (which was the bottom part and volition be now the tiptop). The relative social club of the cards is maintained: you don't shuffle them. But if you cut them in this way several times, it obfuscates the original location of the cards (every bit it's in practice impossible to follow their position changes) so you can't tell who put which carte where. Therefore the terminal arrangement, when revealed, is anonymized.

Okay gotcha, what was confusing me was how we could randomize it and preserve the relationships of the cards at the same time, but I see at present this shuffle is more like "secure past magic trick" than "secure by cryptography", that makes sense. Or equivalently, we put it into a black box, that flips a secure coin, and either does or doesn't swap the cards. Give thanks you.

Yep sorry, my original diction was confusing, I've tried to analyze that the _shuffle_ is the magic trick, the overall cryptosystem is real.

The only affair that makes sense is keeping the heart red menu in identify and swapping the pinnacle two for the bottom two repeatedly? Anything else could alter the answers? I dont get the practice

No, the club of the cards is preserved. The "cutting" of the deck is just a rotation.

I personally prefer the red ball - green brawl version, where a colourblind person can find out if both balls are the same color or non. Simpler, with fewer variables and still very clean in its explanation.

I don't actually understand this. Who is hiding what from whom? Is the idea that the outside observers can discover that either Alice or Bob said no, but non know which one? Why practice that with 5 cards? Why can Alice and Bob not just hand a unmarried card to you, saying "Aye" or "No". You then mix the cards and reveal them. Now you lot know if there's a "No" but not who said it.

Just using single cards volition let bystanders know when both Alice and Bob say "No". The 5 bill of fare solution makes it impossible to differentiate between when both say "No" and when only i says "No".

While the cryptographic part is easily understandable, what are the practical uses of this scheme? It can only verify half of the bits on average.

You lot could use this to allow ii people that both demand to say "yes" without anyone else knowing who said "no" if the ii yeah doesn't occur. All the same, information technology does leak noesis to Alice and Bob; if either said yeah they will know what the other chose. This is probably unavoidable.

If yous tin can verify half of a set of bits, sometimes you can apply an mistake-correcting code to verify a full prepare of $.25. Or sometimes to verify a property of those $.25. Think of RAID storage. If some drives can't be read, but not too many, you can all the same read all the data.

These days I'chiliad working on "proof of execution" and "proof of data availability", which are an interesting application of zero-cognition proofs to very big sequences of values. The steps aren't revealed, but the rule which the steps must follow is revealed. It's almost magical how information technology'due south possible to prove that N billion steps of a simulated virtual computer, run exactly according to specification, complete with CPU and retentivity, given a particular set of input files (or even a hash of an input) and program (or hash of a program), produces a particular set up of output files. All summarised in a short proof that a verifier can easily and quickly check, so it doesn't have to redo the ciphering itself - information technology tin trust the outputs it receives, due to the proof.

Does this hateful we could have cryptocurrencies with proof-of-work mechanisms that perform useful work? Y'all could have a decentralised crowd sourced general supercomputer which could perform folding-at-home, neural network preparation etc. and you could get paid for it with no middleman?

Sort of, yeah, merely doing that would exist a waste material of energy, compared with altruistically donating your cycles like in folding@home. The price of proving execution is loftier compared with the cost of execution without proof. (Even in a dedicated proof-of-execution hardware CPU, which by the way I'1000 also working on a petty, in example someone out there finds themselves looking to rent someone doing this sort of thing ;-) On the other hand, for proof-of-stake and similar systems, these kinds of proofs completely change the dynamics because there is no need for every node to duplicate all the land auto updates. Current blockchains have hundreds or thousands of total nodes, each of them executing the same lawmaking to verify the behaviour is the same. They can have proofs instead, and then that executions are done by only a few nodes. That greatly changes the scaling toll. With a few more tricks information technology starts to look more like a giant CRDT with lightweight nodes maintaining simply a "view" of the office they are interested in, and some more tricks on top of that for latency hiding, it starts to wait more real-time, every bit in MMO levels of interactive operation, not the blockchain you lot are used to.

> The cost of proving execution is high compared with the cost of execution without proof. What ratio are we talking virtually here roughly? Is is x% higher or 1000x college?

Roughly, closer to 100x-10000x than +10%. GPU vs CPU vs FPGA vs ASIC makes a lot of deviation. New algorithms are being discovered or developed that improve the speed. I think we may see roughly 10x in the next few years on ideal hardware for the task, just the economics might not be there to pay for building it.

Can you accomplish something similar by having multiple (e.g. 5) randomly chosen nodes perform the aforementioned adding and compare their results? Or is at that place always a way effectually that?

That'due south a dissimilar sort of proof, the computer equivalent of social proof. It's not equally cryptographically stiff equally zip-knowledge proofs tin can exist. Those five nodes could all be dishonest, unless you know they are not. Whereas you don't accept to trust a zilch-noesis prover at all. A dishonest prover will "always" be detected (for a definition of "always" similar to full general cryptography, i.east. extreme probabilities). Zk proofs (of the type I'm using) are more similar fancy hash functions, where in that location'southward one right respond and no node-specific key. Unlike, say, TLS PKI where you accept to obtain certificates and trust detail nodes. (There are sometimes keys in zk, chosen "trusted setup", but those keys are computed in distributed ceremonies and shared with anybody.) That said, there are some interesting tricks, similar to your idea, for distributing a zk computation amid nodes who cross-verify-and-evidence each other's work without needing to trust each other, reducing the amount of work per node and perhaps latency. You exercise need the social proof blazon as well in practice. The zk proofs affirm some fact which may accompany data, and some clever networking protocols can build on that, like proofs of (contempo) data availability. Simply for consensus protocols, the zk proofs don't tell you which of those facts everyone is collectively agreeing to. For that, comparing results is required. In blockchains where the p2p networking is automated, typically there'southward an assumption that your node will find at least one honest node with respect to the consensus, or some small number, and their information will outweigh bad data from other nodes. While bootstrapping more honest nodes are required than afterwards, when following a networking in its live state. But at that place's always a possibility that a node is only able to connect to a coordinated group of dishonest nodes, particularly if someone is hacking the network aroud the target node, east.g. by affecting the routers. That's chosen an eclipse set on. Note: I keep talking about blockchains because you asked about PoW, and that's where a lot of the zk proof of execution and proof of data availability stuff is focused these days, and information technology'south a natural fit when multiple nodes and networking get discussed. Just there are many non-blockchain uses likewise!

Tank you lot for your fourth dimension, it'southward very interesting stuff! What are the non-blockchain uses of zk proofs?

IMO the strongest applications are blockchain-related, only here are some other ideas which have been suggested - - One can selectively disclose certain aspects of their identity. Due east.k. given a delivery to my Dna, I tin can prove that it doesn't match that of a suspect. (Though the police force demand some manner to trust the commitment, possibly a signature from the firm that sequenced it.) - We tin can build trustless games, similar an implementation of battleship where cheating is cryptographically hard. - We could take trustless ciphering services, similar ec2, or like SETI@home, etc. Though it's difficult to brand this practical given the computational overhead of ZKPs. - ZKPs tin can turn any delay function (like an iterated hash) into a verifiable delay office (VDF). VDFs could enable trustless lotteries/sortition. - Given a general-purpose ZKP, it'south fiddling to build a signature scheme, e.k. by proving knowledge of a hash pre-image. This tin sometimes lead to very practical signature schemes, such every bit Picnic, one of the leading hash-based signature proposals. Ring signatures are another generally-useful awarding. - I think ZKPs take also been used as a building block in some FHE and MPC systems, though I don't know much most those areas. - One tin show the existence of an exploit earlier divulging the details. This might exist useful for e.g. convincing anybody to disable a sure TLS primitive which was just broken.

Yes. Also networks that perform unproblematic versions of useful work exist today. I work on a network which uses zk proofs to check storage of user input data and pays out blockchain consensus rewards accordingly.

Yes, like Cairo. In fact I almost applied to a job working with Cairo recently, but I was told someone else had just started it. It's possible to build more standard CPUs as well which use ordinary arithmetics, logic and retention, at some cost to efficiency. Just the toll is almost entirely borne by the prover.

As a beginning I suggest y'all look at whatever is written about SNARK and STARK in the Ethereum globe. Vitalik Buterin's blog has some proficient technical manufactures (literally look for those words in the titles). They don't cover proofs of CPU-like systems, though. In that location are a lot of other articles, papers, etc. I'one thousand just suggeting those search terms as a starting point. The Cairo organization from Starkware is a pretty good, modern CPU-like arrangement (admitting using finite fields and an unusual CPU model, instead of normal numbers), which is simpler than its predecessors in some ways because the techniques have matured and they have been able to utilize techniques devised past many unlike R&D groups before that iteration. As far as I'm aware, still, performance at the billions of steps level is more on the frontier. I'd beloved to share details of what I've been working on, and I hope I volition be able to i day. I problem is I'm looking for work, and there's an interesting company I'm negotiating with merely their view of IP may preclude me from publishing my own piece of work in this area later I've started. Meanwhile, I haven't published nonetheless, even though I've done a lot of work on it. I do not similar this, I e'er desire to share, but...

I mean when you go to the point where your kids are asking almost cipher-knowledge protocol instead of a new iphone...

The explanation I read used Finding Wally as an example: I can put a piece of paper with Wally'south silhouette cutting off in front of the book. Align Wally to fit into the silhouette and you're done! The paper just needs to exist considerably bigger than the actual book, and then other people can tell I know where Wally is without actually knowing his location.

The network sit-in of knowledge of the secret passage past 40 coin flips appears unnecessarily complicated. Why not only ship Mick downward the left path and show him returning from the right? That straight demonstrates Mick knows a passage from left to correct (at least to all observers at the fork. home viewers withal worry about video editing).

To be a proper zero noesis proof, it mustn't prove to bystanders that Mick knows the secret. With your simple proposal, everyone watching is convinced. In the more complicated version, only the person calling left/correct knows for sure. Every bit far as everyone else knows, Mick doesn't actually know the hugger-mugger and the reporter colluded with Mick to pre-conform a sequence of left/correct calls.

> To exist a proper nix knowledge proof, it mustn't prove to bystanders that Mick knows the secret. Citation needed.

This is the second time I've read this Ali Baba paper and I'yard pretty certain I got hung up on this, too. And I don't see what that property is good for (though I am aware that other people do). Maybe the paper should have a preface. It might piece of work for entertaining someone who already knows all about zero noesis proofs, but it doesn't seem to do much to educate those who do non.

Try whatsoever cryptography textbook! This is the whole point of cipher cognition proofs: that you lot tin can convince someone, all the same they have no evidence (i.e, "cipher noesis") that they can take to another person and expect to convince them.

No, the zero noesis role is that they only acquire that you lot know a secret, only they don't learn anything nearly the hush-hush. Information technology'south not near convincing others.

If you get some slice of show that you can have to others, and so yous do in fact learn something about the secret.

Why should bystanders non know? It seems like Micks proof is an attempt at fame, so he would want everybody to know.

Because it'due south an imperfect real-globe illustration for something used in cryptography

Yeah, I understand why the author wants to turn information technology into a probabilistic argument, merely it doesn't quite work with the circular cavern analogy. Yous need something where the entry and the exits are different, and Mick Ali were able to use his secret to affect the outcome at the exit. What if Mick Ali were going downward one of those twisty waterslide tubes, and could say his clandestine phrase to shunt himself off to a different fork, so he could come out at a different tube get out at the bottom?

if y'all just sent Mick down the left path and he came out the correct, and so a video would conclusively testify he knew the password. And this is why "How to explain cypher-cognition protocols to your children" is probably the worst fashion to explain cypher-knowledge protocols to anyone. Its not explaining what a aught-knowledge proof is or how it works. It's explaining what a simulator is when proving a protocol is nothing-cognition . Oh, and the explanation only works for interactive protocols.

I must take missed something in the telling of this story, because it sounds like their just cheating.

I think the point is, that a nil knowledge proof only works between 2 parties, the proofer and the verifier. If I want to proof something to you lot I cant just say "Hey I showed it to Bob over there. Inquire him if I'chiliad telling the truth." But that doesnt really come through in the analogy.

> I think the point is, that a nix cognition proof only works between two parties Ah! I did non get that role of it. Thank you for clarifying. I don't think the story made that role clear enough. For instance, in the epilogue it says "Countless people saw Mick Ali on television receiver, and he became famous." But, as you say, one of the main points was that watching information technology on boob tube shouldn't take been enough to convince the viewers at dwelling. They could have been watching the faked version. Information technology would take been clearer if the epilogue had said "Endless viewers saw Mick Ali on television and remained skeptical, merely the reporter himself was convinced Ali must accept been telling the truth."

Yes, yous must have missed something. If you want someone to help clarify it for you and so you'll need to be more specific. Who exercise you recollect is adulterous? How do you think they are cheating? Why practise you think they are cheating? And then on.

... unfortunately I didn't sympathise how this story relates to nothing-noesis protocols....

Source: https://news.ycombinator.com/item?id=32951001

Share this post