一、地址监控

一个 HD 钱包管理的是一组自动计算的地址。以比特币为例，在确定了根扩展私钥 m 后，得到一组地址为 m/44'/0'/0'/0/x，其中 x=0~2 的 31 次方。

HD 钱包需要在链上监控每个 TX 的输入和输出，看看上述管理的一组地址是否存在与输入和输出中。如果作为输入，则钱包余额减少，如果作为输出，则钱包余额增加。

现在问题来了：如何根据 TX 的输入和输出地址快速判断这些地址中是否存在 HD 钱包管理的地址？

首先，可用的地址高达 2 的 31 次方个，这个数太大了，用户不可能用完，因此，HD 钱包只会预生成前 1000 个地址（即索引号为 0～999）并保存在本地数据库中，如果不够了，再继续扩展 1000 个，这样，HD 钱包管理的地址数量不会太大。

其次，要在上千个地址集合中快速判断某个地址是否存在，查询数据库是一个非常低效的方式。以哈希表存储在内存中虽然效率很高，但管理的集合数量太多，占用的内存会非常大。

要做到高效的查询和低空间占用率，可以使用布隆过滤器（Bloom Filter），它是由 Burton Howard Bloom 在 1970 年提出的，其原理是将每个元素通过若干个哈希函数映射成一个位数组的若干个点，将其置 1。检索的时候，先计算给定元素对应位是否全 1，如果是全 1，则给定元素很可能存在，否则，元素必定不存在。

因此，Bloom Filter 有个重要特点，就是判断元素时，如果不存在，那么肯定不存在，如果存在，实际上是以一定概率存在（例如，99%），还需要再次从数据库查询以确定元素真的存在。

Bloom Filter 的缺点就是它无法 100% 准确判断存在，此外，添加新的元素到 Bloom Filter 很容易，但删除元素就非常困难。构造 Bloom Filter 时，要先预估元素个数并给定存在概率，才能计算所需的内存空间。

Bloom Filter 广泛用于垃圾邮件地址判断，CDN 服务等。Bloom Filter 也非常适合 HD 钱包监控链上每个交易的地址。

二、小结

HD 钱包通过 Bloom Filter 可以高效监控链上的所有地址，并根据是否是本地管理的地址决定如何计算钱包余额。