Linear-Time Polynomial Holographic Interactive Oracle Proofs with Logarithmic-Time Verification for Rank-1 Constraint System from Lookup Protocol

Modern SNARKs are constructed using polynomial Interactive Oracle Proofs (IOPs) and polynomial commitments. In this work, we introduce a novel polynomial holographic IOP for the NP -Complete language Rank-1 Constraint System (R1CS), where holographic IOP means that the proof system supports preprocessing. Our construction achieves linear-time proving, logarithmic-time verification, and constant query complexity. For an R1CS instance with size O ( N ) over a sufficiently large finite field, the prover’s time is O ( N ), the verifier’s time is O (log N ), and the query complexity is O (1). By combining our polynomial holographic IOP with the recent polynomial commitment scheme Orion, we obtain a transparent SNARK for R1CS with remarkable performance: the prover’s time is O ( N ), the verifier’s time is O (log 2 N ), and the proof size is O (log 2 N ). The core technique in our construction is the classical SumCheck protocol, which enables us to efficiently check whether an n-variate polynomial sums to a specific value on a given domain, such as {0, 1} n . Additionally, we showcase how to achieve holography from the lookup protocol, which allows us to efficiently verify that all elements in a vector are contained in another vector. We introduce a new polynomial IOP for the lookup relation with a linear-time prover.