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

Shuangjun Zhang ()
Additional contact information
Shuangjun Zhang: Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, China

Mathematics, 2025, vol. 13, issue 8, 1-41

Abstract: 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.

Keywords: polynimal IOP; SNARK; holographic proofs; SumCheck protocol; lookup protocol (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/8/1309/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/8/1309/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:8:p:1309-:d:1636226

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().