云計(jì)算視角下可驗(yàn)證計(jì)算的分析研究

張　琳

(蕪湖職業(yè)技術(shù)學(xué)院網(wǎng)絡(luò)工程學(xué)院，安徽 蕪湖 241003)

0　引言

目前，云計(jì)算被認(rèn)為是信息技術(shù)時(shí)代的重要變革，其獨(dú)特的魅力就在于其強(qiáng)大的計(jì)算能力、高效性、資源共享性等優(yōu)點(diǎn)。云計(jì)算利用云服務(wù)器端進(jìn)行數(shù)據(jù)存儲(chǔ)、分包以及程序運(yùn)行等操作，提高了用戶(hù)對(duì)數(shù)據(jù)管理的便捷及可操作性。但在云計(jì)算環(huán)境下，數(shù)據(jù)信息和應(yīng)用軟件都被轉(zhuǎn)移到云服務(wù)器端，所有服務(wù)維護(hù)和數(shù)據(jù)管理都委托給云計(jì)算服務(wù)提供商來(lái)完成，云計(jì)算機(jī)的運(yùn)行模式給其廣泛應(yīng)用與大力推廣帶來(lái)很多數(shù)據(jù)安全和用戶(hù)數(shù)據(jù)隱私方面的問(wèn)題[1]。云服務(wù)的使用者如何才能確信云計(jì)算服務(wù)提供商提供的計(jì)算結(jié)果和信息是正確的、是可被接受的，這就需要可驗(yàn)證計(jì)算來(lái)加以分析。

1　可驗(yàn)證計(jì)算概述及基本流程

1.1　可驗(yàn)證計(jì)算概述

可驗(yàn)證計(jì)算是在云計(jì)算或分布式計(jì)算的環(huán)境下,用于驗(yàn)證遠(yuǎn)程服務(wù)器在分包計(jì)算過(guò)程中的計(jì)算結(jié)果是否具有可靠性的重要手段?？沈?yàn)證計(jì)算主要涵蓋交互式證明系統(tǒng)(IPs)、概率可驗(yàn)證系統(tǒng)(PCPs)和密碼學(xué)等方面內(nèi)容[2]。關(guān)于可驗(yàn)證計(jì)算的一般過(guò)程可概述如下：

使用者U將輸入變量x和相關(guān)程序f(x)，一并傳輸給P，證明者P計(jì)算出f(x)的值，并將計(jì)算結(jié)果y重新發(fā)送給U。此時(shí)，使用者U和證明者P之間就會(huì)發(fā)生如下的交互行為：

1)如果返回的結(jié)果y和使用者U輸入的f(x)的數(shù)據(jù)完全一樣，則表示證明者P為使用者U返回的數(shù)據(jù)y完全正確，則說(shuō)明證明者P可驗(yàn)證準(zhǔn)確結(jié)果。在這一交互過(guò)程中，不僅完成使用者U交付給驗(yàn)證者P的工作，還為使用者U提供判斷依據(jù)。

2)如果返回的結(jié)果y不等于使用者輸入的f(x)的值，那么說(shuō)明驗(yàn)證者P輸出的值y與使用者U所發(fā)送的數(shù)據(jù)存在一定差異，那么使用者U就很有可能拒絕接受驗(yàn)證者的信息。

1.2　可驗(yàn)證計(jì)算的一般流程

可驗(yàn)證計(jì)算的一般流程主要包括編譯處理、交互處理和驗(yàn)證分析等階段。可驗(yàn)證計(jì)算協(xié)議的流程如圖1所示。

圖1　可驗(yàn)證計(jì)算協(xié)議一般流程圖

