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(log2N), and the proof size is O(log2N). 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.