什么是Bloom过滤器

Bloom过滤器是一个允许用户描述特定的关键词组合而不必精确表述的基于概率的过滤方法。它能让用户在有效搜索关键词的同时保护他们的隐私。在SPV节点里,这一方法被用来向对等节点发送交易信息查询请求,同时交易地址不会被暴露。

用我们之前的例子,一位手中没有地图的游客需要询问去特定地方的路线。如果他向陌生人询问“教堂街23号在哪里”,不经意之间,他就暴露了自己的目的地。Bloom过滤器则会这样问,附近有带‘堂’字的街道吗?”这样的问法包含了比之前略少的关键词。这位游客可以自己选择包含信息的多少,比如“以‘堂街’结尾”或者“‘教’字开头的街道”。如果他问得越少,得到了更多可能的地址,隐私得到了保护,但这些地址里面不乏无关的结果;如果他问得非常具体,他在得到较准确的结果的同时也暴露了自己的隐私。

Bloom过滤器可以让SPV节点指定交易的搜索模式,该搜索模式可以基于准确性或私密性的考虑被调节。一个非常具体的Bloom过滤器会生成更准确的结果,但也会显示该用户钱包里的使用的地址;反之,如果过滤器只包含简单的关键词,更多相应的交易会被搜索出来,在包含若干无关交易的同时有着更高的私密性。

首先,SPV节点会初始化一个不会匹配任何关键词的“空白”Bloom过滤器。接下来,SPV节点会创建一个包含钱包中所有地址信息的列表,并创建一个与每个地址相对应的交易输出相匹配的搜索模式。通常,这种搜索模式是一个向公钥付款的哈希脚本、,该脚本是一个会出现在每一个向公钥哈希地址付款的交易中的锁定脚本。如果SPV节点需要追踪P2SH地址余额,搜索模式就会变成P2SH脚本。

然后,SPV节点会把每一个搜索模式添加至Bloom过滤器里,这样只要关键词出现在交易中就能够被过滤器识别出来。

最后,对等节点会用收到的Bloom过滤器来匹配传送至SPV节点的交易。

Bloom过滤器的实现是由一个可变长度(N)的二进制数组(N位二进制数构成一个位域)和数量可变(M)的一组哈希函数组成。。这些哈希函数的输出值始终在1和N之间,该数值与二进制数组相对应。并且该函数为确定性函数,也就是说任何一个使用相同Bloom过滤器的节点通过该函数都能对特定输入得到同一个的结果。Bloom过滤器的准确性和私密性能通过改变长度(N)和哈希函数的数量(M)来调节。

在图6-8中,我们用一个小型的十六位数组和三个哈希函数来演示Bloom过滤器的应用原理。

Bloom过滤器的应用原理

Bloom过滤器数组里的每一个数的初始值为零。关键词被加到Bloom过滤器中之前,会依次通过每一个哈希函数运算一次。该输入经第一个哈希函数运算后得到了一个在1和N之间的数,它在该数组(编号依次为1至N)中所对应的位被置为1,从而把哈希函数的输出记录下来。接着再进行下一个哈希函数的运算,把另外一位置为1;以此类推。当全部M个哈希函数都运算过之后,一共有M个位的值从0变成了1,这个关键词也被“记录”在了Bloom过滤器里。

图6-9显示了向图6-8里的简易Bloom过滤器添加关键词“A”。

简易Bloom过滤器

增加第二个关键是就是简单地重复之前的步骤。关键词依次通过各哈希函数运算之后,相应的位变为1,Bloom过滤器则记录下该关键词。需要注意的是,当Bloom过滤器里的关键词增加时,它对应的某个哈希函数的输出值的位可能已经是1了,这种情况下,该位不会再次改变。也就是说,随着更多的关键词指向了重复的位,Bloom过滤器随着位1的增加而饱和,准确性也因此降低了。该过滤器之所以是基于概率的数据结构,就是因为关键词的增加会导致准确性的降低。准确性取决于关键字的数量以及数组大小(N)和哈希函数的多少(M)。更大的数组和更多的哈希函数会记录更多的关键词以提高准确性。而小的数组及有限的哈希函数只能记录有限的关键词从而降低准确性。

图6-10显示了向该简易Bloom过滤器里增加第二个关键词“B”。

image.png

为测试某一关键词是否被记录在某个Bloom过滤器中,我们将该关键词逐一代入各哈希函数中运算,并将所得的结果与原数组进行对比。如果所有的结果对应的位都变为了1,则表示这个关键词有可能已被该过滤器记录。之所以这一结论并不确定,是因为这些字节1也有可能是其他关键词运算的重叠结果。简单来说,Bloom过滤器正匹配代表着“可能是”。

图6-11是一个验证关键词“X”是否在前述Bloom过滤器中的图例。相应的比特位都被置为1,所以这个关键词很有可能是匹配的。

image.png

另一方面,如果我们代入关键词计算后的结果某位为0,说明该关键词并没有被记录在过滤器里。负匹配的结果不是可能,而是一定。也就是说,负匹配代表着“一定不是”。

图6-12是一个验证关键词“Y”是否存在于简易Bloom过滤器中的图例。图中某个结果字段为0,该字段一定没有被匹配。

image.png

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。