Interactive Oracle Proofs

IOP defines as interactive oracle proofs are denoted by a system $S=(P,V)$ of interactive randomised algorithms where interaction happens between entities involved in the system: $P=\text{Prover},V=\text{Verifier}$. Verifier is given oracle access to the message sent by prover to the verifier in any round.

Properties of an IOP system:

• Round complexity, $r(N)$: number of rounds of interaction between $\mathcal{P}$ and $\mathcal{V}$
• Proof length, $l(N)$: sum of length of all messages sent by $\mathcal{P}\to \mathcal{V}$
• Proof complexity, $q(N)$: number of entries read by $\mathcal{V}$ from the various prover messages

PIOP

Polynomial interactive oracle proofs are interactive protocols between prover and verifier where with each message, prover creates an oracle and verifier can query any oracle supplied by the prover.

Method to convince verifier that the proof generated by prover is correct.

$S(C):S_p,S_v$ :- setup procedure of circuit

$S_v=[f_0],[f_{-1}],[f_{-2}]\cdots [f_{-s}]$ :- $S_v$ consists of commitments to $s+1$ polys.

• Why does $S_v$ contains commitments to different polynomial?::maybe due to having different sets of polynomial for each part of circuit.
• What if prover commits to a zero polynomial? i.e. what if $f(x)=0\forall x\in {\mathbb{F}}_p$ :: then we can do zero test on polynomial. i.e. take a random point $r$ in ${\mathbb{F}}_p$ and test whether it’s zero or not. and prob. of being zero is negligible with value $d/p$ where d is the degree of polynomial. example: $p=2^{256},d=2^{40}$
• what if prover commits to same polynomial? :: do equality test, take $r\in {\mathbb{F}}_p$ if $f(r)=g(r)$, then $f=g$ with very high prob. Not straightaway understandable to me tho.

• Prover sends t commitments to verifier
• verifier sends t random values to prover
• verifier runs a verify algorithm taking all the commitments and the random values, and previously generated setup summary $S_v$, i.e. $s+1$ commitments to polynomials.
  • It can ask prover to open any of the commitment at any point.
  • Verifier accepts/reject the proof.

$(t,q)$ Poly-IOP:

• $t$: no. of commitments to polynomials
• $q$: no. of eval queries in verify

1. Prover sends $t$ commitments
2. Verifier verifies at $q$ evaluations by running PCS eval.

Info

Length of SNARK: $t$ commitments + $q$ eval proofs

Verifier time: $q\ast O(eval)+O(IOP-verify)$

Prover time: $t\ast O(commit)+q\ast O(prove)+O(IOP-prove)$

References

• FRI #1.1.1 IOP