公平高效的安全雙邊云資源拍賣方案

段 靚 沈玉龍 高晟凱 徐振楠

1(河海大學計算機與信息學院 江蘇 南京 210098) 2(西安電子科技大學計算機科學與技術學院 陜西 西安 710071) 3(網聯清算有限公司 北京 100045)

0 引 言

拍賣作為一種高效的云資源交易模式，被諸多主流云虛擬機提供商采用[1]。例如，Amazon公司在Amazon EC2平臺中使用了拍賣機制來分配虛擬機(VM)并對其定價[2]。然而，現有的大多數云虛擬機拍賣方案(或稱為云資源拍賣)只關注經濟特性，例如真實性(Truthfulness)與社會福利最大化(Social welfare maximization)，而忽略了隱私保護的內在需求，直接將競拍信息暴露在全體拍賣參與者面前，而敏感競拍信息的泄露會影響拍賣系統的正常運行。

云虛擬機通常是在有限且固定的時間單元內進行分配的，因此云虛擬機拍賣被認為是一個連續過程[3-4]。買賣雙方可以通過不斷監測和分析其他參與者的歷史出價，調整其真實出價以獲得更高的利潤；拍賣商也可以根據歷史出價主動調整定價策略以增加收益；惡意競標者還可以根據歷史出價提交一個精心設計的競標價格，從而擾亂整個拍賣市場。所以，拍賣過程中敏感信息的泄露將會造成巨大的經濟損失。

目前，已經有學者對安全拍賣問題展開了研究。Naor等[5]率先基于密碼學工具構建了簡易通用的安全拍賣框架；Suzuki等[6]基于同態密碼構造了一種安全的廣義二次拍賣模型，但這些方案均沒有針對具體應用場景進行設計，并不能直接實際應用。針對具體拍賣場景的安全拍賣研究是近年來的熱點，其中安全頻譜拍賣、安全云資源拍賣得到了廣泛關注。Chen等[7]基于秘密分享技術提出了一種信息論安全的頻譜拍賣方案，但是該方案只能適用于單邊市場情形下(即只存在單個賣方)的頻譜拍賣。Wang等[8]針對雙邊市場下(即存在多個賣方)的安全頻譜拍賣問題，基于半同態加密設計了一種競價隱私保護的拍賣方案。Chen等[9]首次在安全頻譜拍賣中考慮到了公平支付的問題，并基于可驗證計算技術提出了相應解決方案。此外，安全云虛擬機拍賣也得到了廣泛研究。Chen等[10]基于混淆電路(garbled circuit，GC)技術設計了一種隱私保護的云拍賣方案，然而該方案只適用于單邊市場下的云拍賣，而非更實際的面向雙邊市場的云拍賣。Cheng等[11]結合秘密分享、同態加密等設計了一種混合式的安全雙邊云資源拍賣方案，使用兩個不串謀的服務器構建而成，采用輕量級的加法秘密分享執行了大部分的線上安全操作，然而該方案線下階段包含大量同態加解密與密文運算，整體效率較低，且通信開銷過大。在其他領域也存在一些保護隱私的雙重拍賣設計。然而，由于云虛擬機拍賣存在異構資源分配和實時性要求高等特殊需求，使得現有的工作無法滿足安全云虛擬機拍賣的實際需求。因此，如何在不泄露隱私的情況下實現安全雙邊云資源拍賣仍然是一個難題。

