Comment by bobbiechen
6 months ago
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#Ge...) really helped me handwave the math into "mixing easy, unmixing hard".
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.ht...
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.
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.
everyone in this thread needs to read this paper: https://dl.acm.org/doi/abs/10.1145/3411497.3420225
Where’s Waldo as presented isn’t even a proof of knowledge
1 reply →
Is that "Draw a Waldo with this outline"?
3 replies →
Plot twist: In addition to the cutout paper, the prover also brings their OWN picture of waldo, which they always place behind the cutout.
[dead]
Sorry but that is not intuitive for me. You wrote one line of analogy and then went into 4.5 paragraphs of technical explanation.
"The Ali Baba Cave" example from the Wikipedia article is what made it click for me: https://en.wikipedia.org/wiki/Zero-knowledge_proof.
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.
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.
2 replies →
My colleague Amit made a simple video explanation about zkp with Wired. https://youtu.be/fOGdb1CTu5c?si=EyBQS92WyeduIpH-
That doesn't explain the way this scheme works, but it's a nice start.
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.
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).
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-kno...
That's only for interactive proofs though. Like GP I have no problem understanding those.
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.
5 replies →
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.
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?
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.
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?
9 replies →
(1) in this case, an identity issuer provides the source of truth identity information. Examples include state DMV, your passport (you can try "Id pass" in Google wallet), etc.
(2) One of the goals of this project was to layer ZK on top of current identity standards that DMVs already issue, so that gov orgs don't have to change what they currently do to support the strongest user privacy. One example format is called Mdoc.
(3) The user holds the identity information on their device only. No other copies. The user's device makes the zkp proof on-device. This was one of the major technical challenges.
(4) The relying party (eg a website) runs the zk verification algorithm on the proof that is produced by the device to ensure soundness.
(5) Yes, the user can use any compatible implementation to produce the proof. We have open-sourced our implementation and we have a spec for the proof format that others can also reimplement.
If you can achieve RCE on the chip and run arbitrary code without invalidating signatures, does the protocol still stay secure?
If so, what's the point of requiring your implementation to run on a verified secure element? If not, the protocol seems only as strong as the weakest chip, as obtaining just a single private key from a single chip would let you generate arbitrary proofs.
9 replies →
Would something like this be considered a ZK proof? https://crypto.stackexchange.com/questions/96232/zkp-prove-t...
2 replies →
Thanks for the reply. So in theory, I could get this MDOC file and store it on my desktop computer, and use an open-source library whose behavior I can verify, to provide the proof to the website via my web browser. Yeah? This sounds good to me.
8 replies →
Are you trying to say that there’s a signed blob called an MDOC, that happens to have the age and name of the user, and this library allows a website to prove that the provided age belongs to the person with the MDOC, but not also see the name?
3 replies →
It is decentralized. The holder provides the data, which was ultimately provided to them by the government, they're the client. The verifier is the entity that wants to know how old the holder is, the server.
The form are eg things like the JSON Web Token (JWT), Digital Credentials, and the Federated Credential Management API (FedCM).[1][2][3][4][5] The software can be anything since they're expected to use open protocols, so yes, web browsers.[6] Per the Commission, "For remote presentation flows, … the Wallet Instance implements the OpenID for Verifiable Presentation protocol OpenID4VP in combination with the W3C Digital Credentials API."[7]
[1] https://en.wikipedia.org/wiki/JSON_Web_Token
[2] https://github.com/w3c-fedid/digital-credentials
[3] https://w3c-fedid.github.io/digital-credentials/
[4] https://github.com/w3c-fedid/FedCM
[5] https://w3c-fedid.github.io/FedCM/
[6] https://github.com/w3c-fedid/FedCM/blob/main/explorations/HO...
[7] https://eu-digital-identity-wallet.github.io/eudi-doc-archit...
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?
There's a Where's Waldo explanation that I can't find right now but helped me a lot.
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.
Intuition of what it is (ie interface) or how it works (implementation)?