SIGN IN SIGN UP
Verifying the correctness of remote executions: from wild implausibility to near practicality Full Text: Author:
PDF
Tools and Resources Buy this Article
Get this Article
Michael Walfish NYU and UT Austin
2013 Article
Published in: · Proceeding HotDep '13 Proceedings of the 9th Workshop on Hot Topics in Dependable Systems Article No. 7 Farmington, Pennsylvania — November 03 - 03, 2013 ACM New York, NY, USA ©2013 table of contents ISBN: 978-1-4503-2457-1 doi> 10.1145/2524224.2524225
Recommend the ACM DL to your organization TOC Service: Email
Bibliometrics · Citation Count: 1 · Downloads (cumulative): 61 · Downloads (12 Months): 12 · Downloads (6 Weeks): 2
RSS
Save to Binder Export Formats: BibTeX EndNote ACM Ref Upcoming Conference: SOSP '19 Share:
|
Contact Us | Switch to single page view (no tabs) Abstract
Authors
References
Cited By
Index Terms
Publication
Reviews
Comments
Table of Contents
How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant today, as much computation is now outsourced: it is performed by machines that are rented, remote, or both. Various solutions have been proposed that make assumptions about the class of computations, the failure modes of the performing computer, etc. However, deep results in theoretical computer science---interactive proofs (IPs) [3, 9, 10, 13, 19] and probabilistically checkable proofs (PCPs) [1, 2] (coupled with cryptographic commitments [11, 12] in the context of arguments [5])---tell us that a fully general solution exists that makes no assumptions about the third party: the local computer can check the correctness of a remotely executed computation by inspecting a succinct proof returned by the third party. The rub is practicality: if implemented naively, the theory would be preposterously expensive (e.g., trillions of CPU-years or more to verify simple computations). Over the last several years, a number of projects have brought this theory to near-practicality in the context of implemented systems [4, 6--8, 14--18, 20--22]. The pace of progress has been rapid, and there have been many encouraging developments in this emerging area of proof-based verifiable computation. My talk will cover the high-level problem, the theory that solves the problem in principle, the projects that have reduced the theory to near-practicality and implemented it, and open questions for the area. My hope is to communicate the excitement surrounding all of the projects in the area.
Powered by The ACM Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc. Terms of Usage Privacy Policy Code of Ethics Contact Us
