Abstract: As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown in- creasingly 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 requested computations herself. By design, these protocols impose a minimal computational burden on the client. However, existing protocols require the server to perform a very large amount of extra bookkeeping, on top of the requested computations, 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.
In this paper, 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, and we obtain 40-120× server-side speedups relative to a state-of-the-art sequential implementation. For benchmark problems, our implementation thereby reduces the slowdown of the server to within factors of 100-500× relative to the original computations requested by the client. Furthermore, we reduce the already small runtime of the client by 100×. Similarly, we obtain 20-50× 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.|
Date: |
January 2012 |
Source Code: |
[zip] (Please read the README file.) |
This page contains source code for the paper Verifiable Computation with Massively Parallel Interactive Proofs , by Justin Thaler, Mike Roberts, Michael Mitzenmacher, and Hanspeter Pfister.
I intend to maintain this code indefinitely.
This page was last updated on Sunday, February 12, 2012.