PhD Oral Proposal:  Srinath Setty

Date: July 29th
Time: 11AM
Place: GDC 6.516
Research Supervisor: Michael Walfish

Dissertation title: Making verifiable computation nearly practical

Abstract:
We consider the following fundamental question in computer systems
security: how can a client check the correctness of a computation
outsourced to a remote, untrusted server, without locally reexecuting
the computation? The motivation is the rise of third-party computing,
like cloud computing, volunteer computing, and peer-to-peer computing,
in which computations are outsourced to an entity that is different
from the actual “consumer” of the computation. In addition, allowing
clients to verify their outsourced computations can help cloud
services as a major barrier to their adoption---lack of trust---would
be surmounted.

In principle, this problem can be solved by applying deep results in
complexity theory (e.g., by using probabilistically checkable proofs
(PCPs) in conjunction with cryptographic primitives, or by using
interactive proofs (IPs)). Unfortunately, these theoretical tools are
notoriously impractical, requiring hundreds of trillions of CPU years
to verify even simple computations.

We propose a system, called Pantry, for verifiable outsourcing of
computations. Pantry includes a series of theoretical innovations and
systems engineering techniques to improve performance by over 20
orders of magnitude, relative to an implementation of the theory
without our refinements; this applies to computations expressed as
degree-2 algebraic constraints (a generalization of arithmetic
circuits). In addition, Pantry applies the underlying verification
machinery to a much larger class of computations: those that interact
with storage or state. As a result, Pantry applies to computations for
which people actually use the cloud: MapReduce jobs, database queries,
etc. While Pantry is not truly practical, it brings something that was
previously wildly impractical into the realm of plausibility.