We present the first Interactive Oracle Proofs of Proximity (IOPPs) for linear-time encodable codes that achieve \(\lambda \) -bit security with linear prover time and optimal \(O(\lambda )\) query complexity. This implies (via standard techniques) the first IOP for NP with O(n) prover time and \(O(\lambda )\) query complexity, and hence also the first SNARK for NP in the random oracle model with linear prover time and \(O(\lambda ^2 \log n)\) proof size. The technical core of our result is a novel IOPP for tensor codes. Our tensor IOPP leverages error correction in a novel way to reduce checking proximity of a purported codeword to the tensor code to checking the proximity of \(\varTheta (\lambda )\) -many of its columns to the column code. Our key insight is that it in fact suffices to just prove that a constant fraction of these new proximity claims hold (as opposed to all of them). We devise a new lossy batching protocol that provides the foregoing guarantee with just \(O(\lambda )\) query complexity. By combining this tensor IOPP with prior “codeswitching” reductions, we obtain IOPPs for a large class of linear-time encodable codes. We complement our IOPP construction with a lower bound that shows that, when proving proximity to constant-rate codes, one cannot construct IOPPs with query complexity better than \(O(\lambda )\) . This establishes the optimality of our IOPP’s query complexity.