郭 禎 張 銀 安方林 趙科杰 張文杰 葉 俊

1(海南大學(xué)計算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院 ?？?中國 570228)

受限于本地計算資源,在大數(shù)據(jù)分析、機(jī)器學(xué)習(xí)以及人工智能需求不斷提高的環(huán)境下,許多用戶需求都無法實(shí)現(xiàn)。隨之出現(xiàn)了一種新的計算范式——外包計算。向外提供服務(wù)的計算機(jī)通常具備高性能硬件條件,并按需分成不同的產(chǎn)品類型為用戶提供不同的服務(wù),用戶可以用按量付費(fèi)等方式獲取計算服務(wù)。外包計算模式的出現(xiàn),以解決本地資源開銷過大的問題。

區(qū)塊鏈?zhǔn)乾F(xiàn)代經(jīng)濟(jì)中最新的、有無限前景的技術(shù)。在數(shù)據(jù)處理的信任度、透明度、安全性以及可靠性等方面都能為工業(yè)領(lǐng)域提供良好的解決方案。區(qū)塊鏈去中心化的特質(zhì),使得系統(tǒng)可以在沒有中間人的介入下還能公平公正運(yùn)行。在區(qū)塊鏈挖礦機(jī)制的設(shè)立下,參與工作量證明(PoW)的計算節(jié)點(diǎn),往往都是具有很強(qiáng)計算資源與能力的節(jié)點(diǎn),這正是那些計算資源匱乏又具有高強(qiáng)度計算要求的本地計算用戶所需要的。后續(xù)智能合約的發(fā)展彌補(bǔ)了區(qū)塊鏈不具備圖靈完備性的缺點(diǎn),它可以定義為一個自我執(zhí)行的合約,利用區(qū)塊鏈技術(shù)以數(shù)字方式執(zhí)行、驗(yàn)證或者促進(jìn)合約的履行,并且可以培養(yǎng)合約雙方之間的交易可信度,而無需第三方的參與。我們將外包過程通過智能合約放在區(qū)塊鏈上,其中流程靠智能合約自主嚴(yán)格執(zhí)行,區(qū)塊鏈存儲交易信息。借助區(qū)塊鏈和智能合約不可篡改等等優(yōu)點(diǎn),建立一個基于區(qū)塊鏈的外包計算模型。

在計算機(jī)科學(xué)中,許多科學(xué)計算都是基于線性代數(shù)的,但這些計算往往可以簡化為多項(xiàng)式的運(yùn)算,所以多項(xiàng)式計算對計算機(jī)科學(xué)起著重要的作用。研究多項(xiàng)式計算不僅可以為計算機(jī)這門學(xué)科帶來進(jìn)展,同時在密碼學(xué)等其他很多學(xué)科都會產(chǎn)生意想不到的促進(jìn)效果。但與此同時,多項(xiàng)式計算往往伴隨到十分復(fù)雜的計算過程,本地計算機(jī)無法承擔(dān)如此龐大的計算資源消耗。外包計算正好是目前解決這個問題的最佳方式。本文將重點(diǎn)研究多項(xiàng)式外包計算的相關(guān)問題。

即使區(qū)塊鏈中的計算節(jié)點(diǎn)可以為多項(xiàng)式計算提供強(qiáng)大的資源助力,但是還是存在一些亟待解決的問題。第一個問題：用戶數(shù)據(jù)的保密性問題。用戶在外包過程中,會將數(shù)據(jù)往外傳送,放在一個專門存儲數(shù)據(jù)的過渡場所,然后再由計算節(jié)點(diǎn)通過區(qū)塊鏈領(lǐng)取計算任務(wù),獲得智能合約,執(zhí)行智能合約,完成外包計算,這就造成了計算節(jié)點(diǎn)或者是攻擊者搜集、利用用戶數(shù)據(jù)可能性增高,進(jìn)而造成用戶的直接或間接損失。在用戶使用外包計算服務(wù)的過程中,用戶不可避免地需要考慮輸入隱私安全問題。用戶一方面需要從外部獲得高效便捷的服務(wù),另一方面希望自己的隱私數(shù)據(jù)不會泄漏給不完全可信的計算節(jié)點(diǎn)。在以往的外包計算方案中,為了保護(hù)用戶數(shù)據(jù)的安全和隱私,常用的辦法是對數(shù)據(jù)進(jìn)行加密預(yù)處理,然后再外包給云服務(wù)提供商(CSP)[1]。盡管完全同態(tài)加密(FHE)[2]被設(shè)計為支持密文上的各種計算,但是這樣也帶來了更大的計算資源的消耗[3],并且使用加密也會使云計算過程變得復(fù)雜。

