結合區塊鏈技術的改進K-匿名激勵機制方案

徐 健，溫 蜜，張 凱

上海電力大學 計算機科學與技術學院，上海200090

1 引言

隨著移動互聯網的迅猛發展，基于位置的服務大量出現在日常生活服務中，如美團、百度地圖和餓了么等。基于位置服務（Location Based Service，LBS）[1]是服務提供商基于用戶地理位置信息向其提供相應服務的一種網絡服務。然而，移動用戶的位置隱私所面臨的諸多威脅并沒有得到充分關注，因為用戶只有將自己的地理位置信息提交給服務商后，才可以享受服務商提供的服務。Beresford 和Stajano[2]首先將位置隱私定義為阻止其他各方了解自己當前或過去的位置的能力。為了保護位置隱私，Chow 等人[3]提出了多種保護移動用戶位置隱私的方法，目前最廣泛的方法是Gruteser和Grunwald[4]從數據隱私保護中[5]引入的K-匿名技術。K-匿名[6]技術的基本思想是在移動用戶和LBS 提供商之間設置一個安全可信第三方代理進行中繼通信。當移動用戶使用LBS，代理通過返回一個至少包含K-1其他移動用戶的隱匿區域來調整實際用戶位置信息的分辨率并將其發送給LBS 服務器，然后將LBS 服務器返回的數據轉發給請求用戶，從而使攻擊者無法準確區分出同一隱匿區域中的真正的請求服務用戶和其他用戶[7]。K-匿名技術簡便易于實現，無需占用大量計算資源，并能取得較好的隱私保護效果，因此被大量應用于位置隱私保護方案中[8]。然而，K-匿名技術要求必須至少有K 個處于匿名集合之中的移動用戶生成一個隱匿區域。在實際的LBS 應用場景中，各用戶節點間互不信任，并且不是所有用戶都關注他們的隱私泄漏問題[9]。而且，在實際應用中，即使某一個節點愿意向其他節點提供幫助生成K-匿名隱匿區域，它也無法從中獲得任何利益。因此，一般節點通常會拒絕向他人提供幫助，導致LBS請求者無法構造K-匿名集合，無法獲得匿名服務。

因此，Yang等人[10]將P2P網絡中被大量研究的激勵機制引入到了生成K 匿名集合中，它的基本思想是用拍賣游戲來實施激勵機制通過向其他節點提供服務，使網絡中的節點直接受益。該方案是基于文獻[11]中的拍賣模式提出的。

然而，文獻[10]所提出的方案有以下不足：（1）文中所提拍賣師是一個可信的第三方，這在現實中是不存在的，并且一旦該第三方受到DOS 攻擊，激勵機制就無法正常運作；（2）由于交易信息過度集中化，當用戶出現大量訪問請求，會導致運行激勵機制的第三方服務器瞬間癱瘓；（3）同時該方案缺乏有效的懲罰機制，無法限制惡意用戶的參與。從而限制了激勵機制在K-匿名隱私保護場景中的應用。

針對以上問題，本文提出了一種新的K-匿名隱私保護激勵機制設計方案。首先改進現有的激勵機制方案并與區塊鏈[12]智能合約[13]結合，具備以下創新點：（1）激勵機制運行于區塊鏈各參與節點中可以做到去中心化交易有效抵御DOS攻擊；（2）區塊鏈采用P2P交易形式，可避免交易信息過度集中出現算力瓶頸；（3）智能合約中加入保證金準入機制，可有效限制惡意用戶加入，且由于運行于公鏈上可激勵更多用戶加入該激勵機制。

2 區塊鏈與智能合約

區塊鏈是一種由所有用戶同時存儲和維護的點對點去中心化交易賬本[14]。該賬本是按照時間順序將交易數據由礦工打包處理生成區塊，并以順序相連的方式組合成的一種鏈式數據結構，利用密碼學數字簽名方式保證數據不可篡改和不可偽造。礦工可以通過計算隨機哈希散列的數值解爭奪處理交易和維護區塊鏈賬本的權力并收取費用，并且能夠自由加入和退出以達到去中心化的作用[15]。

