Zero-knowledge proof of knowledge without replay

Question

Given a hash function:

$H(x)$ = y

$y$ is publicly known.

Alice wants to prove to Bob that she knows $x$. Alice could create a non-interactive zero-knowledge proof, and share it with Bob. Then Bob could verify that Alice has a valid $x$.

The protocol is describe here: https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

Now suppose that Bob wants to prove to Carol that he knows $x$. Bob could re-send the same proof that Alice sent to him, even though he doesn't know $x$.

Is there any way to create a proof that cannot be replayed by a malicious verifier?

Answer 1

"She knows" has a definition: an extractor algorithm should exist that produces the witness $x$ while talking to the proving party in place of verifier. For zk-SNARK from Christian Lundkvist in the medium post you referenced, the protocol is non-interactive and the "proof of knowledge" is derived from the "knowledge of exponent assumption", not from the extractor algorithm. It seems there's a consensus that both definitions are good enough.

My point is, a non-interactive "proof of knowledge" is very different from an interactive one. It seems it was a design choice that zk-SNARK proofs should be verifiable by everyone without interaction.

There's a chance with a designated verifier (introduced in late 80s). As a setup, the potential verifier sends some hash $t$ to prover and runs this protocol to show he knows the witness $s$ for that additional hash: $H(s) = t$. The prover then runs a protocol to show his knowledge of either one of two preimages ($s$ or $x$). This could mean a circuit representing equations: \begin{gather*} z (1 - z) = 0 \\ H(zs + (1 - z)x) = zt + (1 - z)y \end{gather*} It follows only that a verifier that keeps his $s$ secret can be assured original statement $H(x) = y$ is true.

Make a protocol interactive again :)