什么是布隆过滤器?它如何应用于区块链技术?
April 25th, 2023

布隆过滤器是一种数据结构,可用于通知用户特定项目是否是集合的一部分。虽然它不能确定一个元素是否在集合中,但它可以确定该元素是否在集合中。

Bloom 过滤器由 Burton Howard Bloom 于 1970 年创建,由于其在空间利用方面的效率,对一系列应用程序来说是一个有吸引力的产品。在某些加密货币(最著名的是比特币)中,它们在简化支付验证或SPV中发挥着不可或缺的作用。

用户可以使用 SPV 客户端与比特币网络通信,而无需运行完整节点。由于其特定的存储和处理需求,全节点很难在智能手机等低功耗设备上运行。而 SPV 客户端仅向完整节点询问与用户钱包有关的信息。

将此信息传达给用户的最简单方法是将客户端密钥通知完整节点,确保只向它们发送相关交易。这显然是一个糟糕的选择,因为客户的隐私会受到损害。另一方面,下载每笔交易只是为了删除其中的大部分将是一种带宽浪费。引入布隆过滤器。

让我们举例说明。假设客户端 Alice 有一笔高价值的交易,她不想让运行全节点的 Bob 知道。她构建了一个 Bloom 过滤器,我们将其展示为 10x1 网格:

她通过两个不同的散列函数传递她感兴趣的交易数据,输出两个介于 0 和 9 之间的数字。我们称它们为 4 和 7。她将过滤器发送给 Bob。

看着这个网格,你不知道爱丽丝传递给过滤器的数据是什么。如果您有一个包含数据的集合,您将能够对其进行哈希处理并将其与过滤器进行比较——如果匹配,则可能是 Alice 请求的信息。

同时,可能有很多输入会映射到 4 和 7,因此 Bob 无法确定 Alice 对数据的哪一部分感兴趣。他只是简单地返回所有匹配项,而 Alice 在她这边过滤它们。

当然,这过于简单化了,但它证明了这个概念:Bloom 过滤器混淆了客户的真正利益。这不是一个完美的方法(仍然存在对其隐私的担忧),但它是对非屏蔽请求节点的改进。

Subscribe to 0x9b8F…Bc40
Receive the latest updates directly to your inbox.
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from 0x9b8F…Bc40

Skeleton

Skeleton

Skeleton