陳嘉良,林鴻瑞,黃鈿捷

(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350108)

1 引言

由于靈活性和高可用性等好處,云計算可以提供包括存儲和計算在內(nèi)的服務(wù).因此,許多個人和企業(yè)將他們的數(shù)據(jù)外包到云平臺上以節(jié)省成本.但是與云的通信通常非常耗時,而作為云計算的擴(kuò)展,霧計算使計算任務(wù)能夠在網(wǎng)絡(luò)邊緣實(shí)現(xiàn)并提供低延遲的服務(wù).在霧計算中,資源受限的用戶(由O 表示的外包用戶)可以將計算任務(wù)外包給霧計算節(jié)點(diǎn)來完成(由W 表示的工作節(jié)點(diǎn))并支付報酬給他們.

本文考慮能將計算任務(wù)分配給霧節(jié)點(diǎn)運(yùn)行的場景,每個霧計算節(jié)點(diǎn)完成相應(yīng)的任務(wù)后將結(jié)果返回給用戶.在指定時間內(nèi)完成任務(wù)后,霧計算節(jié)點(diǎn)將從用戶處獲得報酬.然而,由于用戶和霧計算節(jié)點(diǎn)之間的不信任,公平支付的問題應(yīng)該被考慮.一方面,霧計算節(jié)點(diǎn)可能沒有完成計算任務(wù),也就是說,霧計算節(jié)點(diǎn)可能會發(fā)送一些錯誤的結(jié)果給用戶.另一方面,霧計算節(jié)點(diǎn)誠實(shí)地完成了任務(wù),但惡意用戶卻并不支付報酬.

目前已有一些解決問題的方案,一方面,用戶在支付服務(wù)費(fèi)用時需要驗(yàn)證計算結(jié)果.文獻(xiàn)[1]提出了一種基于抽樣的方案.文獻(xiàn)[2]提出了一種審計機(jī)制,通過使用計算證明來檢測計算節(jié)點(diǎn)的惡意行為.文獻(xiàn)[3]提出了一種基于重復(fù)計算和ringer 的方案,以驗(yàn)證計算結(jié)果的正確性.文獻(xiàn)[4-6]提出了概率驗(yàn)證方法檢測作弊者.文獻(xiàn)[7]提出了一種基于抽樣的解決方案,該解決方案使用Merkle 樹來防止計算節(jié)點(diǎn)作弊.另一方面,應(yīng)考慮支付報酬的問題.文獻(xiàn) [8,9]基于分割選擇方案和秘密共享方案來防止惡意計算節(jié)點(diǎn)并考慮支付了問題.

在上述方案中,要么不考慮支付的問題,要么采用傳統(tǒng)的支付框架,例如銀行.然而,傳統(tǒng)的支付解決方案存在一些缺點(diǎn),銀行可能是支付系統(tǒng)的瓶頸.不同于傳統(tǒng)的支付方式,區(qū)塊鏈?zhǔn)且环N分布式的系統(tǒng),不受任何一方控制,可以直接轉(zhuǎn)移報酬.而區(qū)塊鏈技術(shù)已經(jīng)被用在了很多外包服務(wù)中[10-12],文獻(xiàn)[1]提出了一種基于抽樣并結(jié)合比特幣的方案.

為了解決公平支付的問題,本文提出了一個用于外包計算的基于以太坊區(qū)塊鏈的公平支付方案.在我們提出的方案中,外包用戶和工作節(jié)點(diǎn)可以互不信任.基于以太坊的智能合約,本文可以實(shí)現(xiàn)誠實(shí)的工作節(jié)點(diǎn)將會獲得報酬,同時如果工作節(jié)點(diǎn)未完成計算任務(wù),外包用戶可以獲得賠償.本文引入可信第三方T 來解決外包用戶和霧計算節(jié)點(diǎn)的沖突.

2 系統(tǒng)模型

系統(tǒng)模型如圖1 所示,包含外包者O,工作節(jié)點(diǎn)W,第三方T 和一個區(qū)塊鏈.

圖1 系統(tǒng)模型

