田有亮，蔣小霞

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州大學(xué)省部共建公共大數(shù)據(jù)國家重點(diǎn)實(shí)驗(yàn)室（籌），貴州 貴陽 550025；3.貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025）

1 引言

委托計(jì)算[1]是云計(jì)算與大數(shù)據(jù)背景下的新型計(jì)算范式，資源受限的委托方可將自己無法完成的計(jì)算任務(wù)委托給具有強(qiáng)大資源的計(jì)算方。針對如何驗(yàn)證計(jì)算方返回結(jié)果正確性的問題，傳統(tǒng)的委托計(jì)算通?；谟?jì)算復(fù)雜度理論構(gòu)造方案，其主要工具為交互式證明系統(tǒng)[2]、概率檢測證明定理[3]、非交互式證明[4-7]等。其中，Costello 等[7]于2015 年基于簡潔承諾證明（SCP,succinct commit-and-prove）提出一個通用的可公開驗(yàn)證計(jì)算系統(tǒng)Geppetto。

近年來，將博弈論與傳統(tǒng)委托計(jì)算相結(jié)合的理性委托計(jì)算成為研究熱點(diǎn)。Belenkiy 等[8]提出了一個激勵外包計(jì)算方案，對不同類型的承包商進(jìn)行獎懲。Kupcu[9]指出文獻(xiàn)[8]不提供公平支付，無法抵抗非理性的惡意承包商，因此提出了一個能抵抗惡意承包商的激勵外包計(jì)算方案。Dong 等[10]將博弈論與智能合約結(jié)合，設(shè)置不同合約激勵計(jì)算方誠實(shí)執(zhí)行協(xié)議。Tian 等[11]將博弈論與信息論相結(jié)合探究了委托計(jì)算中參與者的攻防極限。

除了經(jīng)濟(jì)激勵以外，信譽(yù)激勵是理性委托計(jì)算方案的另一分支。Zhang 等[12]提出了基于信譽(yù)的激勵眾包計(jì)算協(xié)議，并采用重復(fù)博弈框架建立博弈模型。Ma 等[13]利用演化博弈理論構(gòu)建了可信眾包服務(wù)中基于信譽(yù)的激勵博弈模型。Jiang 等[14]提出了通用可組合（UC,universally composable）框架[15]下基于信譽(yù)和合同理論的理性委托計(jì)算協(xié)議。

在以上基于經(jīng)濟(jì)或信譽(yù)激勵的委托計(jì)算方案中，文獻(xiàn)[8,10,12,14]假設(shè)委托方為誠實(shí)參與者，僅對理性計(jì)算方設(shè)置激勵機(jī)制；文獻(xiàn)[9,11,13]雖然將委托方與計(jì)算方均視為理性，但是往往假設(shè)存在一個可信的第三方系統(tǒng)維護(hù)參與者之間的經(jīng)濟(jì)支付與信譽(yù)評價(jià)。為實(shí)現(xiàn)公平性，許多學(xué)者利用區(qū)塊鏈去中心化特性基于比特幣[16]設(shè)計(jì)外包計(jì)算公平支付方案[17-19]。

2016 年，Kosba[20]提出了密碼學(xué)的區(qū)塊鏈模型Hawk，利用UC 理論描述與區(qū)塊鏈交互的分布式協(xié)議安全性。同年，Juels 等[21]采用Hawk 模型分析智能合約的安全性。2020 年，Dorsala 等[22]基于智能合約實(shí)現(xiàn)了外包計(jì)算的公平支付方案，并采用文獻(xiàn)[20-21]中框架分析協(xié)議安全性。該方案針對傳統(tǒng)基于驗(yàn)證的1 對1（即一個委托方對一個計(jì)算方）委托計(jì)算場景，采用文獻(xiàn)[6]中算法實(shí)現(xiàn)協(xié)議的公開可驗(yàn)證性，但方案中缺乏相應(yīng)的博弈模型、UC 安全模型以及UC 安全性證明。

本文利用文獻(xiàn)[20-21]中模型探究在UC 框架下的公平理性委托計(jì)算，具體研究工作如下。

1) 構(gòu)建雙向信譽(yù)激勵模型。本文結(jié)合直接信譽(yù)和間接信譽(yù)形成全局信譽(yù)模型，其中，委托方與計(jì)算方均具有信譽(yù)，雙方根據(jù)自己的信譽(yù)要求選擇合適的合作方，且參與者的行為對其信譽(yù)產(chǎn)生影響。

2) 基于博弈論構(gòu)建理性委托計(jì)算博弈模型。本文將委托方與計(jì)算方均視為理性參與者，根據(jù)雙方行為策略形式化具有完美信息的動態(tài)博弈，通過博弈分析得到委托方與計(jì)算方均選擇誠實(shí)執(zhí)行協(xié)議時(shí)達(dá)到該博弈模型下的唯一子博弈精煉納什均衡。

3) 構(gòu)建公平理性委托計(jì)算UC 安全模型。本文分析公平理性委托計(jì)算場景需滿足可驗(yàn)證性安全需求、參與者理性決策需求、經(jīng)濟(jì)與信譽(yù)公平需求，以及敵手模型，基于UC 理論構(gòu)造公平理性委托計(jì)算理想函數(shù) F(Ideal-FRDC)。

4) 設(shè)計(jì)可安全實(shí)現(xiàn)理想函數(shù) F(Ideal-FRDC)的公平理性委托計(jì)算協(xié)議。本文分別采用SCP 方案[7]實(shí)現(xiàn)公開可驗(yàn)證性、利用博弈論分析參與者的理性行為、采用智能合約實(shí)現(xiàn)經(jīng)濟(jì)與信譽(yù)公平性。方案分析證明了該協(xié)議滿足UC 安全性。

2 準(zhǔn)備知識

2.1 SCP

