zlacker

>>doomro+(OP)
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...

>>bobbie+yc
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.

>>JanisE+un
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.

>>deegle+2y
Is that "Draw a Waldo with this outline"?

>>goopyp+sB
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.