= Soundness of an interactive proof
{title2=$s(n)$}
\b[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^*$, an acceptance bound $s(|x|)$ requires
$$
\Pr[V\text{ accepts }\langle P^*,V\rangle(x)]\leq s(|x|).
$$
In the usual <interactive proof system> definition, the quantifier includes computationally unrestricted cheating strategies. Bounding only one tested strategy is insufficient.<Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems by Oded Goldreich and others>[Definitions of interactive proof systems, universal soundness condition]{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> gives
$$
\Pr(A_1\cap\cdots\cap A_k)
=\prod_{i=1}^k\Pr(A_i\mid A_1,\ldots,A_{i-1})
\leq s^k,
$$
with 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.
Back to article page
