Round-by-Round Knowledge Soundness for Linear-Time IOPs

Interactive oracle proofs, or IOPs, are an important class of proof systems which are used to construct non-interactive arguments via the BCS transformation. Constructions of IOPs often use generic linear codes, whose properties affect the parameters of the IOP. Prior works such as (Bootle et al., TCC 2020) and (Golovnev et al., Crypto 2023) use this strategy, instantiated with linear-time encodable codes, to give constructions of succinct linear-time non-interactive arguments with linear-time prover algorithms.

To guarantee that the non-interactive arguments produced using the BCS transformation are secure in the random oracle model, the underlying IOP must satisfy strong knowledge soundness properties. Until recently, these had only been demonstrated for IOPs based on codes with efficient error-tolerant decoding algorithms, which excluded known constructions of linear-time encodable codes used in IOPs.

In this work, building on recent work (Buenz et al.) which demonstrated strong knowledge soundness properties for IOPs based on erasure-decoding, we prove that an IOP construction based on the aforementioned works, which is built from general error-correcting codes, satisfies a strong knowledge soundness notion known as round-by-round knowledge soundness. The property of round-by-round knowledge soundness is known to imply knowledge soundness for both the IOP and its BCS transformation. As a direct consequence, we obtain security guarantees for the non-interactive arguments with linear-time provers derived from the IOP.