通用可組合框架下的公平理性委托計算

田有亮，蔣小霞

（1.貴州大學計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學省部共建公共大數據國家重點實驗室（籌），貴州 貴陽 550025；3.貴州大學密碼學與數據安全研究所，貴州 貴陽 550025）

1 引言

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

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

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

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

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

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

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

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

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

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

2 準備知識

2.1 SCP

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

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

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

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

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

2.2 博弈論

定義2擴展式博弈[23]。擴展式博弈的基本表達式為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為博弈模型的終端節點集合；支付組合U=(u1,u2,…,un)，其中，ui:Z→R 表示參與者Pi在終端節點上的效用函數[10]。

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

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

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

2.3 UC 框架

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

定義5UC 實現[15]。令F、Π 分別為理想函數和協議。如果協議Π UC-仿真F 的理想協議，則稱協議Π UC-實現理想函數F，也稱協議Π 安全實現理想函數F，此時Π 是UC 安全的。

2.4 智能合約

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

2.5 密碼學的區塊鏈模型

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

3 問題陳述

3.1 系統模型

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

圖1 系統模型

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

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

一旦收到來自委托方的確認消息，智能合約僅需負責相應的收益分配和交互評價。但當收到來自計算方的仲裁請求時，智能合約還將調用內部的仲裁合約解決爭端。

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

3.2 敵手模型

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

錯誤報告。收到來自計算方提交的誠實計算結果后，委托方向智能合約發送認證失敗的反饋信息，試圖獲取因為擁有正確計算結果帶來的收益而拒絕向計算方支付委托費用以實現更大效用。

搭便車。收到來自委托方的計算任務后，計算方為了節省計算資源，隨意地向智能合約和計算方提交計算結果和證明而非認真執行計算任務。

4 信譽模型

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

4.1 直接信譽

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

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

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

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

4.2 間接信譽

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

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

所有推薦者對Wj的間接信譽評估為

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

4.3 全局信譽

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

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

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

5 博弈模型

傳統委托計算僅側重于方案的可驗證性，無法考慮參與者自利行為對協議造成的影響。本文從博弈論角度出發，將委托方和計算方均視為理性參與者，且參與者為理性是共同知識，利用擴展式博弈對參與者進行理性建模，博弈模型如圖2 所示。

圖2 博弈模型

此博弈為具有完美信息的動態博弈。Di收到來自Wj提交的計算結果，并對其進行驗證以獲知對方是否選擇誠實執行任務后，再決定自己的行動。Wj觀測Di是否完成支付的行動后，再選擇自己是否發起仲裁請求。

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

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

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

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

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

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

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

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

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

表1 貨幣參數及其含義

為確保Di與Wj之間滿足激勵相容，貨幣參數需滿足以下關系。

1)wij＞cj。Di的委托費用應比Wj誠實執行任務的開銷大，否則Wj不會愿意接受此計算任務。

2)fi＞wij+ci。Di因計算任務獲得的收益應比自己付出的委托費用和驗證開銷總和多，否則Di不會愿意將此計算任務外包給Wj。

3)di＞cj+hj。為確保誠實Wj的利益，Di的押金應大于Wj誠實計算的開銷與仲裁費用的總和。

4)dj＞ci。為確保誠實Di的利益，Wj的押金應大于Di的驗證開銷。

通過對理性委托計算博弈模型進行分析，得出博弈模型中各終端節點對應委托方與計算方的效用，具體如表2 所示。

表2 效用分析

6 理想世界

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

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

可驗證性。計算方提交的結果可被正確驗證。對于任意計算結果y，均存在一個對應的證明π可以驗證y是否正確。

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

經濟公平性。委托方向計算方支付委托費用當且僅當計算方提交的結果被驗證為正確。

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

攻擊行為。被賄賂的委托方將拒絕向計算方支付委托費用；被賄賂的計算方將提交錯誤的計算結果。

7 現實世界

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

7.1 合約設計

本文借鑒文獻[22]中的思想設計合約，委托方需準備委托合約和仲裁合約。其中，委托合約用于描述委托方與計算方之間的正常交互；仲裁合約用于解決委托方與計算方之間的爭端，僅當參與者雙方存在爭議時才會被觸發。

7.1.1 委托合約

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

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

2)Di與Wj均同意時間參數υ＜υ1＜υ2＜υ3＜υ4＜υe，其中，υ為當前的時間。

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

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

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

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

7)Di需在截止時間υ4之前提交驗證結果。當=1 時，合約終止且將$dj與$wij發送給Wj，且Di獲得$di。

8) 當Di未在υ4前發送驗證結果，或在規定時間內提交的結果不符合計算方Wj的預期，Wj可以選擇發送任務與計算結果觸發仲裁合約以解決爭端，且合約終止。Wj一旦發起仲裁便花費$hj。若仲裁合約返回的結果為=1，將發送給Di，將$di與$dj發送給Wj。否則，將$di、$dj與$wij發送給Di。

9) 當υ＞υe且合約還未終止，即仲裁合約未能在規定時間內給出仲裁結果時，將$wij發送給Di，將$di與$dj發送給Wj。

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

根據委托合約的設計可基于文獻[20-21]的框架形式化描述委托合約程序ConP-Delegate，具體內容如下。

7.1.2 仲裁合約

僅當Wj對Di的驗證結果不滿時，仲裁合約才被觸發。仲裁合約程序ConP-Arbitrate 執行如下。

7.2 協議描述

本文設計的理性委托計算協議包含協商階段和執行合約階段，具體描述如下。

7.2.1 協商階段

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

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

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

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

7.2.2 執行合約階段

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

2)Wj在本地執行任務計算，將結果承諾與中間參數摘要發送至委托合約后，私下將計算結果y和中間參數摘要發送給Di。

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

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

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

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

此外，需根據協議形式化相應的用戶端程序UserP-FRDC，具體內容如下。

當從Wj收到(Prove,sid,π)時，執行以下步驟。

8 方案分析

8.1 安全性分析

定理1現實世界中的協議安全實現理想函數F(Ideal-FRDC)。

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

仿真委托方Di如下。

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

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

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

仿真計算方Wj如下。

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

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

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

現實世界與理想世界的不可區分性。

現實世界（Real）。首先定義僅存在虛擬敵手的現實世界，此敵手只轉發來自環境Z 的消息，或將消息傳遞給Z。

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

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

混合2（Hybrid 2）。模擬器仿真合約函數G(ConP-Deleg ate)。因為發送至G(ConP-Delegate)的所有消息都是公開的，所以仿真合約函數是簡單的。故對于環境Z 而言，Hybrid 2 與Hybrid 1具有相同分布。

混合3（Hybrid 3）。Hybrid 3 與Hybrid 2 相同除了以下區別：當誠實的Di對評估密鑰EK和驗證密鑰VK 進行哈希承諾，誠實的Wj對計算結果y進行哈希承諾時，模擬器通過調用H(·) 算法得到仿真哈希承諾，將仿真哈希承諾發送至環境Z。

事件2（Fact 2）。如果哈希函數是安全的，則不存在多項式時間環境Z 能以不可忽略的概率區分Hybrid 3 與Hybrid 2。

證畢。

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

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

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

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

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

證畢。

8.2 方案對比

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

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

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

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

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

本文考慮委托方與計算方均為理性且具有信譽激勵的情況，利用博弈論構建具有完美信息的兩方動態博弈模型。本文采用文獻[7]中的Geppetto協議實現計算結果的公開可驗證，利用智能合約實現了經濟公平性和信譽公平性，并構建相應的可組合安全模型，證明協議的UC 安全性。

9 結束語

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