Computer Science Colloquium

Using Computers Without Trusting Them to Compute Correctly

Michael Walfish, University of Texas at Austin

April 19, 2013 11:30AM
Warren Weaver Hall, 1302
251 Mercer Street
New York, NY 10012

Spring 2013 Colloquia Calendar


Denis Zorin


How can a machine specify a computation to another one and then, without
executing the computation, check that the other machine carried it out
correctly? And how can this be done without assumptions about the
performer (replication, trusted hardware, etc.) or restrictions on the
computation? This is the problem of _verified computation_, and it is
motivated by the cloud and other third-party computing models. It has
long been known that (1) this problem can be solved in theory using
complexity-theoretic tools (interactive proofs and probabilistically
checkable proofs (PCPs)) coupled with cryptography, and (2) the
performance of these solutions is wildly impractical (trillions of
CPU-years or more to verify simple computations).

I will describe several implemented systems that challenge the second
piece of this folklore. These systems are based on two strands of
theory: a PCP-based efficient argument [IKO CCC07] (whose performance we
have improved by 20 orders of magnitude) and an interactive proof [GKR
STOC08, CMT ITCS12] that we have refined. We have also built a compiler
that takes as input a program written in a subset of C, chooses the best
available protocol for the computation, and produces executables that
implement the protocol entities. These systems apply to a range of
computations; a demonstration application is verifiable MapReduce. While
the performance of the systems is not ideal, they show that the
theoretical machinery could a real tool for building actual systems.

Time permitting, I will talk about other projects in the realm of
untrusted computing resources, including a distributed storage system
that works even if _all_ of the machines misbehave.


Michael Walfish is an assistant professor in the Computer Science
Department at The University of Texas at Austin. His research interests
are in systems, security, and networking. His honors include an Air
Force Young Investigator Award, an NSF CAREER Award, a Sloan Research
Fellowship, a Teaching Excellence Award from the UT College of Natural
Sciences, the Intel Early Career Faculty Honor Program, and the UT
Society for Teaching Excellence. He received his B.A. from Harvard summa
cum laude and his Ph.D. from MIT, both in Computer Science

top | contact webmaster