The intuition behind prover claims in Interactive Proofs

In interactive proofs, the prover can prove to a verifier that it executed a function \(f\) on input \(x\) and that the value is \(y\), i.e. claim that \(y=f(x)\). This seems almost magical, what does the execution proof for something general like a function look like?

The idea that IP uses is to “extend” the function using a multilinear extension (MLE) over field \(\mathbb{F}\). This is the Lagrange interpolation of multilinear polynomial. Note that while any function \(f: \{0,1\}^v \to \mathbb{F}\) has many polynomicals that extend it, there’s exactly one extension polynomial which is multilinear.

TODO: multilinear extension; lagrange interpolation

TODO: Explain distance-amplifying; “indirect way”

Once you have the extension, you essentially have a distance-amplifying encoding of the function in \(\mathbb{F}\). The polynomial thus generated by the prover is used by verifier (albeit in an indirect way, by querying the prover at various points). The ability of the prover to provide the queried value again and again over multiple interaction runs convinces the verifier of the claim.

This technique is very similar to erasure coding wherein data is broken into fragments, expanded and encoded with redundant data pieces. The original data can be reconstructed by even if some of the fragments are lost or corrupted etc. Look at its use in the Guide for the Aspiring Dropbox Decentralizer or data availability guarantees in Ethereum.