Time-optimal interactive proofs for circuit evaluation
From MaRDI portal
Abstract: Recently, researchers have been working toward the development of practical general-purpose protocols for verifiable computation. These protocols enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the computations correctly. Despite substantial progress, existing implementations are not yet practical. The main bottleneck is typically the extra effort required by the prover to return an answer with a guarantee of correctness, compared to returning an answer with no guarantee. We describe a refinement of a powerful interactive proof protocol originally due to Goldwasser, Kalai, and Rothblum. Cormode, Mitzenmacher, and Thaler show how to implement the prover in this protocol in time O(S log S), where S is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits whose wiring pattern is sufficiently "regular"; for these circuits, we bring the runtime of the prover down to O(S). That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee. We argue that our refinements capture a large class of circuits, and prove some theorems formalizing this. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than 10x slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right. Our final contribution is a protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many pieces of data.
Recommendations
Cited in
(41)- Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs
- Scalable zero knowledge via cycles of elliptic curves
- Verification protocols with sub-linear communication for polynomial matrix operations
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Multi-server verifiable delegation of computations: unconditional security and practical efficiency
- Flexible and efficient verifiable computation on encrypted data
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- Sumcheck arguments and their applications
- Efficient proof composition for verifiable computation
- Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
- Gemini: elastic SNARKs for diverse environments
- Practical verified computation with streaming interactive proofs
- Competing provers protocols for circuit evaluation
- Competing-provers protocols for circuit evaluation
- Arguments of proximity (extended abstract)
- scientific article; zbMATH DE number 176510 (Why is no real title available?)
- Polynomial time interactive proofs for linear algebra with exponential matrix dimensions and scalars given by polynomial time circuits
- Verifiable stream computation and Arthur-Merlin communication
- Computational integrity with a public random string from quasi-linear PCPs
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- On the virtue of succinct proofs
- HyperPlonk: Plonk with linear-time prover and high-degree custom gates
- Ligero: lightweight sublinear arguments without a trusted setup
- Brakedown: linear-time and field-agnostic SNARKs for R1CS
- Nova: recursive zero-knowledge arguments from folding schemes
- Making \(\mathsf{IP}=\mathsf{PSPACE}\) practical: efficient interactive protocols for BDD algorithms
- Fiat-Shamir security of FRI and related SNARKs
- Simulation-extractable KZG polynomial commitments and applications to HyperPlonk
- \textsf{Jolt}: SNARKs for virtual machines via lookups
- Unlocking the lookup singularity with \textsf{Lasso}
- \textsc{Zeromorph}: zero-knowledge multilinear-evaluation proofs from homomorphic univariate commitments
- On soundness notions for interactive oracle proofs
- Mangrove: a scalable framework for folding-based SNARKs
- Streaming zero-knowledge proofs
- How to prove false statements: practical attacks on Fiat-Shamir
- SNARKs for virtual machines are non-malleable
- Interactive line-point zero-knowledge with sublinear communication and linear computation
- \textit{Ceno}: non-uniform, segment and parallel zero-knowledge virtual machine
- Scalable zkSNARKs for matrix computations. A generic framework for verifiable deep learning
- \textsf{FREPack}: improved SNARK frontend for highly repetitive computations
- Time-space trade-offs for sumcheck
This page was built for publication: Time-optimal interactive proofs for circuit evaluation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849387)
