基于智能合约的三方博弈防共谋委托计算协议

周全兴,李秋贤,樊玫玫

(1.凯里学院 大数据工程学院,贵州 凯里 556011; 2.贵州大学 数学与统计学院,贵阳 550025)

0 概述

随着新型委托计算[1]模式的兴起,用户不再受自身存储、计算等能力限制,可以在任意时间和地点使用云计算服务完成庞大的计算任务。新型计算模式在给用户带来便利的同时,如何保证计算结果的隐私性、完整性与正确性成为其面临的问题。传统委托计算包括基于复杂性理论构造的委托计算、基于安全硬件构造的委托计算、基于密码学技术构造的委托计算3种方案。其中,基于复杂性理论构造的计算方案包括交互式证明系统[2-3]、概率验证证明(Probabilistically Checkable Proofs,PCP)技术[4-5]和基于随机预言机的证明技术[6]等工具构造方案。基于安全硬件构造的计算方案从电子商务角度提出基于安全协议处理器的委托计算[7],该方案局限性在于其不能保证数据的隐藏性。基于密码学技术构造的计算方案包括全同态加密[8-9]、混淆电路[10]和同态MAC/签名[11]等工具构造方案。

在实际委托计算环境中,由于计算方具有自利性,因此其可能会偏离计算协议。例如,计算方希望通过投资更少计算资源与收取更多费用以提高收入,这使得委托方付出较大代价但得不到正确结果。计算方为从某种计算方式输出中受益也可能尝试修改特定结果。此外,委托方需要在计算协议中验证结果正确性,从而降低了协议计算效率。为此,考虑将博弈理论和传统委托计算相结合形成理性委托计算方案以解决此类问题。

理性委托计算属于理性密码学[12]研究范畴,其中,理性多方计算[13]、理性秘密共享[14]、理性安全通信[15]和理性交换协议[16]等已成为理性密码协议的研究热点。文献[17]提出一种证明参与方为理性的系统。文献[18]深入研究计算能力受限的理性Arguments,解决了秘密共享协议重建阶段玩家不合作的问题。文献[19]从理性角度分析安全通信问题,提出贝叶斯理性秘密共享方案。文献[20]利用博弈论优势设计理性委托计算协议,该协议参与方达到帕累托最优状态。

本文提出一种基于智能合约的三方博弈防共谋理性委托计算协议。利用博弈论和信誉机制建立三方博弈委托计算模型,将计算结果交给信誉度较高的裁判方验证,使理性参与方诚实对待计算任务,采用基于以太坊区块链的智能合约框架设计委托计算协议,以提高委托计算效率,并确保计算结果的正确性和可追溯性。

1 相关理论

1.1 扩展式博弈

扩展式博弈G的表达式为:

G={P,S,u}

(1)

1个扩展式博弈是1个五元组,表示为:

P,Q,p,(Ii)i∈P,(≤i)i∈P

(2)

其中:P为参与方集合;p为参与方函数,其赋予每个非终端序列(Q的元素)1个P的元素,Z为结果向量;Ii为参与方i∈P的信息集,其代表参与方进行选择时已知的信息;≤i为参与方的偏好关系,每个i∈P都有Z上的1个偏好关系;Q为行动序列集合,且满足如下性质:

1)空序列∅∈Q。

1个扩展式博弈可视为1棵博弈树,树的边和节点分别对应博弈行动和行动序列,树的根对应空序列∅。博弈开始于空序列∅,结束于终端节点(树叶)。当到达任意非终端行动序列q∈Q后,参与方从A(q)中选择行动a,序列q被行动a扩展后,博弈历史变为q.a。当1个行动序列q达到终端节点后,博弈结束。终端节点以收益向量标识代表参与方间的偏好关系。

1.2 贝叶斯纳什均衡

(3)

1.3 智能合约

