委托計(jì)算下基于區(qū)塊鏈的公平支付方案

李沓，田有亮,3，向康，高鴻峰

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025；2.貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽(yáng) 550025；3.貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025；4.貴州大學(xué)網(wǎng)絡(luò)與信息化管理中心，貴州 貴陽(yáng) 550025）

1 引言

隨著大數(shù)據(jù)、云計(jì)算的迅速發(fā)展，數(shù)據(jù)的處理及存儲(chǔ)能力受到越來(lái)越多的重視。一些自身能力有限的委托方往往需要將復(fù)雜的計(jì)算任務(wù)委托給計(jì)算能力強(qiáng)的計(jì)算方。而在實(shí)際環(huán)境中，無(wú)論是委托方還是計(jì)算方，都是理性參與者，都希望讓自己的利益最大化。

傳統(tǒng)委托計(jì)算過(guò)程中，需要對(duì)計(jì)算方返回的結(jié)果進(jìn)行驗(yàn)證從而保證結(jié)果的準(zhǔn)確性。Xu 等[1]提出在不使用昂貴的完全同態(tài)加密的情況下，誠(chéng)實(shí)但好奇的第三方可以幫助驗(yàn)證外包計(jì)算任務(wù)的結(jié)果，而不需要學(xué)習(xí)計(jì)算任務(wù)或其結(jié)果。通過(guò)在參數(shù)系統(tǒng)模型中結(jié)合新穎的承諾協(xié)議和加法同態(tài)加密來(lái)保護(hù)計(jì)算任務(wù)和來(lái)自不受信任的第三方驗(yàn)證者的結(jié)果。Wang 等[2]為了解決傳統(tǒng)的VC（verifiable computation）問題，提出了一種可驗(yàn)證的外包計(jì)算，具有完全委托FD-VC（verifiable out sourced computation with full delegation），通過(guò)將預(yù)處理委托給云，大大降低了客戶端的計(jì)算成本。Zhao 等[3]使用加同態(tài)加密技術(shù)和混淆電路構(gòu)造了可驗(yàn)證計(jì)算方案?，F(xiàn)有的對(duì)于委托計(jì)算結(jié)果的驗(yàn)證方案大多采用第三方或者處理速度較慢的加密技術(shù)。雖然保證了結(jié)果的正確性，但會(huì)泄露參與方的隱私而且極大地增大了委托方的開銷。

而在實(shí)際環(huán)境中，由于參與者的自利性，眾多學(xué)者利用博弈論研究委托計(jì)算中參與者之間的關(guān)系，從而保證計(jì)算方誠(chéng)實(shí)進(jìn)行計(jì)算從而取締第三方驗(yàn)證過(guò)程。Yin 等[4]基于博弈論研究了委托計(jì)算的驗(yàn)證復(fù)雜問題，提出了基于比特幣和Micali-Rabin的隨機(jī)向量表示技術(shù)的公平理性委托計(jì)算協(xié)議。該協(xié)議不僅解決了傳統(tǒng)委托計(jì)算驗(yàn)證復(fù)雜的問題，而且保證了誠(chéng)實(shí)參與者的利益。Li 等[5]利用博弈委托代理理論，構(gòu)造委托計(jì)算博弈模型并結(jié)合全同態(tài)加密技術(shù)構(gòu)造理性委托計(jì)算協(xié)議保證了參與者雙方的利益。Dong 等[6]利用博弈論和智能合約技術(shù)來(lái)激勵(lì)云之間的約束、背叛和不信任，這樣理性云就不會(huì)串通和欺騙。在沒有串通的情況下，通過(guò)交叉檢查來(lái)自2 個(gè)云的結(jié)果，可以容易地驗(yàn)證外包云對(duì)用戶計(jì)算任務(wù)的正確性。

