 Soundness of an interactive proof

Soundness of an interactive proof bounds how often a verifier in an interactive proof can be induced to accept a false statement. For every false input $x$ and every cheating prover in an interactive proof strategy $P^{\ast }$, an acceptance bound $s(|x|)$ requiresIn the usual interactive proof system definition, the quantifier includes computationally unrestricted cheating strategies. Bounding only one tested strategy is insufficient.^[ref]

An original repetition example shows why conditional bounds matter. Suppose a single fair bit $B$ is reused in two tests, and both accept exactly when $B=0$. Each test separately accepts with probability $1/2$, but both accept with probability $1/2$, not $1/4$. Merely multiplying marginal probabilities would be wrong.

Instead, if every next test has acceptance probability at most $s$ conditional on every preceding accepting history, the chain rule for probabilities giveswith the first term unconditional and zero-probability histories handled trivially. For $s=1/2$ and $k=8$, the bound is $1/256$. The relevant protocol must justify those conditional bounds, rather than assuming that repetition automatically makes every transcript independent.

Soundness protects the false-statement side of verification. It neither guarantees acceptance of true statements nor establishes that a successful interaction hides a cryptographic witness; those are separate completeness and zero-knowledge proof questions.