此外,用戶也非常擔(dān)心數(shù)據(jù)計算結(jié)果的正確性。用戶對計算接待你的非絕對掌控導(dǎo)致了一個新的問題產(chǎn)生——計算節(jié)點(diǎn)返回的結(jié)果或許因?yàn)橛嬎懔刻^龐大,為節(jié)省計算資源,從而返回一個虛假的計算結(jié)果；又或者是結(jié)果在傳輸過程中,收到了來自惡意第三方的攻擊、篡改等等,都會導(dǎo)致用戶不能按時按需收到正確的計算結(jié)果,從而導(dǎo)致后續(xù)工作無法正常進(jìn)行,消耗人力物力財力,以及一些不可預(yù)計的可怕后果。有專門研究這一問題的領(lǐng)域——可驗(yàn)證計算[4]?？沈?yàn)證計算力求運(yùn)用各種方案,來解決不可信第三方服務(wù)器返回結(jié)果驗(yàn)證問題。Ye 等人[5]提出了一種新的高階多項(xiàng)式安全外包算法,用戶可以輕松地驗(yàn)證返回的結(jié)果,并且不需要用戶的私人信息(密鑰)等,來驗(yàn)證返回結(jié)果的正確性,對可驗(yàn)證計算領(lǐng)域的研究,具有一定的啟發(fā)意義。

為解決上述的外包計算的隱私泄漏問題以及不可信計算節(jié)點(diǎn)返回結(jié)果無法準(zhǔn)確驗(yàn)證的問題,本文提出了一種基于區(qū)塊鏈的具有隱私保護(hù)的多項(xiàng)式外包計算方案,主要貢獻(xiàn)如下：

· 提出了基于區(qū)塊鏈和智能合約的外包計算解決方案。

· 提出了一種多項(xiàng)式盲化方法,可以有效保證多項(xiàng)式自身的安全性。

· 提出了高效的可驗(yàn)證方案,用戶只需付出極小計算代價的情況下,做到了不可信計算節(jié)點(diǎn)返回結(jié)果的可驗(yàn)證。

本文的其余部分安排如下。在第二部分中,我們簡要討論了外包計算安全研究、可驗(yàn)證多項(xiàng)式外包計算以及基于區(qū)塊鏈的外包計算領(lǐng)域中的相關(guān)工作；在第三部分中,我們介紹了本方案需要用到的關(guān)鍵技術(shù)；在第四部分中,我們提出了基于區(qū)塊鏈的具有隱私保護(hù)的多項(xiàng)式外包計算方案；在第五部分中,我們分析了本方案的安全性能；第六部分,與相關(guān)工作進(jìn)行了比較；最后,對本文工作進(jìn)行了總結(jié)。

1 相關(guān)工作

1.1 外包計算安全協(xié)議研究