拍賣的公平交易支付問題也是近年來的研究熱點。目前，研究人員設計了一些基于區塊鏈的拍賣方案，利用區塊鏈去中心化特征，消除了拍賣中存在可信第三方問題。為確保投標價格的可靠性、公平性和交付過程中價格消息的安全性，Shu等[12]討論將私有區塊鏈應用到拍賣方案。Chen等[13]為避免電子投標系統中的第三方信任問題，提出了基于區塊鏈的電子投標系統，利用智能合約處理投標交易，并確保投標過程的完整性。面向傳統眾包數據交易系統中心化信任問題，An等[14]提出了一種基于反向拍賣和區塊鏈的眾包數據交易系統(RADT)，設計RADToken智能合約來強制不信任的各方誠實地參與數據交易。Franco等[15]提出一種基于區塊鏈的反向拍賣架構(BRAIN)，引入一種可審計的方法來降低網絡功能虛擬化(NFV)技術商業化的成本，并分析其優缺點。Hassija等[16]提出了一種在客戶和供應商之間進行能源交易的雙重拍賣方案，通過智能合約實施分布式算法以最大化個人參與利潤。Hassan等[17]開發了一種基于區塊鏈的微電網能源拍賣方法，并使用差分隱私技術確保參與者私有信息的安全。然而，在云虛擬機拍賣領域，還沒有切實可行的保證支付公平的拍賣方案。因此，如何利用區塊鏈和智能合約保證雙邊云資源拍賣支付公平的問題仍有待研究。

針對上述問題，本文提出了一種公平高效的安全雙邊云資源拍賣方案。引入兩個代理商服務器，與拍賣商服務器構成三方計算模型，三方協作運行一系列安全高效的協議來實現整個拍賣流程，在不泄露拍賣隱私的情況下，大幅提高了計算效率。具體地，本文在安全三方計算模型下設計了安全比較協議和安全排序協議，該協議通過第三方生成輔助計算參數，盡可能地減少同態加密等耗時操作的使用。在此基礎上，實現了一個兼顧競價隱私和拍賣效率的安全雙邊云資源拍賣方案。為了滿足云資源拍賣的效率要求，采用輕量級加法秘密分享方法執行大部分安全計算功能，同時將耗時的加解密與密文域操作次數降至最低。此外，本文還考慮了云虛擬機拍賣的公平支付交易問題。由于云虛擬機交易具有高實時性要求，獲勝買家拒絕付款或延遲付款都會給賣家帶來經濟損失。因此，本文基于智能合約對拍賣交易流程進行限定以保證交易支付的公平性。

本文主要貢獻如下：1) 基于加法秘密分享采用“置亂再計算”(Shuffle-then-compute)策略設計了一種安全高效的三方安全排序協議，該協議可以作為各種安全拍賣方案的基礎；2) 基于加法秘密分享和智能合約實現了公平高效的安全雙邊云資源拍賣方案，通過使用輕量級秘密分享方法執行大部分安全計算功能，顯著提高了拍賣的性能；3) 開發實現原型系統，并通過大量實驗驗證了該方案的正確性和高效性。

1 系統定義

1.1 系統模型

本文考慮雙邊市場下隱私保護的云虛擬機拍賣問題，系統模型如圖1所示。參與實體包括多個買方、多個賣方、拍賣商服務器(A)、2臺拍賣代理服務器(B和C)。在該模型下，M個賣方出售K種類型的虛擬機資源給N個買方。在拍賣過程中，買方和賣方在本地分別對其出價和報價進行加法秘密分享，然后將秘密分享份額分別發送至拍賣商服務器A和拍賣代理服務器B。接下來，拍賣商服務器A聯合拍賣代理服務器B和C執行一系列三方安全計算協議來確定最終獲勝的買方、賣方，以及相應的支付價格和資源售賣數量。最后，拍賣商服務器A調用智能合約自動完成支付交易流程。系統參數如表1所示。

圖1 系統模型

表1 系統參數

1.2 安全模型及需求

本文研究半可信攻擊模型下的雙邊云虛擬機拍賣，即所有參與方都是誠實且好奇的，這些實體將會嚴格執行所設計協議，但是會試圖通過傳輸的中間消息推測其他參與方的隱私信息。此外，本文假設參與安全計算的服務器之間不會發生共謀。本文旨在設計公平的安全雙邊云虛擬機拍賣方案，將保證以下特性：

(1) 安全性：任一參與方均不會獲得除了拍賣結果以外的隱私信息。(2) 公平性：一旦拍賣成功，在一定時限內獲勝賣家可獲取相應報酬，獲勝買家可獲取相應的資源，參與計算的代理商和代理服務器可獲取相應的傭金；反之，導致流拍的參與方將會扣罰保證金。

2 背景知識

2.1 雙邊云虛擬機拍賣

1) 勝者匹配。拍賣商首先計算每個買家的出價密度：