基于以太坊的智能合约[21]是定位于以太坊1个特定地址上的代码和数据集合。智能合约记录均寄存在区块链中,当触发合约中某些条件后,定义在合约中的代码将自主执行,且执行结果可溯源但不可更改。理想智能合约可视为1台图灵机,其按照预先编好的规则自动执行程序,不受外界影响。基于区块链去中心化去信任的环境,各理性参与方在该环境中将实现智能合约。多个理性参与方创建智能合约后,在区块链中发布其所创建的智能合约并按照预设条件执行,将结果发布在区块中。智能合约区块链架构[21]如图1所示。

图1 智能合约区块链架构Fig.1 Smart contract blockchain architecture

2 系统模型

理性委托计算结合博弈论和委托计算思想,从参与方自利角度出发,通过效用函数保障计算结果的可靠性。参与方根据激励合约采取策略,在追求自身利益最大化的同时保证全局利益最优化,从而达到贝叶斯纳什均衡。本文结合博弈论与智能合约技术建立委托计算博弈模型,为理性委托计算协议的构建和分析提供模型依据。

2.1 系统参数

本文基于智能合约的三方博弈防共谋委托计算协议参数设置如表1所示。

表1 协议参数设置Table 1 Protocol parameter setting

在表1中,i={2,3}={C,R}为理性计算方和裁判方的计算成本。为使合约保持均衡,协议中部分参数遵循如下关系:

1)ri>ci,否则计算方与裁判方不会接受计算任务。

2)d>c2,当押金足够大时,激励参与方总是诚实地计算函数。

3)b

4)b>t,否则裁判方不会执行共谋协议。

5)m>e,n>e,否则计算方或裁判方将因计算本身价值过高而采取非合作行为。

在理性委托计算方案中,参与方的行为具有自利属性,会尽量使自身收益达到最大。在理性委托计算方案中,参与方的效用根据其能否完整无误完成计算任务来评估。基于贝叶斯博弈研究委托计算问题,根据扩展式博弈模型对理性委托计算协议机制建模,其中主要包括建模委托计算协议博弈的参与方集合、信息集、可行策略以及参与方效用函数等。

2.2 参与方

对理性委托计算协议的各参与方建模,在该系统中主要存在委托方D、计算方C和裁判方R3个参与方。由于理性委托计算无需再验证结果,将裁判方R作为1个参与方以保证整个委托计算过程公平和结果正确,因此该理性委托计算博弈的参与方集合定义为P={D,C,R}。

2.3 信息集

2.4 可行策略

在博弈模型中:委托方策略集为sD={sD1,sD2},sD1、sD2分别表示委托方选择激励和不激励策略;计算方的策略集为sC={sC1,sC2},sC1、sC2分别表示计算方选择诚实和不诚实策略;裁判方策略集为sR={sR1,sR2},sR1、sR2分别表示裁判方选择合作和不合作策略。

2.5 效用函数

在理性委托计算方案中,根据参与方是否正确完成计算任务衡量其效用函数。假设f为委托方发送给计算方的计算任务,由于参与方均有理性,裁判方可能为更大利益选择与计算方同盟而返回无效计算结果给委托方。向量Z=(zD,zC,zR)表示委托计算博弈的结果,且(zD,zC,zR)∈[0,1]3,当zD=α、zC=β、zR=δ时:委托方最少以概率α选择激励计算方以完成计算任务,并选择激励裁判公平对待计算结果;计算方最少以概率β诚实对待计算任务,并将计算结果返还给裁判方与委托方;裁判方最少以概率δ选择与委托方合作,并最多以概率1-δ选择与计算方合作,这是因为如果裁判方被委托方发现,则将面临更多货币和信誉惩罚。

在本文方案中:委托方希望计算方能诚实计算委托的计算任务,在结果向量Z=(zD,zC,zR)中表现为zC越大越好,该效用记为uD(zC);委托方希望裁判方选择与其合作,公平对待计算任务,在结果向量Z中表现为zR越大越好,该效用记为uD(zR);计算方希望委托方有最大奖励激励,在结果向量Z中表现为zD越大越好,该效用记为uC(zD);计算方希望裁判方能与其合作,返回无效结果给委托方以获得更大效益,在结果向量Z中表现为zR越大越好,该效用记为uC(wR);裁判方希望委托方有最大奖励激励,在结果向量Z中表现为zD越大越好,该效用记为uR(zD);裁判方希望计算方选择与其合作,并获得来自计算方的额外奖励,在结果向量Z中表现为zC越大越好,该效用记为uR(zC)。理性委托计算三方博弈支付矩阵分别如表2～表5所示。表5中裁判方合作与不合作策略是针对委托方而言。

