Verifying the Correctness of Remote Executions: from Theoretical Possibility to Near Practicality
Weekly Lecture Series: Verifying the Correctness of Remote Executions: from Theoretical Possibility to Near Practicality.
Speaker: Michael Walfish, NYU Courant
How can a machine specify a computation to another one and then, without executing the computation, check that the remote machine carried it out correctly? And how can this be done without assumptions about the performer (replication, etc.) or restrictions on the computation? This is a classic problem in systems security, and it is particularly relevant in the context of cloud computing. For decades, it has been known that this problem can be solved in theory, using probabilistically checkable proofs (PCPs) coupled with cryptographic tools. The rub was practicality: if implemented naively, the theory would be astronomically more expensive than simply executing the computation locally.
Over the last several years, a number of projects have brought this
theory to near practicality in the context of implemented systems. In
this emerging area of _proof-based verifiable computation_, the pace of progress has been rapid, and there have been many encouraging
developments. I will discuss this general area and my group's efforts.
We have developed a protocol that begins with an efficient argument (due to [IKO CCC '07]) and incorporates new theoretical work to improve performance by 20+ orders of magnitude; broadened the computational model from Boolean circuits to something general-purpose; developed a compiler that transforms from programs to executables that implement the protocol entities; fully implemented the system; accelerated it with GPUs; and extended the machinery to handle real applications of the cloud (MapReduce, etc.).
I will also cover the remaining obstacles to true practicality in this
research area. My hope is to communicate cautious optimism.
------
Michael Walfish is an associate professor in the CS department in the
Courant Institute at NYU, which he joined at the beginning of this year. Prior to that, he was an assistant professor 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 and his Ph.D. from MIT, both in Computer Science.
Friday, December 12, at 11am in 10.099, 2 Metrotech Center