但在委托計(jì)算的支付過(guò)程中，計(jì)算方的作假行為和委托方的抵賴行為會(huì)使誠(chéng)實(shí)參與者的利益受到損失。因此，既要保證誠(chéng)實(shí)的參與者的利益，又要對(duì)惡意的參與者進(jìn)行懲罰。目前，越來(lái)越多的研究者基于區(qū)塊鏈技術(shù)及比特幣系統(tǒng)來(lái)研究支付的公平性。Zhang 等[7]提出了一種基于區(qū)塊鏈的公平支付框架BCpay，用于云計(jì)算中的外包服務(wù)，保證了參與者的利益不受損失。Andrychowicz 等[8-9]利用比特幣系統(tǒng)保證雙方安全通信協(xié)議的公平性，并設(shè)計(jì)了一種安全的雙方協(xié)議，以實(shí)現(xiàn)從一方到另一方的“強(qiáng)制”財(cái)務(wù)轉(zhuǎn)移的功能。Bentov等[10]研究了安全計(jì)算中的公平模型，并展示了在比特幣網(wǎng)絡(luò)中如何在雙方和多方環(huán)境中實(shí)現(xiàn)。Wang 等[11]提出了基于智能合約的可審計(jì)的公平支付和實(shí)物資產(chǎn)交付協(xié)議。利用區(qū)塊鏈的可追溯性和可審計(jì)性為整個(gè)運(yùn)輸中的資產(chǎn)和數(shù)據(jù)共享提供了有效的方法。Yu 等[12-13]為了防止比特幣的雙花攻擊，設(shè)計(jì)了公平存款以抵御雙重支出。公平存款既保證了支付過(guò)程中的付款方因雙倍花費(fèi)而受到處罰，又保證了受害者的損失得到賠償，保證了在支付過(guò)程中的公平性。Baza 等[14]提出了一種基于公共區(qū)塊鏈的分散式乘車共享服務(wù)B-Ride，利用智能合約和零知識(shí)集成員證明引入時(shí)間鎖定存款協(xié)議來(lái)實(shí)現(xiàn)位置隱私隱藏以及公平付款。Zhao 等[15]提出了一種名為 SPS（secure pub-sub）的新架構(gòu)，去除了第三方，基于區(qū)塊鏈的公平支付和聲譽(yù)實(shí)現(xiàn)數(shù)據(jù)的機(jī)密性和可靠性、訂閱者的匿名性及發(fā)布者和訂閱者之間的支付公平性。Huang 等[16]提出了一種新的基于比特幣的外包計(jì)算公平支付方案。因?yàn)楸忍貛耪Z(yǔ)法的優(yōu)點(diǎn)，用戶可以直接進(jìn)行交易而不需要銀行。Liu 等[17]為實(shí)現(xiàn)加密貨幣支付收據(jù)之間的公平交換，引入了公平交換協(xié)議的強(qiáng)時(shí)效性概念，并提出了2 個(gè)公平的收款協(xié)議實(shí)例，利用區(qū)塊鏈的功能來(lái)實(shí)現(xiàn)強(qiáng)大的及時(shí)性。

當(dāng)前，基于區(qū)塊鏈技術(shù)的支付方案中主要利用了比特幣系統(tǒng)的去中心化特性，保證了支付過(guò)程中參與者的公平性。但多數(shù)方案中是針對(duì)結(jié)果驗(yàn)證后進(jìn)行獎(jiǎng)懲，不僅耗費(fèi)參與方的代價(jià)，而且驗(yàn)證過(guò)程的效率較低。博弈論在研究經(jīng)濟(jì)體制中有獨(dú)特的地位，因此利用博弈論分析支付過(guò)程的納什均衡解可以很好地保證雙方誠(chéng)實(shí)選擇行為策略，從而提高委托計(jì)算的效率，降低委托方的成本。

本文結(jié)合博弈論與區(qū)塊鏈技術(shù)提出了基于區(qū)塊鏈的公平支付方案，實(shí)現(xiàn)了委托計(jì)算支付過(guò)程下的納什均衡解。所提方案首先保證了參與方誠(chéng)實(shí)執(zhí)行策略，其次保護(hù)了參與方的隱私，最后實(shí)現(xiàn)了對(duì)誠(chéng)實(shí)參與者的獎(jiǎng)勵(lì)以及惡意參與者的懲罰。本文的具體工作如下。

1)利用博弈論刻畫了委托計(jì)算中參與方在支付過(guò)程中的博弈模型，并給出了唯一的納什均衡解。

2)利用區(qū)塊鏈技術(shù)提出委托計(jì)算過(guò)程中計(jì)算方的信譽(yù)值模型，并實(shí)現(xiàn)不可篡改。

3)提出基于比特幣時(shí)間承諾技術(shù)的公平支付協(xié)議，實(shí)現(xiàn)委托計(jì)算下支付的公平性。

4)對(duì)協(xié)議的安全性與性能進(jìn)行分析，證明協(xié)議的安全性，并且保證參與者在支付過(guò)程中誠(chéng)實(shí)選擇行為策略。

2 準(zhǔn)備知識(shí)

2.1 委托計(jì)算

委托計(jì)算[18]主要是指委托方由于自身計(jì)算能力不足或資源受限而無(wú)法計(jì)算一個(gè)復(fù)雜任務(wù)，將復(fù)雜任務(wù)委托給一個(gè)計(jì)算能力強(qiáng)的計(jì)算方，由計(jì)算方返回一個(gè)正確計(jì)算結(jié)果而委托方支付相應(yīng)報(bào)酬。但在實(shí)際環(huán)境中，由于參與者雙方的自利行為，支付過(guò)程中存在計(jì)算方作假以及委托方抵賴等行為。

