[JanisErdmanis]

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.

[deegles]

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.

[yababa_y]

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

[edanm]

I think the Where's Waldo example, while not technically zero knowledge, gives a pretty good intuition of the idea behind it.

It certainly gives a "layperson" example of being able to prove you know something without revealing it, which isn't the whole definition of ZK but is the idea driving it.

[goopypoop]

Is that "Draw a Waldo with this outline"?

[cma]

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.

[goopypoop]

Thanks. So is it really different from "what's (the hash of) word x on page y of the manual?"?

[cma]

I think my example isn't great and would need to be modified like maybe give the hash of a neighboring area to prove you found it, so your answer couldn't be used by others to find the location much more cheaply.

[arcastroe]

Plot twist: In addition to the cutout paper, the prover also brings their OWN picture of waldo, which they always place behind the cutout.

[SavioMak]

Sorry but that is not intuitive for me. You wrote one line of analogy and then went into 4.5 paragraphs of technical explanation.