2
$\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.

$\endgroup$
  • $\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 Jun 12 '18 at 23:07
  • 1
    $\begingroup$ Completeness = "statement is true $\Rightarrow$ I become convinced" // Soundness = "I become convinced $\Rightarrow$ statement was true" $\endgroup$ – Mikero Jun 12 '18 at 23:58
8
$\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.

$\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.