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.
(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.
I’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.
(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).
Things 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.
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.
For many existing MPC protocols, ZKPs are overkill for achieving malicious security, and more efficient approaches exist (eg: information-theoretic MACs)
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).
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?
The 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
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.
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.
The 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.
non-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.
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.
The interactive version works not because the verifier is making the queries, but because the prover is not. The intuition behind making an interactive protocol non-interactive is use unbiasable queries that can be predicted ahead of time used hashes for pseudo-randomness.
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.)
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).
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.
The 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.
The 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.
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
> 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.
Not all zero knowledge proofs offer compression, or small proof sizes. You can have linear sized proofs with useful properties, eg, zero knowledge. Indeed, the first ZKPs weren't concerned with succinctness at all.
How can you prove something about what happens in the real world with some computer program? Okay we run some hash once and then I go chuck the hard drive in a smelter.
You’re most likely referring to recursive zero knowledge proofs or zero knowledge proof composition, where a proof can verify proofs that can verify proofs. Which I don’t explain here unfortunately :)
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.
They use additive homomorphic functions, not fully homomorphic functions, which is the one you’re talking about. If you only support one type of operation instead of two (+ and x) then it’s pretty straight forward (even RSA was additively homomorphic)
66 comments
[ 4.3 ms ] story [ 148 ms ] threadOne 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.
(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.
3 seems cool but not particularly impactful in terms of the guarantees offered by CT.
4 can be achieved in many ways without ZKPs.
(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).
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.
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.
Often ZKP can be used to prove those steps were correctly followed.
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.
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
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
Zcash does, and they are planned to be implemented on Ethereum
Not all crypto is "crypto".
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-tal...
That said, this page is implicitly focused on ZK computational proofs for general computations. It's also fairly out of date at this point.
On second thought, whilst that might be colloquially true. It might not meet the actual definition. An extractor might be hard to build.
(This is not a slight against the maintainers; the space is moving incredibly quickly, so it's difficult to keep updating regularly.)
If your concern is trusted setups, those are quickly being phased away by better constructions that are fully transparent.
If you've got some resources that you'd be willing to share, I'd appreciate it.
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
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.
https://en.m.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristi...
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).
[0] https://medium.com/swlh/a-zero-knowledge-proof-for-wheres-wa...
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.
[0]: https://news.ycombinator.com/item?id=24815649
They’re going to change the world, not just for privacy, but for compression.
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.
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.
That’s an interesting way to put it!
Not necessarily =)
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.
https://www.researchgate.net/publication/221355016_How_to_Ex...