TWC: Medium: Scaling proof-based verifiable computation

这项研究解决了系统安全中的一个基本问题：一台机器如何将计算指定给另一台机器，然后在不执行计算的情况下，检查另一台机器是否正确地执行了计算？在过去的几年里，出现了一种解决这个问题的新方法，其基础是改进加密和理论工具，并将它们纳入已建成的系统中。然而，尽管取得了令人兴奋的进步，但由此产生的系统在正常意义上仍然不实用。这个项目的目标是在现实的输入大小下，为某些现实世界的问题提供真正的实际性能。这项研究可能会对云计算、分布式系统、不可信的硬件制造商和国防应用等第三方计算模型产生广泛影响。更广泛地说，真正廉价的可验证计算将使构建系统的新方法成为可能。该项目应用编程语言社区的想法来更有效地表示计算；应用程序近似的概念来产生有效的部分可验证性；改进和实现承诺减少内存使用的协议；并开发减少开销并且更适合重要计算类别的新协议。这些方法包括改进和适应现有的理论，在改进的基础上实现系统，对性能和成本进行建模，以及进行严格的实验评估。结果将通过同行评议的出版物以及免费提供的软件和实验配置进行传播。

This research addresses a fundamental problem in systems security: how can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? Over the last several years, a new approach to this problem has emerged, based on refining cryptographic and theoretical tools, and incorporating them into built systems. However, despite exciting advances, the resulting systems are still not practical in the normal sense. This goal of this project is truly practical performance for certain real-world problems at realistic input sizes. This research could have wide-ranging impact on third-party computing models such as cloud computing, distributed systems, untrusted hardware manufacturers, and defense applications. More broadly, truly inexpensive verifiable computation will enable new ways of building systems. The project applies ideas from the programming languages community to represent computation more efficiently; applies notions of program approximation to produce efficient partial verifiability; refines and implements protocols that promise reduced memory utilization; and develops new protocols that reduce overhead and are better-suited to important classes of computations. The methods include refining and adapting existing theory, implementing systems based on the refinements, modeling performance and costs, and conducting rigorous experimental evaluations. The results will be disseminated through peer-reviewed publications, and through software and experimental configurations that will be available freely.