表2 委托方与计算方之间的混合策略支付矩阵Table 2 Hybrid strategy payment matrix between delegation party and computing party

表3 委托方与裁判方之间的混合策略支付矩阵Table 3 Hybrid strategy payment matrix between delegation party and referee party

表4 计算方与裁判方发起合谋的混合策略支付矩阵Table 4 Mixed-strategy payment matrix initiated by the computing party and referee party

表5 委托方、计算方和裁判方之间博弈支付矩阵Table 5 Game payment matrix between delegation party,computing party and referee party

3 方案构造

基于智能合约的三方博弈防共谋委托计算协议的安全性与参与方效用函数密切相关。参与方为获得最大利益必须遵循激励合同,偏离协议的参与方将受到严重惩罚,罚金远大于其在委托计算中获得的收益。委托计算分为初始化、委托计算和支付效用3个阶段。

3.1 初始化阶段

假设协议中委托方D具有计算数据m,在该阶段委托方对数据进行加密以防止计算方篡改。委托方选择函数f并输入x,计算m1=H(f)、m2=H(x)和2个承诺s1=Com(m1)、s2=Com(m2)。委托方将承诺作为契约的一部分发送到区块链,并将(f,x,s1,s2)发送到云端。云层验证区块链上的承诺正确后,委托方与计算方签署合约。

3.2 委托计算阶段

由于委托方希望计算方预付押金以激励其正确计算,因此双方签署合约。如果计算方返回正确答案,则退还押金;如果计算方不诚实,未返回正确答案,则押金归委托方所有,具体操作流程如下:

1)委托方与计算方签署委托合约C1。

2)计算方接收输入x函数f(·)的计算任务。

3)委托方向计算方支付金额r2,用以正确及时地计算f(x)。

4)作为接收计算任务的条件,计算方与委托方签订委托合约时需支付金额为d的押金,该押金由智能合约持有。

5)为激励计算方不偏离协议,委托方选择支付金额为w的货币以激励计算方诚实计算委托任务。

6)计算方需在时间T1之前支付押金。如果支付时间T>T1,合约将终止,并退还已付押金。

7)计算方必须在时间T2之前完成计算,并传递计算结果f(x)。

8)在截止时间T2后,委托方执行以下操作:

(1)如果计算方未能交付计算结果,则押金全部归委托方所有。

(2)如果计算方交付计算结果,委托方将其与裁判方发送的结果进行对比,如果结果相同,则委托方必须支付约定金额r2并将押金d退还计算方,否则押金全部归委托方所有,且裁判方将公布此计算方信誉度为H-。

9)如果在时间T3>T2之后,委托方既没有提出异议也没有支付金额给计算方,则裁判方将强制委托方向计算方支付金额r2并退回押金。

委托方与计算方所签订合约C1中有各阶段的截止时间T1

此外,需考虑到计算方可能为得到更大利益而与裁判方发起共谋合约。在共谋合约中,计算方支付金额为b的贿赂金给裁判方。如果裁判方选择与计算方合作,则双方提交金额为t的押金以激励双方合作,且违反合谋一方将受到失去押金的惩罚,具体操作流程如下:

1)计算方发起与裁判方的共谋合约C2。

2)共谋双方将f′(x)≠f(x)作为计算结果发送给委托方。

3)作为签署合约的条件,计算方必须支付金额为b+t的押金,裁判方必须支付金额为t的押金,上述押金由智能合约持有。

4)在时间T2结束之前,双方需交付上述押金,否则合约终止。

5)双方共谋合约完成后,会出现以下情况:

(1)如果双方均在合约中输出f′(x),那么金额为t的押金返还计算方,金额为t+b的押金返还裁判方。

