interactive proof system
An interactive proof system is a conversation. One party, the prover, is trying to convince another party, the verifier, that some statement is true — say, "I know a solution to this puzzle" or "this computation was done correctly." Instead of handing over a static document, the two exchange a back-and-forth of messages: the verifier throws random challenges, the prover answers, and after a few rounds the verifier either accepts or rejects. The point of the interaction is that a cheating prover — one whose statement is false — gets caught with overwhelming probability no matter how cleverly they reply.
Formally, such a system must satisfy completeness (an honest prover with a true statement always convinces an honest verifier) and soundness (a lying prover convinces the verifier only with negligible probability). The verifier's randomness is the crucial ingredient: because the prover cannot predict the next challenge, they cannot prepare a script of lies in advance. A classic illustration is the "Ali Baba cave" story, where repeated random coin flips drive a cheater's success probability down to (1/2)^k after k independent rounds. When the protocol additionally leaks nothing about why the statement is true, it is also zero-knowledge.
Interactive proofs are deep complexity theory, not just cryptography: the class IP of problems with efficient interactive proofs equals PSPACE, a startling result showing that interaction plus randomness buys enormous verifying power. For blockchains the practical descendants matter most — sigma protocols, the sumcheck protocol, and the interactive arguments inside STARKs — because almost every modern succinct proof begins life as an interactive protocol and is then compiled to a single-message, non-interactive one (typically with the Fiat-Shamir heuristic) so it can be posted on-chain.
Soundness here is often only per-round; security comes from repetition. A single round of a (1/2)-soundness protocol is nearly useless — you repeat until the cheating probability is astronomically small, e.g. below 2^-128.