Fair Payments for Outsourced Computations

Initiated by volunteer computing efforts, the computation outsourcing problem can become a compelling application for networked set-top-boxes and mobile devices. In this paper we extend such environments with the ability to provide secure payments in exchange for outsourced CPU cycles. Previous contributions in wired networks have almost exclusively tackled only one side of the problem -- offering incentives for volunteer participation and preventing worker laziness. This makes sense in static environments where reputable outsourcers have little to gain from incorrectly rewarding honest participation. However, this assumption is no longer valid in ad hoc environments, where unique identities are difficult to provide and anyone can outsource computations. In this paper we propose a solution that simultaneously ensures correct remuneration for jobs completed on time and prevents worker laziness. Our solution relies on an offline bank to generate and redeem payments; the bank is oblivious to interactions between outsourcers and workers. In particular, the bank is not involved in job computation or verification. Our experiments show that the solution is efficient: the bank can perform hundreds of payment transactions per second and the overheads imposed on outsourcers and workers are negligible.

I. Introduction

While extensively studied for their information dissemination and media hosting capabilities, ad hoc networks have received considerably less attention for their computing outsourcing potential. The reasons are obvious: mobile devices are usually less capable than PCs and their reliance on battery power makes them an unlikely choice for outsourcing their CPU. In this work we consider however a special type of networked devices: set-top-boxes (STBs) and mobile phones. IP based STBs are not only always plugged in and networked but also idle for long intervals. Moreover, many cellphones are left on while charging and at night incur minimal networking fees. Most STBs and smartphones have processors in the 300MHz-1GHz range [6], [18]. This, coupled with the pervasiveness of such devices ¹

There are hundreds of millions of cellphones and tens of millions of IP STBs in use today.

make them an excellent platform for executing outsourced computations.