φi=ci/(xi·μ)

(1)

式中：公開參數μ=(μ1,μ2,…,μk)T是每種虛擬機的最大服務率。拍賣商根據出價密度對所有出價信息進行降序排序，即:

φα1≥φα2≥…≥φαN

(2)

拍賣商根據報價對不同類型虛擬機的報價信息進行升序排列，即:

(3)

接下來，拍賣商根據以下不等式來確定是否有買家和買家贏得本輪拍賣：

(4)

2) 定價與虛擬機分配。拍賣商計算獲勝買家winb的支付金額：

(5)

獲勝賣家wins對于類型m虛擬機售價為：

(6)

獲勝賣家wins出售的類型m虛擬機的數量為：

(7)

拍賣商將本輪獲勝的買家賣家從拍賣中移除，重復步驟1)和步驟2)直至式(6)無法成立。

2.2 安全計算原語與協議

1) 加法秘密分享[18]：加法秘密共享方通過將l位的輸入值x在環Z2l上隨機地拆分為2個加法秘密份額〈x〉0和〈x〉1，并分別發送給參與方A和B；對于x的秘密分享形式〈x〉，有〈x〉0+〈x〉1≡x(mod 2l)。為了恢復秘密值x(Rec(〈x〉0,〈x〉1))，A和B互換秘密份額并計算x=〈x〉0+〈x〉1。兩個加法秘密分享值和求和計算定義為：參與方A和B分別在本地計算〈z〉i=〈x〉i+〈x〉i(mod 2l)(i∈{0,1})。本文余下部分將省略mod運算。

2) 安全計算協議：在之前的工作中[19-20]，基于加法秘密分享提出了兩種基本的安全計算協議。

(1) 安全乘法(SMUL)協議[19]：參與方A持有〈x〉0,〈y〉0∈Z2l，參與方B持有〈x〉1,〈y〉1∈Z2l，A和B在輔助計算方C的協助下計算(〈z〉0,〈z〉1)=SMul(〈x〉,〈y〉)，滿足〈z〉0+〈z〉1=x·y，其中:〈z〉0僅被A獲取，〈z〉0僅被B獲取。

(2) 安全除法(SDIV)協議[20]：參與方A持有〈x〉0,〈y〉0∈Z2l，參與方B持有〈x〉1,〈y〉1∈Z2l，A和B協同計算(〈z〉0,〈z〉1)=SDiv(〈x〉,〈y〉)，滿足〈z〉0+〈z〉1=x/y，其中:〈z〉0僅被A獲取，〈z〉0僅被B獲取。

2.3 智能合約

區塊鏈概念源于2009年中本聰提出的比特幣[21]。經過了十年的發展，區塊鏈已經能夠在金融、供應鏈等領域成熟應用。以太坊(Ethereum)是一個開源的具有智能合約功能的公有鏈平臺[22]。由于圖靈完備，以太坊成為應用最廣泛的區塊鏈加密貨幣平臺。以太坊能夠通過其專有的Ether和Gas提供去中心化以太虛擬機[23](Ethereum Virtual Machine,EVM)和去中心化應用(Decentralization Applications,DAPPs)來處理點對點智能合約[24](Smart Contracts)。

智能合約是以太坊相對于比特幣的巨大進步。智能合約本質是跑在以太坊上的一段代碼，通過分布式一致性和自動執行來保證代碼運行的不可更改、不可人為操控，從而實現其安全性和不可篡改性。Solidity是以太坊為了開發智能合約專門設計的一種高級編程語言，能夠良好地運行在EVM上[25]。Solidity可以實現投票、眾籌、拍賣、多重簽名錢包等智能合約。

3 安全計算子協議設計

根據2.1節的雙邊云虛擬機拍賣流程可知，比較和排序操作是拍賣過程的主要操作，因此提出兩種安全三方計算協議來實現安全高效的比較與排序操作。以下協議均在1.1節描述的安全三方計算模型下進行，并假設參與方A擁有加法同態密碼公私鑰pk/sk，其他參與方擁有公鑰pk。

3.1 安全比較協議

