IABC：一種基于區塊鏈和布谷鳥過濾器的跨域認證方法

黃 穗，李 健，范冰冰

(華南師范大學 計算機學院，廣州 510631)

1 引 言

身份認證是一項對網絡實體身份有效性進行鑒別的技術，而基于公鑰基礎設施(Public Key Infrastructure，PKI)的身份認證通過可信任的第三方認證中心CA將用戶公鑰和身份標識綁定在數字證書，以此為用戶提供身份認證服務，是目前較為成熟且廣泛采用的認證技術，適用于大規模的網絡環境[1].

隨著社會信息化的不斷提高，不同機構和服務間需要頻繁交互和多域訪問，出現跨域認證[2]需求.針對這一需求，文獻[3]提出橋形結構認證模型，通過架設一個所有域都信任的橋CA來使不同信任域根CA建立對等的信任關系，實現集中的分布式認證結構，證書路徑構建簡單，但該方案需要實現一個各方信任的第三方CA，實用性較差.分級結構認證模型[4]是一種倒置的樹形結構，根CA處于頂部，能夠為直接后繼的子CA頒發證書，每一層子CA都可以為直接后繼的子CA或用戶實體頒發證書.根CA是分級結構模型的唯一信任錨，所有節點都信任它，因而存在單點故障的風險.

區塊鏈技術起源于比特幣，通過將共識機制、時間戳、P2P網絡、非對稱加密、哈希算法、智能合約等多種技術進行深度整合解決了分布式系統節點間信任建立的問題[5，6]，有效防止單點故障的發生，許多學者開始將區塊鏈技術應用在身份認證領域[7].Certcoin[8，9]是一個基于比特幣區塊鏈的分布式PKI認證系統，通過區塊鏈交易的方式將用戶身份和證書公鑰相關聯，實現證書的注冊、更新和撤銷，但交易信息對所有節點可見，因而造成用戶隱私泄露的問題.馬曉婷等人[10]提出一種基于聯盟鏈的跨異構域認證方案，設計了跨域認證與重認證協議，實現IBC和PKI異構域之間的信息服務實體(ISE)安全認證，但是該方案的ISE端計算量較大，而且未解決證書更新和撤銷的問題.文獻[11]以聯盟鏈為基礎設計BCCA信任模型，由各域的信任錨根CA充當聯盟鏈的共識節點，負責在鏈上寫入和查詢跨域證書，在不改變原有各PKI域認證方式的前提下，實現用戶身份在不同PKI域之間的點對點認證，可擴展性較強，是一套較為成熟的跨域認證方案.但是，BCCA模型部署的區塊鏈，其底層的數據存儲系統采用基于鍵值對的LevelDB[12]，系統的讀性能較低，難以滿足證書重認證時頻繁查詢的需求.同時，該方案僅在鏈上寫入證書的附加狀態，并未真正解決證書撤銷的問題.

布谷鳥過濾器[13]是一種支持高并發讀的數據結構，能夠快速檢測某個元素是否存在集合內，同時具有刪除集合內元素的功能.為此，本文提出一種基于區塊鏈和布谷鳥過濾器的跨域認證方法，在不改變原有認證架構的前提下，利用智能合約在區塊鏈上構造布谷鳥過濾器，設計區塊鏈跨域數字證書的組成結構，將證書映射為指紋信息插入到過濾器，降低了證書存儲成本，實現證書的高效注冊、查詢和撤銷.

2 相關技術

2.1 區塊鏈技術

區塊鏈是一種以數據區塊為基本單位的按照特定時序組合形成的鏈式數據結構，并以密碼學方式保證的不可篡改、不可偽造和集中維護的分布式賬本[14].區塊鏈通過自信任的共識機制實現全網數據的一致性，利用智能合約技術規范化數據處理，將哈希算法、Merkle樹和非對稱加密技術相結合以保證數據不可偽造、不可篡改和可追溯，實現在無需可信第三方中介機構情況下進行對等實體之間高效安全的價值交換，進而解決分布式環境下實體間信任建立的問題[15].

圖1 智能合約運行機制Fig.1 Smart contract operation mechanism

