Interactive Oracle Proof (IOP)
Interactive Oracle Proof (IOP)
Schwartz-Zipple lemma
schwartz-zippel lemma state that a polynomial f(x) with degree \(d\). There are at most \(d\) root making f(x)=0. Assume the domain of x is \(S\). The domain S is far bigger than \(d\) numbers. Thus, \(Pr[f(x_0) = 0] \le frac{d}{S}\) with randomly sampled \(x_0\). The Schwartz-Zippel lemma turns the problem of proof of knowledge into the problem of proving the correctness of an evaluation of the polynomial at a random coordinate.
IOP with polynomial commitment
The knowledge can be hidden as coefficients in a polynomial. Then, the zero proof of knowledge can be done by utilizing Schwartz-Zippel lemma, which is called IOP protocol. The IOP protocol is idealized because the randomness and the reveal of the evaluation cannot be easily implemented in the real world. Luckily, the polynomial commitment with hiding and binding properties can make it. The prover first commits the polynomial to the verifier. With the binding property, the same commitment cannot be made without the same polynomial. Then, the verifier randomly chooses a value \(x_0\) and asks the prover to open the polynomial commitment at point \(x_0\). With the hiding property, the knowledge of the polynomial can be protected from leakage in the open stage. If the prover indeed provides a right value of \(f(x_0)\), it has reason to believe that the prover indeed knows and commits the claimed f(x).
In summary, the process of the polynomial commitment-based Interactive Proof of knowledge
- Alice hides the knowledge in the polynomial by arithmetization
- Alice generates commitment \(C\) by evaluating \(f(x)\) at the secret coordinate, and tell Bob
- Bob randomly chooses \(x_0\), and tell Alice <--- Fiat-Shamir Transform: \(x_0 = hash(C)\)
- Alice claimed \(y_0\) is the evaluation of \(f(x)\) at \(x_0\) and generates proof for Bob
- Bob verify the proof with the commitment \(C\), \(x_0\), \(y_0\)
TODO: -[ ] proof of knowledge vs zero-knowledge proof