智能合約[16]是一套以數字形式定義的承諾，該承諾控制著數字資產流轉，并包含了合約參與者約定的權利和義務，合約是由計算機系統自動執行。智能合約以數字化的形式寫入區塊鏈中，由區塊鏈技術的特性保障存儲、讀取、執行[17]。同時，由區塊鏈自帶的共識算法構建出一套狀態機系統，使智能合約能夠高效地運行[18]。

智能合約允許交易實體根據其他事務、事件或時間存儲和轉移資金的條件編寫規范，提供了實施和執行金融交易規則的機會，并且不依賴于可信的第三方（如銀行、公用事業）。如圖1 所示：在區塊鏈2.0 中，可以將各種合約提前用代碼邏輯編寫好，由礦工記錄發布于區塊鏈上，每個節點都可以訪問它，通過向其發送指定的交易和事件觸發寫好的代碼邏輯然后進一步生成新的交易和事件，同時可以包含公鏈上通用貨幣的代管，然后根據合約中規定的條件支付給各種其他合約。

圖1 區塊鏈2.0

智能合約與區塊鏈相結合迎來了區塊鏈2.0 時代，以期實現更為復雜的功能。目前，比特幣[12]和以太坊[16]是最被廣泛使用的兩大公共區塊鏈。盡管比特幣交易可以包括基本的腳本能力但其主要還是作為密碼貨幣。而以太坊除了對以太坊密碼貨幣的支持外還可以執行智能合約。

3 系統結構

本文基于區塊鏈智能合約，提出了一種去中心化K-匿名激勵機制。智能合約開發時寫入合約自動達成時的條件，以激勵用戶加入一個K 匿名群體。服務請求者和K-匿名服務提供者按照智能合約中的規則合作以實現K-匿名的目標。生成K-匿名隱匿區域并通過合智能合約驗證后，這些K-匿名服務提供者會得到相應的獎勵。為了安全以及更好地確定參與用戶人選，該方案采取保證金準入機制并使用與文獻[10]中所不同的單向拍賣機制來完成K-匿名的需求，拍賣過程被整合到智能合同中[19]。拍賣記錄由礦工保存在區塊鏈系統中，而不是在一個中心服務器中，實現去中心化的目的。