作為區塊鏈應用層的核心組成部分，智能合約是區塊鏈載入的一種預置規則、具有狀態、條件響應的，可封裝、驗證、執行分布式節點復雜業務邏輯，完成信息交換、價值轉移和資產管理的計算機程序[16].智能合約在Hyperledger Fabric里又稱為鏈碼[17]，用戶可以在Docker的隔離環境中運行用戶鏈碼，在賬本上讀取和寫入(或更新)一組鍵值對狀態數據，并通過賬本中的讀集合和寫集合來查詢和寫入狀態數據庫(LevelDB).智能合約的誕生使區塊鏈具備計算處理能力，極大地擴展了區塊鏈的應用場景，以Hyperledger Fabric為例，智能合約的運行機制如圖1所示.

2.2 布谷鳥過濾器

布谷鳥過濾器是一種基于Cuckoo Hashing[18]算法的數據結構.該算法采用兩種哈希函數將待插入元素映射到一維數組桶的兩個位置.查找某個元素的時候，只需判斷兩個哈希函數所對應位置中的任意一個是否存在該元素即可[19].插入元素時，如果兩個位置中至少有一個位置為空，可以在任意一個空位置插入該元素.否則，從兩個位置中選擇一個將上面的元素踢出，將當前元素插入.被踢出的元素重復上述的插入步驟，直到找到一個空位置或者反復踢出的次數超過預設的某個閾值.當后者的情況發生時，算法將進行rehash操作來擴展數組容量，重新插入所有元素.Cuckoo Hashing通過改善傳統哈希算法的沖突解決方式，提高了哈希表的負載因子和查詢性能[20]，其算法流程如圖2所示.

圖2 Cuckoo Hashing算法流程Fig.2 Algorithm flow of Cuckoo Hashing

Bin等人基于Cuckoo Hashing設計的布谷鳥過濾器對一維數組進行擴展，在每個桶位置上增加若干個槽位(slot)形成多維結構，顯著降低了元素的被踢出次數.與Cuckoo Hashing不同的是，布谷鳥過濾器存儲的是元素的二進制指紋信息，能夠壓縮插入元素的存儲空間，因而具備存儲海量數據的能力.布谷鳥過濾器查詢元素的時間復雜度不會隨著過濾器元素個數的增加而增加，因而為O(1)[21].刪除元素的操作流程與查詢算法類似，只需找出指紋的存放位置，刪除指紋即可，故其時間復雜度也為O(1).結合以上特性可知，布谷鳥過濾器能夠支持大規模并發的讀操作，快速檢測某個元素是否為其成員，以及高效刪除集合中的某個成員，因此布谷鳥過濾器可用于證書注冊、查詢和撤銷，提高跨域認證效率.

3 基于布谷鳥過濾器的跨域身份認證方法

3.1 區塊鏈跨域數字證書BCDC

基于區塊鏈技術構建分布式PKI需要考慮與現有證書系統的兼容性[22].為此，本文設計一種區塊鏈跨域數字證書(Blockchain Cross-domain Digital Certificate，BCDC)，由區塊鏈上多個域的根CA節點生成，插入到智能合約構造的布谷鳥過濾器.由于布谷鳥過濾器多次存入重復數據時會在相同的數組桶位置上插入，很容易造成插入失敗.為了避免重復證書的插入，BCDC在文獻[11]提出的區塊鏈證書基礎上添加了證書生成時間戳、生成者的域ID和使用者的域ID3個屬性，證書生成時間戳由生成者域的根CA產生，生成者的域ID和持有者的域ID作為生成域、使用域的唯一標識，從時間和空間兩個維度上保證了BCDC的唯一性.

3.2 設計基于區塊鏈和布谷鳥過濾器的跨域身份認證方法

傳統基于區塊鏈的跨域認證方案采用的認證模型類似于網狀結構模型，由各域的根CA(信任錨)充當聯盟鏈共識節點來執行鏈上數據的讀寫，認證步驟分為首次認證、重認證和撤銷認證3個階段.

3.2.1 首次認證