定義1SCP。對于表示計(jì)算函數(shù)F(x)的所有變量元組χ，其固定長度為l，以及對應(yīng)的多項(xiàng)式時(shí)間可驗(yàn)證關(guān)系{?λ}λ∈N，Geppetto 協(xié)議[7]包含6 個多項(xiàng)式時(shí)間算法(KenGen=(KenGen1,KenGen2),Digest,Prove,Verify=(Verify1,Verify2))。

密鑰產(chǎn)生包含2 個概率算法。(τ) ←KeyGen1(1λ)：將安全參數(shù)λ作為輸入，輸出包含仿真和提取部分的陷門τ=(τS,τE)，陷門獨(dú)立于關(guān)系R∈?λ。(EK,VK) ←KeyGen2(τ,R)：將陷門τ和關(guān)系R∈?λ作為輸入，輸出公開評估密鑰EK 和公開驗(yàn)證密鑰VK。其中，EK 包含摘要密鑰EKz，VK 包含摘要驗(yàn)證密鑰VKz，z∈[l]。

π←Prove(EK,χ,O)：輸入評估密鑰EK，消息χ和隨機(jī)數(shù)組O，確定證明算法輸出簡潔證明π，即π的長度是關(guān)于λ的多項(xiàng)式。

{0,1}←Verify1()：將摘要驗(yàn)證密鑰VKz和摘要作為輸入；若摘要通過驗(yàn)證，確定摘要驗(yàn)證算法輸出1，否則輸出0。

{0,1}←Verify2(VK,C,π)：將驗(yàn)證密鑰VK、l個摘要C 和證明π作為輸入；若證明通過驗(yàn)證，確定驗(yàn)證算法輸出1，否則輸出0。

2.2 博弈論

定義2擴(kuò)展式博弈[23]。擴(kuò)展式博弈的基本表達(dá)式為G={P,A,S,s,Z,U}，且參與者的行動具有先后順序。其中，參與者集合P={P1,P2,…,Pn]；行動集合A={A1,A2,…,An]，Ai={ai}為參與者Pi可以選擇的行動集合；策略集合S={S1,S2,…,Sn]，參與者Pi可以選擇的策略集合用Si={si]表示；策略組合s=(s1,s2,…,sn)，其中策略si∈Si；Z為博弈模型的終端節(jié)點(diǎn)集合；支付組合U=(u1,u2,…,un)，其中，ui:Z→R 表示參與者Pi在終端節(jié)點(diǎn)上的效用函數(shù)[10]。

定義3子博弈精煉納什均衡[23]。在一個具有完美信息的動態(tài)博弈中，如果滿足以下條件，則各參與者的策略組合s*=是一個子博弈精煉納什均衡。

1) 它是原博弈的納什均衡。

2) 它在每一個子博弈中都構(gòu)成納什均衡。

2.3 UC 框架

定義4UC 仿真[15]。令Π 和ρ為概率多項(xiàng)式時(shí)間（PPT,probabilistic polynomial time）協(xié)議。如果對于任何PPT 敵手A，存在PPT 敵手S 使對任何PPT 環(huán)境Z，無法以一個不可忽略的概率區(qū)分現(xiàn)實(shí)世界與理想世界，在現(xiàn)實(shí)世界中Z 與A、Π 交互，而在現(xiàn)實(shí)世界中Z 與S、F 交互，則稱協(xié)議Π UC-仿真協(xié)議ρ。

定義5UC 實(shí)現(xiàn)[15]。令F、Π 分別為理想函數(shù)和協(xié)議。如果協(xié)議Π UC-仿真F 的理想?yún)f(xié)議，則稱協(xié)議Π UC-實(shí)現(xiàn)理想函數(shù)F，也稱協(xié)議Π 安全實(shí)現(xiàn)理想函數(shù)F，此時(shí)Π 是UC 安全的。

2.4 智能合約

智能合約[24]是運(yùn)行在區(qū)塊鏈上的一個計(jì)算機(jī)程序?qū)嵗?，由所有共識節(jié)點(diǎn)執(zhí)行。其主要由程序代碼、存儲文件和賬戶余額組成。任何用戶都可以通過向區(qū)塊鏈發(fā)送事務(wù)來創(chuàng)建合約，然后將合約部署到區(qū)塊鏈中。合約創(chuàng)建時(shí)，固定的程序代碼反映了交易用戶間的合約條款邏輯，一旦滿足合約觸發(fā)條件便自動執(zhí)行，不受外界干預(yù)。因此，可將智能合約看作一個可信的第三方，其代碼邏輯執(zhí)行的正確性由共識機(jī)制保證。

2.5 密碼學(xué)的區(qū)塊鏈模型

密碼學(xué)的區(qū)塊鏈模型[20]將理想描述以及在區(qū)塊鏈上或者用戶端運(yùn)行的協(xié)議用偽碼形式表示成程序，分別被稱為理想程序、合約程序和用戶程序。該模型依賴封裝器對協(xié)議進(jìn)行模塊化設(shè)計(jì)，可將程序編譯成UC 框架中的函數(shù)或者協(xié)議。具體地，理想封裝器 F(·)將理想程序轉(zhuǎn)換成理想函數(shù)F(IdealP)；合約封裝器 G (·)將合約程序轉(zhuǎn)換成合約函數(shù) G(ConP)，此合約函數(shù)包含在區(qū)塊鏈上執(zhí)行的程序；協(xié)議封裝器 Π (·) 將用戶程序轉(zhuǎn)換為用戶端協(xié)議 Π(UserP)。

3 問題陳述

3.1 系統(tǒng)模型

本文假設(shè)場景中存在M個委托方與N個計(jì)算方，則委托方集合與計(jì)算方集合分別可用D={D1,…,DM}和W={W1,…,WN}表示。系統(tǒng)模型如圖1 所示，具體描述如下。

圖1 系統(tǒng)模型

