ACM通信
研究突出了
技术视角:在卸载计算中捕捉谎言(和错误
考虑这样一个客户，他想在一些数据集上运行一个计算机程序，但是缺乏这样做的处理能力。因此，客户端(或验证者)访问强大但不可信的验证者，验证者不仅必须运行程序并返回输出，还必须提供输出正确性的正式保证。这个框架捕捉了各种各样的真实场景。验证者和验证者可以建模一个客户端和一个商业云计算服务，或者一个CPU和一个快速但可能有故障的协处理器，或者一个外围设备和一个大型计算机。
验证者如何获得正确性的保证，而不只是忽略验证者并在本地执行程序?至少在没有对“作弊”证明者的行为做出强有力的假设的情况下，这甚至都不明显是可能的。事实上，研究人员已经提出了许多依赖于这些假设的解决方案，包括复制、审计和使用可信硬件。相比之下，可验证计算(VC)的研究领域更有野心:它寻求的解决方案不需要对作弊证明者的行为做出任何假设。
理论计算机科学家在20世纪80年代末和90年代初发现了效率惊人的VC协议。虽然有几种形式(称为交互证明、概率可检验证明和参数系统)，但它们都提供了以下保证:如果证明者返回的输出是不正确的，那么验证者将以很高的概率发现证明者在说谎，无论验证者如何努力试图说服验证者。此外，这些协议确保验证者所做的仅仅是读取输入，验证者所做的仅仅是执行程序。
这些发现对计算复杂性理论产生了变革性的影响，许多结果至今仍在探索中。但是，尽管它们有显著的渐近性，所有这些协议都被认为是不切实际的，而且有很好的理由。简单的实现会有高得可笑的具体成本，证明者需要数百万年的时间来证明正确性，即使是很小的计算，验证者只有在真正巨大的输入上才会节省相对于本地执行的时间。
但在过去几年里，这一观点受到了挑战，因为一些研究小组开发出了成本大幅降低的VC协议。这些团体遵循不同的理论方法，采取了几种不同的方针。最终的实现集合结合了算法改进和系统工作，以实现接近真正的实用性的成本。
下文中描述的匹诺曹系统完善了Gennaro等人的一个重要理论进展。1这两件作品共同代表了速度、通用性和功能方面的巨大改进。匹诺曹提供了一个非交互参数系统，支持用C的子集编写的程序，并以可验证的方式自动执行程序。匹诺曹的验证器会进行一次性的预计算，根据要执行的计算构造一个公钥;如果同一个计算机程序在多个输入端运行，那么可以对所有输入使用同一个键。由匹诺曹的证明程序产生的证明很短(288字节)，并且易于验证。作者通过几个测试程序证明了系统的能力，从矩阵乘法到晶格气体模拟。
将《匹诺曹》置于更广泛的背景下是值得的。各种实现的VC协议在表达性、特性和效率之间提供了广泛的权衡，blumberg和Walfish提供了这些权衡的详细比较。2一般来说，交互证明是最不通用的，但在应用时成本最低。论证系统，尤其是像匹诺曹这样的非交互式系统，更昂贵:匹诺曹的一些成本仍然非常高，尤其是验证程序的运行时间。此外，验证器的一次性预计算可能比局部执行的成本高几个数量级，这意味着验证器需要许多输入来节省工作。但这些费用伴随着普遍性和功能的大幅增加。特别是，匹诺曹支持的一个关键特性是零知识，可以用一个例子来最好地解释:假设一个计算机程序接受两个输入，一个来自验证者，另一个来自验证者，并且验证者的输入是敏感的。有人可能希望验证者运行程序并向验证者提供答案，而不透露任何关于验证者输入的额外信息。一个典型的例子是，有人想要和别人比较他或她的工资，但其他人的实际工资必须保密。匹诺曹是第一个提供这种零知识证明的实现系统。
随着VC协议成本的不断提高，它们可能会在更广泛的应用中真正具有实用性，从而为处理真实系统中的信任和正确性问题提供了一种新的方法。但关键的一点是，当多方持有敏感的输入时，可能没有替代零知识证明的方法(相比之下，当输入不敏感时，本地执行总是替代外包计算的方法，尽管不那么吸引人)。因此，即使效率的提高逐渐减少，在一些重要的场景中，像匹诺曹这样的系统是唯一的选择。在这些设置中，作者实现的效率提高是至关重要的，我们在像Pinocchio这样的系统中看到的各种开销可能已经可以接受了。
参考文献
1.Gennaro, R.等。二次跨度程序和没有pcp的简洁NIZKs。EUROCRYPT、2013、626645。
2.Walfish, M.和Blumberg, A.J.在不重新执行的情况下验证计算:从理论可能性到接近实际。Commun。ACM 58岁2(2015年2月)，7484。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM股份有限公司
没有发现记录