開始認證前，雙方信任錨CAA和CAB將自生成的區塊鏈證書BCertCAA和BCertCAB的哈希值記入區塊鏈中.首次認證步驟如圖3所示.

圖3 傳統跨域認證流程Fig.3 Traditional cross-domain authentication steps

1)UA→CAB：{Request}.UA向CAB發送跨域認證請求.

2)CAB→UA：{str1}.CAB收到UA請求后，向UA發送隨機數str1.

3)UA→CAB：{sign(str1)，str1，CertUA}.UA對該隨機數進行簽名，將數字簽名sign(str1)、本域內的證書CertUA和隨機數str1發送給CAB.

4)CAB驗證sign(str1)、CertUA和str1是否有效.

5)CAB→CAA：{Request，str2}.驗證通過后，CAB通過解析證書CertUA確定使用域的信任錨CAA，向CAA發送請求申請獲得信任錨CAA自生成的區塊鏈證書BCertCAA，同時發送隨機數str2.

6)CAA→CAB：{BCertCAA，str2}.CAA收到請求后，向CAB發送BCertCAA和隨機數str2.

7)CAB→Blockchain：{BCertCAA}.CAB檢查隨機數str2是否有效，將BCertCAA發送到區塊鏈上.

8)CAB通過區塊鏈提供的查詢接口查詢信任錨CAA證書BCertCAA是否在區塊鏈上存在且為生效狀態.若查詢結果為空或證書處于失效狀態，則認證失敗.否則，進入下一步.

9)CAB→Blockchain：{h}.CAB將為UA生成跨域區塊鏈證書BCertUA，CAB，并把BCertUA，CAB的哈希值h記入區塊鏈.

10)CAB→UA：{BCertUA，CAB}.CAB將跨域區塊鏈證書BCertUA，CAB發送給UA，實現生成域對使用域用戶UA的身份認證.

3.2.2 重認證

證書重新認證時，UA只需將跨域區塊鏈證書BcertUA，CAB發送給CAB，由CAB在鏈上調用查詢接口驗證證書哈希值的有效性即可.

3.2.3 撤銷認證

由于區塊數據具有只增不改特性，只能由生成域信任錨CAB在區塊鏈上寫入證書的附加狀態revoke實現證書撤銷.

然而傳統方案中的區塊鏈系統底層使用LevelDB 存儲數據，它是一種寫性能較強但讀性能較弱的數據存儲系統，并不支持跨域認證場景中大規模并發查詢數字證書的操作，同時失效證書仍保存在區塊鏈上，并未真正解決證書撤銷的問題.布谷鳥過濾器的引入能有效解決上述問題.

針對首次認證階段，本文做出以下改進：

1.信任錨CAA和CAB在區塊鏈上采用布谷鳥過濾器插入(Insert)算法，將自生成的區塊鏈證書BCertCAA和BCertCAB插入到過濾器并把布谷鳥過濾器記入區塊鏈，取代傳統的直接將證書哈希值記入區塊鏈的方法.

2.將步驟8)更改為CAB在鏈上采用布谷鳥過濾器查詢(Lookup)算法查詢信任錨CAA證書BCertCAA.

3.將步驟9)改進為CAB在鏈上執行布谷鳥過濾器插入(Insert)算法，將跨域區塊鏈證書BCertUA，CAB插入到過濾器中，最后把過濾器記入區塊鏈.

針對重認證階段，本文將查詢跨域區塊鏈證書的方法修改為：CAB使用布谷鳥過濾器查詢(Lookup)算法，判斷證書BCertUA，CAB是否存在過濾器中.

針對撤銷認證階段，本文將撤銷跨域區塊鏈證書的方法改進為：CAB采用布谷鳥過濾器刪除(Delete)算法移除證書BCertUA，CAB的指紋信息，最后把過濾器記入區塊鏈.

圖4 IABC跨域認證流程Fig.4 Cross-domain authentication process of IABC

上述改進方法能將在區塊鏈上的證書查詢時間復雜度從O(n)或O(log(n))降至O(1)，有效提高跨域認證效率.IABC的跨域認證流程如圖4所示.

3.3 鏈碼的設計與實現