早在2005 年,Hohenberger 等人[6]就對外包計算安全性進(jìn)行了定義,包括效率和可檢查性的概念并且還提供了兩種實(shí)用的外包安全方案——使用兩個不受信任的程序進(jìn)行外包安全的模塊化冪運(yùn)算,這對后來的云外包安全計算研究進(jìn)程具有極大的促進(jìn)作用。Yang 等人[7]給出了一種高效、安全的RSA 密碼外包計算算法,能做到很容易地擴(kuò)展到多個客戶端,可是在假設(shè)中沒有考慮服務(wù)器不誠實(shí)的情況。Abadi 等人[7-8]提出了兩個在外包私有數(shù)據(jù)集上進(jìn)行委派私鑰集交集(PSI)計算的協(xié)議,目的也是為了保護(hù)外包數(shù)據(jù)的安全,使用此協(xié)議無需透露任何有關(guān)數(shù)據(jù)和計算結(jié)果的信息,可是該協(xié)議的強(qiáng)弱基于假設(shè),協(xié)議不具有穩(wěn)定性。Wang 等人[9]為抵御來自云服務(wù)器提供商的某些攻擊,提出了加密序列比較算法,結(jié)合外包計算流程,設(shè)計了一種新的可計算加密算法,保護(hù)了用戶的數(shù)據(jù)隱私,并支持密文的有效計算,但是由于最終結(jié)果是共享的,所以存在一定的可能性會被其他惡意用戶恢復(fù),造成隱私泄露。在將數(shù)據(jù)外包給云之前,控制器應(yīng)使用本地代理掩蓋數(shù)據(jù),Domingo 等人[10]分析了三種已驗(yàn)證的數(shù)據(jù)保護(hù)方法(數(shù)據(jù)拆分,匿名化和加密)各有優(yōu)缺點(diǎn)。為了實(shí)現(xiàn)適用于資源受限的移動用戶的安全的基于屬性的數(shù)據(jù)共享(ABDS),Li 等人[11]引入了一種新的在線/離線基于屬性加密(ABE)方案,該方案通過添加系統(tǒng)公共參數(shù)來消除計算任務(wù)的繁重性,同時將加密計算開銷移到了服務(wù)器上,有效地控制了用戶本地計算資源承受負(fù)擔(dān)。Yu 等人[12]借助于完全同態(tài)加密和多項(xiàng)式因子分解算法,提出了一種可驗(yàn)證的加密數(shù)據(jù)外包計算方案,改方案在保護(hù)外包處理中的用戶數(shù)據(jù)安全的同時,并允許以零知識對云服務(wù)提供商(CSP)處理的計算結(jié)果進(jìn)行公開驗(yàn)證,但加密計算過程復(fù)雜度還可以進(jìn)行優(yōu)化。Li 等人[13]提出了一種在單個不可信服務(wù)器模型中用于模塊化冪運(yùn)算的安全外包算法,以及一種生成轉(zhuǎn)換密鑰的新方法,該方案將用戶端的轉(zhuǎn)換密鑰成本降低為一個常數(shù),如此獲得安全性以及高效性。Jiang 等人[14]在外包環(huán)境下,提出了一種保護(hù)雙方隱私的協(xié)作k-means 聚類協(xié)議,由于大部分計算都是在云上進(jìn)行的,所以任何計算能力較弱的本地客戶端都可以運(yùn)行該協(xié)議來實(shí)現(xiàn)隱私保護(hù)的目的,但是在通信效率上還需要改進(jìn)。Domingo 等人[15]為外包計算設(shè)計了幾種安全協(xié)議,確保了外包保持分離,從而保持隱私,但是對于更多類型的數(shù)據(jù)并沒有考慮到。全韓彧[16]提出了一種雙方SIMD 編碼協(xié)議,用戶先加密,再允許云服務(wù)器和數(shù)據(jù)分析者聯(lián)合解密接觸向量,并證明了云服務(wù)器不能得到任何的中間和最終計算結(jié)果,但是在服務(wù)器計算優(yōu)化方面還有待提升。張靜等人[17]提出了一種基于云服務(wù)器外包的安全二方集計算協(xié)議,該協(xié)議結(jié)合多項(xiàng)式的點(diǎn)值計算和Boneh 加密系統(tǒng),實(shí)現(xiàn)了參與者的隱私保護(hù),但是該協(xié)議缺乏在惡意云服務(wù)器環(huán)境下的測試。

1.2 可驗(yàn)證多項(xiàng)式云外包計算安全性研究

