6 ms·

Anyone have a good explanation on the intuition of non-interactive zero-knowledge proofs? For example, I thought the "paint-mixing" analogy for Diffie-Hellman k

Anyone have a good explanation on the intuition of non-interactive zero-knowledge proofs? For example, I thought the "paint-mixing" analogy for Diffie-Hellman key exchange (https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#General_overview https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Ge...) really helped me handwave the math into "mixing easy, unmixing hard". https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... was a good intro for interactive ZK proofs but I haven't been able to find something for non-interactive ones. This blog post comparing ZK-STARKs to erasure coding is in the right flavor but didn't quite stick to my brain either: https://vitalik.eth.limo/general/2017/11/09/starks_part_1.html https://vitalik.eth.limo/general/2017/11/09/starks_part_1.ht...

supernikio2 1y ago
"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof https://en.wikipedia.org/wiki/Zero-knowledge_proof.
- bobbiechen 1y ago
  This is an interactive example, isn't it? It doesn't help me understand non-interactive proofs like SNARKs/STARKs, where the verifier isn't communicating live with the prover.
  - quantumgarbage 1y ago
    Look for the "Fiat Shamir heuristic" to understand the non interactive part. It basically consists in the prover getting its random challenges from hashing public inputs, rather than from the verifier's coin tosses.
    - bobbiechen 1y ago
      Thank you!! If I understand correctly: * The prover commits to a starting value (public input) * Instead of waiting for an interactive challenge, they hash it and use the resulting hash output as if it were a challenge If we believe the hash is a random oracle (as we do for cryptographic hash functions), then it is hard for the prover to manipulate the challenges. Is that it?
      - MatteoFrigo 1y ago
        You got it. There are a few nuisances, e.g. the "theorem statement" must be hashed as well so that proving that name=Mickey has a different oracle than proving that name=Goofy, but your basic understanding is correct.
coldpie 1y ago
Yeah I'm also interested in some of the details here, but the linked library repo is a bit too low-level for my current understanding. For example, in the usecase of providing a proof-of-age to a website: who provides the verification data (the government?); what form does that take (a file in a standard format?); who holds/owns the verification data (the user?); who runs the verification software (the end-user's web browser?). Can the user use any implementation to provide the proof, or must it be a "blessed" implementation such as Google Wallet?
- MatteoFrigo 1y ago
  The specifics depend on local regulations, but roughy speaking: the government gives you a document in a standard format (eg MDOC). Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. The government gives documents to whatever wallet they want, which may be a special government wallet. They may or may not give the document to Google Wallet.
  - coldpie 1y ago
    Thank you. > Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. So it does require a "blessed" implementation, and I have to trust Google or Apple to handle my data? I cannot own the document myself and use an open-source client that I trust to provide the proof?
    - MatteoFrigo 1y ago
      It depends on local regulations. As far as I can tell Europe will require some sort of blessing of the wallet. To be clear, governments will develop their own apps and it's not clear that Google will be blessed. We (Google) are giving them the code pro bono to improve privacy.
      - deleted 1y ago
        [deleted]
abhv 1y ago
My colleague Amit made a simple video explanation about zkp with Wired. https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH- https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH- That doesn't explain the way this scheme works, but it's a nice start.
- JW_00000 1y ago
  This is what I was going to post. It helped me a lot by first giving a very intuitive understanding of the concept of ZKPs using the Where's Waldo/puffin-among-the-penguins example, but then also going deeper with the graph-coloring example.
