= Verifier in an interactive proof
{title2=$V$}
A \b[verifier in an interactive proof] is the efficient participant that evaluates a public statement using messages from a <prover in an interactive proof> and its own random choices. Its <algorithm> specifies which challenge to send, how to process the response and when to accept or reject. In the standard model it runs in probabilistic <polynomial time> in the public input length.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Sections1.1.2–1.2, verifier strategy and resource bound]{ref}
The verifier's guarantee concerns more than one successful conversation. <Completeness of an interactive proof> requires a suitable honest prover to succeed on true statements. <Soundness of an interactive proof> bounds success of every cheating strategy on false statements. A verifier that accepts whenever it receives any message meets neither requirement merely by being fast.
For an original checking example, suppose a response claims a <graph isomorphism> between two20-vertex <graphs> encoded by adjacency matrices. Checking that the vertex mapping is a <bijection> and that all $20^2=400$ adjacency entries agree with their mapped entries verifies that response. It does not require searching through all $20!$ vertex <permutations>.
An <interactive proof system> can use such inexpensive checks in a randomized conversation. The verifier's random choices must follow the specified protocol: exposing a challenge too early, reusing randomness in an unjustified way or changing the acceptance rule can alter its mathematical guarantees.
Back to article page
