Why must the pen swapping experiment be repeated multiple times to constitute a valid zero-knowledge proof?

Conditions

• The prover must possess a secret capability (e.g., distinguishing colors).
• The verifier controls the randomization (e.g., swapping pens behind their back).
• The protocol is repeated multiple times to reduce the soundness error.

Reasoning, step by step

1. Start with two objects that the prover can distinguish but the verifier cannot.
2. Let the verifier randomly choose whether to swap the objects after receiving them.
3. Ask the prover to announce whether a swap occurred.
4. Calculate the probability of a correct guess in one round as $1/2$.
5. Repeat the protocol to multiply the probabilities, reducing the cheating chance to 25% after two rounds and 12.5% after three.

Example

The speaker explains that if a verifier randomly swaps the pens behind their back, a prover claiming to distinguish colors faces a binary guess. A color-blind impostor would succeed by chance with probability 0.5 per round. By repeating the protocol, the cumulative cheating probability drops to 0.25 after two rounds and 0.125 after three.

Common misconceptions

• Mistaking one successful round for full proof: A single correct answer is insufficient because a cheating prover still has probability $1/2$ of guessing correctly in a single round.
• Assuming the verifier learns the colors: The verifier only learns that the prover can distinguish the pens, not which pen is red or blue.

Watch the explanation

Explore next

• What are the three formal criteria that define a valid zero-knowledge proof protocol?
• How does revealing all other cards prove a hidden card is red without exposing its number?