Verifiable computing (or verified computation or verified computing) enables a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted users in projects such as SETI@home and also to the growing desire to enable computationally-weak devices to outsource computational tasks to a more powerful computation service, as in cloud computing. The concept dates back to work by Babai et al., and has been studied under various terms, including "checking computations" (Babai et al.), "delegating computations", "certified computation", and verifiable computing. The term verifiable computing itself was formalized by Rosario Gennaro, Craig Gentry, and Bryan Parno, and echoes Micali's "certified computation".
Motivation and overview The growing desire to outsource computational tasks from a relatively weak computational device (client) to a more powerful computation services (worker), and the problem of dishonest workers who modify their client's software to return plausible results without performing the actual work motivated the formalization of the notion of Verifiable Computation. Verifiable computing is not only concerned with getting the result of the outsourced function on the client's input and the proof of its correctness, but also with the client being able to verify the proof with significantly less computational effort than computing the function from scratch. Considerable attention has been devoted in verifying the computation of functions performed by untrusted workers including the use of secure coprocessors, Trusted Platform Modules (TPMs), interactive proofs, probabilistically checkable proofs, efficient arguments, and Micali's CS proofs. These verifications are either interactive which require the client to interact with the worker to verify the correctness proof, or are non-interactive protocols which can be proven in the random oracle model.
Verification by replication The largest verified computation (SETI@home) uses verification by replication. The SETI@home verification process involves one client machine and many worker machines. The client machine sends identical workunits to multiple computers (at least 2). When not enough results are returned in a reasonable amount of time—due to machines accidentally turned off, communication breakdowns, etc.—or the results do not agree—due to computation errors, cheating by submitting false data without actually doing the work, etc.—then the client machine sends more identical workunits to other worker machines. Once a minimum quorum (often 2) of the results agree, then the client assumes those results (and other identical results for that workunit) are correct. The client grants credit to all machines that returned the correct results.
Verifiable computation Gennaro et al. defined the notion of verifiable computation scheme as a protocol between two polynomial time parties to collaborate on the computation of a function F: {0,1}n → {0,1}m. This scheme consists of three main phases:
Preprocessing. This stage is performed once by the client in order to calculate some auxiliary information associated with F. Part of this information is public to be shared with the worker while the rest is private and kept with the client. Input preparation. In this stage, the client calculates some auxiliary information about the input of the function. Part of this information is public while the rest is private and kept with the client. The public information is sent to the worker to compute F on the input data. Output computation and verification. In this stage, the worker uses the public information associated with the function F and the input, which are calculated in the previous two phases, to compute an encoded output of the function F on the provided input. This result is then returned to the client to verify its correctness by computing the actual value of the output by decoding the result returned by the worker using the private information calculated in the previous phases. The defined notion of verifiable computation scheme minimizes the interaction between the client and the worker into exactly two messages, where a single message is sent from each party to the other party during the different phases of the protocol.
An example scheme based on fully homomorphic encryption Gennaro et al. defined a verifiable computation scheme for any function F using Yao's garbled circuit combined with a fully homomorphic encryption system. This verifiable computation scheme VC is defined as follows: VC = (KeyGen, ProbGen, Compute, Verify) consists of four algorithms as follows:
… excerpt ends here. Continue reading the full article.
