Analysing a protocol as a discrete random variable

Probabilistic proof protocols can be modelled as a coin flipping game which helps simplify the protocol and how the bounds work.

1. It’s just a Bernoulli Trial (Coin flip with accept = 1, reject = 0)

Model a protocol execution as a single Bernoulli trial, a discrete random variable $X$ where

• $X = 1$ verifier accepts
• $X = 0$ verifier rejects The prover’s statement is either true or false and the outcome of the random variable identifies which condition was observed (completeness, soundness).

2. Statement and Premise

It helps to separate the high-level “Statement” from the mathematical “Premise” used in the proof.

• The Statement: This is the human-readable claim (e.g., “This distribution $\mathbf{p}$ is non-uniform”).
• The Premise: This is the formal math condition that defines what “true” or “false” means for the proof.

For Completeness, the premise that the statement is true is: $d_{TV}(\mathbf{p}, \mathbf{u}_k) \ge \varepsilon_2$.

For Soundness, the premise that the statement is false is: $d_{TV}(\mathbf{p}, \mathbf{u}_k) \le \varepsilon_1$.

The Soundness guarantee is an “if-then” rule: IF the statement is false (meaning the premise $d_{TV} \le \varepsilon_1$ holds), THEN we guarantee that a cheater’s success probability is capped at a very low level.

3. The Two Coins: $X_G$ (Good) and $X_B$ (Bad)

The protocol forces the “game” to be played with one of two different biased coins, $X_G$ or $X_B$. The Verifier’s job is to figure out which coin was flipped.

• Good Coin ($X_G$) - Completeness: This coin is used when the statement is true. Its acceptance probability is high: $P(X_G=1) \ge \frac{1}{2} + \frac{\varepsilon_2}{2}$. This is significantly biased above a random $\frac{1}{2}$ guess.

• Bad Coin ($X_B$) - Soundness: This coin represents a cheater’s best effort when the statement is false. Its acceptance probability is low: $P(X_B=1) \le \frac{1}{2} + \frac{\varepsilon_1}{2}$. This is only negligibly better than a random $\frac{1}{2}$ guess.

4. The Goal: Statistical Inference

The verifier doesn’t know which coin is being flipped. Verifier runs the protocol (flip the coin) and observes the outcome ($1$ or $0$). Based on this outcome, V deduces which coin was more likely.

• If the verifier sees $1$ (accept), it’s most probably the good coin ($X_G$) so the statement is true (the distributions are non-uniform).
• If the verifier see a $0$ (reject), it’s most probably the bad coin ($X_B$), concluding the statement is false.

The protocol’s security relies on the statistical gap ($\frac{\varepsilon_2 - \varepsilon_1}{2}$) between the two coins, which is what makes their outcomes distinguishable.

5. the bounds

Completeness is a lower bound on the probability the protocol accepts an honest Merlin, soundness is an upper bound on the probability that any malicious Merlin succeeds which should be very small.

• Completeness: is a lowerbound, the condition $P(X_G=1) \ge \frac{1}{2} + \frac{\varepsilon_2}{2}$ is a minimum for an honest prover with a true statement

• Soundness: is an upper bound, the condition $P(X_B=1) \le \frac{1}{2} + \frac{\varepsilon_1}{2}$ is a maximum on any cheating Merlins success. Any malicious prover with a false statement cannot fool the verifier with a probability higher than this.

TODO

• Amplification (parallel, sequential)
• Zero Knowledge