針對多項(xiàng)式云外包計算方面的研究,He 等人[18]提出了一種多矩陣函數(shù)外包的可驗(yàn)證計算方案,該方案可公開授權(quán),存儲復(fù)雜度小,無論在客戶端計算和在服務(wù)器端計算,都能節(jié)省成本。但該方案未能實(shí)現(xiàn)公開可驗(yàn)證,且未能保護(hù)用戶輸入輸出的隱私性。Shen 等人[19]提出了一種基于多項(xiàng)式承諾的可公開驗(yàn)證云計算外包方案,該方案計算結(jié)果可公開驗(yàn)證,且計算成本較低。Guo 等人[20]提出了一種新的可驗(yàn)證的更新數(shù)據(jù)庫外包計算方案,該方案客戶端通過生成兩個多項(xiàng)式和,將原始數(shù)據(jù)進(jìn)行偽裝,發(fā)送給云服務(wù)器,且云服務(wù)器無法獲取原始數(shù)據(jù),保護(hù)了數(shù)據(jù)的安全性,但該方案僅適用于資源受限的客戶端。Wang 等人[21]構(gòu)建了一種具有完全授權(quán)的可驗(yàn)證外包計算,該方案與多項(xiàng)式的階數(shù)無關(guān),降低了客戶端計算成本,但該方案在標(biāo)準(zhǔn)模型中,可驗(yàn)證性基于雙線性配對和雙線性Diffie-Hellman 指數(shù)問題的硬度假設(shè)。羅小雙等人[22]基于BGN 和多線性映射,提出了一種基于雙服務(wù)器模型的多元多項(xiàng)式公開可驗(yàn)證的擴(kuò)展計算方案,該方案雖然確保了輸入輸出的安全性與專有性,但是擴(kuò)展計算效率有待改進(jìn)。Zhou 等人[23]在有限域上基于擴(kuò)展歐幾里得算法,構(gòu)造了一種大規(guī)模多項(xiàng)式的外包計算方案。Premkamal等人[24]提出了一種密文策略屬性基加密(CP-ABE)的可驗(yàn)證外包計算方案,通過大量的數(shù)據(jù)計算外包給云服務(wù)器,減少了計算開銷,且可驗(yàn)證計算結(jié)果的正確性,但該方案僅適用于云中的大數(shù)據(jù)隱私和訪問控制。Zhang 等人[25]設(shè)計了一種基于矩陣向量乘法的多元多項(xiàng)式分解為兩步計算的高次多項(xiàng)式外包方案,該方案可公開授權(quán)和可公開驗(yàn)證,提高了用戶輸入和多項(xiàng)式函數(shù)的私密性。Sun 等人[26]構(gòu)建了一種可公開驗(yàn)證的保護(hù)系數(shù)和輸出的多項(xiàng)式外包計算方案,該方案保護(hù)了多項(xiàng)式的隱私性,結(jié)果可驗(yàn)證正確性,但該方案僅支持特定類型的多項(xiàng)式。Zhang 等人[27]設(shè)計了一種高效且公開可驗(yàn)證的矩陣乘法外包計算方案,該方案在密鑰生成和計算階段節(jié)省了大量計算開銷,但該方案的可證明安全性是基于co-CDH 假設(shè)下。Zheng 等人在文獻(xiàn)[28]中提出了快速的多項(xiàng)式外包方案,但是只能針對特定的輸入進(jìn)行計算。Liu 等人[29]設(shè)計了一種新的安全外包內(nèi)產(chǎn)品協(xié)議,以實(shí)現(xiàn)安全的輕量級單層神經(jīng)網(wǎng)絡(luò),同時提出了一種保護(hù)隱私的分段多項(xiàng)式計算協(xié)議,但是該方案只是考慮了隱私性,并沒有考慮可驗(yàn)證性。Elkhiyaoui 等人[30]引入了兩個用于公開可驗(yàn)證計算的加密協(xié)議,允許輕量級客戶安全地將單變量多項(xiàng)式的計算和大型矩陣的乘法外包給云服務(wù)器,但是該方案沒有考慮用戶輸入的隱私性。

1.3 基于區(qū)塊鏈的外包計算

Zhang 等人[31]基于區(qū)塊鏈設(shè)計了一種高效可靠的用于云服務(wù)的外包計算解決方案,該方案不依賴任何第三方的情況下,實(shí)現(xiàn)了可驗(yàn)證計算結(jié)果,且計算成本較低,但外包計算的應(yīng)用受到了限制。Huang 等人[32]基于區(qū)塊鏈和承諾抽樣提出了一種實(shí)現(xiàn)公平支付的外包計算方案,但該方案的外包計算需要通過第三方(比特幣腳本)來解決信任問題,使得外包數(shù)據(jù)的安全性和隱私性得不到保障。Fan 等人[33]提出了一種基于區(qū)塊鏈技術(shù)中的智能合約實(shí)現(xiàn)安全可靠的外包計算方案,但該方案中任何用戶都能獲取計算結(jié)果。Krol 等人[34]在可信執(zhí)行環(huán)境(TEE)中構(gòu)建了基于區(qū)塊鏈智能合約的安全外包計算方案,雖然該方案高效且提高了用戶隱私性,但是TEE 的開發(fā)成本較高。Lin 等人[35]基于區(qū)塊鏈技術(shù)提出了雙線性配對的外包計算(SOBP)方案,該方案改進(jìn)了原有SOBP 局限性,并有效解決了限制,且提高了其安全性,但需要大量的計算成本。Benil 等人[36]使用區(qū)塊鏈對電子醫(yī)療數(shù)據(jù)進(jìn)行外包計算的解決方案,該方案實(shí)現(xiàn)了醫(yī)療數(shù)據(jù)的安全性,提高了患者敏感數(shù)據(jù)的隱私性,但該方案的計算負(fù)擔(dān)較高。表1 所示為區(qū)塊鏈解決外包計算的方案的現(xiàn)狀梳理。

表1 區(qū)塊鏈解決外包計算的方案的現(xiàn)狀梳理Table 1 Presents the status quo of outsourcing computing solutions for block chain

2 預(yù)備知識

本節(jié)將會介紹一些后續(xù)方案會使用到的解決方法和技術(shù)要點(diǎn)。

2.1 可忽略函數(shù)

在本方案存在一個攻擊者消耗大量時間也不能準(zhǔn)確定位的函數(shù) g (x),找出此函數(shù)破解該方案的幾率非常小,概率小到“可忽略”,所以我們引入可忽略函數(shù)的定義：

