Zero-Knowledge Proofs
zkp.science
zkp.science
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.
(This is not a slight against the maintainers; the space is moving incredibly quickly, so it's difficult to keep updating regularly.)
https://www.researchgate.net/publication/221355016_How_to_Ex...
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.
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.
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
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.
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.
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.
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...