(2)如果计算方背叛裁判方,那么金额为2t+b的押金返还裁判方。

(3)如果裁判方背叛计算方,那么金额为2t+b的押金返还裁判方。

根据上述情况,委托方选择与裁判方签署合作合约,以避免计算方与裁判方之间发起共谋合约。委托方提供额外奖励给裁判方,以激励裁判方公平对待计算结果,具体操作流程如下:

1)委托方与裁判方签署合约C3。

2)裁判方必须返回f(x)作为计算结果。

3)作为签署合约的条件,委托方必须支付裁判方在计算过程中所需金额和奖励金额之和的押金,裁判方需支付金额远大于2d的押金,该押金由智能合约持有。

4)为激励裁判方不偏离协议,委托方选择支付金额为w的奖金以激励裁判方诚实计算接收任务。

5)合约C3必须在时间T2之前签署,否则合约终止,已交付的押金退回。

6)裁判方需在时间T2之前提交计算结果,并将委托方与计算方返还的计算结果进行对比,具体操作如下:

(1)如果双方计算结果相等,则委托方与裁判方的押金将被退回,裁判方宣布计算方信誉度为H+,委托方支付给计算方和裁判方奖金。

(2)如果双方计算结果不相等,则裁判方宣布计算方信誉度为H-,委托方收取计算方提交的押金。

(3)如果双方计算结果相等,但委托方在使用计算结果时发现有误,则委托方通过智能合约追溯计算方与裁判方,并对双方进行惩罚,宣布裁判方信誉度为H--,计算方信誉度为H-。

3.3 支付效用阶段

当委托方收到计算方返还的计算结果后,将其与裁判方返还结果进行比对,如果相同,则委托方接收此计算结果,否则委托方拒绝接收。同时,还需考虑委托方与计算方交互时间T3的范围,若时间T

委托方、计算方和裁判方进行交互式证明后,委托方只需验证计算方与裁判方返还的承诺值,根据各方期望效用函数对自身在委托计算中的成效进行判断。若任何一方偏离协议,则根据合约另外两方有权要求取得远大于计算成本的赔偿金作为补偿,并在区块链上记录偏离协议一方的信誉度。由于本文方案中参与方均为理性状态,因此通过制定激励合约和效用函数以激励各参与方积极遵守协议,从而提高委托计算效率。

4 方案分析

定理1如果α=0,m>t+c2,n>b+t+c3且参与方均为理性状态,则基于智能合约的委托计算三方博弈方案存在贝叶斯纳什均衡。

证明根据本文构建的三方博弈模型,存在以下情况:

1)当委托方对计算方和裁判方同时实施激励(α=1)时,若计算方以概率β对委托方诚实地执行计算任务,则已签订共谋协议裁判方继续执行该协议的预期效用表示为:

EuR(合作)=β(r3-w+b+t-n)+

(1-β)(r3-w+b-n)

(4)

裁判方不再执行共谋协议的预期效用表示为:

EuR(不合作)=β(r3+w-c3)+

(1-β)(r3+w-c3-t)

(5)

当裁判方合作与不合作的效用函数相等时,实现博弈均衡,即:

EuR(合作)=EuR(不合作)

(6)

由式(6)计算得到:

n*=b+t-2w+c3

(7)

当裁判方违背计算任务的罚金额度n=n*时,无论裁判方是否选择与计算方合作均可以实现效用相等;当n>n*时,裁判方最佳选择策略是不与计算方合作而诚实对待计算任务;当n

若裁判方以概率δ选择与计算方共谋执行计算任务,则签订共谋协议计算方对委托方诚实的预期效用表示为:

EuC(诚实)=(1-δ)(r2+w-c2-b-t)+

δ(r2+w-c2)

(8)

计算方对委托方不诚实的预期效用表示为:

EuC(不诚实)=(1-δ)(r2-w2-b-m)+

δ(r2-w-m+t)

(9)

当裁判方合作与不合作的效用函数相等时,实现博弈均衡,即:

EuC(诚实)=EuC(不诚实)

(10)

由式(10)计算得到:

