基于智能合約的三方博弈防共謀委托計算協議

周全興,李秋賢,樊玫玫

(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 結束語

本文提出一種將博弈理論與傳統委托計算相結合的理性委托計算協議。基于信譽機制建立三方博弈委托計算模型,把計算任務交給不受信任且自利的計算方和裁判方,采用激勵機制和智能合約框架設計委托計算協議,保證參與方不偏離協議執行。基于以太坊區塊鏈的實驗結果表明,該協議委托計算效率較直接計算和傳統委托計算協議更高,可使三方博弈達到貝葉斯納什均衡。下一步將在本文基礎上對更多參與方理性委托計算進行研究,以滿足多方委托計算協議的需求。