简易支付验证（SPV）节点& Bloom过滤器工作原理分
中本聪白皮书中有写到：“不运行全节点也可以验证支付，用户只需要保存所有的区块头（Block Header）就可以了。用户虽然不能自己验证交易，但如果能够从区块链的某处找到相符的交易，就可以知道网络已经认可了这笔交易，而且得到了网络的多个确认。”这里边提到的仅保存区块头的方案就是今天要介绍的SPV，简单支付验证。可以说SPV是个了不起的创新，解决了人们在支付验证时如何处理超大规模区块数据的难题。
SPV（简单支付验证）
我们知道并非所有的节点都有能力储存完整的区块链。受限于存储空间的的限制，很多节点是以SPV（Simplified Payment Verification简单支付验证）钱包接入比特币网络，通过简单支付验证可以在不必存储完整区块链下对交易进行验证。随着比特币的使用热潮，SPV节点逐渐变成比特币节点（尤其是比特币钱包）所采用的最常见的形式。因为SPV节点只需下载区块头，所以
SPV节点不能构建所有可用于消费的UTXO的全貌，这是由于它们并不知道网络上所有交易的完整信息。SPV节点验证交易时所使用的方法略有不同，这个方法需依赖对等节点“按需”提供区块链相关部分的局部视图。
可以把全节点理解成拿着详细地图的人，而SPV节点是出于各种原因手里只有主干道名称的人。那么SPV节点向去到某个地方的话，需要通过随机询问陌生人来获取分段道路指示，且始终存在陌生人不认路或者故意使坏甚至曝露自己个人信息给陌生人的可能性。
SPV通过参考交易在区块链中的深度，而不是高度，来验证它们。全节点会构造一条验证链，这条链是由沿着区块链按时间倒序一直追溯到创世区块的数千区块及交易组成。而SPV节点会验证所有区块的链（但不是所有的交易），并且把区块链和有关交易链接起来。
例如，一个全节点要检查第30万号区块中的某个交易，它会把从该区块开始一直回溯到创世区块的30万个区块全部都链接起来，并建立一个完整的UTXO数据库，通过确认该UTXO是否还未被支付来证实交易的有效性。
SPV节点则不能验证UTXO是否还未被支付。相反地，SPV节点会在该交易信息和它所在区块之间建立Merkle路径。
查询交易K，Merkle路径为：HL 、HU、HMNOP、HABCDEFGH （蓝色） 再通过路径计算出：HKL、HIJKL、HIJKLMNOP和Merkle树根（虚线）
总结起来，就是：
完整的区块链节点是通过检查整个链中在它之下的数千个区块来保证这个UTXO没有被支付，从而验证交易。而SPV节点是通过检查在其上面的区块将它压在下面的深度来验证交易。
如果网络中的其他节点都接受了第30万号区块，并通过足够的工作在该块之上又生成了六个区块，根据代理网关协议，SPV节点就可以证明该交易不是双重支付。
如果一个交易实际上不存在，SPV节点也不会误认为该交易存在于某区块中。SPV节点会通过请求Merkle路径证明以及验证区块链中的工作量证明，来证实交易的存在性。可是，一个交易的存在是可能对SPV节点“隐藏”的。
SPV节点完全可以验证某个交易存在，但它不能验证某个交易（譬如同一个UTXO的双重支付）不存在，这是因为SPV节点没有一份关于所有交易的记录。
这个漏洞会被针对SPV节点的拒绝服务攻击或双重支付型攻击所利用。为了防御这些攻击，SPV节点需要随机连接到多个节点，以增加与至少一个可靠节点相连接的概率。这种随机连接的需求意味着SPV节点也容易受到网络分区攻击或Sybil攻击。在后者情况中，SPV节点被连接到虚假节点或虚假网络中，没有通向可靠节点或真正的比特币网络的连接。
SPV节点使用的是一条getheaders消息，而不是getblocks消息来获得区块头。发出响应的对等节点将用一条headers 消息发送多达2000个区块头。这个过程与全节点获取全部区块没什么区别。SPV节点还在与对等节点的连接上设置了过滤器，用以过滤从对等节点发来的未来区块和交易数据流。任何目标交易都是通过一条getdata的请求来读取的。对等节点生成一条包含交易信息的tx消息作为响应。区块头的同步过程如图1所示。
由于SPV节点需要读取特定交易从而选择性地验证交易，这样就又产生了隐私风险。与全区块链节点收集每一个区块内的全部交易所不同的是，SPV节点对特定数据的请求可能无意中透露了钱包里的地址信息。例如，监控网络的第三方可以跟踪某个SPV节点上的钱包所请求的全部交易信息，并且利用这些交易信息把比特币地址和钱包的用户关联起来，从而损害了用户的隐私。
所以在引入SPV节点/轻量级节点后不久，比特币开发人员就添加了一个新功能：Bloom过滤器，用以解决SPV节点的隐私风险问题。Bloom过滤器通过一个采用概率而不是固定模式的过滤机制，允许SPV节点只接收交易信息的子集，同时不会精确泄露哪些是它们感兴趣的地址。
Bloom过滤器定义
Bloom过滤器是一种允许用户描述特定的关键词组合但不必精确表述、基于概率的过滤方法。它能让用户在有效搜索关键词的同时保护他们的隐私。在SPV节点里，这一方法被用来向对等节点发送交易信息查询请求，同时交易地址不会被暴露。
用我们之前的例子，一位手中没有地图的游客需要询问去特定地方的路线。如果他向陌生人询问“教堂街23号在哪里”， 不经意之间，他就暴露了自己的目的地。Bloom过滤器则会这样问，附近有带‘堂’字的街道吗？”这样的问法包含了比之前略少的关键词。这位游客可以自己选择包含信息的多少，比如“以‘堂街’结尾”或者“‘教’字开头的街道”。如果他问得越少，得到了更多可能的地址，隐私得到了保护，但这些地址里面不乏无关的结果；如果他问得非常具体，他在得到较准确的结果的同时也暴露了自己的隐私。
Bloom过滤器可以让SPV节点指定交易的搜索模式，该搜索模式可以基于准确性或私密性的考虑被调节。一个非常具体的Bloom过滤器会生成更准确的结果，但也会显示该用户钱包里的使用的地址；反之，如果过滤器只包含简单的关键词，更多相应的交易会被搜索出来，在包含若干无关交易的同时有着更高的私密性。
Bloom过滤器工作原理
Bloom过滤器的实现是由一个可变长度（N）的二进制数组（N位二进制数构成一个位域）和数量可变（M）的一组哈希函数组成。这些哈希函数的输出值始终在1和N之间，该数值与二进制数组相对应。并且该函数为确定性函数，也就是说任何一个使用相同Bloom过滤器的节点通过该函数都能对特定输入得到同一个的结果。Bloom过滤器的准确性和私密性能通过改变长度（N）和哈希函数的数量（M）来调节。图2中，我们用一个小型的十六位数组和三个哈希函数来演示Bloom过滤器的应用原理。
图2
Bloom过滤器数组里的每一个数的初始值为零。关键词被加到Bloom过滤器中之前，会依次通过每一个哈希函数运算一次。该输入经第一个哈希函数运算后得到了一个在1和N之间的数，它在该数组（编号依次为1至N）中所对应的位被置为1，从而把哈希函数的输出记录下来。接着再进行下一个哈希函数的运算，把另外一位置为1；以此类推。当全部M个 哈希函数都运算过之后，一共有M个位的值从0变成了1，这个关键词也被“记录”在了Bloom过滤器里。 图3显示了向图8-8里的简易Bloom过滤器添加关键词“A”。
图3
增加第二个关键是就是简单地重复之前的步骤。关键词依次通过各哈希函数运算之后，相应的位变为1，Bloom过滤器则记录下该关键词。需要注意的是，当Bloom过滤器里的关键词增加时，它对应的某个哈希函数的输出值的位可能已经是1了，这种情况下，该位不会再次改变。也就是说，随着更多的关键词指向了重复的位，Bloom过滤器随着位1的增加而饱和，准确性也因此降低了。该过滤器之所以是基于概率的数据结构，就是因为关键词的增加会导致准确性的降低。准确性取决于关键字的数量以及数组大小（N）和哈希函数的多少（M）。更大的数组和更多的哈希函数会记录更多的关键词以提高准确性。而小的数组及有限的哈希函数只能记录有限的关键词从而降低准确性。图4显示了向该简易Bloom过滤器里增加第二个关键词“B”。
图4
为测试某一关键词是否被记录在某个Bloom过滤器中，我们将该关键词逐一代入各哈希函数中运算，并将所得的结果与原数组进行对比。如果所有的结果对应的位都变为了1，则表示这个关键词有可能已被该过滤器记录。之所以这一结论并不确定，是因为这些字节1也有可能是其他关键词运算的重叠结果。简单来说，Bloom过滤器正匹配代表着“可能是”。图5是一个验证关键词“X”是否在前述Bloom过滤器中的图例。相应的比特位都被置为1，所以这个关键词很有可能是匹配的。
图5 在bloom过滤器中测试模式“X”的存在。 结果是一个概率正匹配，意思是“或许”
另一方面，如果我们代入关键词计算后的结果某位为0，说明该关键词并没有被记录在过滤器里。负匹配的结果不是可 能，而是一定。也就是说，负匹配代表着“一定不是”。图6是一个验证关键词“Y”是否存在于简易Bloom过滤器中的图例。图中某个结果字段为0，该字段一定没有被匹配。
SPV节点如何使用Bloom过滤器
Bloom过滤器用于过滤SPV节点从其对等体接收的交易（和包含它们的块），仅选择SPV节点感兴趣的交易，而不会泄露其感兴趣的地址或密钥。
SPV节点将初始化“过滤器”为“空”; 在该状态下，Bloom过滤器将不匹配任何模式。然后，SPV节点将列出所有感兴趣的地址、密钥和哈希，它将通过从其钱包控制的任何UTXO中提取公钥哈希和脚本哈希和交易ID来实现。SPV节点然后将其中的每一个添加到Bloom过滤器，以便如果这些模式存在于交易中，则Bloom过滤器将“匹配”，而不会自动显示模式。
然后，SPV节点将向peer发送一个过滤器加载消息，其中包含在连接上使用的Bloom过滤器。peer上，针对每个传入交易检查Bloom过滤器。全节点根据Bloom过滤器检查交易的几个部分，寻找匹配。
由于全节点向SPV节点发送交易，SPV节点丢弃任何误报，并使用正确匹配的交易来更新其UTXO集和钱包余额。随着它更新自己的UTXO集视图，它还会修改Bloom过滤器，以匹配任何引用其刚刚发现的UTXO的交易。然后，完整节点使用新的Bloom过滤器来匹配新交易，并重复整个过程。
总结起来，就是：SPV节点告诉服务器自己关心的交易特征过滤器，然后这个过滤器有个特点：我们想要的一定在，我们不关心的可能会包含进来。这样也一定程度上保护了SPV节点的隐私。
相关阅读：BIP-37 (Peer Services)中定义了SPV节点的网络协议和Bloom过滤机制。