本文方案系統架構如圖2 所示，由賣家(K-匿名請求人）和買家（投標人）組成，并假設每個賣家和投標人都可通過智能設備訪問，確定是否完成LBS 信息查詢。此外，假定賣方和投標人及其智能設備可以向區塊鏈智能合約發送和接收消息，并且每個投標人都有一份自己的公私密鑰對，能夠對自己發送的內容進行簽名，確保交易內容的唯一性和不可抵賴性。該體系結構實現了四個關鍵部分，包括（1）投標人、（2）賣方、（3）智能設備和（4）智能合約。各部分的功能如下：

申請人代理：申請人代理將在需要服務時發起新的拍賣，并向智能合約發送要求數量K 以及保證金。

投標人代理：每個投標人代理可以隨時監控公鏈上的智能合約狀態，如果有人發起拍賣申請，可申請加入，向智能合約發送一定數量保證金。

智能設備：可以向LBS 服務器發送LBS 請求，也可以向區塊鏈智能合約發送和接收消息。

智能合約：智能合同將接收并存儲來自申請人、投標人和智能設備發送的數據，并執行拍賣和支付功能。

圖2 系統架構

該激勵機制主要執行過程如下：

（1）在公有區塊鏈上部署智能合約。

（2）申請人公布所需要的K 匿名數量及保證金額度。

（3）潛在的競買人監視區塊鏈以進行新的拍賣并提交出價。

（4）智能合約執行拍賣活動以確定中標者。

（5）前K+1名支付保證金最高者獲得任務完成機會，與買家形成一個K 匿名群組。

（6）位置隱私保護任務開始，中標的買家和賣家組成了一個匿名組。組中的所有成員都將其位置和請求發送給服務提供商。攻擊者只能找到K 個用戶一起請求服務，無法確定哪一組位置和請求是真的。

（7）任務完成，進行款項交割，獎勵金加上保證金一并退回中標賬號。

4 激勵機制設計

本章中所使用的符號意義如表1所示。

表1 各符號對應意義

4.1 保證金準入機制

該激勵機制以拍賣活動的形式進行，Us是賣家，Ub是買家，智能合約則作為拍賣人，為了便于說明，當不具體區分買賣雙方時，統稱這二者為代理人。為保證參與用戶權益，需要賣家和買家先向拍賣人支付一定數額的保證金才能發起拍賣活動，以防止任一用戶出現違約情況時，由拍賣人進行賠償。賣家為想要實現的K-匿名隱私保護提供價格，向智能合約發送一筆保證傭金V,并提供Ki件貨物名額（即所需要參加K-匿名用戶數量）。若賣家違約，則該保證金均等賠償給中標用戶。則每位Ub賠償金額為：

而買家則需要向拍賣人支付參與一定數額的保證金Bi才能參加該拍賣活動，若部分買家中途退出或出現違約行為，則保證金全部沒收賠償給賣家。

4.2 單項拍賣算法

（1）本文將K 匿名拍賣建模為單輪密封出價拍賣。拍賣過程如圖3所示。

（2）由于該拍賣活動是密封的出價，每個代理人提供的價格是代理人根據自身要求提出的，沒有代理人有興趣知道由其他人提供的價格。Bj(Bj＞0)既作為保證金同時也作為Ubj的出價（注意Bj不一定等于Cj）。拍賣開始時，賣方首先向拍賣人提出自身要求發起拍賣活動，買方相應提交出價獲得參加資格。以所給出買方的出價和賣方的要求作為輸入，拍賣人確定中標買方組WG，且滿足：

圖3 拍賣游戲

（3）拍賣開始后，委托人賬戶向拍賣人賬戶發送標的數額以及相應的保證金V，競買人若要參加拍賣，則可以向拍賣人賬戶發送愿意支付的保證金Bj，拍賣人對競買人發送的Bj進行排序，且滿足：

拍賣人首先要檢查委托人和競買人的總數是否至少為Ki+2。這里需要比K 匿名要求數量更多的兩個代理人，為了保證真實，需要去掉排名最高和最低的兩個競買人。拍賣人選擇滿足以下要求的Ki+1個競買人作為中標人：

若該情況成立，則繳納保證金額度最多的前K+1個競買人成為中標贏家，每個競買人都得到參與完成該次位置隱私保護任務并可獲取委托人傭金的機會。未中標的買家則返還他們的保證金。

單向拍賣算法流程如圖4所示。

圖4 單項拍賣流程圖

4.3 智能合約設計

本節詳細介紹智能合約以及用于啟用單向拍賣的相關功能。智能合約假定密碼貨幣（例如：以太幣）可以在賣方和買方之間進行貨幣交換且具有現實意義，該智能合約主要包括以下函數：初始化函數、投標函數、拍賣函數、退款函數、獎懲函數。各主要函數功能詳述如下：（1）初始化函數：此函數定義與該拍賣游戲相關的所有值。每一項合同必須保持一組變量，代表拍賣的數量(K)、投標清單（出價）、投標時間（bTime）、交易時間（tTime）、揭曉期時間（rTime）以及拍賣中是否有任何當前的中標者(W)。

委托人必須調用初始化函數來初始化新的拍賣，然而，在進行新的拍賣之前，委托人代理必須向合同支付保證金，以防止惡意拍賣。在委托人所提交的K 匿名位置隱私保護任務完成之后，該保證金將被平均支付給參與任務的中標人。在初始化函數執行之后，該智能合約準備接受各競買人投標。

（2）投標函數：通過監測區塊鏈網絡上的智能合約，不同的競買人可以查看何時有人尋求匿名幫助可供拍賣以及提交他們的出價。這個步驟都必須在預定義的時間bTime 內執行。投標函數向智能合約提交了一個投標，但沒有透露他們的出價。投標函數接受數據為＜b,Hbid,deposit,nonce ＞ 的 元 組 ，Hbid=H(bid,nonce),H 是一個陷門函數（例如密碼散列函數），Nonce是為該交易選擇的隨機值，hbid 將被存儲在區塊鏈上，直到投標周期結束。投標函數還要求各競買人將保證金從競買人的代理賬戶轉移到智能合約賬戶中，以防止競標人提交欺詐性投標。

（3）拍賣函數：在每個出價被披露之后，合同將執行拍賣函數來執行單項拍賣算法來確定拍賣買受人和結算價格。拍賣函數將每個顯示的出價與當前規定范圍內的最低出價進行比較。如果發現新的高出價，規定范圍內的最低和次最低出價將增加，并記錄當前規定范圍內的最低出價投標者。

（4）退款函數：在bTime時間后，拍賣買受人將被選中，開始執行K-匿名任務。此時調用退款函數將未中標競買人的保證金退還，而買受人將繼續留在智能合約中。

（5）獎懲函數：在隱私保護交易完成(t ＞tTime)后執行，以完成最終K 匿名任務和金融結算的結果核算。最后確定功能從中標者發送的LBS服務信息中獲得輸入，以驗證他們分別完成了LBS 查詢任務。獎懲函數將被調用，用以獎勵或處罰相關用戶。

5 實驗部分

5.1 拍賣算法用時比較

實驗所使用1臺計算機配置為Inter i7-8550U 1.99GHz處理器和8 GB 內存，Windows10 64 位操作系統。實驗使用Python 3.6 語言分別模擬不同數量的用戶使用單向拍賣機制算法競拍并與文獻[10]進行相關實驗對比。生成K-匿名群組所需要的時間與買家數量變化關系的結果如圖所示，其中方塊表示文獻[10]中算法，圓點表示單向拍賣算法。

如圖5 所示，當K=20時，文獻[10]中由于假定具有相同隱私保護請求的用戶已超過20 且自行組成K-匿名群體，從而不需要請求其他用戶幫助，因此在該匿名要求下，文獻[10]中所需要的時間與參與游戲的買家數量并沒有關系。而單向拍賣算法依舊需要對參與游戲的買家進行排序選擇生成群組，因而生成K 匿名組合時間相對于文獻[10]較長。

圖5 K=20時匿名區域生成時間

如圖6 所示，當K=120 時，文獻[10]中算法需對賣家和買家分別進行排序，隨著參與人數增加所花費時間越來越多。而本文中算法僅是針對參與游戲的買家用戶進行排序，當參與人數少于120 時生成K 匿名區域失敗，當參與人數大于或等于120 時，采用快速排序算法并生成K-匿名區域。從圖中可以看出單項拍賣算法生成K 匿名組合時間相對于文獻[10]中較短。

圖6 K=120時匿名區域生成時間

5.2 智能合約實驗

以太坊是一個可實現智能合約的開源區塊鏈平臺，智能合約相當于存儲在該平臺區塊鏈中的程序，以太坊虛擬機支持運行已編寫好的智能合約，可允許用戶使用測試區塊鏈進行智能合約的測試。以太坊平臺有其專屬通用代幣，在測試時可以自動為指定賬戶充值一定量代幣做實驗。

本文智能合約采用類似于JavaScript 的高級語言Solidity 語言編寫，并在以太坊環境下使用其官方推薦的IDE—Remix 上對智能合約進行實驗測試，內核版本為0.4.24，同時Remix 提供了相應的程序接口。合約調試編譯結果及部分代碼如圖7所示。

圖7 智能合約

Remix 為智能合約提供了一個區塊鏈環境，圖7 頁面為測試智能合約時的部分頁面，該頁面頂部提供了測試合約時可使用的功能。智能合約代碼在調試后在圖中底部出現藍色框則表示合約代碼編譯成功，ABI則表示該智能合約的接口地址。接著可對智能合約中各主要函數進行測試，測試界面如圖8 所示：該測試環境會默認提供多個賬戶，且賬戶中有少量以太幣用于調用函數測試交易，圖8 下方則顯示該智能合約中設計的各函數，可依次點擊各函數進行交易測試。

圖8 智能合約函數測試

目前以太坊的平均出塊時間為15 s，上述智能合約的實驗測試結果可以看出，該智能合約很好地實現了激勵機制所設計的功能，并且實驗驗證了智能合約的有效性與可行性。以區塊鏈網絡為載體，使本文所提激勵機制可面向更多用戶。

6 安全性能分析

（1）無需第三方機構：與傳統的激勵機制設計不同，本文所提激勵機制采用基于區塊鏈的去中心化架構來保證其安全性，智能合約充當第三方機構被同步運行在公有區塊鏈所有節點中，不依賴于全局可信的第三方實體機構，各節點間采用端到端的通信方式，分布式存儲交易數據，可以有效解決中心化模式下的計算資源不足等問題；而當部分公有區塊鏈節點遭遇分布式拒絕服務攻擊時，其他的公有區塊鏈節點中依舊可以正常工作并保存著所有的交易記錄，不至于使整個激勵機制系統崩潰。

（2）節點身份隱私保護：由于本文所提激勵機制是基于區塊鏈系統實現，參與該激勵機制的用戶為區塊鏈中各代理節點，且都采用假名保護的方式來進行通信，切斷了用戶名與其真實身份之間的聯系，通信雙方或第三方無法獲知通信節點的真實身份；同時，結算過程中使用不同用戶的非對稱密鑰對發送的數據進行加密，攻擊者很難破解所有節點的加密密鑰，最大可能保證相關交易信息安全。

（3）位置隱私保護：保護用戶的位置隱私是保護用戶身份信息與位置信息的關聯。本文采取K 匿名技術通過對使用K 名用戶同時向LBS服務器發送服務申請，混淆身份信息與位置信息的一一對應關系。該公有區塊鏈上每個用戶只是用一串數字賬戶作為代理，初始便以假名機制構造K-匿名群組，極大提高了安全性。該基于區塊鏈的K 匿名激勵模型只是隱藏了身份信息與位置信息的對應關系；但保留了精確的位置數據，并且在選擇K 匿名組成員時比之前方案更充分地考慮了用戶的忠誠度，也采取收取保證金的方式在一定程度上限制了部分惡意節點的參與，提高了形成K 匿名組的成功率。因此，本方案既保護了用戶的位置隱私也提供了較高的服務質量。

7 結束語

本文提出了一種基于區塊鏈智能合約的K-匿名激勵機制。通過引入保證金制度可以有效限制惡意玩家節點的加入，從而有效提高生成K-匿名區域的成功率。本文基于區塊鏈的去中心化架構可使智能合約運行于所有區塊鏈節點中，憑借眾多的公有區塊鏈用戶節點，可以吸引更多用戶參與K-匿名。并提出一種單向拍賣算法，實驗仿真結果顯示相較于相關工作在算法執行速度上有一定的優勢。本文對該方案進行分析，相關結果證明該方案安全可靠且該激勵機制是具有實用性的。后續工作可以對該激勵機制算法進一步優化以及采用盲簽名技術等密碼學方法加強智能合約中節點間發送交易數據的安全性。