對于一個函數(shù)negl (x),如果對于任意一個正多項(xiàng)式poly (x),存在一個Nc＞ 0,使得對于所有的x ＞ Nc有

我們就稱negl (x)是可忽略的。

2.2 秦九韶算法

我國南宋數(shù)學(xué)家秦九韶將增乘開方術(shù)進(jìn)行了推廣,以求解任意高次方的多項(xiàng)式的值。該算法看似簡單,其最大的意義在于把求n 次多項(xiàng)式的值轉(zhuǎn)化成求n 個一元多項(xiàng)式的值。其中心思想就是簡化多項(xiàng)式的計算,以減少中央處理器的運(yùn)算時間。

設(shè)有n+1 項(xiàng)的n 次函數(shù)

將前n 項(xiàng)提取公因子x,得

再將括號內(nèi)的前n-1 項(xiàng)提取公因子x,得

如此反復(fù)提取公因子x,最后將函數(shù)化為

最后 fn為所求。

2.3 區(qū)塊鏈與智能合約

區(qū)塊鏈從本質(zhì)上說是一種新型的數(shù)據(jù)庫,并且當(dāng)新的區(qū)塊連接到區(qū)塊鏈上時,幾乎不可能更改或是刪除它。區(qū)塊鏈技術(shù)是結(jié)合分布式網(wǎng)絡(luò),透明、可靠的鏈型結(jié)構(gòu),不可改變、穩(wěn)定的技術(shù)。工作量證明(PoW)是安全的算法,挖礦是解決PoW 協(xié)議所帶來的計算挑戰(zhàn)的過程。參與挖礦的節(jié)點(diǎn)必須使用PoW協(xié)議才能將新的區(qū)塊添加到區(qū)塊鏈中。區(qū)塊中存儲著區(qū)塊鏈節(jié)點(diǎn)的交易信息,并存儲著前一個區(qū)塊塊頭的哈希值,所以能做到供所有節(jié)點(diǎn)審查的情況下,也能做到區(qū)塊數(shù)據(jù)防篡改。

智能合約是在存儲在區(qū)塊鏈上的具有圖靈完備性的協(xié)議。它由唯一的地址、一組可執(zhí)行函數(shù)和狀態(tài)變量組成。智能合約將在鏈上的每個節(jié)點(diǎn)按已建立的順序自動獨(dú)立、嚴(yán)格地執(zhí)行。

2.4 星際文件系統(tǒng)

星際文件系統(tǒng)(InterPlanetary File System,縮寫IPFS)是一個旨在創(chuàng)建持久且分布式存儲和共享文件的網(wǎng)絡(luò)傳輸協(xié)議[37],是一種內(nèi)容可尋址的對等超媒體分發(fā)協(xié)議。IPFS 是一種分布式文件系統(tǒng),并提供了一個高吞吐量的塊存儲模塊,結(jié)合了分布式散列表,并沒有單點(diǎn)故障,不需要節(jié)點(diǎn)相互信任。而且支持FUSE 與HTTP 的訪問方式。

因?yàn)閰^(qū)塊鏈上的區(qū)塊存儲容量一般只有3～4M,不能存儲大容量數(shù)據(jù),而IPFS 相比區(qū)塊鏈更適合存儲和處理大型文件,且IPFS 在存儲文件后可拋出該文件對應(yīng)的IPFS 地址,區(qū)塊鏈上只需存儲該地址,即可追溯該文件。如此大大擴(kuò)展了區(qū)塊鏈的應(yīng)用范圍,將本地文件添加到該文件系統(tǒng)后,便可向全世界的用戶提供文件訪問功能。

2.5 可驗(yàn)證外包計算

通過可驗(yàn)證計算方案,用戶可以將經(jīng)過處理后的函數(shù) f (x)的計算交給外包計算者,在客戶端可以驗(yàn)證返回結(jié)果的正確與否。

關(guān)于可驗(yàn)證計算的現(xiàn)有實(shí)現(xiàn)方案,可用加密算法配套的外包計算協(xié)議,正式定義分基本是由四個算法組成：密鑰生成(KeyGen)、問題生成(ProGen)、計算(Compute)以及驗(yàn)證(Verify)?？沈?yàn)證的計算方案 由以下算法定義：

KeyGen(g,r) →(PKg,SKg,EKg) 。密鑰生成算法根據(jù)函數(shù)g 和隨機(jī)參數(shù)r 的生成一對密鑰對——公鑰PKg和私鑰SKg,還有一個經(jīng)過混淆后的加密函數(shù),EKg以及公鑰PKg提供給外包計算者,私鑰SKg則由用戶自己保存在客戶端。

