INTERACTIVE PROOF OF PROXIMITY ( IOPP )
An Interactive Oracle Proof of Proximity (IOPP) is a cryptographic proof system that allows a verifier to check that a prover has access to (or is “close” to) a valid codeword in some error-correcting code but without the verifier needing to read the whole object themselves.
This concept is actively used/explored in scalable zk proofs, data availability sampling (or DAS), and probabilistic proof systems like STARKs.
Key Points:
• Both prover and verifier have access to vector of symbols. Prover claims that this vector is close to the code C i.e. there is at least one codeword that does not differ from the vector in the oracle in too many positions.
• A vector is withing unique decoding radius, if there is exactly one such codeword i.e closest codword in unique.
Steps:
1. The prover provides an oracle to evaluations of f over a large domain.
2. The verifier samples a few points at random and checks local consistency with degree-2 tests, like linearity tests or low-degree tests.
3.If the samples all pass, the verifier is convinced (with high probability) that f is “close” to a low-degree polynomial.
In the context of Interactive Oracle Proofs of Proximity (IOPPs), the term “close” refers to how similar a given string or function is to a valid codeword in an error-correcting code, usually measured using the Hamming distance.
Given a string x and a code C, we say that x is δ-close to the code C if there exists a codeword c such that x differs from c in at most δn positions.
In other words, by changing only a small fraction of the entries in x, we can obtain a valid codeword. This notion of proximity is crucial in IOPPs because the verifier does not require the prover’s input to be exactly a codeword, only that it is sufficiently close to one.
This allows the verifier to query a small number of positions in x and still be confident that the entire object is mostly correct. In practical terms, this is what enables efficient verification without reading the entire input or proof.
The concept is especially useful in scenarios like low-degree testing or data availability sampling, where you want to check the integrity of data with minimal access.