What are soundness and completeness?

Completeness means an honest prover can always convince the verifier of a true statement. Soundness means a cheater cannot convince the verifier of a false one, except with a negligible chance.

Also called Soundness error.

Completeness

Completeness means that a true statement can always be proved. If the statement is true and both sides follow the protocol, the verifier accepts.

For example, someone who really owns a coin can always produce the proof that spends it.

Soundness

Soundness protects the verifier from a cheat. If the statement is false, a cheating prover cannot make the verifier accept, except with a negligible chance.

A chance is negligible when it is so small that no realistic attempt is likely to succeed. Many systems let the verifier repeat its random checks, and each repetition makes a cheat less likely to pass.

Why both matter

Completeness without soundness accepts false claims, and soundness without completeness rejects true ones. A useful proof system has both properties.

A system whose soundness holds only against cheaters with limited computing power is called an argument. Systems whose soundness depends on hash functions being hard to break are arguments in this sense.

Related terms

Prover and verifierIn a proof system, the prover makes a claim and builds a proof, and the verifier checks that proof. The verifier accepts only a valid proof, so the prover's claim does not have to be trusted.Zero-knowledge proofA zero-knowledge proof lets someone prove that a statement is true without revealing anything else, for example that they own funds and may spend them, without showing which funds or who they are.Succinct proofA succinct proof is far shorter than the computation it covers, and far quicker to check than to redo. Its size and checking time grow only slowly as the computation grows, so a blockchain can verify a long computation cheaply.Fiat-Shamir transformThe Fiat-Shamir transform turns an interactive proof, where the verifier sends random challenges, into a single message. The prover computes each challenge as a hash of everything sent so far, so no back-and-forth is needed.FRIFRI is the low-degree test used in STARKs. It checks that committed values come from a polynomial of low degree by halving the problem round after round and testing a few random points, and it rests only on hash functions.

Sources: Zero-knowledge proofs, ethereum.org · Fast Reed-Solomon Interactive Oracle Proofs of Proximity, ECCC 2017

Updated November 1, 2026. All terms