首先，委托方Di需向計(jì)算方集合廣播任務(wù)請求及信譽(yù)要求，其中，?i∈{1,2,…,M}。一旦收到來自計(jì)算方的響應(yīng)消息，便從區(qū)塊鏈查看響應(yīng)者的歷史交互評價(jià)并計(jì)算其信譽(yù)值，選擇信譽(yù)最高且滿足自己信譽(yù)要求的計(jì)算方簽署委托合約。Di發(fā)送相關(guān)信息觸發(fā)委托合約，并私下將真實(shí)的任務(wù)發(fā)送給被選擇的計(jì)算方。一旦收到來自計(jì)算方的計(jì)算結(jié)果，Di產(chǎn)生結(jié)果摘要并分別發(fā)送至智能合約和計(jì)算方。當(dāng)從計(jì)算方處收到中間參數(shù)摘要和結(jié)果證明后，Di在本地驗(yàn)證摘要和證明，然后向智能合約發(fā)送確認(rèn)消息以表明計(jì)算方成功執(zhí)行任務(wù)。

計(jì)算方Wj一旦收到Di的廣播信息，便在本地計(jì)算Di的信譽(yù)，其中，?j∈{1,2,…,N}。一旦Di的信譽(yù)滿足自己的信譽(yù)要求，便向Di發(fā)送響應(yīng)信息。若Wj被成功委任，則在本地計(jì)算來自Di的任務(wù)，然后向智能合約提交結(jié)果承諾和中間參數(shù)摘要，并在私下將結(jié)果和中間參數(shù)摘要發(fā)送給Di。收到來自Di的結(jié)果摘要后，Wj生成結(jié)果證明并將其私下發(fā)給Di，將結(jié)果證明承諾發(fā)送給智能合約。若Wj在規(guī)定的時(shí)間內(nèi)未收到合理的支付，可向智能合約發(fā)起仲裁請求。

一旦收到來自委托方的確認(rèn)消息，智能合約僅需負(fù)責(zé)相應(yīng)的收益分配和交互評價(jià)。但當(dāng)收到來自計(jì)算方的仲裁請求時(shí)，智能合約還將調(diào)用內(nèi)部的仲裁合約解決爭端。

由于僅當(dāng)Di選擇不誠實(shí)行為時(shí)，Wj才有可能向委托合約發(fā)起仲裁請求，委托合約隨之調(diào)用仲裁合約，因此，本文在系統(tǒng)模型圖中將這2 個步驟用虛線表示以區(qū)別于正常的交互流程。本文將證明當(dāng)Di和Wj都是理性參與者時(shí)，協(xié)議將不會執(zhí)行這2 個步驟。

3.2 敵手模型

場景中的委托方與計(jì)算方均被視為理性參與者，因此兩者均存在自利行為從而做出偏離協(xié)議的決策。本文考慮以下2 種攻擊策略，且設(shè)計(jì)的協(xié)議在這些可能的攻擊行為下仍是安全的。

錯誤報(bào)告。收到來自計(jì)算方提交的誠實(shí)計(jì)算結(jié)果后，委托方向智能合約發(fā)送認(rèn)證失敗的反饋信息，試圖獲取因?yàn)閾碛姓_計(jì)算結(jié)果帶來的收益而拒絕向計(jì)算方支付委托費(fèi)用以實(shí)現(xiàn)更大效用。

搭便車。收到來自委托方的計(jì)算任務(wù)后，計(jì)算方為了節(jié)省計(jì)算資源，隨意地向智能合約和計(jì)算方提交計(jì)算結(jié)果和證明而非認(rèn)真執(zhí)行計(jì)算任務(wù)。

4 信譽(yù)模型

現(xiàn)有大多數(shù)信譽(yù)方案僅考慮委托方對計(jì)算方進(jìn)行評估的單向信譽(yù)模型，計(jì)算方不掌握委托方的信譽(yù)信息從而無法選擇優(yōu)質(zhì)的合作者。而本文考慮雙向信譽(yù)評估，且結(jié)合直接信譽(yù)和間接信譽(yù)最終形成全局信譽(yù)模型。下文以委托方對計(jì)算方的信譽(yù)評估為例，計(jì)算方可按照相同方式對委托方進(jìn)行信譽(yù)評估。

4.1 直接信譽(yù)

直接信譽(yù)是指由參與交易的Di和Wj以往相互合作累積形成的交互評價(jià)。直接信譽(yù)與歷史交互相關(guān)，且越接近此次交易的交互評價(jià)應(yīng)越能反映參與者當(dāng)前的信譽(yù)。由于委托方與計(jì)算方的每次交易及交互評價(jià)最終都會部署在區(qū)塊鏈上，用參數(shù)t表示部署在區(qū)塊鏈上的第t次交易，且t∈{0,1,2,…]，其中t=0表示參與者尚未開始交易。

其中，當(dāng)Wj在第t次交易中誠實(shí)執(zhí)行由Di委任的任務(wù)時(shí)，=positive ；否則，=negative。若在第t次交易中Wj與Di并未發(fā)生交易，則。顯然，，?i∈[1,…,M]，?j∈[1,…,N]。

其中，λ∈[0,1]為交互評價(jià)的影響因子，且λt-t′減小了歷史交互評價(jià)的影響程度。同樣，?i∈[1,…,M]，?j∈[1,…,N]。由于人類交互的信譽(yù)評價(jià)符合 Gompertz 模型[26]描述的一般發(fā)展規(guī)律，因此本文采用Gompertz 模型來構(gòu)造信譽(yù)模型。則有

其中，a、b、c為模型參數(shù)，a指定信譽(yù)的最大值，b控制沿x軸的位移，c調(diào)節(jié)信譽(yù)模型的增長速率。因此，第t次交易后Di對Wj當(dāng)前的直接信譽(yù)評估可用表示。當(dāng)t=0 時(shí)，即任何委托方與計(jì)算方尚未開始交互，Di無法根據(jù)與Wj以往交互的歷史信息對其進(jìn)行信譽(yù)評估，此時(shí)=0，相應(yīng)的信譽(yù)評估為。因此，參與者之間的默認(rèn)直接信譽(yù)評估值便為aeb。

4.2 間接信譽(yù)

