soundness and completeness

Completeness and soundness are the two promises every proof system must keep, and they pull in opposite directions. Completeness says: if the statement is true and the prover is honest, the verifier will accept — no honest party is ever wrongly rejected. Soundness says: if the statement is false, no prover, however cunning, can make the verifier accept except with negligible probability — no liar is ever wrongly believed. A protocol that always accepts is trivially complete but useless; one that always rejects is trivially sound but useless. A real proof system needs both at once.

The probabilities matter. Completeness is often perfect (probability 1), while soundness is statistical or computational: a single round might let a cheater succeed with probability 1/2, so protocols repeat or use large challenge spaces to drive the soundness error down to something like 2^-128, astronomically small. There is also a stronger flavor relevant to blockchains: knowledge soundness, which says a convincing prover must actually know a witness (an extractor could recover it) — not merely that one exists. This is why these systems are called arguments of knowledge, the "K" in SNARK and STARK.

The distinction between statistical and computational soundness separates whole families of systems. STARKs offer statistical (information-theoretic) soundness, secure even against unbounded attackers, which underlies their post-quantum claim. Pairing-based SNARKs like Groth16 offer only computational soundness — secure assuming certain math problems are hard — so a future quantum computer or a broken assumption could undermine them. Zero-knowledge is a third, independent property layered on top: a proof can be sound and complete while revealing everything, or sound, complete, and zero-knowledge.