傳統(tǒng)委托計(jì)算主要分為兩類，分別是基于復(fù)雜性理論構(gòu)造方案和基于密碼技術(shù)構(gòu)造方案。傳統(tǒng)的委托計(jì)算方案主要利用PCP（probabilistic checking of proof）定理、全同態(tài)加密、混淆電路等技術(shù)進(jìn)行方案構(gòu)造，通常假設(shè)委托方是誠(chéng)實(shí)的，對(duì)計(jì)算方返回結(jié)果進(jìn)行公開驗(yàn)證。而在現(xiàn)實(shí)環(huán)境中，由于參與者有一定的偏好取向，不能保證參與者都是誠(chéng)實(shí)的，因此出現(xiàn)了理性委托計(jì)算。

理性委托計(jì)算假設(shè)參與者都是理性的，其目的是最大化自身效用，利用博弈論分析參與者的行為策略從而獲得納什均衡解，使參與者雙方誠(chéng)實(shí)選擇行為策略，保證委托計(jì)算結(jié)果的正確性及參與者雙方的公平性。

2.2 比特幣交易

比特幣[19]由中本聰于2008 年提出，比特幣沒有發(fā)行機(jī)構(gòu)，它依據(jù)特定算法，通過(guò)大量的計(jì)算產(chǎn)生，通過(guò)整個(gè)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)達(dá)成共識(shí)來(lái)確認(rèn)并記錄所有的交易行為。

比特幣交易[8]Tx 的最常見形式為

((y1,a1,σ1),…,(yn,an,σn),(v1,π1),…,(vm,πm),t)

Tx 的輸入是三元組 (y1,a1,σ1),…,(yn,an,σn)，其中 yi是某個(gè)先前事務(wù)的哈希值，ai是輸出的索引，iσ 稱為輸入腳本。Tx 的輸出是一對(duì)對(duì)的列表 (v1,π1),…,(vm,πm)，其中 vi是Tx 的第i 個(gè)輸出值，iπ 是輸出腳本。t 是時(shí)間鎖定，表示Tx 僅在時(shí)間范圍t 內(nèi)有效。

2.3 比特幣時(shí)間承諾

Andrychowicz 等[8-9]基于比特幣系統(tǒng)構(gòu)建了一種定時(shí)承諾，其中提交者必須在特定時(shí)間范圍內(nèi)揭示其秘密，否則提交者需要支付罰款。

比特幣時(shí)間承諾方案由CS(S,C,d,t,s)表示，在委托計(jì)算中此承諾方案在計(jì)算方S 和委托方C 之間執(zhí)行，其中計(jì)算方S 充當(dāng)提交者，委托方C 充當(dāng)接收者，s 表示計(jì)算方與委托方各自的秘密值。具體地，S 承諾秘密并且必須在特定時(shí)間t 之內(nèi)打開承諾以贖回他的存款d。否則，存款將支付給C。承諾方案包括3 個(gè)階段。

1)承諾階段CS.commit(S,C,d,t,s)

2)打開階段CS.open(S,C,d,t,s)

3)懲罰階段CS.fine(S,C,d,t,s)

2.4 博弈論

博弈論[20]是研究一些人或者團(tuán)體在某種特定的環(huán)境下如何進(jìn)行決策及決策均衡問題的理論，在委托計(jì)算的過(guò)程中，由于委托方和計(jì)算方都有自利行為，因此，可用博弈論來(lái)分析雙方的行為。

定義1博弈表達(dá)的基本形式[21]由局中人集合P、策略空間Y 和效用函數(shù)u 這3 個(gè)要素組成，即G={P,Y,u}，其中P={ P1,…,Pn}，Y={Y1,…,Yn}，u={ u1,…,un}。效用函數(shù) ui:Y→ R（R 代表實(shí)數(shù)空間），它表示第i 個(gè)局中人在不同組合下所得的效益。

3 支付博弈模型

在委托計(jì)算的支付過(guò)程中，由于參與者雙方的自利行為，使實(shí)際結(jié)果出現(xiàn)偏差。對(duì)于委托方而言，只想得到計(jì)算的正確結(jié)果而不想向計(jì)算方支付服務(wù)費(fèi)，這將導(dǎo)致計(jì)算方即使提供了正確的結(jié)果依然得不到相應(yīng)的獎(jiǎng)勵(lì)。對(duì)于計(jì)算方來(lái)說(shuō)，只想得到獎(jiǎng)勵(lì)而不想提供相應(yīng)的計(jì)算服務(wù)，這將導(dǎo)致委托方在支付了相應(yīng)的服務(wù)費(fèi)之后不能得到正確的結(jié)果。本文基于博弈論的角度分析了委托計(jì)算過(guò)程中支付的博弈模型，其支付博弈樹如圖1 所示，其中，S 表示計(jì)算方，U 表示委托方，Si表示計(jì)算方的收益，Ui表示委托方的收益。

圖1 支付博弈樹