間接信譽(yù)是指由其余委托方對計(jì)算方產(chǎn)生的累加直接信譽(yù)評估，且不同委托方應(yīng)具有不同權(quán)重。此時(shí)，其余委托方被視為推薦者，且若Dk與Di擁有越多相似的交互歷史，即與相同的計(jì)算方交易，則其對間接信譽(yù)的影響越大。令simt(i,k)表示在第t次交易后Di與Dk的相似系數(shù)，本文采用修正余弦函數(shù)來衡量相似度，具體表達(dá)式為[27-28]

其中，I與K分別表示與Di和Dk交互過的計(jì)算方集合；C表示同時(shí)與Di和Dk交互過的計(jì)算方集合，即C=I∩K；與分別表示在第t次交易后Di和Dk對所有交互過的計(jì)算方的平均直接信譽(yù)評估；與分別表示在第t次交易后Di和Dk對Wj的直接信譽(yù)評估。

所有推薦者對Wj的間接信譽(yù)評估為

其中，k∈K，K表示與Wj交互過的推薦者集合。

4.3 全局信譽(yù)

參與者最終的信譽(yù)被稱為全局信譽(yù)，包含直接信譽(yù)和間接信譽(yù)的加權(quán)影響。在第t次交易后，Di對Wj的全局信譽(yù)評估方式為

其中，α∈[0,1]為間接影響因子，當(dāng)α→1時(shí)，間接信譽(yù)即其余委托方對Wj的信譽(yù)評估更能夠決定Wj的最終信譽(yù)，反之亦然。

若Di與Wj在第t+1次交易期間開始交互，雙方將根據(jù)對方前t次交易的累積全局信譽(yù)判斷其是否滿足自己的最低信譽(yù)要求。分別用與表示Di和Wj在第t次交易時(shí)的信譽(yù)閾值要求，對方的信譽(yù)必須不小于此信譽(yù)閾值才會考慮進(jìn)行合作。

5 博弈模型

傳統(tǒng)委托計(jì)算僅側(cè)重于方案的可驗(yàn)證性，無法考慮參與者自利行為對協(xié)議造成的影響。本文從博弈論角度出發(fā)，將委托方和計(jì)算方均視為理性參與者，且參與者為理性是共同知識，利用擴(kuò)展式博弈對參與者進(jìn)行理性建模，博弈模型如圖2 所示。

圖2 博弈模型

此博弈為具有完美信息的動態(tài)博弈。Di收到來自Wj提交的計(jì)算結(jié)果，并對其進(jìn)行驗(yàn)證以獲知對方是否選擇誠實(shí)執(zhí)行任務(wù)后，再決定自己的行動。Wj觀測Di是否完成支付的行動后，再選擇自己是否發(fā)起仲裁請求。

Di與Wj在第t次交易中的博弈模型可表示為Gt=(P,A,S,s,Z,U,E)。

1) 參與者集合P指參與協(xié)議的委托方與計(jì)算方，P={Wj,Di}。

2) 行動集合A指參與者可能選擇的所有行動，A={Aj,Ai}。Wj在面對被委托的任務(wù)時(shí)可能誠實(shí)執(zhí)行，也可能惡意地提交一個錯誤結(jié)果；Wj在面對Di是否支付委托費(fèi)用的行動后，可選擇是否向智能合約發(fā)起仲裁請求。因此，其行動空間為Aj={誠實(shí),惡意,起訴,沉默}。而Di在面對由Wj提交的計(jì)算結(jié)果時(shí)，可選擇向其支付委托費(fèi)用或者拒絕支付，此時(shí)Di的行動空間為Ai={支付,拒絕}。

3) 策略集合S指參與者所有可選擇的策略，S={Sj,Si}。計(jì)算方Wj作為先行動者僅有2 個策略，即={誠實(shí),惡意}；而委托方Di的策略集為Si={{支付,支付},{支付,拒絕},{拒絕,支付}，{拒絕，拒絕}}；此時(shí)，計(jì)算方Wj可進(jìn)一步選擇的策略空間為={{起訴,起訴},{起訴,沉默},{沉默,起訴},{沉默,沉默}]。

4) 策略組合s指各參與者選擇策略形成的二維向量，s=(sj,si)。sj與si表示W(wǎng)j和Di選擇的特定策略。

5) 終端節(jié)點(diǎn)集合Z指博弈模型的所有終端節(jié)點(diǎn)，Z={v1,v2,v3,v4,v5,v6}。

6) 支付組合U=(uj,ui)，其中，ui,uj：Z→R分別為參與者Wj與Di在終端節(jié)點(diǎn)Z的實(shí)值效用函數(shù)。

7) 均衡E指各參與者的最優(yōu)策略組合，即

Di與Wj分別需要提前提交di和dj，參與者僅在誠實(shí)執(zhí)行協(xié)議時(shí)能夠被退還押金，否則，參與者將失去押金。誠實(shí)的參與者不僅能夠收到自己的押金，還將收到非誠實(shí)參與者的押金，作為雙方在交易中誠實(shí)行為的保障。Di需向Wj支付wij作為誠實(shí)完成計(jì)算任務(wù)的酬勞，而計(jì)算方為執(zhí)行計(jì)算任務(wù)需要花費(fèi)cj，假設(shè)計(jì)算方提交錯誤結(jié)果的開銷為0。Di需對Wj提交的計(jì)算結(jié)果進(jìn)行驗(yàn)證，從而花費(fèi)驗(yàn)證ci；而當(dāng)Di收到誠實(shí)計(jì)算的結(jié)果后將獲得fi。若Wj選擇發(fā)起仲裁請求，其開銷為hj。博弈模型中的貨幣參數(shù)及其含義如表1 所示。

表1 貨幣參數(shù)及其含義

為確保Di與Wj之間滿足激勵相容，貨幣參數(shù)需滿足以下關(guān)系。

1)wij＞cj。Di的委托費(fèi)用應(yīng)比Wj誠實(shí)執(zhí)行任務(wù)的開銷大，否則Wj不會愿意接受此計(jì)算任務(wù)。

