区块链理论：Bloom过滤器

alanoddsoff 发布于2019-06-27 18:28 / 960人阅读

摘要：在过滤器的实现是由一个可变长度的二进制数组和数量可变的一组哈希函数组成。数组的长度越长，哈希函数的个数越多，准确性越高。为测试某一关键词是否被记录在某个过滤器中，我们将该关键词逐一代入各哈希函数中运算，并将所得的结果与原数组进行对比。

Bloom过滤器

由于SPV节点需要从区块链其他节点获取感兴趣的交易信息从而选择性的验证交易，与全节点收取每一个区块内的全部交易不同的是，SPV节点对特点数据的请求可能无意中透露了钱包里的地址信息，这样就产生了隐私风险。例如监控网络的第三方可以跟踪某个SPV节点上的钱包所请求的全部交易信息，并且利用这些信息把交易地址和钱包的用户关联起来，从而损害了用户的隐私。而Bloom过滤器可以解决SPV节点的隐私风险问题。Bloom过滤器是一个允许用户描述特定的关键词组合而不必精确表述的基于概率的过滤方法，在SPV节点里，这一方法被用来向其他区块链节点发送交易信息查询请求，同时交易地址不会被暴露。

假设你来到一个陌生的城市旅游，而你的手里又没有地图，这个时候你可能会向路人打听你要去的目的地。如果你向陌生人直接表述：“您好，请问去颐和园怎么走？”，无意间你就暴露了目的地。而如果使用Bloom过滤器，你就会想陌生人表述“您好，请问最近有带园字的旅游景点吗？”，虽然这样的表述方式没有之前的清晰，并且获得了很多的无用信息，但是你可以根据询问到的信息自己进行筛选。你的目的地暴露的概率就会小很多。

Bloom原理

Bloom过滤器可以让SPV节点指定交易的搜索模式，该搜索模式可以根据私密性和准确性被调节。更高的准确性则会暴露更多的隐私，而更高的私密性也意味着更低的准确性。在Bloom过滤器的实现是由一个可变长度的二进制数组(N)和数量可变的一组哈希函数(M)组成。这些函数的输出值在1～N之间与数组的长度对应，并且该函数为确定性函数，任何一个节点，相同的输入都会产生相同的输出。数组的长度越长，哈希函数的个数越多，准确性越高。反之准确性越低，隐私性越好。我们来详细看一下这个过程，以一个长度为16的数组和数量为3个的哈希函数组成的Bloom过滤器为例

Bloom过滤器中的二进制数组的初始值为0，关键词通过哈希函数的计算被添加到二进制数组中，例如关键词“A”，经过第一个哈希函数计算得出的数值是3，那么二进制数组中下标为1的位置就会被替换成1，经过第二个函数得出的数字是1，那么下标1的位置就会被替换成1，以此类推。当全部M个哈希函数都运算过之后，一共有M个位的值从0变成了1，这个关键词也被“记录”在了Bloom过滤器里

如果某个关键词经过哈希函数的计算得出的数字为3，那么此时3的位置已经是1了，此时3位置的1不会改变。该过滤器之所以是基于概率的数据结构，就是因为关键字的增加导致准确性降低。

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

如图，“X”符合请求节点的要求，但是这个“X”并不一定就是请求节点想要的。因为现在发送过来的二进制数组中数值是经过“A”和“B”计算后重叠的结果。如果我们代入关键词计算后的结果某位为0，说明该关键词并没有被记录在过滤器里。负匹配的结果不是可能，而是一定。也就是说，负匹配代表着“一定不是”

云服务器超融合服务器区块链区块链区块链研发区块链区块链区块链研发 bloom

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/24120.html

以太坊基础概念详解

摘要：主要讲解以太坊中的一些基本元素，如区块账户状态交易费用等。所以它表示的是整个以太坊系统所有账户当前的状态。账户以太坊中有两种账户外部拥有账户，一般指自然人拥有的账户。总结以上就是以太坊里的一些基础元素，没有讲到复杂的交易执行等，后续再写。本文不讲区块链，也就意味着你有一些区块链的基本认知。主要讲解以太坊中的一些基本元素，如：区块、账户、状态、交易、费用等。因这些概念之间相互紧密联系，...

pingink 2019-06-27 18:18 评论0 收藏0
Python以太坊区块链交互将数据存入数据库

摘要：是一个用于连接以太坊区块链的库。网络执行以太坊协议，该协议定义节点彼此之间的交互规则及网络上的智能合约。数据库设计下一步是设计数据库。关于区块链介绍性的研讨会通常以易于理解的点对点网络和银行分类账这类故事开头，然后直接跳到编写智能合约，这显得非常突兀。因此，想象自己走进丛林，想象以太坊区块链是一个你即将研究的奇怪生物。今天我们将观察该生物，并与其进行交互然后将有关它的所有数据收集到一...

paulli3 2019-06-27 18:41 评论0 收藏0
Python以太坊区块链交互将数据存入数据库

摘要：是一个用于连接以太坊区块链的库。网络执行以太坊协议，该协议定义节点彼此之间的交互规则及网络上的智能合约。数据库设计下一步是设计数据库。关于区块链介绍性的研讨会通常以易于理解的点对点网络和银行分类账这类故事开头，然后直接跳到编写智能合约，这显得非常突兀。因此，想象自己走进丛林，想象以太坊区块链是一个你即将研究的奇怪生物。今天我们将观察该生物，并与其进行交互然后将有关它的所有数据收集到一...

baukh789 2019-07-30 17:42 评论0 收藏0