假設(shè)存在一次委托任務(wù)，使委托方得到計(jì)算結(jié)果后的收益為P，委托方需要支付的服務(wù)費(fèi)為T，計(jì)算方在收到任務(wù)后完成正確結(jié)果需要耗費(fèi)的成本為S。由于參與者雙方都有自利行為，為了防止參與者雙方做出欺騙的行為，假定委托方在發(fā)布任務(wù)的時(shí)候需要支付押金Q，計(jì)算方在接受任務(wù)時(shí)需要支付押金R，其中，Q ＞ P ＞T，S ＜ T ＜R ?；诓┺哪Ｐ偷姆治觯梢缘玫饺绫? 所示的委托方和計(jì)算方的交付效用矩陣，根據(jù)參與方各自的行為得到最終的效用函數(shù)。

表1 支付效用矩陣

由效用矩陣可以看出，委托方和計(jì)算方在此次委托任務(wù)過(guò)程中的唯一納什均衡解是雙方都做出誠(chéng)實(shí)的行為，只有這樣雙方的利益才不會(huì)有損失。無(wú)論哪一方做出惡意行為，做出惡意行為的一方將會(huì)損失自身的利益。若雙方都做出惡意行為，則雙方都將受到懲罰，損失自己的利益。

4 系統(tǒng)模型

本節(jié)主要介紹系統(tǒng)模型，系統(tǒng)模型如圖2 所示。在此模型中，計(jì)算方首先上傳自己的信譽(yù)值到區(qū)塊鏈上，委托方查看區(qū)塊鏈根據(jù)不同的任務(wù)需求選擇相應(yīng)的計(jì)算方進(jìn)行任務(wù)發(fā)布。然后計(jì)算方與委托方共同創(chuàng)建公共存款交易，若參與者雙方誠(chéng)實(shí)執(zhí)行策略，則基于公共存款交易創(chuàng)建支付交易完成委托計(jì)算的支付。若參與者存在不誠(chéng)實(shí)行為，則根據(jù)公共存款交易創(chuàng)建打開懲罰交易實(shí)現(xiàn)對(duì)誠(chéng)實(shí)參與者的獎(jiǎng)勵(lì)以及惡意參與者的懲罰。

圖2 系統(tǒng)模型

4.1 計(jì)算方信譽(yù)度模型

每個(gè)計(jì)算方基于它的交易歷史或者工作性質(zhì)都會(huì)形成相對(duì)應(yīng)的信譽(yù)值。在本文中，由于計(jì)算任務(wù)需求的不同往往需要不同的計(jì)算方。在委托計(jì)算的過(guò)程中，計(jì)算方信譽(yù)度的取值由于在社會(huì)網(wǎng)絡(luò)中的關(guān)系很難量化，所以本文基于計(jì)算方的交易歷史進(jìn)行信譽(yù)值評(píng)估。

4.1.1 本地信譽(yù)值

計(jì)算方在一次交易后有2 種狀態(tài)，分別是誠(chéng)實(shí)評(píng)價(jià)和不誠(chéng)實(shí)評(píng)價(jià)。每一次交易完成后計(jì)算方都將計(jì)算自己的信譽(yù)值。由于委托的任務(wù)有相應(yīng)的要求，故不同的任務(wù)對(duì)應(yīng)不同的難度系數(shù)。在一次交易中，任務(wù)要求越高，難度越大，其復(fù)雜度系數(shù)越大，反之則越小。由此，計(jì)算方的本地信譽(yù)值計(jì)算模型為

其中，Lcred 表示計(jì)算方的本地信譽(yù)值，T(t)表示計(jì)算方總的交易次數(shù)，H(t)表示計(jì)算方總交易次數(shù)中誠(chéng)實(shí)交易的次數(shù)，D 為一次交易中任務(wù)的復(fù)雜度系數(shù)。

4.1.2 全局信譽(yù)值

在一次委托計(jì)算任務(wù)完成后，計(jì)算方計(jì)算自己的本地信譽(yù)值并與上一次的全局信譽(yù)值進(jìn)行運(yùn)算，然后得到此次委托計(jì)算的全局信譽(yù)值并進(jìn)行簽名上傳到區(qū)塊鏈上，此全局信譽(yù)值計(jì)算模型可以表示為

其中，Gcred 表示計(jì)算方的全局信譽(yù)值。

信譽(yù)值是計(jì)算方可以得到計(jì)算任務(wù)的基礎(chǔ)，委托方根據(jù)不同的任務(wù)需求選擇相應(yīng)的計(jì)算方進(jìn)行委托。計(jì)算方的信譽(yù)值越高，其被選擇的概率越大。全局信譽(yù)值是將計(jì)算方的信譽(yù)值形成可信鏈，在每一次任務(wù)完成后計(jì)算方都需要更新自己的全局信譽(yù)值并重新上傳。

