Toward Practical Verification of Outsourced Computations Using Probabilistically Checkable Proofs (PCPs)
Abstract
This paper describes preliminary results and outlines the plan of attack for an on-going project to develop a practical system for verifying outsourced computations. We want a client to be able to describe a computation to a server, get back a purported output and some auxiliary information, and use that auxiliary information to verify that the output is correct. For outsourcing to be worthwhile, the verification process should be substantially more efficient than simply executing the computation. Our approach to this problem is to exploit the theory of probabilistically checkable proofs (PCPs). Specifically, our project seeks to build a bridge between the theory and an implementable system. We describe a protocol for outsourced computation that includes algorithmic refinements of the PCP protocol and end-to-end instantiation of the necessary steps (e.g., compilation to a form suitable for application of the PCP theorem). Although we are in the process of implementing the protocol and do not have experimental results, we present a detailed analysis that provides cause for optimism: our cycle and memory usage costs strongly suggest that our system will be useful. We focus on the example of matrix multiplication, where we show that for large matrices, our method achieves enormous savings for the client and requires feasible amounts of bandwidth.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 12, 2010
- Accession Number
- AD1024615
Entities
People
- Andrew Blumberg
- Michael Walfish
- Srinath Setty
Organizations
- University of Texas at Austin