Zero-Knowledge Proofs

[baby]

IMO 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-explanat... and in my book https://www.manning.com/books/real-world-cryptography?a_aid=...

They’re going to change the world, not just for privacy, but for compression.

[rstuart4133]

I just wanted to say a big thank you for that page. I've read a few explanations of ZKP's, of the Ali Baba map type and now this map colouring explanation, and I came away none the wiser.

Well, wiser were wiser means "I build another ZKP". The map colouring explanation was actually more confusing than helpful, as anybody who has attempted to colour a map with just three colours knows you often have the entire thing coloured in, except for one problematic vertex which may be one vertex among billions. If you reveal 20 vertexes at random out of a billion, the odds of finding the proof the problem wasn't solved is worse 1 in 10e5, which isn't a proof of anything.

Your page revealed there are lots of ingredients needed to make ZKP's work. Mapping the problem proving some knowledge about a function being the first step, and one you would never guess from the simplistic descriptions. But by far the most surprising one to me is they (or at least ZK-SNARK's) use homomorphic operations. Homomorphic operations are often in the news (most recently a toolkit from Google), but are so slow (from what I can see about 10e9 times slower than doing the same thing without homomorphic operations) I couldn't imagine a real world use case. But here, right under my nose, are homomorphic operations being used in the real world. And no general purpose toolkits were needed.

[rocqua]

A ctrl-f on the article did not find compression. Can you explain how zero knowledge proofs are going to help compression?

[Ar-Curunir]

FWIW, 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]

Do you have a more up-to-date link/source?

[clashmeifyoucan]

Another 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

[0]: https://news.ycombinator.com/item?id=24815649

[toolslive]

best intro is still this paper: "How to explain zero-knowledge Protocols to your Children";

https://www.researchgate.net/publication/221355016_How_to_Ex...

[rocqua]

I 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.

[knownjorbist]

Wikipedia gives 11 different links for MPC under "Computers and Electronics". Which is this? Massively Parallel Computing?

[Vervious]

A 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).

[Ar-Curunir]

For many existing MPC protocols, ZKPs are overkill for achieving malicious security, and more efficient approaches exist (eg: information-theoretic MACs)

[throw2500]

The 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".

[tylersmith]

You 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]

What are "ZKPPs"?

[maverick-iceman]

ZK 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]

Is 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?

[koheripbal]

Which coins currently use it besides Monero?

[tylersmith]

ZKPs 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.

[SheinhardtWigCo]

What sort of computations are you excited about?

[gjvc]

http://srp.stanford.edu/

[transitory_pce]

Great, one more thing to add to my never ending list of things I want to get good at.

[adamgluck]

Mina protocol is a cryptocurrency that just launched leveraging ZK Snarks. Will be interesting to see what happens with that technology.

[baby]

For anyone interested: 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).

[diplodocusaur]

the best ELI5 for a ZKP I've found follows

[0] https://medium.com/swlh/a-zero-knowledge-proof-for-wheres-wa...

[paulgerhardt]

I’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.

[politician]

I don’t understand why non-interactive zero-knowledge proofs are worth trusting (in the cryptocurrency context of ZK-SNARKs and friends).

[a1369209993]

For the same reason public-key signatures are worth trusting: if correctly designed and validated, it's computationally intractable to construct one without the information (private key or otherwise) being proved. (You do lose the inability of coparties to prove that you know the thing, but that's not always a problem.)

[tylersmith]

Why 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.