· 用戶將加密后的函數(shù)EKg以及輸入 σx發(fā)送給外包計算者,服務(wù)器計算后返回 σy。

3 基于區(qū)塊鏈的可驗(yàn)證多項(xiàng)式外包計算方案

3.1 外包計算模型

對于多項(xiàng)式函數(shù)：

其中P 是一個大素數(shù)(2048bit) 。已知系數(shù)(a0,a1,…,an)及自變量x,客戶需要通過在區(qū)塊鏈上具有強(qiáng)大計算能力的外包計算者去求出函數(shù)值 f (x),并對最終結(jié)果進(jìn)行驗(yàn)證。

由于需要計算的多項(xiàng)式系數(shù)和自變量數(shù)據(jù)集的龐大,且計算量很高,客戶端計算機(jī)的數(shù)據(jù)處理能力達(dá)不到計算要求,所以需要向區(qū)塊鏈上計算功能強(qiáng)大的外包計算者尋求幫助,由外包計算者進(jìn)行計算出值,其計算過程如下：

外包計算者根據(jù)秦九韶算法：

迭代計算出每一步的值：

由于考慮整個區(qū)塊鏈部分節(jié)點(diǎn)是不可信的,為了用戶的安全和隱私考慮,不能將所要計算的多項(xiàng)式系數(shù)泄漏出去。本文采取的方案是：

在客戶端將預(yù)處理數(shù)據(jù)進(jìn)行盲化,使得盲化后的多項(xiàng)式不能被區(qū)塊鏈上其他的節(jié)點(diǎn)獲得原多項(xiàng)式函數(shù)系數(shù)；

然后再通過智能合約送至區(qū)塊鏈,外包計算者節(jié)點(diǎn)在領(lǐng)到計算任務(wù)時,會根據(jù)智能合約內(nèi)容進(jìn)行計算,將計算結(jié)果發(fā)布出來；

這時挖礦節(jié)點(diǎn)和客戶端節(jié)點(diǎn)分別用各自的方式進(jìn)行驗(yàn)證,為防止外包計算者作弊而進(jìn)行不誠實(shí)的計算,或是挖礦節(jié)點(diǎn)與外包計算者節(jié)點(diǎn)共謀欺騙用戶,在智能合約里,客戶端對計算結(jié)果驗(yàn)證后,如果沒有通過驗(yàn)證,客戶端具有一票否決權(quán),要求重新更換挖礦節(jié)點(diǎn)進(jìn)行驗(yàn)證,新的挖礦節(jié)點(diǎn)如果發(fā)現(xiàn)計算結(jié)果有問題,就能發(fā)現(xiàn)外包計算者節(jié)點(diǎn)具有欺詐性,就不會給與其報酬。下面講上述的過程細(xì)化成12 個步驟,具體的外包計算模型如圖1 所示。

3.2 計算方案

為了對多項(xiàng)式

進(jìn)行保護(hù),我們構(gòu)造以下多項(xiàng)式：

其中b∈RZp。

g (x)是一個是首項(xiàng)為bx,公比為bx 的等比數(shù)列,所以在已知x 的情況下,用戶可以輕松求出g (x)的值：

在得到 g (x)最終值的情況下,就可以將 f (x)分別盲化為如下：

其中m,k,r1,r2∈RZp。

用戶將盲化后的多項(xiàng)式 F1(x)和 F2(x)的系數(shù)和自變量上傳至IPFS 里,并將其在文件系統(tǒng)里的地址整裝進(jìn)智能合約里。智能合約的偽代碼如圖2 所示：當(dāng)用戶將智能合約發(fā)布到區(qū)塊鏈中,這時會有閑置的外包計算節(jié)點(diǎn)收到任務(wù)來進(jìn)行完成如圖3 所示：

當(dāng)計算結(jié)果已經(jīng)放在區(qū)塊鏈上時,區(qū)塊鏈上的挖礦節(jié)點(diǎn)和客戶端分別進(jìn)行獨(dú)立驗(yàn)證,由于兩個多項(xiàng)式均是由同一個多項(xiàng)式盲化而來,所以本方案采用只隨機(jī)選取其中一個多項(xiàng)式進(jìn)行驗(yàn)證,這里以驗(yàn)證F1 為例,如圖4 所示。

這里我們假設(shè)需要計算x=x0時候的值,用戶將x=x0通過智能合約發(fā)送到區(qū)塊鏈上,最后通過挖礦節(jié)點(diǎn)驗(yàn)證將得到的數(shù)據(jù) F1(x0)和 F2(x0),分別對其進(jìn)行去盲化計算：