本節主要描述布谷鳥過濾器在Hyperledger Fabric鏈碼上的初始化創建方法，以及證書注冊、查詢和撤銷操作的鏈碼實現.

3.3.1 布谷鳥過濾器初始創建

func(t*Cuckoo)createCuckoo(stub sh.ChaincodeStubInterface)

pb.Response{

var n，k uint32 /* 設置數組桶和槽位的大小 */

f：=cuckoo.NewFilter(n，k)

/* 初始化創建一個n個桶k路slot的布谷鳥過濾器 */

cuckooFilter：=f.Encode()

key：="cuckoo_Filter"

res：=stub.PutState(key，cuckooFilter)

/* 調用用戶鏈碼的PutState接口將過濾器寫入賬本 */

if res !=nil{

return sh.Error(res.Error())

}

return sh.Success([]byte("初始化創建成功"))

}

3.3.2 證書注冊

func(t *Cuckoo)Insert(stub sh.ChaincodeStubInterface)

pb.Response{

key：="cuckoo_Filter"

CF，_：=stub.GetState(key)

/* 調用鏈碼的GetState接口從賬本讀取過濾器模型 */

Loader：=cuckoo.Decode(CF)

file，_：=os.Open(BCDC_Sample)

buf：=bufio.NewReader(file)

for( i

b，_：=buf.ReadBytes(′ ′)

/* 讀取BCDC樣本測試集到緩沖區 */

insertSample：=[]byte(string(b))

i++

if !Loader.Insert(insertSample) {

/* 依次將緩沖區中的測試集插入到布谷鳥過濾器 */

continue

}

}

cuckooFilter：=Loader.Encode()

res：=stub.PutState(key，cuckooFilter)

/* 調用PutState接口將過濾器寫入賬本 */

if res !=nil{

return sh.Error(res.Error())

}

return sh.Success([]byte("插入完畢"))

}

3.3.3 證書查詢

func(t * Cuckoo)Lookup(stub sh.ChaincodeStubInterface)

pb.Response{

key：="cuckoo_Filter"

CF，_：=stub.GetState(key)

/* 調用鏈碼的GetState接口從賬本讀取過濾器模型 */

Loader：=cuckoo.Decode(CF)

file，_：=os.Open(BCDC_Sample)

buf：=bufio.NewReader(file)

for( v

b，_：=buf.ReadBytes(′ ′)

/* 讀取BCDC樣本測試集到緩沖區 */

lookupSample：=[]byte(string(b))

v ++

if !Loader.Lookup(lookupSample){

/* 執行布谷鳥過濾器查詢算法，查詢證書是否存在 */

continue

}

}

return sh.Success([]byte("查詢完畢"))

}

3.3.4 證書撤銷

func(t * Cuckoo)Delete(stub sh.ChaincodeStubInterface，

Cert string) pb.Response{

key：="cuckoo_Filter"

CF，_：=stub.GetState(key)

/* 調用鏈碼的GetState接口從賬本讀取過濾器模型 */

Loader：=cuckoo.Decode(CF)

_：=Loader.Delete(Cert)

/* 執行布谷鳥過濾器刪除算法，撤銷證書 */

cuckooFilter：=Loader.Encode()

res：=stub.PutState(key，cuckooFilter)

/*調用PutState接口將過濾器寫入賬本 */

if res !=nil{

return sh.Error(res.Error())

}

return sh.Success([]byte("撤銷成功"))

}

4 實驗與分析

4.1 實驗準備

實驗模型部署在1臺PC機上，配置如下：Intel Xeon(R) E5-2407-v2(2.4GHz)8核CPU，16GB內存.Ubuntu 16.04.10 LTS desktop操作系統，內核版本號4.15.0-70-generic.Hyperledger Fabric v1.0，鏈碼使用Golang 1.9.2開發，Docker版本號為19.03.2.

表1 BCDC組成結構表Table 1 BCDC composition structureTable

實驗測試前，基于區塊鏈跨域數字證書BCDC的格式建立了5000-30000條，步長為5000的6組證書數據集.證書各屬性的組成結構，如表1所示.

4.2 實驗結果及分析

4.2.1 查詢耗時和存儲成本