4.2 任務(wù)發(fā)布

委托方由信譽(yù)值鏈可查看計(jì)算方的全局信譽(yù)值，然后根據(jù)任務(wù)難度選擇相應(yīng)的計(jì)算方發(fā)送任務(wù)進(jìn)行委托。任務(wù)公告如圖3 所示。

假設(shè)委托方U 具有密鑰對(duì)(pku,sku)，則Sigu(m)表示與sku相關(guān)聯(lián)的消息m 上的ECDSA簽名，Veru(m,β)表示消息m 上關(guān)于pku的ECDSA簽名β 的驗(yàn)證結(jié)果。因此，Sigu(task-claim)表示委托方U 對(duì)任務(wù)公告的簽名；name 表示任務(wù)的名稱；requirement 表示任務(wù)的要求；complexity factor 表示任務(wù)的復(fù)雜系數(shù)；K 表示任務(wù)完成后計(jì)算方應(yīng)獲得的報(bào)酬；T 表示任務(wù)完成的截止時(shí)間。

圖3 任務(wù)公告

委托方發(fā)送任務(wù)成功后，創(chuàng)建委托方存款交易TxU，值為d。此交易包含委托方的簽名及委托方的秘密用于創(chuàng)建公共承諾交易，如圖4 所示。

圖4 委托方存款交易

4.3 計(jì)算方接收任務(wù)

計(jì)算方接收來(lái)自委托方發(fā)出的任務(wù)公告，根據(jù)公告內(nèi)容計(jì)算此次委托計(jì)算的代價(jià)。若計(jì)算代價(jià)大于所得報(bào)酬，則計(jì)算方不予計(jì)算；若計(jì)算代價(jià)與所得報(bào)酬相等，則計(jì)算方可以選擇接受或者拒絕；若計(jì)算代價(jià)小于所得報(bào)酬，則計(jì)算方接收此任務(wù)。如果計(jì)算方?jīng)]有在規(guī)定時(shí)間內(nèi)提交任務(wù)，需要支付一定的賠償。因此當(dāng)計(jì)算方接受任務(wù)時(shí)需要向區(qū)塊鏈創(chuàng)建一個(gè)存款交易TxS，此存款交易如圖5 所示。計(jì)算方計(jì)算代價(jià)模型如下。

設(shè)price 表示計(jì)算方的總開銷。有

其中，A 表示此次委托計(jì)算的服務(wù)費(fèi)；accept 表示計(jì)算方接受此次任務(wù)；refuse 表示計(jì)算方拒絕此次任務(wù)。

計(jì)算方接受任務(wù)并創(chuàng)建一個(gè)存款交易TxS，此交易包含計(jì)算方的簽名及計(jì)算方的秘密用于創(chuàng)建公共承諾交易。

圖5 計(jì)算方存款交易

4.4 創(chuàng)建公共承諾交易

委托方與計(jì)算方創(chuàng)建公告承諾交易commit，并最終發(fā)布在區(qū)塊鏈上。commit 由(U ,S,d,t,s)表示，其中，U 和S 是執(zhí)行協(xié)議的雙方，分別代表委托方和計(jì)算方；d 是commit 中存款的價(jià)值；t 為時(shí)間范圍，表示參與者雙方應(yīng)該在時(shí)間t 之前履行承諾，打開交易獲取存款。承諾階段由commit(U ,S,d,t,s)表示，打開階段由open(U ,S,d,t,s)表示，懲罰階段由punish(U ,S,d,t,s)表示，支付階段由pay(U ,S,d,t,s)表示。

4.4.1 準(zhǔn)備階段

U 和S 各自生成密鑰對(duì)u 和s。Su和 Ss是U,S 各自的秘密，并且區(qū)塊鏈上包含未兌換的交易TxU 和TxS，兩者值都為d，分別可以用 Su和 Ss進(jìn)行兌換。hu和 hs分別表示對(duì)U 和S 各自秘密的哈希值，其中，hu=H(Su|| ρu)，hs=H(Ss|| ρs)，ρu←{0,1}α和ρs←{0,1}α，α 是安全參數(shù)。

4.4.2 承諾階段

委托方和計(jì)算方分別利用TxU 和TxS 作為輸入計(jì)算交易commit，如圖 6 所示，委托方對(duì)commit 進(jìn)行簽名后發(fā)送給計(jì)算方，如果在廣播的最大時(shí)延之前計(jì)算方都沒有收到commit，則計(jì)算方收回自己的押金并退出。若計(jì)算方收到了commit，則計(jì)算方對(duì)其簽名后進(jìn)行廣播。委托方等到commit 出現(xiàn)在鏈上，如果在廣播的最大時(shí)延之前commit 沒有出現(xiàn)在鏈上，則委托方收回自己的服務(wù)費(fèi)并退出。若commit 出現(xiàn)在鏈上，則承諾完成，計(jì)算方開始完成相應(yīng)任務(wù)。創(chuàng)建commit 交易的流程如算法1 所示。