(1)外包用戶O:作為外包計算的請求者,O 將一筆報酬存入智能合約中,并向工作節(jié)點(diǎn)W 請求外包計算服務(wù).如果W 提供的結(jié)果正確,則將支付報酬給W.否則,O 可以從W 處獲得賠償.

(2)工作節(jié)點(diǎn)W:作為外包計算服務(wù)的提供者,W 收到計算服務(wù)請求后將一筆押金存入智能合約中.在完成計算任務(wù)后,W 將結(jié)果記錄到區(qū)塊鏈智能合約中,并將結(jié)果發(fā)送給O.在指定時間t 之前若O 未對結(jié)果提出異議則從區(qū)塊鏈獲得報酬.

(3)第三方T:作為第三方,T 接收來自O(shè) 的請求.一旦O 發(fā)現(xiàn)W 的計算結(jié)果錯誤,O 發(fā)送一個請求給T.T 驗(yàn)證該請求,若驗(yàn)證W 的計算結(jié)果錯誤,則執(zhí)行智能合約懲罰W.

(4)區(qū)塊鏈:我們使用一個已被廣泛使用并支持智能合約的區(qū)塊鏈,如以太坊區(qū)塊鏈.智能合約是在區(qū)塊鏈上自我執(zhí)行的程序.

在我們的系統(tǒng)中,外包用戶和工作節(jié)點(diǎn)可以互不信任,同時它們中的任一個都可能是惡意用戶.具體來說,惡意外包用戶的目的是在不支付報酬的情況下獲得外包服務(wù),而惡意工作節(jié)點(diǎn)則希望在不提供有效結(jié)果的情況下獲得報酬.我們的設(shè)計目標(biāo)主要包括正確性和公平性.

(1)正確性:如果外包用戶O 和工作節(jié)點(diǎn)W 都是誠實(shí)的,那么外包用戶O 可以獲得所需的計算結(jié)果,而工作節(jié)點(diǎn)W 將獲得報酬.

(2)公平性:對外包用戶O 的公平性意味著惡意工作節(jié)點(diǎn)W 若未能提供正確的結(jié)果,則無法獲得報酬.對工作節(jié)點(diǎn)W 的公平性意味著惡意外包用戶O 在不支付服務(wù)費(fèi)的情況下無法獲得正確的結(jié)果.如果惡意工作節(jié)點(diǎn)W 未能提供正確的結(jié)果,則外包用戶O 能夠從工作節(jié)點(diǎn)處獲得相應(yīng)的賠償.

3 系統(tǒng)設(shè)計

本文設(shè)計的方案包含4 個階段:初始化階段,計算階段,支付階段和索賠階段.同時引入第三方來解決外包用戶O 和工作節(jié)點(diǎn)W 間的沖突.區(qū)塊鏈智能合約確保外包用戶O 要么獲得正確的結(jié)果,要么獲得賠償.此外,誠實(shí)的工作節(jié)點(diǎn)W 可以獲得相應(yīng)的報酬.

3.1 初始化階段

選擇一個哈希函數(shù)H 如SHA-256,并且每個參與者生成自己的ECDSA 公鑰/密鑰對,表示為( pk,sk),并公布自己的公鑰pk 作為賬戶地址.外包用戶O 的公私鑰對表示為 ( pkO,skO),工作節(jié)點(diǎn)W 的公私鑰對表示為(pkW,skW),第三方T 的公私鑰對表示為( pkT,skT).假設(shè)所有參與者都安全地維護(hù)每個已發(fā)布的公鑰,而密鑰sk 安全的存儲在本地,用于生成簽名.

外包用戶與工作節(jié)點(diǎn)先對計算任務(wù)F 達(dá)成協(xié)議,并在區(qū)塊鏈上建立智能合約.其中計算任務(wù)表示為F=〈f,D,M〉,計算函數(shù)f 在數(shù)據(jù)D 上所有滿足f(x)∈M的x,工作節(jié)點(diǎn)完成相應(yīng)的計算任務(wù)后將包含所有滿足要求的x 結(jié)果集S 返回給外包用戶.智能合約記錄外包用戶和工作節(jié)點(diǎn)還有第三方的賬戶地址,并確定計算任務(wù)需要完成的時間和任務(wù)報酬.外包用戶將任務(wù)報酬存入智能合約中,同時工作節(jié)點(diǎn)也將自己的押金存入智能合約.

