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为实验环境搭建测试模型，验证了方法的有效性和可行性.