CRII: AF: RUI: Verifiable Computation Outsourcing: A Non-Cooperative Approach

Williams College, Williamstown MA

Investigators

Abstract

With the growing popularity of cloud computing, most computation today is not done locally but rather outsourced to third-party service providers (SPs). Outsourcing computation brings up the following research problem: how can the client outsourcing the computation verify that it has been performed correctly, without having to redo it? Most previous work has studied this problem from a security standpoint, assuming that the SPs are malicious or adversarial. This assumption does not capture the nature of SPs on internet marketplaces, who are often profit-driven, performing computation for money. This project approaches the problem of verifying outsourced computation from an economic perspective. In particular, this project focuses on SPs that want to maximize their payment, with the goal of designing payment schemes that directly incentivize correctness. The advantage of this approach is that is leads to verification protocols that are simple and practical, and require extremely small verification overhead on the part of the client. This project will advance understanding of the role of incentives in algorithms, which has wide applications to areas such as crowdsourcing, cloud computing and social computing. Interactive proofs (IP) are a fundamental theoretical framework used to study verifiable computation outsourcing. In an IP, the weak client (or verifier) interacts with powerful service providers (or provers) to determine the truthfulness of their claim. Existing IP protocols largely fall into two categories: the cooperative-prover model such as classical IPs or the competing-prover model such as refereed games. In computation-outsourcing applications, the nature of SPs is arguably in the middle of these two extremes, neither cooperative or competitive, but rational---acting to maximize their own payment. The model of non-cooperative rational interactive proofs was introduced recently to capture this middle ground. This project aims to take advantage of this new model to design extremely efficient interactive proofs tailored for computation outsourcing. As part of this work, new insights and techniques from game theory and mechanism design will be used to design protocols that: (a) achieve extremely small verification overhead compared to existing rational-proof and refereed-games protocols, (b) guarantee robustness against deviating provers (measured by the notion of utility gap), and (c) do not rely on private channels of communication between the verifier and provers. The project is divided into two parts. The first focuses on improving the verification overhead of existing non-cooperative rational proofs exponentially while simultaneously achieving large utility gap. The second focuses on improving the state-of-the-art delegation schemes based on refereed games by removing the requirement that at least one prover is honest and leveraging incentives of non-cooperative provers to improve the verification overhead asymptotically. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.