2)fi＞wij+ci。Di因計(jì)算任務(wù)獲得的收益應(yīng)比自己付出的委托費(fèi)用和驗(yàn)證開銷總和多，否則Di不會愿意將此計(jì)算任務(wù)外包給Wj。

3)di＞cj+hj。為確保誠實(shí)Wj的利益，Di的押金應(yīng)大于Wj誠實(shí)計(jì)算的開銷與仲裁費(fèi)用的總和。

4)dj＞ci。為確保誠實(shí)Di的利益，Wj的押金應(yīng)大于Di的驗(yàn)證開銷。

通過對理性委托計(jì)算博弈模型進(jìn)行分析，得出博弈模型中各終端節(jié)點(diǎn)對應(yīng)委托方與計(jì)算方的效用，具體如表2 所示。

表2 效用分析

6 理想世界

本節(jié)將根據(jù)文獻(xiàn)[20-21]中的框架描述公平理性委托計(jì)算理想程序Ideal-FRDC。令S 為理想敵手。令Winit={W1,…,WN}表示包含所有計(jì)算方的集合。令Wres表示響應(yīng)廣播的計(jì)算方集合，初始化為Wres=?。令Wrep表示響應(yīng)廣播且信譽(yù)滿足信譽(yù)要求的計(jì)算方集合，初始化為Wrep=?。公平理性委托計(jì)算理想程序Ideal-FRDC的設(shè)計(jì)如下。

與經(jīng)典的理想函數(shù)形式化方法不同，本文基于文獻(xiàn)[20-21]中的框架利用理想封裝器F (·)將公平理性委托計(jì)算理想程序Ideal-FRDC轉(zhuǎn)換成公平理性委托計(jì)算理想函數(shù) F(Ideal-FRDC)。在理想世界中，協(xié)議參與者即委托方和計(jì)算方均被視為愚蠢參與者，任何操作均由理想函數(shù)執(zhí)行，而愚蠢參與者只負(fù)責(zé)消息的轉(zhuǎn)發(fā)。理想函數(shù)的執(zhí)行應(yīng)滿足理性委托計(jì)算的傳統(tǒng)安全需求、理性需求、公平需求與敵手模型。具體來說，傳統(tǒng)安全需求包含計(jì)算方提交結(jié)果的可驗(yàn)證性；理性需求包含參與者的理性決策；公平需求包含委托方與計(jì)算方交互的經(jīng)濟(jì)公平性和信譽(yù)公平性；敵手模型刻畫委托方或計(jì)算方可能的攻擊行為。

可驗(yàn)證性。計(jì)算方提交的結(jié)果可被正確驗(yàn)證。對于任意計(jì)算結(jié)果y，均存在一個對應(yīng)的證明π可以驗(yàn)證y是否正確。

理性決策。參與者均作為自利者，基于理性思考后做出效用最大化決策。

經(jīng)濟(jì)公平性。委托方向計(jì)算方支付委托費(fèi)用當(dāng)且僅當(dāng)計(jì)算方提交的結(jié)果被驗(yàn)證為正確。

信譽(yù)公平性。參與者被評估為積極交互僅當(dāng)自己在本次交互中選擇誠實(shí)行為，否則被記錄為消極交互。

攻擊行為。被賄賂的委托方將拒絕向計(jì)算方支付委托費(fèi)用；被賄賂的計(jì)算方將提交錯誤的計(jì)算結(jié)果。

7 現(xiàn)實(shí)世界

為安全實(shí)現(xiàn)理想世界中的理想函數(shù)，現(xiàn)實(shí)世界中的協(xié)議設(shè)計(jì)應(yīng)從可驗(yàn)證安全需求、理性需求和公平需求出發(fā)。本文分別采用文獻(xiàn)[7]中的簡潔承諾證明協(xié)議Geppetto 實(shí)現(xiàn)方案的可驗(yàn)證性，基于博弈論分析參與者的理性決策，利用智能合約實(shí)現(xiàn)參與者之間的信譽(yù)公平性和經(jīng)濟(jì)公平性?；谖墨I(xiàn)[20-21]中的模型，將協(xié)議模塊化設(shè)計(jì)為在區(qū)塊鏈上運(yùn)行的委托合約程序ConP-Delegate 和仲裁合約程序ConP-Arbitrate，以及在用戶端運(yùn)行的程序UserP-FRDC。合約封裝器 G (·)可分別將委托合約程序和仲裁合約程序轉(zhuǎn)換成委托合約函數(shù)G(ConP-Delegate)和仲裁合約函數(shù)G(ConP-Arbitrate)；協(xié)議封裝器 Π (·) 將用戶程序轉(zhuǎn)換為用戶端協(xié)議 Π(UserP-FRDC)。

7.1 合約設(shè)計(jì)

本文借鑒文獻(xiàn)[22]中的思想設(shè)計(jì)合約，委托方需準(zhǔn)備委托合約和仲裁合約。其中，委托合約用于描述委托方與計(jì)算方之間的正常交互；仲裁合約用于解決委托方與計(jì)算方之間的爭端，僅當(dāng)參與者雙方存在爭議時(shí)才會被觸發(fā)。

7.1.1 委托合約

當(dāng)委托方Di與計(jì)算方Wj均同意執(zhí)行任務(wù)F(·)時(shí)，雙方簽署委托合約。當(dāng)且僅當(dāng)計(jì)算方提交的結(jié)果被驗(yàn)證為正確時(shí)，委托方才會向計(jì)算方支付委托費(fèi)用wij。為激勵雙方能夠誠實(shí)行事，要求委托方與計(jì)算方均提前提交押金，誠實(shí)參與者可重新獲得返回的押金，而具有不誠實(shí)行為的參與者將失去押金，且此押金將被誠實(shí)參與者持有。委托合約的具體描述如下。

1) 委托合約由Di與Wj簽署，表明Di選擇將任務(wù)F(·) 委托給Wj，且Wj也同意完成此任務(wù)。

