zlacker

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

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

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

>>quantu+88
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?

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