Soundness, Completeness & Zero Knowledge

Start with the actual problem

Suppose a prover claims that a statement is true.

The verifier does not simply want a message saying “trust me.” The verifier wants a protocol that gives a meaningful cryptographic guarantee.

Three properties describe the heart of that guarantee:

These properties answer three different questions:

Statement and witness

Before discussing the three properties, we need to define what a proof is actually about.

Let:

A relation R tells us whether a particular witness satisfies a particular statement.

The language of provable statements is:

So the prover's claim is usually not simply “I know a number.” It is:

and the prover possesses a witness w demonstrating membership.

Example: knowing a preimage

Suppose:

The public statement is y. The private witness is w.

The prover wants to prove:

without revealing w.

What is a proof protocol?

A proof protocol describes how a prover and verifier interact.

A simple interactive protocol can look like:

Later, Fiat–Shamir can replace the verifier's random challenge with a hash-derived challenge in many non-interactive constructions.

1. Completeness

Completeness describes what happens when everyone behaves honestly and the statement is actually true.

More formally, a proof system is complete if an honest prover with a valid witness causes an honest verifier to accept with probability 1, or with probability negligibly close to 1, depending on the precise definition.

Why can completeness involve probability?

Some protocols contain randomized behavior. For example, a prover or verifier may sample random values.

Therefore the exact statement can be written as:

where ε is the completeness error.

Completeness with a simple example

Suppose Alice knows a valid witness w and follows every proving step correctly.

If the verifier rejects valid proofs often, the system is not useful. A proof system therefore aims to make honest acceptance overwhelmingly likely.

2. Soundness

Soundness is the property that protects the verifier from a dishonest prover.

Imagine that the statement is false:

There is no valid witness satisfying the relation.

A malicious prover may still try to produce messages that make the verifier accept.

Soundness says that this should succeed only with a small probability.

Here P* represents an arbitrary malicious prover and ε is the soundness error.

Why is soundness usually probabilistic?

Many proof protocols use randomness.

The verifier may choose a challenge that the cheating prover cannot predict before committing to its first message.

Suppose a dishonest prover can answer only one particular challenge out of N possible challenges.

If N is large, the cheating probability becomes small.

Repeating a protocol can reduce the error further:

The exact reduction depends on the protocol and how repetitions are composed.

Soundness vs. knowledge soundness

This distinction is important in zero knowledge.

Ordinary soundness says, roughly:

Knowledge soundness is stronger in a different direction. It says that if a prover can convince the verifier, then there should exist an efficient extractor that can obtain a valid witness from that prover, under the construction's formal security model.

This is why the word Knowledge appears in SNARK and STARK terminology.

3. Zero knowledge

Now consider a different question.

Suppose the statement is true and the prover has a valid witness. Does the verifier learn the witness while checking the proof?

A zero-knowledge proof is designed so that the verifier learns nothing beyond what the statement itself reveals, according to the formal definition and security model.

The prover can demonstrate possession of a secret without simply sending the secret to the verifier.

The central idea: simulation

The standard way to formalize zero knowledge is through a simulator.

Imagine two worlds.

If the verifier cannot distinguish these worlds except with negligible advantage, the protocol provides zero knowledge under the relevant definition.

The symbol ≈ represents computational indistinguishability in the common computational zero-knowledge setting.

Why does the simulator matter?

Suppose the verifier's entire view of the real protocol can be generated without knowing the secret witness.

Then whatever information the verifier obtained from the protocol could not depend on actually possessing the witness in the first place.

This is the fundamental intuition behind simulation-based zero knowledge.

Perfect, statistical, and computational zero knowledge

The phrase “indistinguishable” can be interpreted at different strengths.

These are distinct formal security notions.

A classic intuition: proving you know a secret

Imagine a locked cave with two entrances connected by a secret passage.

The prover knows the secret that opens the passage. The verifier wants confidence that the prover really knows it, but does not want the secret itself revealed.

A simplified protocol is:

Repeated rounds make the cheating probability small:

This captures the intuition behind challenge-response protocols.

Why the verifier's challenge matters

The challenge must be unpredictable to a cheating prover at the right point in the protocol.

Conceptually:

If the prover could see the challenge before committing, it might construct a fake commitment tailored to that challenge.

This is one reason commitment schemes are so important in interactive proofs.

From interaction to non-interaction: Fiat–Shamir

Interactive protocols require a verifier to generate random challenges.

For a non-interactive proof, the prover can derive the challenge from a cryptographic hash of the transcript.