3.2 計算階段

在確認(rèn)了外包用戶將報酬存入智能合約后,工作節(jié)點(diǎn)執(zhí)行計算任務(wù)F 后獲得一個結(jié)果集S ={x1,···,xn},其包含了所有滿足 f(x)∈M的x.工作節(jié)點(diǎn)將每個結(jié)果xi的哈希存在智能合約中,并根據(jù)結(jié)果集S 創(chuàng)建一棵Merkle 樹 MTl,保存Merkle 樹的根節(jié)點(diǎn)Iroot在智能合約中.其中l(wèi) 表示Merkle 樹的樹高,而葉子節(jié)點(diǎn)的樹高為0.在Merkle 樹中,對于高度為i 的第j 個節(jié)點(diǎn)的值有Ii,j=H(Ii-1,j||Ii-1,j+2i-1),Ii-1,j和Ii-1,j+2i-1表示 Ii,j的兩個孩子節(jié)點(diǎn).當(dāng)i =l 時,Il,j表示根節(jié)點(diǎn).當(dāng)i =0 時,I0,j表示葉子節(jié)點(diǎn),即第j 個結(jié)果 xj.當(dāng)結(jié)果集的Merkle 樹根被保存在區(qū)塊鏈后,工作節(jié)點(diǎn)之后將無法對結(jié)果集進(jìn)行更改,外包用戶可以確保工作節(jié)點(diǎn)發(fā)送給他的結(jié)果集出現(xiàn)錯誤后無法進(jìn)行否認(rèn).如圖2 是一棵高度為3 的Merkle 樹.當(dāng)結(jié)果存入?yún)^(qū)塊鏈后,工作節(jié)點(diǎn)將結(jié)果集S 發(fā)送給外包用戶,并執(zhí)行一個具有t 時間鎖的支付智能合約,即在t 時間后報酬將支付給工作節(jié)點(diǎn).

圖2 高度為3 的結(jié)果Merkle 樹

3.3 支付階段

外包用戶將計算結(jié)果集S 的每個元素 xi的哈希與存在區(qū)塊鏈上的哈希對比是否一致,若一致則驗(yàn)證結(jié)果是否滿足外包任務(wù)的要求.當(dāng)結(jié)果集S 正確,則工作節(jié)點(diǎn)將在時間t 后從合約中獲得報酬.當(dāng)結(jié)果集S 較大時,可以使用如下的抽樣方案,并驗(yàn)證抽樣的結(jié)果S',使用文獻(xiàn)[7]中的方法進(jìn)行生成m 個抽樣:

其中,Iroot表示結(jié)果集Merkle 樹的根節(jié)點(diǎn),并且:

外包用戶驗(yàn)證抽樣的m 個結(jié)果,文獻(xiàn)[7]中證明了只要m 足夠,則能確保整個結(jié)果的正確性.在外包用戶驗(yàn)證了結(jié)果正確后,工作節(jié)點(diǎn)將在時間t 后獲得報酬.然而,如果外包用戶發(fā)現(xiàn)存在不正確的結(jié)果,則外包用戶將發(fā)送一個裁決請求給第三方.

3.4 索賠階段

當(dāng)?shù)谌絋 從外包用戶處收到裁決請求時,則進(jìn)入索賠階段.第三方T 裁決這個請求的正確性,如果接受這個裁決請求,則第三方T 執(zhí)行智能合約中止支付報酬.考慮以下兩種情況.

(1)若工作節(jié)點(diǎn)發(fā)送給外包用戶的結(jié)果集計算的Merkle 樹根與存在區(qū)塊鏈上的 Iroot不一致,則表明工作節(jié)點(diǎn)發(fā)送的結(jié)果不正確.外包用戶發(fā)送一個裁決請求給第三方包含結(jié)果集與區(qū)塊鏈上的 Iroot,第三方驗(yàn)證后要求工作節(jié)點(diǎn)返回正確的結(jié)果集S,并驗(yàn)證該結(jié)果集的Merkle 樹根是否與 Iroot一致.若一致,則發(fā)送該結(jié)果集給外包用戶O.若不一致,則調(diào)用合約judge 函數(shù)中止支付報酬.