2)Di與Wj均同意時(shí)間參數(shù)υ＜υ1＜υ2＜υ3＜υ4＜υe，其中，υ為當(dāng)前的時(shí)間。

3)Di需提前提交委托費(fèi)用$wij和押金$di，且將任務(wù)承諾(Cx,HEK,HVK)作為輸入觸發(fā)委托合約。

4)Wj需在截止時(shí)間υ1之前提交押金$dj，否則，合約終止且將押金$di和委托費(fèi)用$wij退回給Di。

5) 在截止時(shí)間υ2之前，Wj需提交計(jì)算結(jié)果承諾與中間參數(shù)摘要(Hy,C (Cy∪Cx))，而后Di需提交摘要Cy；否則，合約終止且將押金$di、$dj以及委托費(fèi)用$wij退回給Di。

6)Wj需在截止時(shí)間υ3之前提交證明承諾Hπ。

7)Di需在截止時(shí)間υ4之前提交驗(yàn)證結(jié)果。當(dāng)=1 時(shí)，合約終止且將$dj與$wij發(fā)送給Wj，且Di獲得$di。

8) 當(dāng)Di未在υ4前發(fā)送驗(yàn)證結(jié)果，或在規(guī)定時(shí)間內(nèi)提交的結(jié)果不符合計(jì)算方Wj的預(yù)期，Wj可以選擇發(fā)送任務(wù)與計(jì)算結(jié)果觸發(fā)仲裁合約以解決爭端，且合約終止。Wj一旦發(fā)起仲裁便花費(fèi)$hj。若仲裁合約返回的結(jié)果為=1，將發(fā)送給Di，將$di與$dj發(fā)送給Wj。否則，將$di、$dj與$wij發(fā)送給Di。

9) 當(dāng)υ＞υe且合約還未終止，即仲裁合約未能在規(guī)定時(shí)間內(nèi)給出仲裁結(jié)果時(shí)，將$wij發(fā)送給Di，將$di與$dj發(fā)送給Wj。

10) 委托合約終止前需對Di與Wj的交互行為進(jìn)行評估，且將進(jìn)行存儲。

根據(jù)委托合約的設(shè)計(jì)可基于文獻(xiàn)[20-21]的框架形式化描述委托合約程序ConP-Delegate，具體內(nèi)容如下。

7.1.2 仲裁合約

僅當(dāng)Wj對Di的驗(yàn)證結(jié)果不滿時(shí)，仲裁合約才被觸發(fā)。仲裁合約程序ConP-Arbitrate 執(zhí)行如下。

7.2 協(xié)議描述

本文設(shè)計(jì)的理性委托計(jì)算協(xié)議包含協(xié)商階段和執(zhí)行合約階段，具體描述如下。

7.2.1 協(xié)商階段

此階段，委托方與計(jì)算方根據(jù)信譽(yù)挑選對方作為合作者，具體流程如下。

1) 委托方Di將表示任務(wù)F(·) 的關(guān)系R 及信譽(yù)閾值要求廣播至所有計(jì)算方Wj∈Winit。

2) 計(jì)算方Wj根據(jù)信譽(yù)模型評估Di的信譽(yù)。其中，參與者的單次交互評價(jià)信息可從區(qū)塊鏈上獲取。若，則計(jì)算方Wj同意執(zhí)行此任務(wù)，返回響應(yīng)消息。將Wj加入集合Wres。

3) 委托方Di根據(jù)信譽(yù)模型為計(jì)算方Wj∈Wres評估信譽(yù)。同樣，參與者的單次交互評價(jià)信息可從區(qū)塊鏈上獲取。若將Wj加入集合Wrep。向Wrep中信譽(yù)最高的計(jì)算方Wj發(fā)送響應(yīng)消息。

7.2.2 執(zhí)行合約階段

1) 當(dāng)Di與Wj均完成押金提交后，Di私下將輸入x以及對應(yīng)摘要Cx、公開評估密鑰EK 和公開驗(yàn)證密鑰VK 發(fā)送給Wj。

2)Wj在本地執(zhí)行任務(wù)計(jì)算，將結(jié)果承諾與中間參數(shù)摘要發(fā)送至委托合約后，私下將計(jì)算結(jié)果y和中間參數(shù)摘要發(fā)送給Di。

3) 待Di收到結(jié)果后，同樣需要對結(jié)果進(jìn)行承諾，并將此承諾分別發(fā)送至委托合約和Wj。

4)Wj在本地生成結(jié)果證明π，并對其進(jìn)行承諾得到Hπ，將證明承諾Hπ發(fā)送至委托合約，私下將結(jié)果證明π發(fā)送給Di。

5)Di根據(jù)收到的中間參數(shù)摘要和結(jié)果證明在本地進(jìn)行摘要驗(yàn)證和證明驗(yàn)證，然后將驗(yàn)證結(jié)果發(fā)送至委托合約，如果驗(yàn)證結(jié)果表明Wj成功完成任務(wù)，則進(jìn)行收益分配和交互評估，合約終止。

6) 倘若Wj未收到預(yù)期結(jié)果，則將發(fā)起訴求請求消息以觸發(fā)仲裁合約。仲裁合約給出仲裁結(jié)果后，根據(jù)雙方行為分配收益和交互評估，合約終止。

此外，需根據(jù)協(xié)議形式化相應(yīng)的用戶端程序UserP-FRDC，具體內(nèi)容如下。

當(dāng)從Wj收到(Prove,sid,π)時(shí)，執(zhí)行以下步驟。

8 方案分析

8.1 安全性分析

定理1現(xiàn)實(shí)世界中的協(xié)議安全實(shí)現(xiàn)理想函數(shù)F(Ideal-FRDC)。

證明本文采用文獻(xiàn)[21]中的證明框架完成協(xié)議的UC 安全性證明。對于任意現(xiàn)實(shí)敵手A，需構(gòu)造一個理想世界模擬器S，使任意多項(xiàng)式時(shí)間環(huán)境Z 無法以一個不可忽略的概率區(qū)分現(xiàn)實(shí)世界與理想世界的執(zhí)行。下文將構(gòu)造模擬器SimP 的用戶端部分，模擬器封裝器 S (·)可將模擬器轉(zhuǎn)換成理想敵手 S(SimP)，簡寫為S。