給定兩組加法秘密分享值〈x〉i、〈y〉i(i∈{0,1})，其中：〈x〉0、〈y〉0存儲在A上，〈x〉1、〈y〉1存儲在B上。安全比較(SCMP)協議的功能是在半可信的第三方C的輔助下根據x和y的大小關系輸出z的秘密分享份額〈z〉i，其中z=(x≥y)，〈z〉0僅被A獲取，〈z〉1僅被B獲取。在協議的整個過程中，沒有關于x和y的任何隱私信息泄露給A和B。SComp協議基本原理如下：

(x-y)r≥0?(x≥y)

協議1安全比較SComp協議

輸入：A輸入〈x〉0,〈y〉0，B輸入〈x〉1,〈y〉1。

輸出：A輸出〈z〉0，B輸出〈z〉1，z=(x≥y)。

1) A和B分別生成隨機正整數〈r〉0∈Z2l和〈r〉1∈Z2l，C生成1和0的加法秘密分享份額〈u〉i=〈1〉i和〈v〉i=〈0〉i，i∈{0,1}；

2) A計算〈e〉0=〈x〉0-〈y〉0，B計算〈e〉1=〈x〉1-〈y〉1，A和B在C的輔助下使用SMul協議計算〈f〉=SMul(〈e〉,〈r〉)；

3) A和B將f的加法秘密份額發送給C，C在本地恢復出f的值f=Rec(〈f〉0,〈f〉1)；

4) 如果f≥0，〈z〉i=〈u〉i，否則〈z〉i=〈v〉i，i∈{0,1}，C將〈z〉0和〈z〉1分別發送給A和B。

3.2 安全排序協議

給定一組加法秘密分享形式的序列〈x〉=〈〈x1〉,〈x2〉,…，〈xn〉〉，其中：x0、x1分別存儲在A和B上，安全排序(SST)協議的功能是在C的輔助下將原序列排列成一組加法秘密分享形式的遞增序列〈xφ〉=〈〈xφ(1)〉,〈xφ(2)〉,…，〈xφ(n)〉〉，其中φ是原序列索引與遞增序列索引之間的映射。在協議的整個過程中，沒有關于x的任何隱私信息泄露給A和B。

為了在加法秘密分享的形式上實現安全高效的排序操作，本文采用了“置亂再計算”的策略設計安全排序協議。具體地，在常規排序操作之前添加一個數據置亂操作用來切斷置亂后的序列與原序列的關系，后續對置亂序列的操作則不會泄露原序列元素間大小關系、訪問模式等隱私信息。協議2描述了安全排序協議的流程。

協議2安全排序(SST)協議

1) A和B分別生成隨機序列u=[u1,u2,…,un]，然后A對u進行加法同態加密得到L0=[Epk(u1),Epk(u2),…,Epk(un)]，并發送給C;B以同樣的方式得到加密隨機序列L1=[Epk(v1),Epk(v2),…,Epk(vn)]發送給C。

2) C接收到L0和L1后，計算L2=〈Epk(u1)·Epk(v1),Epk(u2)·Epk(v2),…,Epk(un)·Epk(vn)〉=〈Epk(u1+v1),Epk(u2+v2),…,Epk(un+vn)〉，使用置亂函數π對L2中元素進行置亂操作得到L2=〈Epk(uπ(1)+vπ(1)),Epk(uπ(2)+vπ(2)),…,Epk(uπ(n)+vπ(n))〉并發送給A。

3) A使用私鑰sk對L2解密并取反得到一組序列，記作〈x′〉0=[-uπ(1)-vπ(1),…,-uπ(1)-vπ(1)]。

4) A計算L3=〈〈x1〉0+u1,〈x2〉0+u2,…,〈xn〉0+un〉并發送給C；B計算L4=〈〈x1〉1+v1,〈x2〉1+v2,…,〈xn〉1+vn〉并發送給C。

5) C計算L3+L4并使用π對其進行置亂操作得到〈x′〉1=〈xπ(1)+uπ(1)+vπ(1),xπ(2)+uπ(2)+vπ(2),…,xπ(n)+uπ(n)+vπ(n)〉并發送給B。

6) A和B設置low=1，up=n

7) iflow