第1個(gè)階段：編譯處理階段。使用者U與證明者P，將應(yīng)用程序的高級(jí)語(yǔ)言，這里所提及的高級(jí)語(yǔ)言有別于通常所說(shuō)的高級(jí)語(yǔ)言(比如java、C#等)，而是與C 或Pascal語(yǔ)言比較接近的程序設(shè)計(jì)語(yǔ)言，稱(chēng)為SFDL語(yǔ)言或BFDL語(yǔ)言(針對(duì)兩種不同的編譯器而言),并將其轉(zhuǎn)換為布爾電路集或代數(shù)約束集。

第2個(gè)階段：交互處理階段。證明者P與使用者U進(jìn)行交互處理，基于不同的編譯器所產(chǎn)生的布爾電路集或代數(shù)約束集C表示應(yīng)用程序f，使用者U將變量x輸入，并將x的值發(fā)送給P，證明者P計(jì)算C值，得出結(jié)果為y，y和C所執(zhí)行的軌跡{C，x，y}發(fā)送至使用者U。

第3個(gè)階段：驗(yàn)證分析階段。證明者P如果能夠?qū)C，x，y}構(gòu)建出有效執(zhí)行軌跡，就說(shuō)明這一次運(yùn)算結(jié)果是正確的，那么P就會(huì)得到使用者U的信任，反之，如果證明者P輸出的結(jié)果是錯(cuò)誤的，也就是y不等于f(x)，那么就說(shuō)明對(duì)于{C，x，y}這個(gè)執(zhí)行軌跡，沒(méi)有進(jìn)行正確、有效的執(zhí)行。在此過(guò)程中使用者U須慎重選擇要查詢(xún)編碼的位置，這是可驗(yàn)證計(jì)算中非常重要的問(wèn)題。

2　可驗(yàn)證計(jì)算的基本設(shè)計(jì)原則及計(jì)算模型

2.1　可驗(yàn)證計(jì)算的基本設(shè)計(jì)原則

2.1.1成本原則

在驗(yàn)證計(jì)算的過(guò)程中所產(chǎn)生的成本，要低于在本地使用過(guò)程中所形成的各種成本之和，同時(shí)，使用者所需要的經(jīng)濟(jì)成本需控制在合理的預(yù)算之內(nèi)，驗(yàn)證系統(tǒng)為了確保程序能準(zhǔn)確、快速地運(yùn)行，需提供大量有效的技術(shù)、人力、物力保障。這些成本就需要使用者分?jǐn)偅谠朴?jì)算的具體應(yīng)用中，表現(xiàn)在云計(jì)算廠商會(huì)收取用戶(hù)一定費(fèi)用。

2.1.2證明者不完全可信原則

不可假設(shè)證明者能完全遵守協(xié)議內(nèi)容，在驗(yàn)證過(guò)程中可能出現(xiàn)不遵守規(guī)則的行為，證明者出現(xiàn)惡意攻擊的狀態(tài)等非信任的行為，這些情況的出現(xiàn)表明證明者是不可完全信任的，應(yīng)通過(guò)可驗(yàn)證計(jì)算加以驗(yàn)證。

2.1.3使用通用程序原則

在一些特殊情況下，使用者不會(huì)采用經(jīng)常使用的通用程序，會(huì)采用通過(guò)限制可驗(yàn)證計(jì)算協(xié)議使用的程序，以達(dá)到實(shí)際應(yīng)用的要求。因此，正常情況下就要對(duì)使用者所用的程序做出一些假設(shè)，盡量使用通用程序來(lái)設(shè)計(jì)，可有效保證程序的兼容性[2]。

2.2　云計(jì)算下的可驗(yàn)證計(jì)算模型

云計(jì)算是以數(shù)據(jù)存儲(chǔ)、資源付費(fèi)使用、應(yīng)用程序托管等組成的網(wǎng)絡(luò)架構(gòu)，通過(guò)整合資源、服務(wù)外包形式，使得云用戶(hù)的計(jì)算能力不再受個(gè)體計(jì)算能力與資源約束。在這個(gè)服務(wù)外包的過(guò)程中，會(huì)出現(xiàn)不經(jīng)計(jì)算的答案，某些軟件惡意的外部攻擊，也會(huì)影響計(jì)算結(jié)果的正確性[2]。在云計(jì)算下的可驗(yàn)證計(jì)算是來(lái)源于兩大證明系統(tǒng)和密碼學(xué)理論。

