An interactive proof system is a protocol in which a prover exchanges messages with a verifier to establish that an input belongs to a formal
language 
.
The verifier is a randomized algorithm running
in polynomial time in the input length. The prover
has no restriction on computation time (Goldwasser
et al. 1989).
Let 
be the probability that verifier 
accepts input 
after interacting with prover 
, including the random choices of both participants. In a standard
constant-error formulation, completeness requires
 |
for every 
.
Soundness requires
 |
for every 
and every prover strategy 
, including computationally unrestricted strategies. Thus
false assertions must be rejected with high probability
even when the prover is dishonest. Sequential repetition with fresh randomness and
majority acceptance reduces the error (Goldwasser et al. 1989).
A zero-knowledge proof additionally requires an efficient simulation of the verifier's view.
