Understanding Zero-knowledge proofs through illustrated examples
I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1):<p>> We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition.<p>But that's <i>not</i> completeness in the metamathematical sense. That's a statistical boundary on what it takes to "convince" someone (or "gain knowledge"). But that's a stochastic redefinition of a pretty hard-line property of proof systems. In other words, you could theoretically have no knowledge and just get astronomically lucky to an arbitrary degree (whatever degree it would take to cross that proof threshold).<p>[1] <a href="https://crypto.stanford.edu/cs355/18sp/lec3.pdf" rel="nofollow">https://crypto.stanford.edu/cs355/18sp/lec3.pdf</a>