圖6 承諾交易

算法1commit

輸入Sigu[TxU]，Sigs[TxS]，S's，S'u，Du，Ds

輸出commit

4.4.3 打開階段

委托方和計(jì)算方在commit 交易情況下承諾對(duì)自己的行為進(jìn)行負(fù)責(zé)。若出現(xiàn)不誠(chéng)實(shí)的行為，則委托方和計(jì)算方依然可以得到各自的服務(wù)費(fèi)或押金。原因如下。

委托方在支付階段如果不履行諾言，不用自己的秘密打開支付交易。則計(jì)算方基于承諾交易commit創(chuàng)建計(jì)算方打開交易o(hù)penS 贖回自己的押金。

計(jì)算方在不能提供正確的服務(wù)證明情況下卻不向委托方支付賠償，則委托方基于承諾交易commit 創(chuàng)建委托方打開交易o(hù)penU 贖回自己的押金。openS 與openU 如圖7 所示，創(chuàng)建openU 與openS 交易的流程如算法2 和算法3 所示。

算法2openU

輸入Sigu[commit]，Sigs[commit]，Proof，T

輸出openU

圖7 打開交易

算法3openS

輸入Sigu[commit]，Sigs[commit]，Proof，T1，T2

輸出openS

4.4.4 懲罰階段

若在任務(wù)截止時(shí)間t 之前，計(jì)算方不能給出相應(yīng)的工作證明，則委托方可以基于commit 創(chuàng)建委托方懲罰交易punishS，此交易值為計(jì)算方所交的押金，在全網(wǎng)公告后，所有鏈上節(jié)點(diǎn)達(dá)成共識(shí)，則委托方可以基于他的簽名和秘密來(lái)兌換此交易獲得對(duì)計(jì)算方的罰金。

若計(jì)算方的工作證明得到證實(shí)，但是委托方在打開階段抵賴不承認(rèn)計(jì)算方的工作并且不參與兌換打開交易。則計(jì)算方可在服務(wù)證明證實(shí)之后，基于commit 創(chuàng)建計(jì)算方懲罰交易punishU，此交易的值為委托方的押金，待鏈上節(jié)點(diǎn)達(dá)成共識(shí)后可基于計(jì)算方的簽名和秘密來(lái)兌換此交易。懲罰交易如圖8 所示，創(chuàng)建委托方和計(jì)算方懲罰交易的流程如算法4 和算法5 所示。

圖8 懲罰交易

算法4punishU

輸入Sigu[commit]，Sigs[commit]，Proof，T

輸出punishU

算法5Punish S

輸入Sigu[commit]，Sigs[commit]，Proof，T1，T2

輸出punishS

4.4.5 支付階段

在計(jì)算方提供正確的服務(wù)證明之后，委托方和計(jì)算方基于commit 創(chuàng)建支付交易pay，交易值包括委托方的服務(wù)費(fèi)d 以及計(jì)算方預(yù)存的押金d，委托方和計(jì)算方用各自的秘密共同打開此交易，然后計(jì)算方獲得最后金額。支付交易如圖9 所示，創(chuàng)建支付交易的流程如算法6 所示。

算法6pay

輸入Sigu[commit]，Sigs[commit]，Proof

輸出pay

4.5 更新信譽(yù)值

待一次交易完成后，計(jì)算方根據(jù)此次交易記錄更新自己的信譽(yù)值并重新上傳到區(qū)塊鏈上，等待下一次交易的啟動(dòng)。委托方在發(fā)布任務(wù)的時(shí)候可以從區(qū)塊鏈上查看計(jì)算方的信譽(yù)值。每一次交易過(guò)程中委托方都能知道計(jì)算方在上一次交易中的狀態(tài)，這樣不僅幫助委托方按需選取相應(yīng)的計(jì)算方，同時(shí)使計(jì)算方遵守協(xié)議規(guī)定，做出誠(chéng)實(shí)的行為。

圖9 支付交易

5 協(xié)議分析

5.1 安全性分析

本文的安全性主要從以下2 個(gè)方面來(lái)考慮。

定理1如果基于ECDSA 的簽名是不可偽造的且選取的哈希函數(shù)是抗碰撞的，那么委托方和計(jì)算方的支付是安全的。

證明委托方和計(jì)算方在支付時(shí)需要驗(yàn)證各自的簽名以及各自秘密的哈希值是否正確。只有簽名和秘密的哈希值都正確的情況下才能創(chuàng)建交易獲取相關(guān)比特幣押金。