最終用戶只需要比較去盲化后的結(jié)果,如果

則說明計算結(jié)果是錯誤的,就可以判斷出外包計算者和挖礦節(jié)點(diǎn)是否誠實(shí)。如果驗(yàn)證通過,客戶端就可以接受最終的計算結(jié)果,即 f (x0)=f1(x0)=f2(x0)。

這里會有一個用戶節(jié)點(diǎn)與挖礦節(jié)點(diǎn)博弈的過程,如圖5 所示。

多項(xiàng)式可驗(yàn)證外包計算模型如圖6 所示。

4 安全性證明

4.1 私鑰的隱私性

定理1.區(qū)塊鏈上的節(jié)點(diǎn)能夠隨機(jī)破解出用戶的私鑰b,m 和k 的概率均是,能夠隨機(jī)破解出ri(i=1,2)的概率均是。

證明.由于區(qū)塊鏈上的節(jié)點(diǎn)獲得的多項(xiàng)式是經(jīng)過盲化后的 F1(x)和 F2(x)形式如下：

對于所要計算的每一項(xiàng)ic 和 di,區(qū)塊鏈上的節(jié)點(diǎn)在得知下面的規(guī)律時,即下述這種形式：

而不知道具體各個參數(shù)

的具體值,所以區(qū)塊鏈上的節(jié)點(diǎn)可以隨機(jī)性猜測,而導(dǎo)致破解出各個參數(shù)的概率為：

對于 ri(i=1,2),被區(qū)塊鏈上的節(jié)點(diǎn)隨機(jī)猜測出真實(shí)值的概率是：

4.2 輸入、輸出的隱私性

證明.根據(jù)盲化方法,得到密鑰[b,m,r1]可通過F1(x)計算出 f (x),或者是在得到密鑰[k,b,r2]可通過 F2(x)計算出 f (x),所以其總的概率為：

假如外包計算者節(jié)點(diǎn)通過偽裝給出兩個值想要通過客戶端驗(yàn)證,根據(jù)去盲化規(guī)則：

外包計算者只需要使得：

便可通過客戶端的驗(yàn)證,而在這一過程中外包計算者節(jié)點(diǎn)需要破解出所有的用戶私鑰[b, m, k,r1,r2],其中對于 r1和 r2,外包計算者節(jié)點(diǎn)其只需要根據(jù)已知客戶端提供的0c 和 d0的值及其構(gòu)造規(guī)則：

外包計算者節(jié)點(diǎn)即可通過1r 或2r 的一個通過求解0a 反推出其中另一個的值。所以由以上可知外包計算者節(jié)點(diǎn)通過偽裝假解并通過客戶端驗(yàn)證的概率是

另一方面,如果外包計算者節(jié)點(diǎn)能直接猜測到F1(x0)-F2(x0)的值,也可以偽造能通過驗(yàn)證的結(jié)果。猜中這個值的概率為。

因此,

4.3 計算結(jié)果的可驗(yàn)證性

定理3.計算結(jié)果的正確性是可驗(yàn)證的。

證明.假設(shè)整個區(qū)塊鏈的現(xiàn)有節(jié)點(diǎn)共有S 個,其中與外包計算者可共謀的挖礦節(jié)點(diǎn)個數(shù)為N,那么外包計算者節(jié)點(diǎn)與挖礦節(jié)點(diǎn)共謀C 的概率為：

當(dāng)外包計算者節(jié)點(diǎn)通過不共謀的挖礦節(jié)點(diǎn)而使用假解通過驗(yàn)證NC 時,這種情況下,只有能夠通過計算其中一個多項(xiàng)式的真實(shí)解,這時的概率為：

所以使用假解通過挖礦節(jié)點(diǎn)V 的概率為：

外包計算者節(jié)點(diǎn)根據(jù)盲化后的式子按照程序進(jìn)行去計算,結(jié)果出來以后,挖礦節(jié)點(diǎn)不僅要進(jìn)行驗(yàn)證,客戶端還要進(jìn)一步驗(yàn)證最終的計算結(jié)果f1(x0)=f2(x0)是否成立,這樣外包計算者節(jié)點(diǎn)通過雙重驗(yàn)證而得到報酬W 的概率為：

由于素數(shù)p 是個很大的數(shù),使得上述概率變得極低,這就可以完全杜絕外包計算者節(jié)點(diǎn)的欺詐性,使得計算結(jié)果具有很強(qiáng)的驗(yàn)證性。如果挖礦節(jié)點(diǎn)和客戶端都驗(yàn)證成功,即可判斷外包計算者節(jié)點(diǎn)是誠實(shí)的,進(jìn)而確保得用戶到了真實(shí)的值。

