Interactive vs Non-Interactive Proofs

Interactive Proofs

In an interactive proof, the prover and verifier exchange multiple messages:

Prover                    Verifier
  |                          |
  | ---- Commitment -------> |
  |                          |
  | <---- Challenge -------- |
  |                          |
  | ------ Response -------> |
  |                          |
  |                    (Verify)

Characteristics

• Multiple rounds of communication
• Verifier contributes randomness during the protocol
• Cannot be verified by third parties without re-running the protocol

Example: Schnorr Protocol

Proves knowledge of discrete log:

1. Prover commits: r ← random, send R = g^r
2. Verifier challenges: send c ← random
3. Prover responds: s = r + c·x (where x is the secret)
4. Verifier checks: g^s = R · y^c (where y = g^x)

Non-Interactive Proofs

In a non-interactive proof, the prover generates a single proof that anyone can verify:

Prover                    Public
  |                          |
  | ---- Proof π --------->  |
  |                          |
  |                    (Anyone verifies)

The Fiat-Shamir Transform

Converts interactive Σ-protocols to non-interactive using a hash function:

1. Instead of verifier sending random challenge c
2. Prover computes c = H(commitment, statement)
3. Proof = (commitment, response)

Characteristics

• Single message from prover
• Publicly verifiable
• Can be stored and verified later
• Essential for blockchain applications

Security Considerations

The Fiat-Shamir transform requires:

• Random Oracle Model: Hash function behaves like random oracle
• Transcript Binding: Challenge must include all relevant context

When to Use Each

Next: SNARKs and STARKs