(2)若結(jié)果集S 的元素 xi驗(yàn) 證結(jié)果為 f(xi)?M,即結(jié)果集S 存在不正確的結(jié)果,表明工作節(jié)點(diǎn)W 并未完成計算任務(wù).當(dāng)外包用戶O 發(fā)現(xiàn)工作節(jié)點(diǎn)返回的結(jié)果中存在錯誤結(jié)果 xi,則外包用戶將外包任務(wù)F =〈f,D,M〉,錯誤的結(jié)果 xi與該元素哈希存在區(qū)塊鏈上的位置包含在請求中發(fā)送給第三方T.第三方T 先將元素 xi與該元素在區(qū)塊鏈上的哈希進(jìn)行驗(yàn)證,若不相同,則拒絕該請求.當(dāng)確定該元素為工作節(jié)點(diǎn)的計算結(jié)果后,第三方T 驗(yàn)證元素 xi在 外包任務(wù)F =〈f,D,M〉中結(jié)果是否正確,即將結(jié)果 xi代 入外包任務(wù)中計算驗(yàn)證 f(xi)是否滿足M.若該結(jié)果不滿足外包任務(wù)要求,則第三方T 調(diào)用合約中的judge 函數(shù)修改變量payService 為false 使得callback 函數(shù)中報酬支付中止.使用的部分偽代碼如圖3.

圖3 智能合約部分偽代碼

4 系統(tǒng)分析

4.1 安全分析

根據(jù)本系統(tǒng)的安全目標(biāo),給出了本文的安全分析.

(1)正確性:如果使用的哈希函數(shù)H 是抗碰撞的并且ECDSA 簽名是不可偽造的,則我們的協(xié)議滿足正確性.假設(shè)外包用戶和工作節(jié)點(diǎn)都是誠實(shí)的,并且遵循方案的步驟.在計算階段,工作節(jié)點(diǎn)將每個結(jié)果的哈希和結(jié)果集構(gòu)成的Merkle 樹根節(jié)點(diǎn)存在區(qū)塊鏈上.在支付階段,外包用戶將驗(yàn)證結(jié)果集元素的哈希是否與區(qū)塊鏈保存的一致,保證結(jié)果集S 是工作節(jié)點(diǎn)保存在區(qū)塊鏈上的結(jié)果,之后驗(yàn)證所有或是抽樣的結(jié)果是否滿足外包計算任務(wù)的要求.只有在滿足了結(jié)果是符合外包任務(wù)要求后,工作節(jié)點(diǎn)才能在時間t 后收到報酬.換句話說,如果使用的哈希函數(shù)H 是抗碰撞的并且ECDSA簽名是不可偽造的,由于區(qū)塊鏈的不可篡改,則外包用戶收到的結(jié)果集S 一定是未被篡改的,且工作節(jié)點(diǎn)只有在提供的結(jié)果集S 滿足外包任務(wù)的要求后才能獲得相應(yīng)的報酬.

(2)公平性:我們首先證明對誠實(shí)工作節(jié)點(diǎn)的公平性,然后證明在惡意工作節(jié)點(diǎn)下考慮對外包用戶的公平性.

情況1:假設(shè)工作節(jié)點(diǎn)是誠實(shí)的,而外包用戶是惡意的,即惡意的外包用戶想要獲得一個有效的結(jié)果而不支付報酬.這種情況下,在計算階段,工作節(jié)點(diǎn)只有在確認(rèn)了外包用戶將報酬存入智能合約中才會執(zhí)行計算任務(wù).當(dāng)完成計算任務(wù)后,只有在工作節(jié)點(diǎn)的結(jié)果出現(xiàn)問題時支付才會被第三方T 通過合約中止.由于智能合約的強(qiáng)制執(zhí)行特性,所以只要工作節(jié)點(diǎn)提供的結(jié)果是符合外包計算任務(wù)要求的,則工作節(jié)點(diǎn)一定能夠在時間t 后獲得報酬.

