5
$\begingroup$

I'm reading Matthew Green's great blog, especially the Zero Knowledge Proofs: An illustrated primer post and I'm wondering what is the difference between completeness and soundness?

In the post, there is this part:

  1. Completeness If Google is telling the truth, then they will eventually convince me (at least with high probability).
  2. Soundness Google can only convince me if they're actually telling the truth.

Can I have some explanation? I don't understand the difference.

Improve this question
$\endgroup$
2
  • $\begingroup$ A system where the verifier always accepts is complete. Google does (among other things) convince you if they're trying the truth. Is it sound though? $\endgroup$
    – Maeher
    Commented Jun 12, 2018 at 23:07
  • 1
    $\begingroup$ Completeness = "statement is true $\Rightarrow$ I become convinced" // Soundness = "I become convinced $\Rightarrow$ statement was true" $\endgroup$
    – Mikero
    Commented Jun 12, 2018 at 23:58

1 Answer 1

Reset to default
10
$\begingroup$

The two notions are not specific to ZK, so it is in fact better to try to understand it in the context of general proof systems.

Soundness: the proof system is truthful, so whatever it proves, it is true.

Completeness: the proof system is comprehensive, so it can prove all true statements.

You can have completeness without soundness: if the proof system proves everything including falsity, obviously it is complete but not sound.

You can have soundness without completeness: if the proof system proves nothing, obviously it is sound (after all, it never proves any falsity), but not complete.

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.