Verifiable Computation with Massively Parallel Interactive Proofs

By Justin Thaler, Mike Roberts, Michael M. Mitzenmacher, Hanspeter Pfister. 2012

80 citations recorded by the source corpus.

As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown increasingly urgent. The concept of verifiable computation enables a weak client to outsource difficult computations to a powerful, but untrusted, server. Protocols for verifiable computation aim to provide the client with a guarantee that the server performed the requested computations correctly, without requiring the client to perform the computations herself. By design, these protocols impose a minimal computational burden on the client. However, existing protocols require the server to perform a large amount of extra bookkeeping in order to enable a client to easily verify the results. Verifiable computation has thus remained a theoretical curiosity, and protocols for it have not been implemented in real cloud computing systems. Our goal is to leverage GPUs to reduce the server-side slowdown for verifiable computation. To this end, we identify abundant data parallelism in a state-of-the-art general-purpose protocol for verifiable computation, originally due to Goldwasser, Kalai, and Rothblum, and recently extended by Cormode, Mitzenmacher, and Thaler. We implement this protocol on the GPU, obtaining 40-120x server-side speedups relative to a state-of-the-art sequential implementation. For benchmark problems, our implementation reduces the slowdown of the server to factors of 100-500x relative to the original computations requested by the client. Furthermore, we reduce the already small runtime of the client by 100x. Similarly, we obtain 20-50x server-side and client-side speedups for related protocols targeted at specific streaming problems. We believe our results demonstrate the immediate practicality of using GPUs for verifiable computation, and more generally that protocols for verifiable computation have become sufficiently mature to deploy in real cloud computing systems.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

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, background): “Other work in this area includes [11, 40, 50]; we chose the foundation that we did because [11, 50] imposes certain restrictions that would make our work here difficult (although the work of [52] partially relaxes these) and [40] gives up performance to eliminate interactivity (although it has super”
Full Accounting for Verifiable Outsourcing (2017, methodology): “• Giraffe demonstrates algorithmic improvements that apply to all CMT-based systems [36, 77, 79, 81, 82, 88].”
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.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “Thus, the first works with an explicit motivation to build “practical” systems using probabilistic proofs [40, 80, 82, 83, 86] refine and implement simple interactive protocols of Ishai et al.”
Aurora: Transparent Succinct Arguments for R1CS (2019, background): “The sumcheck protocol plays a fundamental role in computational complexity (it underlies celebrated results such as IP = PSPACE [72] and MIP = NEXP [10]) and in efficient proof protocols [48, 39, 75, 73, 74, 76, 77, 82, 83, 79].”
Verifying computations without reexecuting them (2015, background): “CMT [18, 46] exploits an algebraic insight to save orders of magnitude for the prover, versus a naive implementation of Muggles.”
A Hybrid Architecture for Interactive Verifiable Computation (2013, background): “The following description of our problem statement and framework borrows heavily from our prior treatments [44, 47].”
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).”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, background): “Prior work [99, 103, 104] suggests that Gir is highly parallelizable; exploring this in Hyrax is future work.”
Resolving the conflict between generality and plausibility in verified computation (2013, methodology): “As a practical matter, this demolishes costs: the server’s overhead on all computations is similar to the overhead for the best manually constructed computations in prior work [23, 54, 55].”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, methodology): “While Section 5 describes a specialized protocol for MATMULT that is more efficient than the protocol implied by Theorem 1, MATMULT serves as an important case study for the costs of the more general protocol described in Theorem 1, and allows for direct comparison with prior implementation work tha”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, background): “These protocols have required expensive encoding of computations, monstrously large proofs, high error bounds, prohibitive overhead for the prover, and intricate constructions that make the asymptotically efficient schemes challenging to implement correctly.”
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].”
Verifiable differential privacy (2015, methodology): “One set of projects [11, 45, 46], derived from Goldwasser et al.”