Verifying computations without reexecuting them: from theoretical possibility to near-practicality.
Michael Walfish, Andrew J. Blumberg · Electronic colloquium on computational complexity · 2013
How can a single PC check a herd of supercomputers with unreliable software and untested hardware? This classic problem is particularly relevant today, as much computation is now outsourced: it is performed by machines that are rented, remote, or both. For example, service providers (SPs) now offer storage, computation, managed desktops, and more. As a result, relatively weak devices (phones, tablets, laptops, PCs) can run computations (storage, image processing, data analysis, video encoding, etc.) on banks of machines controlled by someone else. This arrangement is known as cloud computing, and its promise is enormous. A lone graduate student with an intensive analysis of genome data can now rent a hundred computers for twelve hours for less than $200. And many companies now run their core computing tasks (Web sites, application logic, storage, etc.) on machines owned by SPs, which automatically replicate applications to meet demand. Without cloud computing, these examples would require buying hundreds of physical machines when demand spikes . . . and then selling them back the next day. But with this promise comes risk. SPs are complex and large-scale, making it unlikely that execution is always correct. Moreover, SPs do not necessarily have strong incentives to ensure correctness. Finally, SPs are black boxes, so faults—which can include misconfigurations, corruption of data in storage or transit, hardware problems, malicious operation, and more [33]—are unlikely to be detectable. This raises a central question, which goes beyond cloud computing: How can we ever trust results computed by a third-party, or the integrity of data stored by such a party? A common answer is to replicate computations [15, 16, 34]. However, replication assumes that failures are uncorrelated, which may not be a valid assumption: the hardware and software platforms in cloud computing are often homogeneous. Another answer is auditing—checking the responses in a small sample—but this assumes that incorrect outputs, if they occur, are relatively frequent. Still other solutions involve trusted hardware [39] or attestation [37], but these mechanisms require a chain of trust and assumptions that the hardware or a hypervisor works correctly. But what if the third party returned its results along with a proof that the results were computed correctly? And what if the proof were inexpensive to check, compared to the cost of re-doing the computation? Then few assumptions would be needed about the kinds of faults that can occur: either the proof would check or it wouldn’t. We call this vision proof-based verifiable computation, and the question now becomes: Can this vision be realized for a wide class of computations? Deep results in complexity theory and cryptography tell us that in principle the answer is “yes”. Probabilistic proof systems [24, 44]— which include interactive proofs (IPs) [3, 26, 32], probabilistically checkable proofs (PCPs) [1, 2, 44], and argument systems [13] (PCPs coupled with cryptographic commitments [30])—consist of two parties: a verifier and a prover. In these protocols, the prover can efficiently convince the verifier of a mathematical assertion. In fact, the acclaimed PCP theorem [1, 2], together with refinements [27], implies that a verifier only has to check three randomly chosen bits in a suitably encoded proof! Meanwhile, the claim “this program, when executed on this input, produces that output” can be represented as a mathematical assertion of the necessary form. The only requirement is that the verifier knows the program, the input (or at least a digest, or fingerprint, of the input), and the purported output. And this requirement is met in many uses of outsourced computing; examples include MapReducestyle text processing, scientific computing and simulations, database queries, and Web request-response. Indeed, although the modern significance of PCPs lies elsewhere, an original motivation was verifying the correctness of remotely executed computations: the paper quoted in our epigraph [4] was one of the seminal works that led to the PCP theorem. However, for decades these approaches to verifiable computation were purely theoretical. Interactive protocols were prohibitive (exponential-time) for the prover and did not appear to save the verifier work. The proofs arising from the PCP theorem (despite asymptotic improvements [10, 20]) were so long and complicated that it would have taken thousands of years to generate and check them, and more storage bits than there are atoms in the universe. But beginning around 2007, a number of theoretical works achieved results that were especially relevant to the problem of verifying cloud computations. Goldwasser et al., in their influential Muggles paper [25], refocused the theory community’s attention on verifying outsourced computations, in the context of an interactive proof system that required only polynomial work from the prover, and that applied to computations expressed as certain kinds of circuits; Ishai et al. [29] proposed a novel cryptographic commitment to an entire linear function, and used this primitive to apply simple PCP constructions to verifying general-purpose outsourced computations; and a couple of years later, Gentry’s breakthrough protocol for fully homomorphic encryption (FHE) [23] led to work (GGP) on non-interactive protocols for general-purpose computations [17, 21]. These developments were exciting, but, as with the earlier work, implementations were thought to be out of the question. So the theory continued to remain theory—until recently. The last few years have seen a number of projects overturn the conventional wisdom about the hopeless impracticality of proof-based verifiable computation. These projects aim squarely at building real systems based on the theory mentioned above, specifically PCPs and Muggles (FHE-based protocols still seem too expensive). The