m*=t-2w+c2

(11)

当计算方违背计算任务的罚金额度m=m*时,签订共谋协议的计算方任意选择是否诚实对待计算任务均可实现效用相等;当m>m*时,计算方最佳选择策略是不再执行共谋协议而诚实对待计算任务;当m

2)当委托协议不对计算方和裁判方实施激励(α=0)时,若计算方以概率β对委托方诚实地执行计算任务,则裁判方同计算方合作与不合作的博弈均衡表示为:

n*=b+t+c3

(12)

若裁判方以概率δ选择与计算方共谋执行计算任务,则计算方对委托方诚实与不诚实的博弈均衡表示为:

m*=t+c2

(13)

因此,当m>t+c2且n>b+t+c3时,计算方最佳选择策略是诚实对待计算任务,裁判方最佳选择策略是不与计算方合作。

综上所述,在参与方尽量获取各自最大利益的情况下,当α=0、m>t+c2、n>b+t+c3时,委托方的委托代价最小,且计算方与裁判方总以概率1发送正确的计算结果,此时基于智能合约的委托计算三方博弈方案达到贝叶斯纳什均衡。

5 仿真实验与结果分析

本文实验采用Solidity语言编写智能合约,采用3台PC主机分别模拟委托方、计算方和裁判方,具体硬件配置如表6所示。为模拟计算过程中三方博弈,基于以太坊搭建私有链,并将上述合约部署在该链中。

表6 硬件配置Table 6 Hardware configuration

三方博弈过程如图2所示。委托方将待计算任务及初始值x委托给计算方与裁判方,计算方与裁判方分别向合约DCR_C1中存入定金r及押金d,合约签署完成。根据合约,计算方需在规定时间前向委托方返回计算结果fC(x),但计算方为获取更大利益可能与裁判方进行合谋,通过合约DCR_C2约定贿赂金b、合谋押金t及合谋结果fCR(x)。为避免上述合谋,委托方可选择与裁判方签订验证合约DCR_C3,使得计算方及裁判方计算结果公开可验证,以保证出现问题后委托方可对计算方与裁判方进行问责。

图2 三方博弈过程Fig.2 Three-party game process

5.1 合约签署

5.1.1 委托合约DCR_C1

在发布计算委托过程中,委托方与计算方签署委托合约DCR_C1,该合约的伪代码具体如下:

/* Auto-transfer in case of overtime */

}

function Delegate()public payable{

x ← input the x

r ← input reward

timeT1 ← set the delegation time

}

function GetOrder()public payable {

d ← input the deposit of guarantee

timeT2 ← set the computing time

}

function Computing() public{

/* Computing the f(x).*/

}

function SendRes_C()public{

nC_fx ← set the results of calculation

timeT3 ← set the time of refereeing

}

function Referee() public{

nR_fx ← get the result of refereeing

IfnC_fx==nR_fx

then /* pay r and g to computing party.*/

else /* pay r and g to delegation party.*/

end if

}

}

委托方通过调用合约中的Delegate()函数传入计算变量值x,并向合约中预付定金r作为计算方的计算报酬。当合约完成定金扣除后,设置委托任务截止时间timeT1,计算方需在该时间前通过GetOrder()向合约预付计算押金d以获得该任务计算权。当合约完成押金扣除后,设置计算截止时间timeT2,计算方需在该时间前通过SendRes_C ()向委托方发送计算结果nC_fx,并设置仲裁截止时间 timeT3。委托方可根据实际需要决定是否调用Referee()完成计算结果验证。在上述过程中,系统通过TimeTick()对超时任务流程进行自动支付或退款,以保证合约账户中资金被锁死。

5.1.2 共谋合约DCR_C2

计算方接到计算任务后,为使自身利益最大化,可能会与裁判方签署共谋合约DCR_C2,该合约的伪代码具体如下:

contract DCR_C2{

function TimeTick( ){

/* Auto-transfer in case of overtime */

}

function Bribery()public payable{

nC_tb ← input the bribery

nCR_fx ← set bribery answer

timeT2 ← set the computing time

}

function GetBribery()public payable{

nR_t ← input the deposit of bribery

}

function CheckRes()public{

/* Get funding based on answers

sent by both parties; */

}

}

