云计算视角下可验证计算的分析研究

2018-04-20张琳

长春工程学院学报（自然科学版） 2018年1期

张　琳

(芜湖职业技术学院网络工程学院，安徽芜湖 241003)

0　引言

目前，云计算被认为是信息技术时代的重要变革，其独特的魅力就在于其强大的计算能力、高效性、资源共享性等优点。云计算利用云服务器端进行数据存储、分包以及程序运行等操作，提高了用户对数据管理的便捷及可操作性。但在云计算环境下，数据信息和应用软件都被转移到云服务器端，所有服务维护和数据管理都委托给云计算服务提供商来完成，云计算机的运行模式给其广泛应用与大力推广带来很多数据安全和用户数据隐私方面的问题[1]。云服务的使用者如何才能确信云计算服务提供商提供的计算结果和信息是正确的、是可被接受的，这就需要可验证计算来加以分析。

1　可验证计算概述及基本流程

1.1　可验证计算概述

可验证计算是在云计算或分布式计算的环境下,用于验证远程服务器在分包计算过程中的计算结果是否具有可靠性的重要手段。可验证计算主要涵盖交互式证明系统(IPs)、概率可验证系统(PCPs)和密码学等方面内容[2]。关于可验证计算的一般过程可概述如下：

使用者U将输入变量x和相关程序f(x)，一并传输给P，证明者P计算出f(x)的值，并将计算结果y重新发送给U。此时，使用者U和证明者P之间就会发生如下的交互行为：

1)如果返回的结果y和使用者U输入的f(x)的数据完全一样，则表示证明者P为使用者U返回的数据y完全正确，则说明证明者P可验证准确结果。在这一交互过程中，不仅完成使用者U交付给验证者P的工作，还为使用者U提供判断依据。

2)如果返回的结果y不等于使用者输入的f(x)的值，那么说明验证者P输出的值y与使用者U所发送的数据存在一定差异，那么使用者U就很有可能拒绝接受验证者的信息。

1.2　可验证计算的一般流程

可验证计算的一般流程主要包括编译处理、交互处理和验证分析等阶段。可验证计算协议的流程如图1所示。

图1　可验证计算协议一般流程图

第1个阶段：编译处理阶段。使用者U与证明者P，将应用程序的高级语言，这里所提及的高级语言有别于通常所说的高级语言(比如java、C#等)，而是与C 或Pascal语言比较接近的程序设计语言，称为SFDL语言或BFDL语言(针对两种不同的编译器而言),并将其转换为布尔电路集或代数约束集。

第2个阶段：交互处理阶段。证明者P与使用者U进行交互处理，基于不同的编译器所产生的布尔电路集或代数约束集C表示应用程序f，使用者U将变量x输入，并将x的值发送给P，证明者P计算C值，得出结果为y，y和C所执行的轨迹{C，x，y}发送至使用者U。

第3个阶段：验证分析阶段。证明者P如果能够对{C，x，y}构建出有效执行轨迹，就说明这一次运算结果是正确的，那么P就会得到使用者U的信任，反之，如果证明者P输出的结果是错误的，也就是y不等于f(x)，那么就说明对于{C，x，y}这个执行轨迹，没有进行正确、有效的执行。在此过程中使用者U须慎重选择要查询编码的位置，这是可验证计算中非常重要的问题。

2　可验证计算的基本设计原则及计算模型

2.1　可验证计算的基本设计原则

2.1.1成本原则

在验证计算的过程中所产生的成本，要低于在本地使用过程中所形成的各种成本之和，同时，使用者所需要的经济成本需控制在合理的预算之内，验证系统为了确保程序能准确、快速地运行，需提供大量有效的技术、人力、物力保障。这些成本就需要使用者分摊，在云计算的具体应用中，表现在云计算厂商会收取用户一定费用。

2.1.2证明者不完全可信原则

不可假设证明者能完全遵守协议内容，在验证过程中可能出现不遵守规则的行为，证明者出现恶意攻击的状态等非信任的行为，这些情况的出现表明证明者是不可完全信任的，应通过可验证计算加以验证。

2.1.3使用通用程序原则

在一些特殊情况下，使用者不会采用经常使用的通用程序，会采用通过限制可验证计算协议使用的程序，以达到实际应用的要求。因此，正常情况下就要对使用者所用的程序做出一些假设，尽量使用通用程序来设计，可有效保证程序的兼容性[2]。

2.2　云计算下的可验证计算模型

云计算是以数据存储、资源付费使用、应用程序托管等组成的网络架构，通过整合资源、服务外包形式，使得云用户的计算能力不再受个体计算能力与资源约束。在这个服务外包的过程中，会出现不经计算的答案，某些软件恶意的外部攻击，也会影响计算结果的正确性[2]。在云计算下的可验证计算是来源于两大证明系统和密码学理论。

在可验证计算领域常见的两大编译器为：FairPlay编译器是较基础的编译器，可将程序编译成布尔电路集；Benjamin编译器是在FairPlay编译器基础上加以改进的，它可将基于高级语言的程序转化为约束集。接下来将转化的布尔电路集或代数约束集进行验证分析。如图2所示：可验证计算基本模型[1]：

图2可验证计算的基本模型

2.3　基于Benjamin编译器的可验证计算操作过程

利用Benjamin编译器将高级程序语言编写的程序转化为代数约束集的操作过程主要分为以下两个部分：

利用BFDL，结合函数内联等转化，编译成单赋值列表；将赋值列表转换为可验证计算所接受的约束集[3]。

BFDL实例描述：以s=9为例，简要概述经过Benjamin编译器，将高级语言编写的程序经过编译、单赋值并转化为代数约束集。单赋值以下为列表：

…

以下为约束集：

3　基于交互系统的可验证计算协议分析

基于交互系统的可验证计算协议是可验证计算中较常见的一种形式，它的一般过程如图3所示。

图3　基于交互系统的可验证计算一般过程

假设执行这一程序：程序目的是计算输入x的函数f(x)。第一步，使用者U将x值和程序f传输给证明者P，并将随机选取的输入多项扩展函数值作为隐含的值m，因为m不依赖即将执行的程序，因此并不需要在输入程序之前去选取m。

第二步，证明者P和使用者U进行一系列交互(电路层数设为d)，在证明者P与使用者U的交互过程中，U控制引导P从而生成U0(0，0，…0)=Q0递归到Ud(Ad)=Qd，x的低阶多项式扩展函数就是Ud，此刻Ud在Ad点的函数值由U来计算，同时检测P的回复值是否一致。

使用者U发送给证明者P询问向量为Ai=(a1，a2，a3…)，P计算Qi=Ui(Ai),Qi是由U以递归的形式检测，由U随机生成询问向量，并将程序f的计算结果植入到证明者P对最开始询问向量的回复值中，依次类推，关于U的输入变量的多项式扩展函数在某一点的值Qd，就包含在P对最后一个询问向量的回复值里，若P对所有询问向量回复的内容都一致，证明者P令使用者U确信其遵守协议，即判断正确执行程序，因此，计算结果被U接受，反之，若U知道P在某处欺骗了它，使用者U就会拒绝接收[3]。