12 ms·
Zero-Knowledge Proofs
- tylersmith 5y agoZKPs are a really exciting crypto primitive. They're finally getting serious development for the cryptocurrency space, but I think we'll see them used in all sorts of protocols over the next decade. One possibility I'm excited about is users being able to perform computations locally without sending their data anywhere, and then providing the results to a company, government, etc with a proof that the results are faithful.
- gjvc 5y agohttp://srp.stanford.edu/ http://srp.stanford.edu/
- teryyy 5y agohttps://blog.cryptographyengineering.com/should-you-use-srp/ https://blog.cryptographyengineering.com/should-you-use-srp/
- SheinhardtWigCo 5y agoWhat sort of computations are you excited about?
- tylersmith 5y agoThings like proving sufficient income to apartments without giving them my paycheck info, better privacy in credit reporting, more privacy-conscious advertising. I worked with the Brave team to sketch out how the latter could be done in their system. It's 1 of 10 proposals and iirc half are using ZKPs to reduce information given to advertisers.
- Ar-Curunir 5y agoEg: (1) This is my credit score, certified by XYZ agency, so please don't ask for my SSN so that you can lose it in a public database leak tmrw (2) Here's a bug in your program, please give me the bug bounty and I will tell you the bug (can help stop sketchy bug bounty programs.) (3) Your Certificate Transparency Provider can prove that, for the latest root, there was no change in your certificate. (This has less to do with privacy and more to do with the succinct verification properties of the latest zkps) (4) Construct postquantum-secure signatures (eg: the Picnic signature scheme) Generally, ZKPs provide selective disclosure: I can prove to you that some fact about me or my accounts is true, without revealing to you any other information. The SSN example is one, you could generalize that to taxes, bank statements, Keybase attestations, etc.
- tylersmith 5y agoGreat examples, and great point. The real magic is in computational integrity proofs and selective knowledge reveals is just a (realy great) feature.
- 0FreedomInUSA 5y agothese definitely are "magic internet applications"
- SheinhardtWigCo 5y agoI’m not seeing how 1 and 2 are directly enabled by ZKPs. In the credit score example, “this is my credit score certified by XYZ” is solved without ZKPs, no? And in the bug bounty example, how does one use a ZKP to prove knowledge of a software bug without leaking any information about it? That sounds fascinating. 3 seems cool but not particularly impactful in terms of the guarantees offered by CT. 4 can be achieved in many ways without ZKPs.
- jude- 5y ago(1) with zkps, you can run the credit check (or any sensitive computation) locally, and export a proof that demonstrates that your credit score is X as calculated by credit algorithm A without revealing your sensitive financial data. (2) As the bug bounty claimant, I compile the program into the zkp proof, run the program with the bad input that leads to the exploited state, and submit the witness to the code author that proves that I know of an input that causes the code to reach an undesirable state (without revealing it).
- noman-land 5y agoGod, I love ZKPs. So much neat stuff you could do. You could prove you're of legal drinking age without having to show a stranger your ID full of sensitive info. You could prove you "liked" a band before a certain date and therefore get discounts on merch or show tickets or something. New ideas come to me every day.
- rocqua 5y agoI think ZKPs will find most of their use in proving MPC protocols were correctly followed. In these protocols you often need everyone to do certain steps correctly to prevent cheating or deadlock. But sharing the information behind those steps reveals way too much data. Often ZKP can be used to prove those steps were correctly followed.
- Ar-Curunir 5y agoFor many existing MPC protocols, ZKPs are overkill for achieving malicious security, and more efficient approaches exist (eg: information-theoretic MACs)
- knownjorbist 5y agoWikipedia gives 11 different links for MPC under "Computers and Electronics". Which is this? Massively Parallel Computing?
- a1369209993 5y agoProbably multi-party computation.
- oh_sigh 5y agoMulti party computation IE compute F(x,y,z) where I have x, you have y, and dang has z, and none of us want each other to know what our values are.
- Vervious 5y agoA correct Multi-party computation protocol (MPC) by definition is private. MPC from its inception has used zero-knowledge proofs as a building block (i.e. see the GMW compiler from the 1980s) (though other approaches exist).
- maverick-iceman 5y agoZK Snarks is where it's at for crypto. Every cryptography gives the cryptographer an immediate asymmetrical advantage, and that's necessary given crypto's adversaries. Said cryptography advantage cannot be wasted by centralizing the social environment where people exchange the tokens Crypto exchanges are the singular main point of failure and that is true for both centralized and de-centralized exchanges
- legutierr 5y agoIs there a third type of exchange that I am not aware of, other than centralized and decentralized exchanges? How else would people exchange tokens but through a crypto exchange? Are you saying people shouldn’t exchange their crypto?
- maverick-iceman 5y agoThe same way people buy stuff like marijuana, prostitution, alcohol where all those things are illegal, except people who have those preferences are few and far in between, whereas everybody and their brother is afraid of inflation, debasement and be diluted by the government and the Fed with the excuse of economic recovery. My prediction is that over time people would simply find a btc dealer and pay them with wire transfer and lie to their bank about the reason of the transfer Same thing with Paypal, credit cards etc. Every regular business is a potential dark crypto exchanger where a person goes there (either physically or online) and there is a tacit deal that they'd pay money but the business won't provide them any goods or services, they'd send them cryptocurrencies instead. That's what true decentralization looks like, a global opaque market where each transaction ought to be negotiated individually between 2 parties. LocalBitcoins.com tried, but people preferred the convenience of exchanges such as coinbase, they'd have to learn the hard way when government cracks down on those. That's really unstoppable, you can never shut it down A huge benefit is also that there would not be an notorious and advertised global price which people can point at and become envious about those who bought bitcoin at 0,01$. Those people are the biggest opposition to BTC/crypto. Not the environmentally concened, but those who think they missed the boat and and now want to gang up on crypto to destroy other people's gains and re-establish parity. Many environmentally concerned are just envious people who use the environment as the excuse , but they really can't stand the wealth differential which emerged between themselves who missed the boat and the early adopters.ff
- politician 5y agoI don’t understand why non-interactive zero-knowledge proofs are worth trusting (in the cryptocurrency context of ZK-SNARKs and friends).
- tylersmith 5y agoWhy not? They're still fairly experimental but many world class cryotographers are working on them and haven't found show stopping issues. If your concern is trusted setups, those are quickly being phased away by better constructions that are fully transparent.
- politician 5y agoThe explanations for interactive proofs are compelling, but the non-interactive variants are confusing. I don't understand how an infinite series of queries can be replaced by a static construction. If you've got some resources that you'd be willing to share, I'd appreciate it.
- rocqua 5y agonon-interactive proofs set an acceptable failure level. Because of this, some people call them "arguments". Generally, the chance of failure is set to something like 1 in 2^256. Which is low enough to be totally trust-worthy. When talking about this chance of failure, you have to take into account that an attacker can try to repeat as often as he wants. If you presume he has 2^64 attempts (which is unreasonably high) then his chance of finding a correct proof would be 1 in 2^192. Which is still truly negligible. This wiki page: https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic Has a nice explanation but I figure you've seen that already. In short the idea is: - Set an acceptable chance of failure (like 1 in 2^256) - Trust the output of a hash function to be random (random oracle model) - Use the hash function to derive the "challenges" normally made a by an interactive verifier based on the commitment Because the challenge(s) are chosen according to the random oracle (hash function) they are random. So it is impossible for the attacker to pick his commitment based on the challenge.
- 5y ago
- throw2500 5y agoThe page seems a bit too heavily weighted towards SNARKs in particular and cryptocurrency applications in general. There's no mention of ZKPPs, for instance. Not all crypto is "crypto".
- Ar-Curunir 5y agoWhat are "ZKPPs"?
- X6S1x6Okd1st 5y agoPossibly Zero Knowledge Password Proof?
- someguyorother 5y agoThat sounds right. A zero-knowledge password proof is a way for one party to prove to another the knowledge of a password, without revealing anything else about the password. Such a protocol prevents an attacker (eavesdropper or man in the middle) from brute-forcing the password offline even if they capture the whole exchange, so insecure passwords become much less of a risk as long as the verifier rate-limits login attempts on its end. Some of these also have the property that a malicious verifier can't fake a success unless it already knows the password, thus making password phishing pretty much pointless: the only thing a phisher can verify is whether the user uses some predetermined password, and if not, the user is immediately made aware that the site expected another password. IIRC, the most recently developed ZKPP is OPAQUE: https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/ https://blog.cryptographyengineering.com/2018/10/19/lets-tal...
- tylersmith 5y agoYou are right that ZKPPs are a type of ZKP. Wikipedia appears to disagree with us, but I maintain we're right for any reasonable definition of ZKP. That said, this page is implicitly focused on ZK computational proofs for general computations. It's also fairly out of date at this point.
- Ar-Curunir 5y agoFWIW, this website is out of date; there's been enormous improvements in zkp constructions and applications in the intervening 2 years. (This is not a slight against the maintainers; the space is moving incredibly quickly, so it's difficult to keep updating regularly.)
- eruleman 5y agoDo you have a more up-to-date link/source?
- SkyMarshal 5y agoHere's one, a podcast that tracks developments in ZKPs: https://www.zeroknowledge.fm/ https://www.zeroknowledge.fm/
- dlubarov 5y agohttps://github.com/matter-labs/awesome-zero-knowledge-proofs https://github.com/matter-labs/awesome-zero-knowledge-proofs is more up to date.
- transitory_pce 5y agoGreat, one more thing to add to my never ending list of things I want to get good at.
- adamgluck 5y agoMina protocol is a cryptocurrency that just launched leveraging ZK Snarks. Will be interesting to see what happens with that technology.
- baby 5y agoFor anyone interested: https://minaprotocol.com/ https://minaprotocol.com/ It compresses the whole history of the blockchain into a proof of less than 21KB using recursive zero knowledge proofs (each block has a proof that the previous proof is valid).
- kreetx 5y agoCan you decompress that 21KB to the entire transaction history? I.e does this qualify as real compression, or is it the equivalent of a hash?
- Datagenerator 5y agoNo, it's just the latest valid checksum afaik
- baby 5y agoIt’s not “real” compression. It’s a proof. So it is one way.
- diplodocusaur 5y agothe best ELI5 for a ZKP I've found follows [0] https://medium.com/swlh/a-zero-knowledge-proof-for-wheres-wally-930c21e55399 https://medium.com/swlh/a-zero-knowledge-proof-for-wheres-wa...
- paulgerhardt 5y agoI’m sad to see that analogy become so popular over the last year. It fails to capture the tremendous amount of work that is required to establish or verify proofs. In the Waldo example verification is O(n). I’ve worked on other analogies but every simplification is damning in its own way. One I particularly like: You want to ask Google for directions to an address in your small town but you don’t want Google to know where you are going or where you live. Instead you ask for a list of directions between every address in your small town. It takes a bit longer to return these results but the it satisfies the conditions. This isn’t of course how ZKP’s work but directionally captures their computational overhead in a way other examples don’t.
- krackers 5y agoThe best example is to show the actual zero-knowledge protocol for something simple, e.g. graph isomorphism. The protocol is short enough that anyone looking at it can intuitively understand correctness, and from there it's not much further to verify the zero-knowledge property either.
- knownjorbist 5y agoIs there an example of this in practice anywhere...?
- bluepnume 5y agoThe Waldo example is more an explanation of "what" a ZKP is than "how" a ZKP works. Not a terrible starting point, but yep, definitely doesn't capture the complexity of the real deal.
- clashmeifyoucan 5y agoAnother nice resource for understanding zk snarks that I found easily digestible was this paper that was shared on hn a few months ago[0]. https://arxiv.org/abs/1906.07221 https://arxiv.org/abs/1906.07221 [0]: https://news.ycombinator.com/item?id=24815649 https://news.ycombinator.com/item?id=24815649
- baby 5y agoIMO these zero-knowledge proofs are the most interesting stuff you can work on in the field of cryptography at the moment. I wrote a bit about them here https://www.cryptologie.net/article/507/the-missing-explanation-of-zk-snarks-part-1/ https://www.cryptologie.net/article/507/the-missing-explanat... and in my book https://www.manning.com/books/real-world-cryptography?a_aid=Realworldcrypto&a_bid=ad500e09 https://www.manning.com/books/real-world-cryptography?a_aid=... They’re going to change the world, not just for privacy, but for compression.
- rocqua 5y agoA ctrl-f on the article did not find compression. Can you explain how zero knowledge proofs are going to help compression?
- openfuture 5y agoDo you think cryptographic hash functions are a means to compression? Zkps are just hashes that can hash the execution of code rather than hashing static data ("dynamic hashes"?)
- maayank 5y ago> Zkps are just hashes that can hash the execution of code rather than hashing static data ("dynamic hashes"?) That's actually a great intuitive explanation. I'm stealing that.
- rocqua 5y ago> Do you think cryptographic hash functions are a means to compression? No. I think I am missing some core idea here. All I can come up with is a backing store of files (or blocks of files) indexed by hash. Then you can store the hash (or chain of hashes if working with blocks) to represent the file. I wouldn't call that compression though, because you still need the underlying backing store. It could lead to something like compression if you have lots of duplicate blocks. Something like tarsnap uses for efficiently keeping incremental backups. But, compression wise, just handling repeating blocks is rather rudimentary. I guess the above idea isn't what you had in mind though.
- toolslive 5y agobest intro is still this paper: "How to explain zero-knowledge Protocols to your Children"; https://www.researchgate.net/publication/221355016_How_to_Explain_Zero-Knowledge_Protocols_to_Your_Children https://www.researchgate.net/publication/221355016_How_to_Ex...