0
$\begingroup$

Suppose the circuit is a hash function with the input being the pre-image (private) and the output being the digest (public). If one knows of a collision can they create 2 different proofs that are equal bit-for-bit by inputting the 2 different pre-images that give the collision?

It seems such a SNARK does not exist at the moment because when the Fiat-Shamir transform is used there is an opening of a polynomial at a certain point which is a function of the witness, so the final proof is also a function of the witness.

Improve this question
$\endgroup$
1
  • $\begingroup$ If replacing "the same proof" in your question with "the same statement", the answer is yes. $\endgroup$
    – X.H. Yue
    Commented Jul 10, 2023 at 6:59

1 Answer 1

Reset to default
0
$\begingroup$

A necessary condition for non-trivial (details below) zero-knowledge proofs is that they are probabilistic. Producing two proofs for the same witness will lead to different transcripts, so this also holds for two proofs with different transcripts.

Intuitively, if the proof is deterministic, then the verifier can know that two provers proving the same statement used the same witness. This is already a problem. The technical reason is that anything that would be provable this way could be efficiently computed by the verifier without the help of the prover. See section 4.5 of this paper by Goldreich and Oren if you're interested in the details.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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