假設(shè)存在敵手EvE 在一次委托計(jì)算中偽造委托方簽名Sigu′，偽造計(jì)算方簽名Sigs′，偽造委托方秘密值為X′，偽造計(jì)算方秘密值為Y′。敵手為了獲取比特幣押金，利用偽造簽名以及秘密值創(chuàng)建打開與懲罰交易，EvE 的具體操作如下。

1)獲取公共存款交易commit。

2)使用偽造的委托方簽名Sigu′、計(jì)算方簽名Sigs′及各自秘密值X′和Y′，時(shí)間承諾T 和計(jì)算結(jié)果證明Proof 。

3)計(jì)算秘密哈希值，hu′=H(X ′|| ρu)，hs′=H(Y ′|| ρs)。

4)驗(yàn)證簽名和秘密值的哈希值是否正確。

Veru′[commit,Sigu′]==true&&hu′=hu

Vers′[commit,Sigs′]==true&&hs′=hs

5)創(chuàng)建打開與懲罰交易轉(zhuǎn)移比特幣押金。

若敵手最終獲取了比特幣押金則說(shuō)明敵手偽造的簽名可以驗(yàn)證通過(guò)，且敵手偽造的秘密值能夠通過(guò)哈希運(yùn)算與最終的哈希值相同。這與假設(shè)相矛盾，故敵手不可能創(chuàng)建打開或懲罰交易，獲取比特幣押金。

同理可得，在支付交易驗(yàn)證中，敵手的驗(yàn)證也不可能通過(guò)。這意味著敵手創(chuàng)建的支付交易不能在鏈上被廣播，因此交易不被承認(rèn)，故敵手不能獲取服務(wù)費(fèi)。

在鏈上的所有交易當(dāng)且僅當(dāng)簽名和秘密值驗(yàn)證通過(guò)，才能獲得比特幣押金。而基于ECDSA的簽名是不可偽造的且選取的哈希函數(shù)是抗碰撞的，所以對(duì)于委托方和計(jì)算方而言支付是安全的。

證畢。

定理2若基于ECDSA 的簽名不可偽造，則計(jì)算方的全局信譽(yù)值是不可篡改的。

證明由計(jì)算方的全局信譽(yù)值計(jì)算模型可知

Gcredi=Sigs(Lcred||Gcredi-1)，假設(shè)存在敵手偽造計(jì)算方的簽名Sigs′，則敵手具體操作如下：

1)敵手通過(guò)偽造的簽名對(duì)計(jì)算方的信譽(yù)值進(jìn)行簽名，同時(shí)上傳至區(qū)塊鏈。若信譽(yù)值在鏈上廣播并最終記錄，則說(shuō)明敵手偽造的簽名驗(yàn)證通過(guò)。這與假設(shè)相矛盾，故計(jì)算方的信譽(yù)值不可能被敵手上傳至區(qū)塊鏈。

2)惡意計(jì)算方偽造本地信譽(yù)值參與計(jì)算全局信譽(yù)值。因?yàn)橛?jì)算方的交易歷史在區(qū)塊鏈上公開可見，若存在惡意計(jì)算方偽造信譽(yù)值進(jìn)行計(jì)算，則節(jié)點(diǎn)驗(yàn)證不能通過(guò)，故不能達(dá)成共識(shí)，全局信譽(yù)值不會(huì)被廣播記錄。

證畢。

5.2 正確性分析

定理3基于比特幣時(shí)間承諾的公平支付協(xié)議具有正確性，而且可以保證雙方達(dá)到唯一納什均衡解。

證明在承諾階段若委托方U 和計(jì)算方S 誠(chéng)實(shí)執(zhí)行該策略，則雙方共同創(chuàng)建交易commit，交易commit 包含了委托方的押金Q 和計(jì)算方的押金R，計(jì)算方誠(chéng)實(shí)進(jìn)行計(jì)算最終委托方獲得收益P，計(jì)算方花費(fèi)成本S，而委托方需要支付的服務(wù)費(fèi)為T。

若委托方U 選擇誠(chéng)實(shí)策略，計(jì)算方S 選擇惡意策略，則委托方獲得效用Q+T +R，計(jì)算方獲得效用-R 。

若委托方U 選擇惡意策略，計(jì)算方S 選擇誠(chéng)實(shí)策略，則委托方獲得效用-(Q+T)，計(jì)算方獲得效用Q+R+T-S 。

若委托方U 和計(jì)算方S 均選擇惡意策略，則委托方獲得效用-Q，計(jì)算方獲得效用-R 。

若委托方U 和計(jì)算方S 均選擇誠(chéng)實(shí)策略，則委托方獲得效用Q+P-T，計(jì)算方獲得效用R+T-S 。

在博弈模型中，由于支付效用有如下關(guān)系Q ＞ P ＞T，S ＜ T ＜R，只有當(dāng)參與方都選擇執(zhí)行誠(chéng)實(shí)策略，委托方U 和計(jì)算方S 才能獲得最大效用，此時(shí)雙方達(dá)到唯一納什均衡解。