- icelancer 1y ago
  Was looking to see if someone posted this video. The first few interviews are excellent - the later ones, not so much (in terms of explaining ZK - they're good chats, of course).
tptacek 1y ago
If you're looking for something at the level of paint cans, I think you want Matthew Green's "crayons and hats": https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
- remram 1y ago
  That's only for interactive proofs though. Like GP I have no problem understanding those.
  - _alternator_ 1y ago
    There is a trick to convert an IP to a non-IP. Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability. So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc. Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes. The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
    - tptacek 1y ago
      This is Fiat-Shamir, right?
      - _alternator_ 1y ago
        Correct. I didn’t remember the name, so thanks!
    - remram 1y ago
      It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?
noman-land 1y ago
There's a Where's Waldo explanation that I can't find right now but helped me a lot.
- rrakow 1y ago
  You want to prove to everyone that you know where the Waldo on Page 12 of Where's Waldo In Iceland, so you hold a big white sheet of paper with a hole in it in front of the page such that the hole is centered on Waldo. Then you let your friend see. Your friend now knows that you know where Waldo is, but they still don't know where Waldo is, because they don't know the relative position of the book under the sheet. This is also why they can't use your proof to falsely prove to anyone else that they know where Waldo is too.
JanisErdmanis 1y ago
An intuitive explanation is that of proving you can find Waldo in a picture without revealing his exact location. Digital wallets can be interpreted as fancy signature schemes that operate on third-party issued commitments C instead of public keys that directly link users to their identities. A simple signature scheme is based on proof of knowledge PoK{x : pk = g^x}, which is transformed into a noninteractive variant via the Fiat-Shamir transformation, where the message is appended to the hash. Range proofs work similarly, with the simplest form being for a single bit: PoK{(b,r) : C = g^b * h^r & b(b−1)=0}. This proves that commitment C contains a bit b in {0,1} without revealing which value it is. Arbitrary ranges can then be constructed using the homomorphic properties of commitments. For an n-bit range, this requires n individual bit proofs. Bulletproofs optimize this to O(log n) proof size, enabling practical applications. The commitment C can be issued by a trusted third party that signs it, and the user can then prove certain properties to a service provider, such as age ranges or location zones (constructed from latitude and longitude bounds). A key challenge is that reusing the same commitment C creates a tracking identifier, potentially compromising user privacy.
- deleted 1y ago
  [deleted]
- deegles 1y ago
  for explanation i've seen for the where's waldo analogy: imagine the single page of the where's waldo puzzle, and another giant piece of paper with the shape of waldo cut out of it. by providing a picture of waldo in the cut-out, you can prove you know where he is without providing the location. a zero knowledge proof.
  - goopypoop 1y ago
    Is that "Draw a Waldo with this outline"?
    - cma 1y ago
      Imagine it isn't Waldo, but an unknown figure and you are only given the silhouette to find. If you can draw what's within the silhouette or something, you've proven you've located it to high certainty without saying where. Say the whole image looked like noise and was generated from quantum measurements, and the coordinates to hash for the problem were generated with quantum measurements, and you were given the silhouette and the hash of the noise within to look for. I could see it for proof of work: you could slide along a hashing window and prove you actually did work examining half the image on average or whatever.
orblivion 1y ago
The explanation that one person gave me was basically that you use an RNG to generate the challenges. Not sure if this is quite "proper", but it makes sense to me so long as you can't game the system. Perhaps make the RNG slow to prevent picking a convenient sequence?
notfed 1y ago
Intuition of what it is (ie interface) or how it works (implementation)?
deleted 1y ago
[deleted]
deleted 1y ago
[deleted]
a_tartaruga 1y ago
The surprising part of STARKS and SNARKS comes down to the nature of polynomials. It's surprisingly easy to tell two polynomials apart with a small number of random checks (Schwartz Zippel lemma). In light of this it's not surprising there is good reading comparing them to erasure codes which rely on exactly this property of polynomials. The non-interactive piece is pretty straightforward you just simulate challenge response conversation with unbiasible public randomness and show the transcript (Fiat Shamir transform). Another area worth exploring is how some of these proof systems can have such incredibly small proofs (192 bytes for any computation in groth16 zk snarks). That relies on the much more difficult to intuit theory of elliptic curve pairing functions.

supernikio2 1y ago

"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof https://en.wikipedia.org/wiki/Zero-knowledge_proof.

bobbiechen 1y ago
This is an interactive example, isn't it? It doesn't help me understand non-interactive proofs like SNARKs/STARKs, where the verifier isn't communicating live with the prover.
- quantumgarbage 1y ago
  Look for the "Fiat Shamir heuristic" to understand the non interactive part. It basically consists in the prover getting its random challenges from hashing public inputs, rather than from the verifier's coin tosses.
  - bobbiechen 1y ago
    Thank you!! If I understand correctly: * The prover commits to a starting value (public input) * Instead of waiting for an interactive challenge, they hash it and use the resulting hash output as if it were a challenge If we believe the hash is a random oracle (as we do for cryptographic hash functions), then it is hard for the prover to manipulate the challenges. Is that it?
    - MatteoFrigo 1y ago
      You got it. There are a few nuisances, e.g. the "theorem statement" must be hashed as well so that proving that name=Mickey has a different oracle than proving that name=Goofy, but your basic understanding is correct.

coldpie 1y ago

Yeah I'm also interested in some of the details here, but the linked library repo is a bit too low-level for my current understanding. For example, in the usecase of providing a proof-of-age to a website: who provides the verification data (the government?); what form does that take (a file in a standard format?); who holds/owns the verification data (the user?); who runs the verification software (the end-user's web browser?). Can the user use any implementation to provide the proof, or must it be a "blessed" implementation such as Google Wallet?

MatteoFrigo 1y ago
The specifics depend on local regulations, but roughy speaking: the government gives you a document in a standard format (eg MDOC). Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. The government gives documents to whatever wallet they want, which may be a special government wallet. They may or may not give the document to Google Wallet.
- coldpie 1y ago
  Thank you. > Your phone stores the document, with cooperation from a secure element that binds the document to the phone. The website you visit verifies the proof. So it does require a "blessed" implementation, and I have to trust Google or Apple to handle my data? I cannot own the document myself and use an open-source client that I trust to provide the proof?
  - MatteoFrigo 1y ago
    It depends on local regulations. As far as I can tell Europe will require some sort of blessing of the wallet. To be clear, governments will develop their own apps and it's not clear that Google will be blessed. We (Google) are giving them the code pro bono to improve privacy.
    - deleted 1y ago
      [deleted]