實驗根據IABC方法以及文獻[11]提出的基于區塊鏈的跨域認證方案進行性能測試，證書數據集一共分為6組，其中1-6組的測試數據分別與5000、10000、15000、20000、25000、30000條BCDC樣本相對應.為了避免實驗結果的偶然性，每組實驗重復10次算出平均值.兩種方法的證書查詢耗時對比如圖5所示.兩種方法在區塊鏈上的證書存儲成本對比如圖6所示.

圖5 證書查詢耗時對比Fig.5 Query time comparison of certificates

通過性能測試可以看出，傳統方法的證書查詢耗時隨著測試集規模增加呈線性增長，而IABC的查詢時間約為前者的百分之一，僅為毫秒級別，適用于跨域認證大規模查詢證書的應用場景.與此同時，相對于傳統方法，IABC只需在布谷鳥過濾器上插入證書的指紋信息，因而將證書存儲成本降低了一個數量級.綜合以上，本文在區塊鏈上引入布谷鳥過濾器用于跨域認證，提升了用戶的認證效率，同時降低了證書的存儲成本，具備一定的有效性和可行性.

圖6 證書存儲成本對比Fig.6 Storage cost comparison of certificates

4.2.2 假陽性率

布谷鳥過濾器是基于Cuckoo Hashing算法設計的概率數據結構，與其他哈希算法一樣，在極限情況下可能會在指紋信息上發生哈希碰撞，從而導致集合外的元素被判斷存在于集合內的誤判問題，誤判的概率稱為假陽性率.一個具有k個桶，每個桶上有s個槽位，指紋信息位數為f的布谷鳥過濾器，其每個槽位存儲的二進制指紋信息在同等條件下成功出現誤判的概率P滿足式(1)：

(1)

當布谷鳥過濾器對某個元素執行查詢算法時，需要經過2s次判斷，則理論上的假陽性率PCF滿足式(2).

(2)

考慮到布谷鳥過濾器的假陽性率可能會對跨域認證結果造成影響，實驗為過濾器設置不同槽位個數用于測量證書查詢的真實誤判率.證書查詢數量采用數據集中最大規模的30000條樣本，為了保證實驗結果的準確性，數據集分為測試集和驗證集，二者證書皆不相同.實驗首先執行插入算法，將每條測試集映射為16位指紋信息后存儲到過濾器中，再執行查詢算法統計驗證集中判斷為真的證書數量，將其與測試集數量相除得出真實條件下的假陽性率，實驗測試結果如表2所示.

表2 假陽性率測試結果Table 2 Test results of false positive rate

從表2測試結果可知，布谷鳥過濾器假陽性率的真實值皆小于假陽性率的理論值.假陽性率總體上隨著槽位數量減少而逐漸降低，當槽位數量s=16時，假陽性率達到最大值0.03%，但仍處于合理范圍之內.當槽位數量s=4時，布谷鳥過濾器能夠達到其實際使用所接受的誤判率0.0033%，因而具有一定的實用性.

5 總 結

區塊鏈技術在跨域認證場景的研究是一個具有學術意義和應用價值的研究方向，逐漸受到諸多學者的關注.布谷鳥過濾器是一種能夠支持大規模并發讀操作的數據結構，具備存儲大規模數據的能力.雖然在查詢過程中可能存在誤判問題，但假陽性率仍處于實際使用所接受的合理范圍.因此，本文提出了基于區塊鏈和布谷鳥過濾器的跨域認證方法(IABC)，將區塊鏈技術與布谷鳥過濾器進行結合，在不改變原有認證架構的前提下，利用智能合約在區塊鏈應用層上構造布谷鳥過濾器，設計區塊鏈跨域數字證書BCDC的組成結構，并把BCDC映射為二進制指紋信息存儲到過濾器，最終將布谷鳥過濾器模型記入區塊鏈，通過分布式共識維護過濾器的狀態，實現證書注冊、查詢和撤銷的功能，提升了跨域用戶身份的認證效率，降低了證書存儲成本.最后，本文以聯盟鏈平臺Hyperledger Fabric為實驗環境搭建測試模型，驗證了方法的有效性和可行性.