Verifiable computing (or verified computation or verified computing) enables a
computer to
offload the
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as '' computers''. An esp ...
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
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as '' computers''. An esp ...
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 of weak clients to outsource computational tasks to a more powerful computation service like in
cloud computing
Cloud computing is the on-demand availability of computer system resources, especially data storage ( cloud storage) and computing power, without direct active management by the user. Large clouds often have functions distributed over m ...
. 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 ]