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

随着云计算的日益普及，今天的大多数计算不是在本地完成，而是外包给第三方服务提供商(SP)。外包计算带来了以下研究问题：外包计算的客户如何在不重做的情况下验证计算是否正确执行？大多数以前的工作都是从安全的角度研究这个问题，假设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.