| I'm confused on multiple fronts. My understanding is that ZKPs require you to prove only to the verifier that you have the secret information. If proof is convincing to the whole world, that's "too much knowledge" for ZKP. See the Wikipedia article [1] where they use the example of the ring cave with a wall halfway through that requires a secret password. If you wanted to prove to the world that you have the secret, it's enough to go in the left side and come out the right (or vice versa). But that isn't (traditional) ZKP because it proves to everyone that you can bypass the wall. Thus (per discussion page), they have to use a more complicated example, where no one gets to see which side you went in, and the verifier calls out which side you must come out of. [2] In that case, it's only convincing to the verifier. Everyone else (for all they know) can't rule out the possibility that the verifier told you which sides they'd call in advance, allowing you to always go the side that doesn't require you to bypass the wall. OTOH, maybe zcash-style currencies aren't zero-knowledge in that (stronger) sense, because you are trying to convince the whole world of something! That's also why ZKPs have the general format: A) randomize the problem, B) split the knowledge into two pieces where each is useless by itself, C) commit to each piece, and D) allow the verifier to pick which piece you must reveal. How would that work with your Waldo example? Something like: 1) Prover puts a picture behind the cardboard in a position they can't change. 2) Verifier chooses which challenge to give: A) Take off the cardboard and reveal the original picture. B) Punch a hole where Waldo is. 3) Repeat until verifier confidence is high enough. Only a legit prover can always pass. A faker can pass if they cheat and use a fake picture only when the verifier chooses B. (Edit: or if the verifier always picks A) This is not convining to people other than the verifier because they can argue "Come on, you could have told the prover which stream of options you'd take." [1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B... [2] Each time you play, you have a 50/50 chance to pass by dumb luck, but the odds of passing every round decay exponentially in the number of rounds. |
1. Create a series of n problems P, based on some secret S, and and publish them. 2. Get some source of randoms everyone can trust, such as PRF(P) where PRF is some expensive secure hash function 3. Publish the proof of knowledge revealing the the piece specified by the random source.
Anyone can create P but only someone with knowledge of S can tractably pass step 3 because being able to do so implies either being able to predict the output of the hash function in which case the PRF is insecure or or getting winning 2^n coin tosses even if an attacker has an infinite pool of half revealed challenges he can pull from.