陳嘉良,林鴻瑞,黃鈿捷

(福州大學 數學與計算機科學學院,福州 350108)

1 引言

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

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

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

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

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

2 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

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

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

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

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

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

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

3 系統(tǒng)設計

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

3.1 初始化階段

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

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

3.2 計算階段

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

圖2 高度為3 的結果Merkle 樹

3.3 支付階段

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

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

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

3.4 索賠階段

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

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

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

圖3 智能合約部分偽代碼

4 系統(tǒng)分析

4.1 安全分析

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

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

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

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

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

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

4.2 消耗分析

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

表1 智能合約的消耗

5 結語

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