Bloom过滤器

Bloom filter:是一种节省空间,高效率的数据表示和查询结构.它可以利用位数组很简洁地表示一个集合,并能以很高的概率判断一个元素是否属于这个集合.因此,这种数据结构适合应用在能容忍低错误率的场合.

将一个元素映射到一个m长度的阵列上的一个点,当这个点是1时,那么这个元素在集合内,反之则不在集合内.这个方法的缺点就是当检测的元素很多的时候可能会有冲突,解决方法就是使用k个Hash函数对应k个点,如果所有点都是1的话,那么元素在集合内,如果有0的话,那么元素不在集合内

简单来说,就是将要检测的转化为字符串之后进行多次hash,每一次都检测在数据中的下标是0还是1,如果都是1则表示存在

主要用于解决某些元素是否为集合中元素的判断问题.通过一定的错误率换取空间的节省和查询的高效

SPV节点:Simplify Payment Verification,信任别的节点对区块和交易作校验,一般会在与邻节点的连接中设置过滤器,在比特币中叫做Bloom过滤器

Bloom过滤器:只接收包含钱包里的公钥地址的交易

1.当一个邻节点看到一个交易与SPV节点的过滤器设置的条件符合,它就会用merkleblock消息来给该SPV节点发送一个区块

2.该merkleblock消息包含区块头和一个连接该交易到Merkle树根的一个merkle路径.

3.SPV节点可以利用该merkle路径来把交易和包含交易的区块联系起来,并验证交易包含在区块中

4.SPV节点也用区块头来验证包含交易的区块和区块链中的其他区块能连上

5.这两个验证可以证明交易是记录在区块链上.总之,SPV节点只需要接收小于1KB的区块头和merkle路径数据,这个是全节点接收数据的千分之一(目前全节点接收区块的大小是1M)