仿真委托方Di如下。

1) 當(dāng)環(huán)境Z 將消息(Create,sid,x,υ1,υ2,υ3,υ4,υe,$wij,$di,Di)發(fā)送至Di時(shí)，SimP從理想函數(shù)F(Ideal-FRDC)收到 (Create,sid,|x|,υ1,υ2,υ3,υ4,υe,$wij,$di,Di)。SimP 運(yùn)行(τ) ←KeyGen1(1λ)和(EK,VK) ←KeyGen2(τ,R)。SimP 對向量0 計(jì)算摘要，即。SimP 分別對EK 和VK進(jìn)行哈希承諾，即HEK=H(EK)，HVK=H(VK)。SimP 將(Create,sid,,HEK,HVK,υ1,υ2,υ3,υ4,υe,$wij,$di)發(fā)送至內(nèi)部仿真的合約G(ConP-Deleg ate)。

2) 一旦從F(Ideal-FRDC)處收到消息(Compute,sid,Wj)，SimP 對向量0 計(jì)算摘要，即。SimP 將消息(Compute,發(fā)送至仿真的 G(ConP-Deleg ate)。

3) 當(dāng)環(huán)境Z 將消息(Verify,sid,Di)發(fā)送至Di時(shí)，SimP 從 F(Ideal-FRDC)收到(Verify,sid,Di)。SimP 將消息 (Verify,sid,1) 發(fā)送至仿真的G(ConP-Deleg ate)。

仿真計(jì)算方Wj如下。

1) 當(dāng)環(huán)境Z 將消息(Intent,si d,$dj,Wj)發(fā)送至Wj時(shí)，SimP 通過S 路由從 F(Ideal-FRDC)處收到(Intent,si d,$dj,Wj)，并將此消息轉(zhuǎn)發(fā)給內(nèi)部仿真的G(ConP-Deleg ate)。

2) 當(dāng)環(huán)境Z 將消息(Compute,sid,Wj)發(fā)送至Wj時(shí)，SimP 從F(Ideal-FRDC)處收到消息(Compute,sid,Wj)。SimP 分別對向量0 進(jìn)行l(wèi)-2次摘要計(jì)算，即每次根據(jù)不同的摘要公鑰和隨機(jī)數(shù)計(jì)算。SimP 對向量0 進(jìn)行哈希承諾，即Hy0=H(0)。SimP 將(Compute,sid發(fā)送至內(nèi)部G(ConP-Deleg ate)。

3) 一旦從F(Ideal-FRDC)處收到消息(Prove,sid,Wj)，SimP 運(yùn)行π0=Prove(EK,χ0,O0)，并對證明進(jìn)行哈希承諾=H(π0)。SimP 將消息(Prove,sid,)發(fā)送至內(nèi)部 G(ConP-Delega te)。

現(xiàn)實(shí)世界與理想世界的不可區(qū)分性。

現(xiàn)實(shí)世界（Real）。首先定義僅存在虛擬敵手的現(xiàn)實(shí)世界，此敵手只轉(zhuǎn)發(fā)來自環(huán)境Z 的消息，或?qū)⑾鬟f給Z。

混合1（Hybrid 1）。Hybrid 1 與Real 相同除了以下區(qū)別：敵手（或被稱為模擬器）執(zhí)行SCP 方案中仿真的密鑰產(chǎn)生階段，即(τ) ←KeyGen1(1λ)和(EK,VK) ←KeyGen2(τ,R)。當(dāng)誠實(shí)的Wj產(chǎn)生證明時(shí)，模擬器通過調(diào)用Prove(EK,·,·) 算法得到仿真證明，將仿真證明發(fā)送至環(huán)境Z，此過程不泄露任何秘密信息。當(dāng)誠實(shí)的Di對輸入數(shù)據(jù)x與計(jì)算結(jié)果y進(jìn)行摘要計(jì)算，誠實(shí)的Wj對中間數(shù)據(jù)進(jìn)行摘要計(jì)算時(shí)，模擬器通過調(diào)用Digest(EK,·,·) 算法得到仿真摘要，將仿真摘要發(fā)送至環(huán)境Z。

事件1（Fact 1）。因本文采用的SCP 方案具有完美零知識性和綁定承諾，故不存在多項(xiàng)式時(shí)間環(huán)境Z 能以不可忽略的概率區(qū)分REAL 與Hybrid 1。

混合2（Hybrid 2）。模擬器仿真合約函數(shù)G(ConP-Deleg ate)。因?yàn)榘l(fā)送至G(ConP-Delegate)的所有消息都是公開的，所以仿真合約函數(shù)是簡單的。故對于環(huán)境Z 而言，Hybrid 2 與Hybrid 1具有相同分布。

混合3（Hybrid 3）。Hybrid 3 與Hybrid 2 相同除了以下區(qū)別：當(dāng)誠實(shí)的Di對評估密鑰EK和驗(yàn)證密鑰VK 進(jìn)行哈希承諾，誠實(shí)的Wj對計(jì)算結(jié)果y進(jìn)行哈希承諾時(shí)，模擬器通過調(diào)用H(·) 算法得到仿真哈希承諾，將仿真哈希承諾發(fā)送至環(huán)境Z。

事件2（Fact 2）。如果哈希函數(shù)是安全的，則不存在多項(xiàng)式時(shí)間環(huán)境Z 能以不可忽略的概率區(qū)分Hybrid 3 與Hybrid 2。

證畢。

定理2如果wij＜di，{誠實(shí),支付} 為公平理性委托計(jì)算博弈模型Gt中的唯一子博弈精煉納什均衡。

證明本文采用逆向歸納法求解博弈模型Gt的子博弈精煉納什均衡。