情況2:假設(shè)外包用戶是誠實(shí)的,而工作節(jié)點(diǎn)是惡意的,即惡意的工作節(jié)點(diǎn)想要在不提供正確結(jié)果的情況下獲得報酬.首先,若工作節(jié)點(diǎn)未將結(jié)果的哈?；蚪Y(jié)果集的Merkle 樹根保存在區(qū)塊鏈上,則外包用戶發(fā)送一個裁決請求給第三方,第三方要求工作節(jié)點(diǎn)將結(jié)果集哈希保存于區(qū)塊鏈中.若工作節(jié)點(diǎn)未能將結(jié)果集哈希保存在區(qū)塊鏈上,表示工作節(jié)點(diǎn)未完成外包計算任務(wù).第三方T 調(diào)用如圖3 的合約judge 中止報酬的支付,則外包用戶可以獲得賠償并取回報酬.其次,若工作節(jié)點(diǎn)提供的結(jié)果不符合外包計算任務(wù)的要求,外包用戶將錯誤的結(jié)果包含到裁決請求中發(fā)送給第三方.當(dāng)?shù)谌絋 驗(yàn)證了該錯誤結(jié)果后,將中止報酬的支付,則外包用戶可以獲得賠償并將報酬取回.

通過以上的分析,如果使用的哈希函數(shù)H 是抗碰撞的并且ECDSA 簽名是不可偽造的,則本系統(tǒng)滿足正確性和公平性.

4.2 消耗分析

本系統(tǒng)在以太坊官方測試網(wǎng)絡(luò)上實(shí)現(xiàn)了一個智能合約來分析性能.本文使用的哈希函數(shù)是SHA-256.當(dāng)我們進(jìn)行實(shí)驗(yàn)時,gas 價格設(shè)置為2 Gwei,其中1 Gwei =109wei = 10-9ether,目前1 ether=168 USD.我們將它部署在以太坊官方測試網(wǎng)絡(luò)Ropsten 上,使用的偽代碼表示的算法如圖3.表1 是智能合約消耗的實(shí)驗(yàn)結(jié)果,合同創(chuàng)建操作僅執(zhí)行一次以完成初始化其消耗267 202 gas=0.0898 USD.外包用戶的報酬存入和工作節(jié)點(diǎn)的押金存入分別消耗21 485 gas=0.0072 USD 和21 397 gas=0.0072 USD,而支付操作消耗41 533 gas=0.0140 USD.當(dāng)出現(xiàn)惡意工作節(jié)點(diǎn)時,進(jìn)入索賠階段,第三方T 裁決操作judge 消耗22 086 gas=0.0074 USD.同時索賠操作消耗29 383 gas=0.0099 USD.而本實(shí)驗(yàn)當(dāng)未出現(xiàn)錯誤結(jié)果智能合約共需消耗351 617 gas,約為0.1182 USD.當(dāng)出現(xiàn)錯誤結(jié)果時,需執(zhí)行裁決操作與索賠操作,智能合約共需消耗403 086 gas,約為0.1355 USD.第三方T 在智能合約上的消耗只有執(zhí)行裁決操作judge的消耗,而對與鏈下的驗(yàn)證操作需根據(jù)具體的外包任務(wù)來確定.

表1 智能合約的消耗

5 結(jié)語

隨著外包服務(wù)的快速發(fā)展,為了解決外包計算的支付問題,本文提出了基于區(qū)塊鏈的外包服務(wù)公平支付方案.通過使用區(qū)塊鏈將外包任務(wù)的結(jié)果進(jìn)行保存,使其不能篡改.只有在結(jié)果正確時,外包用戶才支付服務(wù)報酬給工作節(jié)點(diǎn),若結(jié)果不正確,外包用戶將可以獲得賠償.本協(xié)議的安全分析和消耗分析表明本協(xié)議是正確的且公平的,同時本協(xié)議的消耗是可接受的.