由協(xié)議分析可知，因?yàn)閰⑴c者雙方皆為理性，故為了使自己的利益最大化，雙方都會(huì)誠(chéng)實(shí)執(zhí)行策略，故協(xié)議具有正確性。

證畢。

6 性能分析

下面對(duì)本文所提方案的時(shí)間開銷進(jìn)行評(píng)估。本文所提方案時(shí)間開銷主要包括創(chuàng)建公共承諾交易時(shí)間以及創(chuàng)建打開、懲罰交易時(shí)間。而比特幣系統(tǒng)平均10 min 產(chǎn)出一個(gè)塊，因此將創(chuàng)建公共承諾交易時(shí)間設(shè)為10 min。即創(chuàng)建公共承諾交易時(shí)間如圖10中曲線y1所示。本文主要考慮委托任務(wù)量與耗費(fèi)時(shí)間的關(guān)系，在傳統(tǒng)委托計(jì)算方案中，需要對(duì)計(jì)算方返回結(jié)果進(jìn)行驗(yàn)證，因此會(huì)耗費(fèi)大量的驗(yàn)證時(shí)間，隨著任務(wù)量的增加，驗(yàn)證時(shí)間也隨之增加，如圖10中曲線 y2所示。而本文所提方案中理性委托方不需要對(duì)返回結(jié)果進(jìn)行驗(yàn)證，僅在創(chuàng)建公共承諾交易時(shí)間的基礎(chǔ)上增加創(chuàng)建打開交易與懲罰交易的時(shí)間，如圖10 中曲線 y3所示。對(duì)比傳統(tǒng)委計(jì)算方案，本文所提方案提高了效率。

圖10 方案時(shí)間開銷

下面將本文提出的委托計(jì)算公平支付協(xié)議與現(xiàn)有的委托計(jì)算協(xié)議進(jìn)行比較。表2 將從委托計(jì)算的參與方隱私性、委托方公平性以及計(jì)算方公平性等方面與其他方案進(jìn)行對(duì)比，其中“√”代表滿足該性能，“×”代表不能滿足該性能。

表2 本方案與其他方案性能對(duì)比

Xu 等[1]提出的協(xié)議中采用誠(chéng)實(shí)但好奇的第三方幫助驗(yàn)證委托計(jì)算任務(wù)的結(jié)果。通過(guò)在參數(shù)系統(tǒng)模型中結(jié)合承諾協(xié)議和加法同態(tài)加密來(lái)保護(hù)計(jì)算任務(wù)和來(lái)自不受信任的第三方驗(yàn)證者的結(jié)果，保證了計(jì)算方誠(chéng)實(shí)計(jì)算結(jié)果，即保證了委托方的公平性。但由于方案中采用了第三方來(lái)幫助驗(yàn)證計(jì)算結(jié)果，因此容易泄露參與者的隱私，且無(wú)法保證最終計(jì)算方可以得到相應(yīng)的服務(wù)費(fèi)，不能保證計(jì)算方的公平性。

Yin 等[4]提出的理性委托計(jì)算協(xié)議中引入了可信第三方幫助委托方和計(jì)算方取回押金。通過(guò)委托方和計(jì)算方預(yù)存押金的形式保證公平性。一旦一方違反承諾，則另一方可以聯(lián)合可信第三方取回押金來(lái)保證協(xié)議的公平性。但是協(xié)議中依然存在第三方，故容易泄露參與者的隱私。

本文提出的委托計(jì)算公平支付協(xié)議利用博弈論構(gòu)建支付博弈模型，并分析了唯一的納什均衡解，利用效用函數(shù)約束參與者雙方誠(chéng)實(shí)執(zhí)行策略，從而保證了委托方的公平性，并取締了委托計(jì)算中結(jié)果的驗(yàn)證過(guò)程，提高了效率。利用比特幣押金保證了計(jì)算方的公平性并且不需要第三方進(jìn)行驗(yàn)證從而保護(hù)參與方的隱私。此外，利用區(qū)塊鏈的激勵(lì)機(jī)制與計(jì)算方的信譽(yù)機(jī)制相結(jié)合提高了委托任務(wù)的通信效率。

7 結(jié)束語(yǔ)

本文基于博弈論分析了委托計(jì)算中支付的公平性，同時(shí)利用比特幣時(shí)間承諾提出了一種在委托計(jì)算中保證公平性的支付方案，保證了參與方能夠誠(chéng)實(shí)選擇行為策略。利用區(qū)塊鏈去除了第三方來(lái)保證參與者的隱私而且實(shí)現(xiàn)責(zé)任溯源。如何減少協(xié)議的通信復(fù)雜度以及確定時(shí)間承諾的極限值將是下一步研究的工作。