3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I think you want an interactive instead of a non-interactive ZKP here. $\endgroup$ – SEJPM Aug 26 '18 at 8:41
2
$\begingroup$

"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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.