僅當(dāng)委托方Di選擇拒絕支付時(shí)，委托方Wj才會進(jìn)行第二輪策略選擇。當(dāng)Wj在第一輪選擇誠實(shí)策略，Di選擇拒絕策略時(shí)，Wj選擇起訴或沉默策略分別可獲得收益di-cj-hj和-cj（di-cj-hj＞-cj），故理性的Wj會選擇起訴對應(yīng)終端節(jié)點(diǎn)v2），此時(shí)Di相應(yīng)的收益為fi-di-ci。當(dāng)Wj在第一輪選擇惡意策略，Di選擇拒絕策略時(shí)，Wj選擇起訴或沉默策略分別可獲得收益-hj-dj和-dj（-hj-dj＜-dj），故理性的Wj會選擇沉默，此時(shí)Di相應(yīng)的收益為dj-ci。

Di需在Wj做出第一輪決策后選擇自己的行動。當(dāng)Wj選擇誠實(shí)策略時(shí)，Di選擇支付或拒絕策略分別可獲得收益fi-wij-ci和fi-di-ci（fi-wij-ci＞fi-di-ci），故理性的Di會選擇支付，此時(shí)Wj相應(yīng)的收益為wij-cj。當(dāng)Wj選擇惡意策略時(shí)，Di選擇支付或拒絕策略分別可獲得收益-wij-ci和dj-ci（-wij-ci＜dj-ci），故理性的Di會選擇拒絕，此時(shí)Wj相應(yīng)的收益為-dj。

Wj在已知自己選擇誠實(shí)策略下的最終收益為fi-wij-ci，而選擇惡意策略的最終收益為-dj。由于wij-cj＞-dj，理性的Wj將會選擇誠實(shí)策略。基于上述分析，理性的Di將會選擇支付策略。故該博弈模型下的唯一子博弈納什均衡為{誠實(shí),支付}，對應(yīng)博弈模型中的終端節(jié)點(diǎn)v1。其結(jié)果為計(jì)算方Wj將誠實(shí)執(zhí)行計(jì)算任務(wù)，委托方Di將支付委托費(fèi)用，意味著該場景下的理性參與者將誠實(shí)執(zhí)行委托合約，不觸發(fā)仲裁合約。

證畢。

8.2 方案對比

本節(jié)將從公開可驗(yàn)證性、經(jīng)濟(jì)公平性、信譽(yù)公平性、博弈模型以及UC 安全性方面與現(xiàn)有的委托計(jì)算方案進(jìn)行對比，結(jié)果如表3 所示。其中，√表示該方案滿足此性質(zhì)，×表示不滿足此性質(zhì)，—表示不涉及此性質(zhì)。

表3 本文方案與其他方案性能對比

文獻(xiàn)[8,10]方案均考慮誠實(shí)的委托方將任務(wù)委托給2 個自利計(jì)算方，通過檢查計(jì)算方返回的結(jié)果是否一致來判斷兩方是否存在不誠實(shí)行為。2 種方案都構(gòu)建了相應(yīng)的博弈模型，但不支持經(jīng)濟(jì)公平性，也不涉及公開可驗(yàn)證性、信譽(yù)公平性以及UC安全性的討論。而文獻(xiàn)[9]方案改進(jìn)了文獻(xiàn)[8]方案，提出了公平支付協(xié)議。

文獻(xiàn)[13,17]方案考慮委托方與計(jì)算方均為理性的情況，分別構(gòu)建對應(yīng)場景下的博弈模型且支持雙方的公平支付。文獻(xiàn)[13]方案考慮用信譽(yù)激勵委托方與計(jì)算方，該方案保證了信譽(yù)公平性。但是2 種方案均不涉及公開可驗(yàn)證性與UC 安全性的討論。

由于本文考慮的是基于證明的理性委托計(jì)算，因此僅與文獻(xiàn)[22]方案進(jìn)行比較。文獻(xiàn)[22]方案基于文獻(xiàn)[6]中的Pinocchio 協(xié)議實(shí)現(xiàn)了對計(jì)算方返回結(jié)果的公開驗(yàn)證，此外，利用智能合約實(shí)現(xiàn)了雙方的公平支付。但是該方案并沒有構(gòu)建博弈模型，也沒有考慮協(xié)議的UC 安全性和信譽(yù)公平性。

本文考慮委托方與計(jì)算方均為理性且具有信譽(yù)激勵的情況，利用博弈論構(gòu)建具有完美信息的兩方動態(tài)博弈模型。本文采用文獻(xiàn)[7]中的Geppetto協(xié)議實(shí)現(xiàn)計(jì)算結(jié)果的公開可驗(yàn)證，利用智能合約實(shí)現(xiàn)了經(jīng)濟(jì)公平性和信譽(yù)公平性，并構(gòu)建相應(yīng)的可組合安全模型，證明協(xié)議的UC 安全性。

9 結(jié)束語

本文利用密碼學(xué)的區(qū)塊鏈模型探究在UC 框架下的公平理性委托計(jì)算方案。首先，結(jié)合直接信譽(yù)和間接信譽(yù)構(gòu)建雙向激勵信譽(yù)模型，委托方與計(jì)算方均可根據(jù)自己的信譽(yù)要求選擇合適的合作方。其次，將委托方與計(jì)算方均視為理性參與者，基于博弈論構(gòu)建理性委托計(jì)算場景下具有完美信息的兩方動態(tài)博弈模型。再次，通過分析該場景下安全需求、理性需求與敵手模型，構(gòu)建可組合安全模型，即公平理性委托計(jì)算理想函數(shù)。最后，通過結(jié)合簡潔承諾證明與智能合約技術(shù)，設(shè)計(jì)可安全實(shí)現(xiàn)理想函數(shù)的公平理性委托計(jì)算協(xié)議。該協(xié)議具有可公開驗(yàn)證性、經(jīng)濟(jì)公平性、信譽(yù)公平性和UC 安全性，且當(dāng)參與者均為理性時(shí)，雙方均選擇誠實(shí)執(zhí)行協(xié)議形成唯一子博弈精煉納什均衡。