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

随着云计算的日益普及，今天的大多数计算都不是在本地完成的，而是外包给第三方服务提供商（SP）。外包计算带来了以下研究问题：外包计算的客户如何验证它已经正确执行，而不必重做？大多数以前的工作已经从安全的角度研究了这个问题，假设SP是恶意的或敌对的。这一假设没有抓住互联网市场上SP的本质，他们通常是利润驱动的，为金钱进行计算。本项目从经济角度探讨了验证外包计算的问题。特别是，该项目侧重于希望最大限度地提高其支付的SP，其目标是设计直接激励正确性的支付方案。这种方法的优点是，它导致验证协议是简单和实用的，并要求在客户端的一部分非常小的验证开销。该项目将促进对激励在算法中的作用的理解，该算法在众包、云计算和社会计算等领域具有广泛的应用。交互式证明（IP）是用于研究可验证计算外包的基本理论框架。在IP中，弱客户端（或验证者）与强大的服务提供者（或证明者）交互，以确定其声明的真实性。现有的IP协议主要分为两类：合作证明模型，如经典的IP或竞争证明模型，如裁判游戏。在计算外包应用中，SP的性质可以说是在这两个极端的中间，既不合作也不竞争，但理性的-采取行动，以最大限度地提高自己的报酬。最近引入了非合作理性交互式证明模型来捕获这一中间立场。这个项目旨在利用这种新的模式来设计非常有效的交互式证明，为计算外包量身定制。作为这项工作的一部分，新的见解和技术，从博弈论和机制设计将被用来设计协议，（a）实现极小的验证开销相比，现有的合理证明和裁判游戏协议，（B）保证鲁棒性对偏离证明（衡量的概念效用差距），（c）不依赖于私人渠道之间的通信验证和证明。该项目分为两个部分。第一个重点是提高现有的非合作理性证明的验证开销指数，同时实现大的效用差距。第二个奖项的重点是通过取消至少有一个证明者是诚实的要求，并利用非合作证明者的激励来改善验证开销，从而改善基于裁判游戏的最先进的授权计划。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.