The Pepper project at NYU and UT Austin is tackling the problem of verifying outsourced computations. Our approach is to reduce to practice powerful tools from complexity theory and cryptography: probabilistically checkable proofs (PCPs), efficient arguments, etc.
Highlights of the project’s results include:
- improving the performance of a PCP-based efficient argument by a factor of 1020
- broadening the computational model used in verifiable computation: from Boolean circuits to a general-purpose model
- extending verifiability to representative uses of cloud computing: MapReduce jobs, simple database queries, interactions with private state, etc.
- a series of built
systems that implement the aforementioned
refinements, with the following features:
- GPU acceleration
- a compiler that allows the developer to express a computation in a restricted subset of C; the compiler produces executables that implement the protocol entities
Though these systems are not yet at true practicality, they are arguably practical in some regimes. More importantly, these systems highlight the potential applicability of the theory, and indeed, there is now a thriving research area based on this promise. Thus, we are hopeful that over the next few years, the underlying theoretical tools will find their way into real systems.