布隆过滤器是什么？区块里快速找交易的捷径

一句话定义

布隆过滤器（Bloom filter）是一种极简集合索引：用一个位数组和 k 个哈希函数，对“某个元素在不在集合里”给出两种回答之一——“肯定不在”，或者“可能在”。它牺牲一点点误报率，换来极小的体积和查询速度，是区块链轻客户端检索的经典组件。

原理三步走

建一个 m 位的数组，初始全 0。插入元素时，用 k 个不同哈希函数各算出一个位置，把这几位置 1。查询时同样算出 k 个位置：只要有任何一位是 0，元素一定不在集合里；如果全为 1，元素“可能”在里面——因为它的位置可能只是被别的元素分别点亮。误差率由位数组大小、元素数量和哈希个数三者决定：位越多、哈希越独立，假阳性越低，但它永远不会漏报（在里面的元素每一位都必然被点过）。这与默克尔树刚好互补：默克尔证明回答“确定在”，布隆过滤器擅长快速排除“确定不在”，剩下的模糊地带再花真力气逐个核对。

链上的两处实战

第一处是轻钱包的历史方案：BIP 37 让 SPV 节点把自己的地址前缀做成布隆过滤器交给全节点，全节点只转发可能相关的交易，节省带宽（该机制因隐私与资源问题在新版比特币核心中默认关闭，SPV 的信任边界见轻钱包凭什么可信）。第二处在以太坊：每笔交易的回执里带一个 256 字节的 logsBloom 字段，把日志地址与主题哈希撒进位图；索引服务和钱包想找“某合约发出的某事件”，可以先用布隆位图过一遍区块，只对命中的少数交易展开完整日志，把全链扫描变成粗筛加复核。

局限要讲透

布隆过滤器不能删除元素：位被共享，清零会误伤别人，想扩容只能重建更大位图；假阳性率随元素增多单调上升，设计时必须预留容量；它也不隐藏“存在过什么”的元数据，位图本身会泄露成员关系的统计信息。在隐私场景，它还可能成为被动观察者侧信道——BIP 37 被弃用的原因之一就是过滤器内容会暴露钱包地址前缀。

快速问答

问：假阳性会不会导致轻钱包漏掉交易？ 答：不会漏报是布隆过滤器的数学保证，它只会多给你不相关的结果；丢交易的风险来自过滤器被篡改或实现缺陷，不是原理缺陷。

问：为什么不直接存一张地址表？ 答：全量表体积太大、查询需比对千万条记录；位图用几十到几百字节换 O(1) 排除，对带宽受限的节点是数量级差异。

问：普通用户会接触到布隆过滤器吗？ 答：以间接方式接触：钱包“秒出”大额转账提醒、浏览器索引事件日志，背后都靠这类粗筛结构。

三个常见误区

误区一：“布隆过滤器会漏掉交易。”原理层面它永不漏报，真正的风险在工程侧——过滤器被节点篡改、前缀泄露隐私、旧版本实现的资源型攻击，BIP 37 被逐步淘汰正是这个原因。误区二：“位图命中就等于交易存在。”命中只是“可能在”，必须回读完整日志或交易做二次确认，把假阳性当结论是索引事故的经典来源。误区三：“能删元素吗？”不能，位图位置被多个元素共享，删除任何元素都可能误伤其他成员，只能整体重建，这也是它不适合动态高频增删场景的原因。把它记成一扇只会说“肯定不在”和“可能在这”的门，轻客户端的很多省钱设计就都顺理成章了。

风险提示：本文仅作数据结构与协议机制科普，不构成投资建议。