A Hybrid Architecture for Interactive Verifiable Computation

By Victor Vu, Srinath T. V. Setty, Andrew Justin Blumberg, Michael Walfish. 2013

177 citations recorded by the source corpus.

We consider interactive, proof-based verifiable computation: how can a client machine specify a computation to a server, receive an answer, and then engage the server in an interactive protocol that convinces the client that the answer is correct, with less work for the client than executing the computation in the first place? Complexity theory and cryptography offer solutions in principle, but if implemented naively, they are ludicrously expensive. Recently, however, several strands of work have refined this theory and implemented the resulting protocols in actual systems. This work is promising but suffers from one of two problems: either it relies on expensive cryptography, or else it applies to a restricted class of computations. Worse, it is not always clear which protocol will perform better for a given problem.We describe a system that (a) extends optimized refinements of the non-cryptographic protocols to a much broader class of computations, (b) uses static analysis to fail over to the cryptographic ones when the non-cryptographic ones would be more expensive, and (c) incorporates this core into a built system that includes a compiler for a high-level language, a distributed server, and GPU acceleration. Experimental results indicate that our system performs better and applies more widely than the best in the literature.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

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 Computer Networks and Communications

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “Additional concurrent work [61] adapts previous GKR-based protocols [25, 26] to the batching model and develops a compiler that chooses amongst three PCP-based backends.”
Verifying computations with state (2013, methodology): “First, the compiler transforms the computation Ψ to an algebraic system of constraints .”
ALITHEIA: Towards Practical Verifiable Graph Processing (2014, methodology): “A VC protocol for graph algorithms can be derived in theory via black-box use of existing general-purpose VC schemes [18, 14, 24, 9, 10, 19, 11], or one of the systems that have been built to apply these techniques [33, 32, 30, 7, 12, 36].”
Distributed Differential Privacy and Applications (2015, background): “Another line of work (Setty, McPherson, Blumberg, and Walfish, 2012a; Setty et al., 2012b; Setty, Braun, Vu, Blumberg, Parno, and Walfish, 2013; Vu et al., 2013) combines the interactive arguments of Ishai, Kushilevitz, and Ostrovsky (2007) with a compiler that supports program constructs such as br”
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”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Variants of this problem have been around for decades [10]; today, cloud computing is a particularly pertinent use case.”
Full Accounting for Verifiable Outsourcing (2017, methodology): “Prior work [81, 82] cut this to O ( d log G ) , by precomputing { f j ( τ )} , and not charging for that.”
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 efficient modular arithmetic implementations, and specifically to the primes p = 2(61) − 1 and p = 2(127) − 1.”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “[107] Victor Vu, Srinath Setty, Andrew J.”
Verifying computations without reexecuting them (2015, methodology): “Allspice [47] has CMT’s low costs but achieves greater expressiveness (under the amortization model described next).”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “[71] provide a system that incorporates both the batching arguments of [63, 65, 66, 64] as well as the interactive proofs of [32, 68, 67].”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, methodology): “These can be done in pre-processing in time O(Si) by enumerating the in-neighbors of each of the Si gates at layer i [14, 37].”
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “See Sect.”
Practical verified computation with streaming interactive proofs (2011, methodology): “To clarify, this use of a single ̃ addi and ̃ multi evaluation for all instances as in [104] is sound only if all of the instances are checked simultaneously.”
Scalable Zero Knowledge with No Trusted Setup (2019, background): “This led to a line of realizations in code, early works lacked ZK [36, 35, 76, 78], but the state-of-the-art ones, like [82] and Hyrax [80], do have it.”