10) forj=lowto (up-1)

14) end if

15) end for

17) A和B設置up=i-1，重復步驟7)至19)

18) A和B設置low=i+1，重復步驟7)至19)

19) end if

20) A設置〈xφ〉0=〈x′〉0，B設置〈xφ〉1=〈x′〉1

具體地，A和B生成隨機序列u=〈u1,u2,…,un〉和v=〈v1,v2,…,vn〉，使用加法同態加密后發給C。C在本地利用加法同態性質計算得到L2=〈Epk(u1+v1),Epk(u2+v2),…,Epk(un+vn)〉，使用置亂函數π對L2中元素進行置亂操作并將置亂后的序列發送給A。

A使用私鑰sk對L2解密并取反得到〈x′〉0=[-uπ(1)-vπ(1),…,-uπ(1)-vπ(1)]。接下來，A和B分別使用u、v對〈x〉0、〈x〉1進行混淆并發送給C，C計算混淆后序列的和并使用π對其進行置亂操作得到〈x′〉1=[xπ(1)+uπ(1)+vπ(1)，xπ(2)+uπ(2)+vπ(2)，…,xπ(n)+uπ(n)+vπ(n)]，然后將〈x′〉1發送給B。至此，A和B上存儲著置亂后序列的加法秘密分享值。接下來，以〈x′〉為輸入，進行快速排序操作。與傳統的快速排序算法相比，本文采用SCMP協議完成加法秘密共享數據上的安全比較操作。由于采用了上述方法，該協議可以很容易地擴展，以支持鍵值對類型數據的安全排序，即數組中的元素是鍵值(ki,xi)，xi用于對數組進行排序。

4 安全雙邊云虛擬機拍賣

基于上述安全計算協議和智能合約，提出了一種公平的安全雙邊云虛擬機拍賣方案，旨在解決拍賣過程可能出現的隱私泄露和公平交易的問題。本節智能合約中相關符號及定義如表2所示。如上文所述，本文安全拍賣協議基于3.1節所介紹的拍賣協議構建，包括系統初始化、安全拍賣和交易支付三個階段，如圖2所示。

表2 智能合約相關符號

圖2 公平的安全雙邊云虛擬機拍賣方案執行流程

4.1 安全排序協議

1) 賣家向區塊鏈注冊拍賣品

2) 賣家設置拍賣保證金額度

3) 賣家設置最長拍賣時間Tauc

4) 賣家設置最長支付時間Tpay

5) 賣家繳納手續費depositrseller

6) 買家繳納保證金和手續費depositbuyer

7) 驗證：押金繳納時間T′

deposit=depositrseller+depositbuyer

depositrseller>(Lsc×GtoP)/2

depositbuyer>(Lsc×GtoP)/2+pledge

(a) 賬戶配置交易(b) 賣方押金交易

(c) 買方押金交易 (d) 勝方支付交易圖3 區塊鏈交易結構

4.2 安全拍賣

2) 拍賣執行：當收到報價的秘密份額后，A與B將執行安全拍賣協議來完成勝者匹配、定價與虛擬機分配，主要步驟如協議3所示。

協議3隱私保護拍賣協議

輸入：A和B中所有秘密分享的報價。

輸出：秘密分享形式的拍賣結果。

1)for1≤i≤N

2)for1≤m≤K

4)endfor

6)endfor

12)for1≤m≤K

14)endfor

15)A,B,C:

17)for1≤j≤M

19) 〈λj〉←SCMP(〈φ〉,〈δj〉)

23)endfor

24)for1≤j≤M-1

25) 〈ηj〉←〈λj〉-〈Vα1〉

26)endfor

27) 〈ηM〉←〈λM〉

28) 〈j*〉←〈η1〉×〈1〉+〈η2〉×〈2〉+…+〈ηM〉×〈M〉

30)for1≤m≤K

32)endfor

λj數組用于表示j是否小于或者等于關鍵索引j*，當j小于等于j*時，λj=1；否則，λj=0。

ηj數組用于表示j是否等于關鍵索引j*，當j等于j*時，ηj=1；否則，ηj=0。

為了幫助理解這一設計，下面給出關鍵索引和兩個標識數組的具體形式：