5 方案比較

由于文獻(xiàn)[28-30]是解決外包計算所使用的在安全性,隱私性或是計算成本來說最優(yōu)良的算法,下面我們將本文方案與文獻(xiàn)[28-30]的方案進(jìn)行比較如表2 所示。

文獻(xiàn)[28]的方案更加注重結(jié)果的可驗(yàn)證性,而沒有對用戶數(shù)據(jù)進(jìn)行隱私保護(hù),這導(dǎo)致其在客戶端的計算復(fù)雜度為 O (n),云服務(wù)器的計算量復(fù)雜度也近似為 O (n) 。所設(shè)方案沒有能夠達(dá)到隱私性和安全性。

文獻(xiàn)[29]的方案更加所構(gòu)造的盲化函數(shù)是一個普通的函數(shù),所以雖然其隱私保護(hù)做得很好,但是為后期用戶去盲化計算增添了麻煩,使得客戶端的計算量達(dá)到了達(dá)到了 O (n),而云服務(wù)器的計算代價也是 O (n)。為了增加隱私性而并沒有注重結(jié)果的可驗(yàn)證性,沒有考慮到云服務(wù)器的欺騙性。

文獻(xiàn)[30]方案使用歐幾里得算法,將原多項(xiàng)式除以一個二次的多項(xiàng)式,從而得到兩個多項(xiàng)式,最后利用雙線性對計算結(jié)果進(jìn)行驗(yàn)證,實(shí)現(xiàn)了可驗(yàn)證性,但是沒有做到對隱私的保護(hù),客戶端的計算復(fù)雜度為 O()1,由于云服務(wù)器需要進(jìn)行累乘冪的積,并且還要計算多項(xiàng)式的值,所以其云服務(wù)器的計算復(fù)雜度為 O (3n)。

本文方案使用特殊方法盲化多項(xiàng)式,不僅能夠很好的保證了用戶隱私的安全性和防欺詐性,也使得在計算量方面大大的減少,客戶端計算量主要在于求出 g (x)的值,由于加法不計入計算量內(nèi),計算的復(fù)雜度在于求 bnxn,采用二分法進(jìn)行遞歸計算可以使得計算復(fù)雜度變?yōu)镺(log2n),挖礦節(jié)點(diǎn)驗(yàn)證復(fù)雜度為 O (s)(s 為該方案驗(yàn)證次數(shù),由安全系數(shù)決定),而外包計算者是針對兩個多項(xiàng)式的計算復(fù)雜度為O (2n),由于是基于雙重驗(yàn)證,相比上述三個方案安全性方面做到了很強(qiáng)的優(yōu)化。

表2 方案比較Table 2 Scheme Comparison

6 總結(jié)

外包計算具有廣泛的應(yīng)用前景,然而外包計算中的數(shù)據(jù)隱私性和計算的可驗(yàn)證性是亟待解決的問題。本文基于區(qū)塊鏈智能合約提出了一種支持可驗(yàn)證的多項(xiàng)式外包計算方案。用戶需要將盲化后的多項(xiàng)式函數(shù)和函數(shù)輸入上傳至IPFS,然后在區(qū)塊鏈上創(chuàng)建一個智能合約,外包計算者從智能合約中獲取計算任務(wù),計算完結(jié)果并上傳,提供給用戶地址,用戶找到地址的計算結(jié)果進(jìn)行驗(yàn)證；同時挖礦節(jié)點(diǎn)通過執(zhí)行智能合約,保證不與用戶和外包計算者交互的前提下執(zhí)行驗(yàn)證過程,將驗(yàn)證結(jié)果反饋給用戶。用戶接收到外包計算者和挖礦節(jié)點(diǎn)的計算結(jié)果進(jìn)行解密驗(yàn)證,將去盲化后的多項(xiàng)式與之進(jìn)行結(jié)果對比,若對比結(jié)果兩者相同,則用戶接受計算結(jié)果,給予相應(yīng)的報酬；反之,用戶拒絕計算結(jié)果,不給予相應(yīng)的報酬。上述返回的計算結(jié)果都是公開可驗(yàn)證。通過安全性和隱私性的分析,與已有的方案對比,所提方案的安全性和隱私性較高,更具有高效性。用戶可驗(yàn)證計算結(jié)果的正確性,且用戶的計算量負(fù)擔(dān)遠(yuǎn)比直接計算多項(xiàng)式函數(shù)小。