ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR13-165 | 10th July 2014 02:34

Verifying computations without reexecuting them: from theoretical possibility to near-practicality

RSS-Feed

Abstract:

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 in the context of cloud computing.

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, probabilistically checkable proofs (PCPs) coupled with cryptographic commitments, etc. -- 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 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 reduced this theory to near-practice in the context of implemented systems; we call this field _proof-based verifiable computation_. The pace of progress has been rapid, and there have been many exciting developments. This paper covers the high-level problem, the theory that solves the problem in principle, the work required to bring this theory to near-practicality, the various projects in the area, and open questions. Many of these questions cut across multiple sub-disciplines of computer science: complexity theory, cryptography, systems, parallel programming, and programming languages.



Changes to previous version:

Substantial text revisions. Additional sidebar. Performance study now compares to our implementation of TinyRAM. This is an expanded version of what will appear in Communications of the ACM.


Revision #2 to TR13-165 | 29th November 2013 14:58

Verifying computations without reexecuting them: from theoretical possibility to near-practicality


Abstract:

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 in the context of cloud computing.

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, probabilistically checkable proofs (PCPs) coupled with cryptographic commitments, etc. -- 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 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 reduced this theory to near-practice in the context of implemented systems; we call this field _proof-based verifiable computation_. The pace of progress has been rapid, and there have been many exciting developments. This paper covers the high-level problem, the theory that solves the problem in principle, the work required to bring this theory to near-practicality, the various projects in the area, and open questions. Many of these questions cut across multiple sub-disciplines of computer science: complexity theory, cryptography, systems, parallel programming, and programming languages.

[Note: this survey, which is about applying complexity-theoretic and cryptographic machinery, is written for a general computer science audience. However, we feel that it may be of interest to the ECCC community, so we are posting it here.]



Changes to previous version:

Add clarification paragraph at end of abstract. Reinsert keywords.


Revision #1 to TR13-165 | 29th November 2013 14:49

Verifying computations without reexecuting them: from theoretical possibility to near-practicality





Revision #1
Authors: Andrew Blumberg, Michael Walfish
Accepted on: 29th November 2013 14:49
Downloads: 520
Keywords: 


Abstract:

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 in the context of cloud computing.

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, probabilistically checkable proofs (PCPs) coupled with cryptographic commitments, etc. -- 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 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 reduced this theory to near-practice in the context of implemented systems; we call this field _proof-based verifiable computation_. The pace of progress has been rapid, and there have been many exciting developments. This paper covers the high-level problem, the theory that solves the problem in principle, the work required to bring this theory to near-practicality, the various projects in the area, and open questions. Many of these questions cut across multiple sub-disciplines of computer science: complexity theory, cryptography, systems, parallel programming, and programming languages.

[Note: this survey, which is about applying complexity-theoretic and
cryptographic machinery, is written for a general computer science
audience. However, we feel that it may be of interest to the ECCC
community, so we are posting it here.]



Changes to previous version:

Added a clarification paragraph to the end of the abstract.


Paper:

TR13-165 | 28th November 2013 17:37

Verifying computations without reexecuting them: from theoretical possibility to near-practicality


Abstract:

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 in the context of cloud computing.

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, probabilistically checkable proofs (PCPs) coupled with cryptographic commitments, etc. -- 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 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 reduced this theory to near-practice in the context of implemented systems; we call this field _proof-based verifiable computation_. The pace of progress has been rapid, and there have been many exciting developments. This paper covers the high-level problem, the theory that solves the problem in principle, the work required to bring this theory to near-practicality, the various projects in the area, and open questions. Many of these questions cut across multiple sub-disciplines of computer science: complexity theory, cryptography, systems, parallel programming, and programming languages.



ISSN 1433-8092 | Imprint