在可驗(yàn)證計(jì)算領(lǐng)域常見(jiàn)的兩大編譯器為：FairPlay編譯器是較基礎(chǔ)的編譯器，可將程序編譯成布爾電路集；Benjamin編譯器是在FairPlay編譯器基礎(chǔ)上加以改進(jìn)的，它可將基于高級(jí)語(yǔ)言的程序轉(zhuǎn)化為約束集。接下來(lái)將轉(zhuǎn)化的布爾電路集或代數(shù)約束集進(jìn)行驗(yàn)證分析。如圖2所示：可驗(yàn)證計(jì)算基本模型[1]：

圖2可驗(yàn)證計(jì)算的基本模型

2.3　基于Benjamin編譯器的可驗(yàn)證計(jì)算操作過(guò)程

利用Benjamin編譯器將高級(jí)程序語(yǔ)言編寫(xiě)的程序轉(zhuǎn)化為代數(shù)約束集的操作過(guò)程主要分為以下兩個(gè)部分：

利用BFDL，結(jié)合函數(shù)內(nèi)聯(lián)等轉(zhuǎn)化，編譯成單賦值列表；將賦值列表轉(zhuǎn)換為可驗(yàn)證計(jì)算所接受的約束集[3]。

BFDL實(shí)例描述：以s=9為例，簡(jiǎn)要概述經(jīng)過(guò)Benjamin編譯器，將高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)過(guò)編譯、單賦值并轉(zhuǎn)化為代數(shù)約束集。單賦值以下為列表：

…

以下為約束集：

3　基于交互系統(tǒng)的可驗(yàn)證計(jì)算協(xié)議分析

基于交互系統(tǒng)的可驗(yàn)證計(jì)算協(xié)議是可驗(yàn)證計(jì)算中較常見(jiàn)的一種形式，它的一般過(guò)程如圖3所示。

圖3　基于交互系統(tǒng)的可驗(yàn)證計(jì)算一般過(guò)程

假設(shè)執(zhí)行這一程序：程序目的是計(jì)算輸入x的函數(shù)f(x)。第一步，使用者U將x值和程序f傳輸給證明者P，并將隨機(jī)選取的輸入多項(xiàng)擴(kuò)展函數(shù)值作為隱含的值m，因?yàn)閙不依賴(lài)即將執(zhí)行的程序，因此并不需要在輸入程序之前去選取m。

第二步，證明者P和使用者U進(jìn)行一系列交互(電路層數(shù)設(shè)為d)，在證明者P與使用者U的交互過(guò)程中，U控制引導(dǎo)P從而生成U0(0，0，…0)=Q0遞歸到Ud(Ad)=Qd，x的低階多項(xiàng)式擴(kuò)展函數(shù)就是Ud，此刻Ud在Ad點(diǎn)的函數(shù)值由U來(lái)計(jì)算，同時(shí)檢測(cè)P的回復(fù)值是否一致。

使用者U發(fā)送給證明者P詢(xún)問(wèn)向量為Ai=(a1，a2，a3…)，P計(jì)算Qi=Ui(Ai),Qi是由U以遞歸的形式檢測(cè)，由U隨機(jī)生成詢(xún)問(wèn)向量，并將程序f的計(jì)算結(jié)果植入到證明者P對(duì)最開(kāi)始詢(xún)問(wèn)向量的回復(fù)值中，依次類(lèi)推，關(guān)于U的輸入變量的多項(xiàng)式擴(kuò)展函數(shù)在某一點(diǎn)的值Qd，就包含在P對(duì)最后一個(gè)詢(xún)問(wèn)向量的回復(fù)值里，若P對(duì)所有詢(xún)問(wèn)向量回復(fù)的內(nèi)容都一致，證明者P令使用者U確信其遵守協(xié)議，即判斷正確執(zhí)行程序，因此，計(jì)算結(jié)果被U接受，反之，若U知道P在某處欺騙了它，使用者U就會(huì)拒絕接收[3]。

