这两天利用空闲时间终于把之前遗留的几个关于布隆过滤器的问题搞明白了，那种感觉无法用语言表达出来，有相同经历的人应该会懂。

区块链网络中并不是所有的节点都有能力储存完整的区块链(几百G)，像数字钱包等手机客户端会因为空间的限制，会通过简易支付验证（SPV）的方式在不必存储完整区块链的情况下工作。

由于SPV节点(没有特殊说明，本文SPV节点均指数字轻钱包)需要读取特定交易从而选择性地验证交易，这样会产生隐私风险——SPV节点对特定数据的请求可能无意中透露了钱包里的地址信息。例如，监控网络的第三方可以跟踪某个SPV节点上的钱包所请求的全部交易信息，并且利用这些交易信息把比特币地址和钱包的用户关联起来，从而损害了用户的隐私。我们可以使用Bloom过滤器来解决SPV节点的隐私风险问题。

0x01.Bloom过滤器保护隐私的原理

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

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

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

0x02.Bloom过滤器如何工作？

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

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

  • 初始化

    Bloom过滤器数组里的每一个数的初始值为零。 图1

  • 向简易Bloom过滤器添加关键词“A”

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

  • 向该简易Bloom过滤器里增加第二个关键词“B”

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

  • 验证关键词“X”是否在前述Bloom过滤器中（相应的比特位都被置为1，所以这个关键词很有可能是匹配的）

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

  • 验证关键词“Y”是否存在于简易Bloom过滤器中

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

0x03.SPV节点如何使用Bloom过滤器？

SPV节点将初始化“过滤器”为“空”;在该状态下，Bloom过滤器将不匹配任何模式。

然后，SPV节点将列出所有感兴趣的地址，密钥和散列，它将通过从其钱包控制的任何UTXO中提取公钥哈希和脚本哈希和交易ID来实现。 SPV节点然后将其中的每一个添加到Bloom过滤器，以便如果这些模式存在于交易中，则Bloom过滤器将“匹配”，而不会自动显示模式。

然后，SPV节点将向对等体发送一个过滤器加载消息，其中包含在连接上使用的bloom过滤器。在对等体上，针对每个传入交易检查Bloom过滤器。完整节点根据bloom过滤器检查交易的几个部分，寻找匹配，包括：交易ID、每个交易输出的锁定脚本的数据组件（脚本中的每个键和哈希）、 每个交易输入、每个输入签名数据组件（或见证脚本）。

通过检查所有这些组件，可以使用Bloom过滤器来匹配公钥哈希，脚本，OP_RETURN值，签名中的公钥或智能合同或复杂脚本的任何未来组件。

在建立过滤器之后，对等体然后将针对Bloom过滤器测试每个交易的输出。只有与过滤器匹配的交易才会发送到节点。

响应于来自节点的getdata消息，对等体将发送一个merkleblock消息，该消息仅包含与过滤器匹配的块和每个匹配交易的merkle路径的块头。然后，对等体还将发送包含由过滤器匹配的交易的tx消息。

由于完整节点向SPV节点发送交易，SPV节点丢弃任何误报，并使用正确匹配的交易来更新其UTXO集和钱包余额。随着它更新自己的UTXO集视图，它还会修改Bloom过滤器，以匹配任何引用其刚刚发现的UTXO的交易。然后，完整节点使用新Bloom过滤器来匹配新交易，并重复整个过程。

设置bloom过滤器的节点可以通过发送filteradd消息将模式交互式添加到过滤器。要清除bloom过滤器，节点可以发送一个过滤清除消息。因为不可能从布局过滤器中删除模式，所以如果不再需要模式，则节点必须清除并重新发送新的Bloom过滤器。

(END)