布隆过滤器

布隆过滤器是一个概率搜索过滤器，采用一种不精确指定的方式来描述期望的匹配模式。布隆过滤器提供了一种在保护隐私的前提下表达搜索模式的有效途径。SPV节点使用这种方式向其对等节点请求匹配特定模式的交易列表，而不用暴露它们搜索的确切地址。

在我们之前类比的例子中，一个没有地图的游客询问到特定地点“教堂街23号（23 Church St.）”的路线。如果他向一个陌生人询问到该街道的路线，无意间就暴露了他的目的地。如果使用布隆过滤器，他可能问的就是“这附近是否有条街道，它的名字以R-C-H结尾？”这种提问方式，暴露的信息就要比直接说“教堂街23号”要少一些。通过这项技术，游客可以使用较详细的信息，如“以U-R-C-H结尾”来描述地址，也可以使用如“以H”结尾这样更简短的信息。通过改变搜索的精确度，游客可得到更多或更少的信息，相应的代价就是获取更精确或更模糊的结果。如果提供模糊的信息，他可以更好地保护隐私，但将得到非常多的地址，而大多数地址都是不相干的。如果提供相对精确的信息，得到的地址则较少，但在保护隐私上也会较弱。

布隆过滤器允许SPV节点通过调节搜索条件的精确度来提供这项服务。更明确的布隆过滤器将产生更精确的结果，但是代价是暴露用户钱包中使用的地址。粗略的布隆过滤器则因匹配更多的交易而带来更大的数据量，这些交易大多与本节点无关，但是可以为节点提供更好的隐私保护。

SPV节点初始化时把布隆过滤器设置为“空”，在此状态下，布隆过滤器不匹配任何模式。接着，SPV节点生成一个钱包中所有地址的列表，并创建一个匹配所有地址的交易输出的搜索条件。通常，每个搜索条件就是“发送到公钥哈希”的脚本，这个脚本实际上就是出现在每个发送到公钥哈希（地址）的交易输出上的锁定脚本。如果SPV节点正在跟踪一个P2SH地址的余额，那么搜索条件就是“支付到脚本哈希”的脚本。接下来，SPV节点将这些条件添加到布隆过滤器中，使过滤器能够在符合搜索条件的情况下识别出交易。最后，把布隆过滤器发送给对等节点，对等节点依据设定条件将匹配的交易传到本地SPV节点。

布隆过滤器在实现过程中由一个包含N比特位（N位域）的可变长度数组和M个哈希函数构成。哈希函数设置成输出总是在1到N之间，与二进制数组长度对应。哈希函数是确定的，因此，任何实现布隆过滤器的节点都使用相同的哈希函数，并且在输入确定的情况下，将得到相同的结果。通过选择不同长度（N）的布隆过滤器，选用不同数量（M）的哈希函数，布隆过滤器可以调整精确程度和隐私保护级别。

在图6.8中，我们使用一个很小的16位数组，以及一个包含3个哈希函数的集合，演示布隆过滤器的工作过程。

图6.8　简单布隆过滤器的例子，使用16位域和3个哈希函数

布隆过滤器初始化时，二进制数组被设置为全零。为了向布隆过滤器中添加新的匹配模式，首先需要顺次利用预设的哈希函数对模式进行计算。使用第一个哈希函数计算后，将得到一个1到N间的数字，然后将数组上对应的比特位（从1到N编号）设置为1，从而记录哈希函数的输出。接着，使用第二个哈希函数设置数组的第二个比特位，以此类推。一旦M个哈希函数都计算完成后，搜索模式将被“记录”在布隆过滤器上——即二进制数组中的M个比特位被从0改为1。

图6.9是向图6.8所示的简单布隆过滤器中添加一个模式“A”的例子。

图6.9　添加模式“A”到简单布隆过滤器中

添加新的模式非常简单，只是重复一下刚才的步骤。模式被每个哈希函数顺序计算，然后在二进制数组相应位置设置1以记录哈希结果。注意，当采用更多的哈希函数时，可能出现多个哈希结果一样的情况，这时该比特位维持为1不变。实际上，随着模式的增多，越来越多的哈希结果会被记录在相同的位置上，过滤器也因设置为1的位置变多而开始变得饱和，准确性也相应降低了。这就是为什么布隆过滤器是一种概率数据结构的原因——它会随着更多的模式加入而变得不精确。精确度依赖添加的模式数量、二进制数组大小（N）及哈希函数数量（M）三者关系。更大的二进制数组、更多的哈希函数可以在较高精确度的情况下记录更多的模式；而较小的二进制数组或者更少的哈希函数只能记录较少的模式，相应的精确度也较低。

图6.10是添加第二个模式“B”到简单布隆过滤器的例子。

图6.10　添加模式“B”到简单布隆过滤器中

为测试一个模式是否为布隆过滤器的一部分，用M个哈希函数依次对模式进行计算，并用其结果与二进制数组进行比对。如果数组中所有索引号等于哈希结果的位均设为“1”，那么这个模式很可能已被记入布隆过滤器。因为这些位也可能是其他模式的哈希结果的重叠，答案是不确定的，但确实有可能性。简而言之，布隆过滤器的正匹配代表“可能是的”。

图6.11是测试模式“X”是否在简单布隆过滤器中存在的例子。其相应的比特位均已设为“1”，因此模式可能是匹配的。

图6.11　测试模式“X”是否在布隆过滤器中，结果是一个概率正匹配，意思是“可能”

相反，如果模式与布隆过滤器测试过后，某些位被设置为0，则可以证明模式没有被布隆过滤器记录。否定的结果不是可能，而是确定。简单地说，布隆过滤器上的负匹配意味着“肯定不是！”

图6.12是测试简单布隆过滤器中是否存在模式“Y”的例子。其中有一位被设成了0，则此模式一定是不匹配的。

图6.12　测试模式“Y”是否在过滤器中，结果是确定不匹配，意味着“肯定不是！”

布隆过滤器在比特币中的实现方式，在比特币改进提案37（BIP0037）中有所描述。参见附录B或访问GitHub（http://bit.ly/1x 6qCiO）。