ECCC-Report TR13-165https://eccc.weizmann.ac.il/report/2013/165Comments and Revisions published for TR13-165en-usThu, 10 Jul 2014 02:34:52 +0300
Revision 3
| Verifying computations without reexecuting them: from theoretical possibility to near-practicality |
Michael Walfish,
Andrew Blumberg
https://eccc.weizmann.ac.il/report/2013/165#revision3How 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.Thu, 10 Jul 2014 02:34:52 +0300https://eccc.weizmann.ac.il/report/2013/165#revision3
Revision 2
| Verifying computations without reexecuting them: from theoretical possibility to near-practicality |
Michael Walfish,
Andrew Blumberg
https://eccc.weizmann.ac.il/report/2013/165#revision2How 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.]Fri, 29 Nov 2013 14:58:19 +0200https://eccc.weizmann.ac.il/report/2013/165#revision2
Revision 1
| Verifying computations without reexecuting them: from theoretical possibility to near-practicality |
Michael Walfish,
Andrew Blumberg
https://eccc.weizmann.ac.il/report/2013/165#revision1How 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.]Fri, 29 Nov 2013 14:49:35 +0200https://eccc.weizmann.ac.il/report/2013/165#revision1
Paper TR13-165
| Verifying computations without reexecuting them: from theoretical possibility to near-practicality |
Michael Walfish,
Andrew Blumberg
https://eccc.weizmann.ac.il/report/2013/165How 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.Thu, 28 Nov 2013 18:01:56 +0200https://eccc.weizmann.ac.il/report/2013/165