计算方通过Bribery()向合约中支付贿赂金nC_tb,并约定共谋函数值nCR_fx,同时设置计算任务截止时间timeT2,裁判方需在截止时间之前支付接受贿赂的押金nR_t以完成共谋合约签订。当委托方利用裁判方发回的结果完成验证后,计算方与裁判方通过CheckRes()完成合谋资金分配。为保证合约执行过程中资金不被锁死,同样通过TimeTick( )完成合约账户资金自动支付或退款。

5.1.3 验证合约DCR_C3

委托方根据自身需要,通过Appeal ()向验证合约DCR_C3预付验证定金d,并设定申请截止时间timeT1,裁判方需在申请截止时间前向合约中存入金额为2d的押金。当双方资金完成扣除后,委托方与裁判方的验证合约DCR_C3正式成立。根据合约,裁判方需在申请截止时间timeT2前通过SendRes_R ( )向委托方发送计算结果。DCR_C3合约的伪代码具体如下:

contract DCR_C3{

function TimeTick(){

/* Auto-transfer in case of overtime */

}

function Appeal ()public payable{

x ← input the x

d ← input the deposit of appealing

timeT1 ← set the appealing time

}

function GetReferee()public payable{

2d ← input the deposit of refereeing

timeT2 ← set the refereeing time

}

function Computing()public{

/* Computing the fx.*/

}

function SendRes_R( )public{

/* Send the result of refereeing

to the delegation party; */

}

}

5.2 合约执行代价

为了解三方博弈过程中各合约执行成本,对合约执行代价进行统计,结果如表7所示。可以看出:委托方在不申请仲裁的情况下,合约执行代价c1=0.15,申请仲裁总代价为c1+c5+c9=0.34;计算方诚实计算直接成本为c2+c3+c4=0.52,发起共谋总成本为c2+c4+c6+c8=0.33;裁判方诚实计算直接成本为c11+c12+c13=0.67,接受贿赂的总成本为c7+c11+c12=0.23。

表7 合约执行代价统计结果Table 7 Statistical results of contract execution costs

在实验过程中,若设置委托方的奖金r=$1.00,则委托方在信任计算方而不申请验证的情况下,委托总代价为r+c1=$1.15,而计算方诚实计算的预期收益为h=r-c2-c3-c4=$0.48。若令贿赂金b=0.5h,t=4b,d=1.5r,m=4d,n=4r,则委托方、计算方及裁判方的收益如表7所示。可以看出,在委托方不信任计算方且计算方与裁判方存在共谋的情况下,若裁判方遵守合约DCR_C2,则最终将遭到严厉惩罚而导致损失;裁判方在选择不遵守该合约而诚实计算的情况下将会获得收益,因而裁判方更愿意选择诚实计算。此外,由于共谋过程中无论裁判方是否诚实计算,计算方都将受到惩罚,因此计算方只能选择诚实计算。在上述过程中,裁判方、计算方都将选择诚实计算,基于此,在该博弈过程中,委托方可选择信任计算方而不进行结果验证,从而降低委托代价。由表7得到三方博弈过程中的代价及收益,如图3所示。

图3 三方博弈过程中的代价及收益Fig.3 The cost and benefit in the process of three-party game

5.3 性能分析

图4 不同模指数计算方案所用时间的对比Fig.4 Comparison of time of different modulus index calculation schemes

6 结束语

本文提出一种将博弈理论与传统委托计算相结合的理性委托计算协议。基于信誉机制建立三方博弈委托计算模型,把计算任务交给不受信任且自利的计算方和裁判方,采用激励机制和智能合约框架设计委托计算协议,保证参与方不偏离协议执行。基于以太坊区块链的实验结果表明,该协议委托计算效率较直接计算和传统委托计算协议更高,可使三方博弈达到贝叶斯纳什均衡。下一步将在本文基础上对更多参与方理性委托计算进行研究,以满足多方委托计算协议的需求。