4 ms·

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:/

by baby 5y ago

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-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 ago
A ctrl-f on the article did not find compression. Can you explain how zero knowledge proofs are going to help compression?
- openfuture 5y ago
  Do 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.
  - Ar-Curunir 5y ago
    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.
  - baby 5y ago
    > hashes that can hash the execution of code rather than hashing static data That’s an interesting way to put it!
- delaaxe 5y ago
  If it's sufficient to store a proof that you own a large dataset instead of the dataset itself, that obviously takes less space
  - foxes 5y ago
    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.
    - snovv_crash 5y ago
      They can tell you to do the same thing again, but starting with a different "random seed"
  - craftinator 5y ago
    > that obviously takes less space Not necessarily =)
  - remram 5y ago
    That's not compression if you can't use the dataset. All you compressed is the proof.
- baby 5y ago
  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 :)
rstuart4133 5y ago
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.
- baby 5y ago
  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)

by baby 5y ago

rocqua 5y ago

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

openfuture 5y ago
Do 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.
- Ar-Curunir 5y ago
  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.
- baby 5y ago
  > hashes that can hash the execution of code rather than hashing static data That’s an interesting way to put it!
delaaxe 5y ago
If it's sufficient to store a proof that you own a large dataset instead of the dataset itself, that obviously takes less space
- foxes 5y ago
  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.
  - snovv_crash 5y ago
    They can tell you to do the same thing again, but starting with a different "random seed"
- craftinator 5y ago
  > that obviously takes less space Not necessarily =)
- remram 5y ago
  That's not compression if you can't use the dataset. All you compressed is the proof.
baby 5y ago
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 :)

rstuart4133 5y ago

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.

baby 5y ago
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)