Incentivized Outsourced Computation Resistant to Malicious Contractors

With the rise of Internet computing, outsourcing difficult computational tasks became an important need. Yet, once the computation is outsourced, the job owner loses control, and hence it is crucial to provide guarantees against malicious actions of the contractors involved. One may want to ensure that both the job itself and any inputs to it are hidden from the contractors, while still enabling them to perform the necessary computation. Furthermore, one would check that the computation was carried out correctly. In this paper, we are not concerned with hiding the job or the data, but our main task is to ensure that the job is computed correctly. We also observe that not all contractors are malicious; rather, majority are rational. Thus, our approach brings together elements from cryptography, as well as game theory and mechanism design. We achieve the following results: (1) We incentivize all the rational contractors to perform the outsourced job correctly, (2) we guarantee high fraction (e.g., 99.9 percent) of correct results even in the existence of a relatively large fraction (e.g., 33 percent) of malicious irrational contractors in the system, (3) and we show that our system achieves these while being almost as efficient as running the job locally (e.g., with only 3 percent overhead). Such a high correctness guarantee was not known to be achieved with such efficiency.