Page 331 - 《软件学报》2021年第5期

张建标 等:一种基于区块链的域间访问控制模型 1555

事务按照类型分类排序,各类型数据达到一定数量后将其封装到一个区块中.
(4) 共识节点在全网广播该区块,其他网络节点验证该区块的合法性:如果合法,则将该区块加入到
本地区块链的尾部;否则,停止传播.
通过以上流程,经过封装成事务的数据存储在区块链网络中,使数据有迹可循,达到透明可信、可追溯、可
验证的目的.
2.4 智能合约
本文所述模型使用智能合约作为代理,为系统提供相关属性及策略的查询或判定服务,其中,PIP Contract
提供属性查询服务,PAP Contract 提供策略查询服务,PDP Contract 提供策略判定服务.数据在使用区块链存储
后,因为在区块链中区块的数量是不断增加的,所以区块链系统的数据查询效率是当前区块链面临的一个重要
问题 [29] .为了提高查询效率,本文使用布隆过滤器(Bloom filter) [30] 配合智能合约进行查询.布隆过滤器是一种利
用空间效率较高的随机数据结构,主要用于迅速判断某一元素是否存在于集合中.下面简单介绍其原理.
存在一个集合 S={x 1 ,x 2 ,…,x n }、m 位二进制向量 BF={B 0 ,B 1 ,…,B m−1 }以及 k 个相互独立的哈希函数 H={h 0 ,
h 1 ,…,h k−1 },且哈希函数的值域均为[0,m−1].首先,将 BF 中所有位的初始值置为 0,然后将集合 S 中的元素 x i 令
BF[h j (x i )]=1,其中,i∈[1,n],j∈[0,m−1],这样就可以得到集合所对应的布隆过滤器 BF S .当判断某一元素 E 是否存在
于集合 S 中时,只需计算 h j (E),j∈[0,m−1],然后检查 BF[h j (E)]是否全部为 1:如果不全为 1,E∉S;否则 E∈S.但是,布
隆过滤器存在一定概率的误判(false positive),误判率为
⎛ ⎛ 1 ⎞ kn ⎞ k ⎛ − kn ⎞ k
P = 1− ⎜ ⎜ 1− ≈ ⎟ 1 e m ⎟ .
− ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎝ ⎝ m ⎠ ⎠ ⎝ ⎠
m
若给定 m,n,则当 k = ln 2 时,误判率最小值:
n
⎛⎞ k m
1
P = ⎜⎟ ≈ 0.6185 .
n
2
⎝⎠
虽然布隆过滤器存在一定概率的误判,但是不会将存在于该集合内的某元素判断为不存在.也就是说,若
E∈S,布隆过滤器给出的结果为 E∈S;若 E∉S,布隆过滤器可能给出 E∈S 的结果.但正是因为布隆过滤器具有较高
的查询效率,且其误判率相比较其效率而言是可以容忍的,因此被应用于当前主流区块链系统 [31] .下面给出智能
合约中布隆过滤器相关算法.
算法 1.
输入:待查询元素(E),待查询集合(S).
输出:查询结果标志(Result_flag).
Begin
//获取待查询集合 S 的布隆过滤器 BF,并将 Result_flag 置为 1
BF=getBF(S), Result_flag=1;
for (i=1; i<hashfunction.length; i++){
bit_key=Hash[i](E);
//判断 BF 的二进制向量 bit_key 位置上是否是 1
if (BF[bit_key]!=1){
Result_flag=0;
break;
}//end if
}//end for
return Result_flag;
}