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

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

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

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

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

即使區(qū)塊鏈中的計算節(jié)點可以為多項式計算提供強(qiáng)大的資源助力,但是還是存在一些亟待解決的問題。第一個問題：用戶數(shù)據(jù)的保密性問題。用戶在外包過程中,會將數(shù)據(jù)往外傳送,放在一個專門存儲數(shù)據(jù)的過渡場所,然后再由計算節(jié)點通過區(qū)塊鏈領(lǐng)取計算任務(wù),獲得智能合約,執(zhí)行智能合約,完成外包計算,這就造成了計算節(jié)點或者是攻擊者搜集、利用用戶數(shù)據(jù)可能性增高,進(jìn)而造成用戶的直接或間接損失。在用戶使用外包計算服務(wù)的過程中,用戶不可避免地需要考慮輸入隱私安全問題。用戶一方面需要從外部獲得高效便捷的服務(wù),另一方面希望自己的隱私數(shù)據(jù)不會泄漏給不完全可信的計算節(jié)點。在以往的外包計算方案中,為了保護(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é)點返回的結(jié)果或許因為計算量太過龐大,為節(jié)省計算資源,從而返回一個虛假的計算結(jié)果；又或者是結(jié)果在傳輸過程中,收到了來自惡意第三方的攻擊、篡改等等,都會導(dǎo)致用戶不能按時按需收到正確的計算結(jié)果,從而導(dǎo)致后續(xù)工作無法正常進(jìn)行,消耗人力物力財力,以及一些不可預(yù)計的可怕后果。有專門研究這一問題的領(lǐng)域——可驗證計算[4]?？沈炞C計算力求運用各種方案,來解決不可信第三方服務(wù)器返回結(jié)果驗證問題。Ye 等人[5]提出了一種新的高階多項式安全外包算法,用戶可以輕松地驗證返回的結(jié)果,并且不需要用戶的私人信息(密鑰)等,來驗證返回結(jié)果的正確性,對可驗證計算領(lǐng)域的研究,具有一定的啟發(fā)意義。

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

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

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

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

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

1 相關(guān)工作

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

早在2005 年,Hohenberger 等人[6]就對外包計算安全性進(jìn)行了定義,包括效率和可檢查性的概念并且還提供了兩種實用的外包安全方案——使用兩個不受信任的程序進(jìn)行外包安全的模塊化冪運算,這對后來的云外包安全計算研究進(jìn)程具有極大的促進(jìn)作用。Yang 等人[7]給出了一種高效、安全的RSA 密碼外包計算算法,能做到很容易地擴(kuò)展到多個客戶端,可是在假設(shè)中沒有考慮服務(wù)器不誠實的情況。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]分析了三種已驗證的數(shù)據(jù)保護(hù)方法(數(shù)據(jù)拆分,匿名化和加密)各有優(yōu)缺點。為了實現(xiàn)適用于資源受限的移動用戶的安全的基于屬性的數(shù)據(jù)共享(ABDS),Li 等人[11]引入了一種新的在線/離線基于屬性加密(ABE)方案,該方案通過添加系統(tǒng)公共參數(shù)來消除計算任務(wù)的繁重性,同時將加密計算開銷移到了服務(wù)器上,有效地控制了用戶本地計算資源承受負(fù)擔(dān)。Yu 等人[12]借助于完全同態(tài)加密和多項式因子分解算法,提出了一種可驗證的加密數(shù)據(jù)外包計算方案,改方案在保護(hù)外包處理中的用戶數(shù)據(jù)安全的同時,并允許以零知識對云服務(wù)提供商(CSP)處理的計算結(jié)果進(jìn)行公開驗證,但加密計算過程復(fù)雜度還可以進(jìn)行優(yōu)化。Li 等人[13]提出了一種在單個不可信服務(wù)器模型中用于模塊化冪運算的安全外包算法,以及一種生成轉(zhuǎn)換密鑰的新方法,該方案將用戶端的轉(zhuǎn)換密鑰成本降低為一個常數(shù),如此獲得安全性以及高效性。Jiang 等人[14]在外包環(huán)境下,提出了一種保護(hù)雙方隱私的協(xié)作k-means 聚類協(xié)議,由于大部分計算都是在云上進(jìn)行的,所以任何計算能力較弱的本地客戶端都可以運行該協(xié)議來實現(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é)合多項式的點值計算和Boneh 加密系統(tǒng),實現(xiàn)了參與者的隱私保護(hù),但是該協(xié)議缺乏在惡意云服務(wù)器環(huán)境下的測試。

1.2 可驗證多項式云外包計算安全性研究

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

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

Zhang 等人[31]基于區(qū)塊鏈設(shè)計了一種高效可靠的用于云服務(wù)的外包計算解決方案,該方案不依賴任何第三方的情況下,實現(xiàn)了可驗證計算結(jié)果,且計算成本較低,但外包計算的應(yīng)用受到了限制。Huang 等人[32]基于區(qū)塊鏈和承諾抽樣提出了一種實現(xiàn)公平支付的外包計算方案,但該方案的外包計算需要通過第三方(比特幣腳本)來解決信任問題,使得外包數(shù)據(jù)的安全性和隱私性得不到保障。Fan 等人[33]提出了一種基于區(qū)塊鏈技術(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)行外包計算的解決方案,該方案實現(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ù)要點。

2.1 可忽略函數(shù)

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

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

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

2.2 秦九韶算法

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

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

將前n 項提取公因子x,得

再將括號內(nèi)的前n-1 項提取公因子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é)點必須使用PoW協(xié)議才能將新的區(qū)塊添加到區(qū)塊鏈中。區(qū)塊中存儲著區(qū)塊鏈節(jié)點的交易信息,并存儲著前一個區(qū)塊塊頭的哈希值,所以能做到供所有節(jié)點審查的情況下,也能做到區(qū)塊數(shù)據(jù)防篡改。

智能合約是在存儲在區(qū)塊鏈上的具有圖靈完備性的協(xié)議。它由唯一的地址、一組可執(zhí)行函數(shù)和狀態(tài)變量組成。智能合約將在鏈上的每個節(jié)點按已建立的順序自動獨立、嚴(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é)合了分布式散列表,并沒有單點故障,不需要節(jié)點相互信任。而且支持FUSE 與HTTP 的訪問方式。

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

2.5 可驗證外包計算

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

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

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ū)塊鏈的可驗證多項式外包計算方案

3.1 外包計算模型

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

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

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

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

迭代計算出每一步的值：

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

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

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

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

3.2 計算方案

為了對多項式

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

其中b∈RZp。

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

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

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

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

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

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

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

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

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

多項式可驗證外包計算模型如圖6 所示。

4 安全性證明

4.1 私鑰的隱私性

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

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

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

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

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

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

4.2 輸入、輸出的隱私性

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

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

外包計算者只需要使得：

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

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

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

因此,

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

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

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

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

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

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

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

5 方案比較

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

文獻(xiàn)[28]的方案更加注重結(jié)果的可驗證性,而沒有對用戶數(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é)果的可驗證性,沒有考慮到云服務(wù)器的欺騙性。

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

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

表2 方案比較Table 2 Scheme Comparison

6 總結(jié)

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