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

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

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.