4.3 公平交易支付

2) 退還非獲勝買家的保證金，即發送pledge給Wbuyer

3) 獲勝買家實際支付金額cost1

6) 更改cost2的所有權給Wseller

7) 更改拍賣資源所有權給Wbuyer

8)differ=cost1-cost2

9) 發送differ給服務器WA

10) 退還獲勝者的保證金，即發送pledge給Wbuyer

11) end if

13) 更改獲勝者押金的所有權給Wseller

14) end if

15) 發送手續費Lsc×GtoP給服務器WA、WB、WC

5 性能評估

本節將對安全計算子協議、安全拍賣協議和公平交易智能合約進行性能評估。本文實驗環境為Intel(R) Core(TM) i7-4790U CPU@3.60 GHz，8 GB RAM配置的64位計算機。對于安全計算協議部分，使用C++實現，平均網絡延遲0.04 ms。對于智能合約部分，在本地服務器上搭建以太坊測試網絡，利用多臺EVM模擬多個以太坊節點。在該網絡中，使用Solidity 0.4.24版本進行智能合約開發。本節對智能合約的性能分析主要針對的是以太坊私有測試網絡，其原因是私有網絡上參與的區塊鏈節點是可控的，部署的智能合約是可分析的。這既符合拍賣場景，又便于實驗分析。同時，由于拍賣過程不會產生大量需要記錄上鏈的交易和區塊，因此本節不考慮世界狀態(World State)對以太坊智能合約調用的影響。

5.1 安全計算協議性能

從安全拍賣方案具體步驟可以看出，安全排序是整個拍賣過程中最為重要且最費時的操作。圖4展示了安全排序(SST)協議和其他兩種基于同態加密[26]和混合式加密[11]解決方案的性能比較。可以看出，隨著元素數量增加，SST協議計算時間呈對數增長，而另外兩種方案接近線性增長。SST協議相較之前兩種方案具有顯著性能優勢，這是因為使用了輕量級的加法秘密共享方法執行了大部分安全計算操作，并且由于第三方輔助服務器的存在，極大地減少了同態加解密與密文域操作的次數。

圖4 安全排序(SST)協議計算時間對比

圖5和圖6分別顯示了在一輪拍賣過程中不同數量的賣家M和買家N情況下安全拍賣協議的計算時間和通信開銷。對于不同數量的買家M，計算時間均隨著賣家數量N的增加以近似線性的速度增加，這與排序協議中相似。對于通信開銷，可以在圖6中看到相同的趨勢，這是因為排序操作的開銷占了整個拍賣開銷的絕大部分。

圖5 不同買家賣家數量時的安全拍賣協議計算時間

圖6 不同買家賣家數量時的安全拍賣協議通信開銷

5.2 智能合約性能

主要分析以太坊節點數量與拍賣智能合約部署和調用時延之間的關聯關系，如圖7所示。首先分析智能合約的部署時延，即在初始化時為每個區塊鏈節點安裝、配置智能合約的平均時間，如圖7實線所示。智能合約的部署時延與節點數量線性相關，隨節點數量的增加而增加。智能合約的執行時延，即執行合約中輸入/輸出功能的平均時間，如圖7虛線所示。智能合約的執行時延隨節點數量的增加而增加，但增幅極小。這是由于大多數以太坊節點只有在保證金繳納和退還階段調用智能合約，獲勝者支付階段只有買賣雙方參與智能合約的執行。

圖7 不同節點數量時的智能合約時延

6 結 語

針對云資源拍賣過程中隱私泄露和公平支付問題，本文基于加法秘密分享提出安全比較和安全排序協議，并基于此設計了一種公平高效的安全雙邊云資源拍賣方案。通過采用置亂再計算的設計策略和第三方代理服務器的輔助，大幅提升了協議的計算和通信效率。此外，本文利用智能合約保證了拍賣過程中公平的交易支付。通過實驗對比分析，本文方案相較于之前的工作在拍賣計算時間和通信開銷方面均具有顯著優勢。在未來工作中，將繼續研究支持各種拍賣算法的安全協議，進一步提升協議的安全性。