abhv 1y ago

My colleague Amit made a simple video explanation about zkp with Wired. https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH- https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH- That doesn't explain the way this scheme works, but it's a nice start.

JW_00000 1y ago
This is what I was going to post. It helped me a lot by first giving a very intuitive understanding of the concept of ZKPs using the Where's Waldo/puffin-among-the-penguins example, but then also going deeper with the graph-coloring example.
icelancer 1y ago
Was looking to see if someone posted this video. The first few interviews are excellent - the later ones, not so much (in terms of explaining ZK - they're good chats, of course).

tptacek 1y ago

If you're looking for something at the level of paint cans, I think you want Matthew Green's "crayons and hats": https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

remram 1y ago
That's only for interactive proofs though. Like GP I have no problem understanding those.
- _alternator_ 1y ago
  There is a trick to convert an IP to a non-IP. Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability. So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc. Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes. The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
  - tptacek 1y ago
    This is Fiat-Shamir, right?
    - _alternator_ 1y ago
      Correct. I didn’t remember the name, so thanks!
  - remram 1y ago
    It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?

noman-land 1y ago

There's a Where's Waldo explanation that I can't find right now but helped me a lot.

rrakow 1y ago
You want to prove to everyone that you know where the Waldo on Page 12 of Where's Waldo In Iceland, so you hold a big white sheet of paper with a hole in it in front of the page such that the hole is centered on Waldo. Then you let your friend see. Your friend now knows that you know where Waldo is, but they still don't know where Waldo is, because they don't know the relative position of the book under the sheet. This is also why they can't use your proof to falsely prove to anyone else that they know where Waldo is too.

JanisErdmanis 1y ago

An intuitive explanation is that of proving you can find Waldo in a picture without revealing his exact location. Digital wallets can be interpreted as fancy signature schemes that operate on third-party issued commitments C instead of public keys that directly link users to their identities. A simple signature scheme is based on proof of knowledge PoK{x : pk = g^x}, which is transformed into a noninteractive variant via the Fiat-Shamir transformation, where the message is appended to the hash. Range proofs work similarly, with the simplest form being for a single bit: PoK{(b,r) : C = g^b * h^r & b(b−1)=0}. This proves that commitment C contains a bit b in {0,1} without revealing which value it is. Arbitrary ranges can then be constructed using the homomorphic properties of commitments. For an n-bit range, this requires n individual bit proofs. Bulletproofs optimize this to O(log n) proof size, enabling practical applications. The commitment C can be issued by a trusted third party that signs it, and the user can then prove certain properties to a service provider, such as age ranges or location zones (constructed from latitude and longitude bounds). A key challenge is that reusing the same commitment C creates a tracking identifier, potentially compromising user privacy.

deleted 1y ago
[deleted]
deegles 1y ago
for explanation i've seen for the where's waldo analogy: imagine the single page of the where's waldo puzzle, and another giant piece of paper with the shape of waldo cut out of it. by providing a picture of waldo in the cut-out, you can prove you know where he is without providing the location. a zero knowledge proof.
- goopypoop 1y ago
  Is that "Draw a Waldo with this outline"?
  - cma 1y ago
    Imagine it isn't Waldo, but an unknown figure and you are only given the silhouette to find. If you can draw what's within the silhouette or something, you've proven you've located it to high certainty without saying where. Say the whole image looked like noise and was generated from quantum measurements, and the coordinates to hash for the problem were generated with quantum measurements, and you were given the silhouette and the hash of the noise within to look for. I could see it for proof of work: you could slide along a hashing window and prove you actually did work examining half the image on average or whatever.

orblivion 1y ago

The explanation that one person gave me was basically that you use an RNG to generate the challenges. Not sure if this is quite "proper", but it makes sense to me so long as you can't game the system. Perhaps make the RNG slow to prevent picking a convenient sequence?

notfed 1y ago

Intuition of what it is (ie interface) or how it works (implementation)?

deleted 1y ago

[deleted]

deleted 1y ago

[deleted]

a_tartaruga 1y ago

The surprising part of STARKS and SNARKS comes down to the nature of polynomials. It's surprisingly easy to tell two polynomials apart with a small number of random checks (Schwartz Zippel lemma). In light of this it's not surprising there is good reading comparing them to erasure codes which rely on exactly this property of polynomials. The non-interactive piece is pretty straightforward you just simulate challenge response conversation with unbiasible public randomness and show the transcript (Fiat Shamir transform). Another area worth exploring is how some of these proof systems can have such incredibly small proofs (192 bytes for any computation in groth16 zk snarks). That relies on the much more difficult to intuit theory of elliptic curve pairing functions.