布隆过滤器是一种数据结构,可用于通知用户特定项目是否是集合的一部分。虽然它不能确定一个元素是否在集合中,但它可以确定该元素是否在集合中。
Bloom 过滤器由 Burton Howard Bloom 于 1970 年创建,由于其在空间利用方面的效率,对一系列应用程序来说是一个有吸引力的产品。在某些加密货币(最著名的是比特币)中,它们在简化支付验证或SPV中发挥着不可或缺的作用。
用户可以使用 SPV 客户端与比特币网络通信,而无需运行完整节点。由于其特定的存储和处理需求,全节点很难在智能手机等低功耗设备上运行。而 SPV 客户端仅向完整节点询问与用户钱包有关的信息。
将此信息传达给用户的最简单方法是将客户端密钥通知完整节点,确保只向它们发送相关交易。这显然是一个糟糕的选择,因为客户的隐私会受到损害。另一方面,下载每笔交易只是为了删除其中的大部分将是一种带宽浪费。引入布隆过滤器。
让我们举例说明。假设客户端 Alice 有一笔高价值的交易,她不想让运行全节点的 Bob 知道。她构建了一个 Bloom 过滤器,我们将其展示为 10x1 网格:
她通过两个不同的散列函数传递她感兴趣的交易数据,输出两个介于 0 和 9 之间的数字。我们称它们为 4 和 7。她将过滤器发送给 Bob。
看着这个网格,你不知道爱丽丝传递给过滤器的数据是什么。如果您有一个包含数据的集合,您将能够对其进行哈希处理并将其与过滤器进行比较——如果匹配,则可能是 Alice 请求的信息。
同时,可能有很多输入会映射到 4 和 7,因此 Bob 无法确定 Alice 对数据的哪一部分感兴趣。他只是简单地返回所有匹配项,而 Alice 在她这边过滤它们。
当然,这过于简单化了,但它证明了这个概念:Bloom 过滤器混淆了客户的真正利益。这不是一个完美的方法(仍然存在对其隐私的担忧),但它是对非屏蔽请求节点的改进。