Time-Optimal Interactive Proofs for Circuit Evaluation

By Justin Thaler. 2013

256 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Hardware and Architecture

Citations in the corpus

Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (2018, methodology): “There are protocols with lower communication than repeatedly using Freivalds’ ((Fiore & Gennaro, 2012; Thaler, 2013; Ghodsi et al., 2017)).”
Geppetto: Versatile Verifiable Computation (2015, background): “Some previous veriﬁable computations systems do not include a compiler [22, 52], while those that do [10, 16, 46] have typically compiled small examples with less than 100 lines of C code.”
Verifying computations with state (2013, background): “One line of work [24, 71, 72] refines the Muggles interactive proof protocol [37], which is purely complexitytheoretic (no cryptography).”
Distributed Differential Privacy and Applications (2015, background): “One set of projects (Cormode, Mitzenmacher, and Thaler, 2012; Thaler, Roberts, Mitzenmacher, and Pfister, 2012; Thaler, 2013), derived from interactive proofs as in Goldwasser, Kalai, and Rothblum (2008), uses a complexity-theoretic protocol that does not require cryptography, making it very efficie”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “(In contrast, when outsourcing P computations, there are implementations without expensive preprocessing: [34,107,108] consider low-depth circuits, and [37] consider outsourcing to multiple provers at least one of which is honest).”
Practical verified computation with streaming interactive proofs (2011, methodology): “Chapter 8 is based on the paper “Time-Optimal Interactive Proofs for Circuit Evaluation” (CRYPTO 2013 [97]).”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “, rm) ∈ Fm, Z̃(r) can be computed, using the above expression, in O(2m) field operations [84, 87].”
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud (2017, methodology): “As in prior works [5, 17, 18], we restrict our choice of p to Mersenne primes since they afford efﬁcient modular arithmetic implementations, and speciﬁcally to the primes p = 2 61 − 1 and p = 2 127 − 1 .”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “IP-based: The proofs for muggles approach [44] scales down Interactive Proofs (IP) from PSPACE to P and leads to excellent solutions for a limited yet interesting class of programs: those with high parallelism and small memory consumption; prover time for IP-based systems was reduced to quasi-linear”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “tions in code, early works lacked ZK [42, 41, 104, 107], but the state-of-the-art ones, like [112] and Hyrax [109], do have it.”
Verifiable differential privacy (2015, methodology): “One set of projects [11, 45, 46], derived from Goldwasser et al.”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “A set of works [32, 68, 67] has optimized and implemented the protocol of [42].”
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “See Sect.”