4　研究展望

在可驗(yàn)證計(jì)算協(xié)議中，成本原因一直困擾其應(yīng)用與發(fā)展。目前可驗(yàn)證計(jì)算由于一些內(nèi)在和外在原因，仍無(wú)法廣泛應(yīng)用于具體云計(jì)算環(huán)境中。但對(duì)于云計(jì)算的某些特殊場(chǎng)景，依然存在巨大的意義。比如資金實(shí)力雄厚的大型企業(yè)，為了掌握非本地設(shè)備是否正常運(yùn)轉(zhuǎn)，而更愿意為了確保云計(jì)算的可信度，而降低對(duì)于成本的影響因素方面的考量。

通過(guò)本文上述分析：目前在云計(jì)算視角下的可驗(yàn)證計(jì)算可在以下方面進(jìn)行后續(xù)研究[4]。

1)可驗(yàn)證計(jì)算協(xié)議須通過(guò)理論工具的不斷改進(jìn)，降低使用者以及系統(tǒng)運(yùn)算帶來(lái)的成本。需將成本控制在較合理范圍，使協(xié)議盡早應(yīng)用于實(shí)際的云計(jì)算場(chǎng)景。

2)進(jìn)一步研究密碼學(xué)相關(guān)的理論分析，考慮多維影響因素，進(jìn)一步完善可驗(yàn)證計(jì)算模型，使其功能更全面，操作更便捷。

3)減少對(duì)可驗(yàn)證計(jì)算的束縛，使可驗(yàn)證運(yùn)算能廣泛應(yīng)用于海量數(shù)據(jù)分析中，降低可驗(yàn)證計(jì)算的門(mén)檻，減少無(wú)關(guān)假設(shè)的影響。

5　結(jié)語(yǔ)

目前，由于可驗(yàn)證計(jì)算協(xié)議在使用過(guò)程中，需要昂貴的經(jīng)濟(jì)成本，短期之內(nèi)還無(wú)法廣泛應(yīng)用到具體的云計(jì)算環(huán)境及其相應(yīng)的應(yīng)用程序中。在研究過(guò)程中發(fā)現(xiàn)，可驗(yàn)證計(jì)算協(xié)議，還有許多需完善的地方，但可驗(yàn)證計(jì)算無(wú)疑是科技領(lǐng)域的一次飛躍，以此希望可驗(yàn)證計(jì)算協(xié)議能早日解決成本問(wèn)題，盡早應(yīng)用到實(shí)際的云計(jì)算場(chǎng)景中。

[1] 張?jiān)?可驗(yàn)證計(jì)算協(xié)議的改進(jìn)與應(yīng)用研究[D].北京：北京郵電大學(xué)，2015.

[2] 薛銳，吳迎，劉牧華，等.可驗(yàn)證計(jì)算研究進(jìn)展[J].中國(guó)科學(xué):信息科學(xué)，2015，45(11):1370-1388.

[3] 王佳慧，劉川意，王國(guó)峰，等.基于可驗(yàn)證計(jì)算的可信云計(jì)算研究[J].計(jì)算機(jī)學(xué)報(bào)，2016，39(2):286-304.

[4] 戚利娜.可驗(yàn)證計(jì)算視角下可信云計(jì)算的研究[J].科技經(jīng)濟(jì)市場(chǎng)， 2017(4):34-35.

[5] 林闖，蘇文博，孟坤，等.云計(jì)算安全:架構(gòu)、機(jī)制與模型評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(9):1765-1784.

[6] 楊青峰.云計(jì)算時(shí)代關(guān)鍵技術(shù)預(yù)測(cè)與戰(zhàn)略選擇[J].中國(guó)科學(xué)院院刊，2015，30(2):148-161.

[7] 王意潔，孫偉東，周松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)[J].軟件學(xué)報(bào)，2012，23(4):962-986.