This is the core intuition behind the Fiat–Shamir transform.

The verifier recomputes the same challenge from the proof transcript.

Security of this transformation requires careful modeling and domain separation; it is not simply “replace randomness with any hash.”

Zero knowledge is not encryption

Encryption hides a message from unauthorized parties.

Zero knowledge is different: it lets one party prove a statement without revealing the secret information used to make the statement true.

The three properties work together

Consider what happens if one property is missing.

How this appears in SNARKs and STARKs

Modern SNARKs and STARKs combine these properties with concrete algebraic and cryptographic mechanisms.

SNARK-style view

Soundness comes from the inability of an efficient adversary to satisfy the required algebraic checks for a false statement, under the construction's assumptions.

Zero knowledge is achieved through blinding, randomization, simulation arguments, or other construction-specific mechanisms.

STARK-style view

Soundness is connected to low-degree testing, query randomness, hash commitments, and the algebraic structure of the protocol.

Zero knowledge requires additional hiding/randomization mechanisms when the underlying proof would otherwise reveal information about the witness or execution trace.

What does zero knowledge mean in a zkVM?

A zkVM executes a program and generates an execution trace.

Suppose the trace contains a private value:

The goal may be to prove that the VM executed correctly without exposing that private value.

Completeness says the honest trace produces an accepted proof.

Soundness says an invalid trace should not produce an accepted proof except with negligible probability.

Zero knowledge says the proof should not unnecessarily reveal the private execution information.

Understanding “negligible probability”

Cryptographic security often uses the word negligible.

Informally, a function negl(λ) is negligible if it becomes smaller than the inverse of every polynomial in the security parameter λ, for sufficiently large λ.

This gives cryptographers a rigorous way to express “so small that an efficient adversary cannot exploit it at meaningful scale.”

The security parameter

The symbol λ commonly represents the security parameter.

Increasing λ generally means increasing the resources required to break the cryptographic guarantee.

Concrete systems translate this abstract parameter into things such as field sizes, hash output lengths, repetition counts, query counts, and group sizes.

What is a cheating prover?

Soundness is not about one specific attacker.

We imagine an arbitrary efficient algorithm:

The star indicates that this prover may deviate from the prescribed protocol in any computationally feasible way.

The security statement is therefore roughly:

This is much stronger than testing the protocol against a few obvious cheating strategies.

What about a malicious verifier?

Zero knowledge must consider what a verifier might do with the information it receives.

A malicious verifier V* may:

• choose challenges differently from an honest verifier;
• keep transcripts;
• try to correlate protocol messages;
• run additional computation on the received data;
• attempt to extract information about the witness.

Therefore, a strong zero-knowledge definition is usually phrased against an arbitrary efficient verifier, not just an honest one.

Honest prover, honest verifier, malicious prover, malicious verifier

Proof vs. argument

The terminology matters.

A classical proof can be sound even against an unbounded prover, depending on the formal setting.

An argument relies on computational limitations: a computationally bounded adversary should not be able to break soundness.

Modern SNARKs and STARKs are generally described as arguments because their soundness relies on computational assumptions.

Interactive vs. non-interactive zero knowledge

In an interactive protocol:

The verifier actively contributes randomness.

In a non-interactive proof:

The prover sends a proof π that the verifier checks.

Many practical ZK systems use Fiat–Shamir or another mechanism to obtain non-interactive proofs from interactive-style protocols.

Rust: a tiny mental model

// Public statement
struct Statement {
    public_value: u64,
}

// Private witness
struct Witness {
    secret: u64,
}

// Relation being proved:
// H(secret) == public_value
fn relation(x: &Statement, w: &Witness) -> bool {
    hash(w.secret) == x.public_value
}

// Completeness:
// an honest prover with a valid witness should produce
// a proof accepted by verify().

// Soundness:
// an efficient prover without a valid witness should
// have only negligible probability of producing a proof
// accepted by verify().

// Zero knowledge:
// the proof should not expose `w.secret`.

fn verify(x: &Statement, proof: &Proof) -> bool {
    // Real systems perform cryptographic verification here.
    todo!()
}

This is deliberately not a cryptographic implementation. It shows where the three security properties sit conceptually in a software system.

Common mistakes

Where the three properties appear in a proving pipeline

Completeness vs. soundness vs. zero knowledge

Interview-level questions

The whole idea in one map

If you remember only one mental model, remember this:

These three properties are not interchangeable. Together, they describe the core correctness, security, and privacy goals that make a zero-knowledge proof system useful.