深入浅出,以太坊LogBloom过滤器是如何生成的

在以太坊的世界里，每一个区块都不仅仅是一笔笔交易的简单集合，它还包含了丰富的状态变更信息，为了高效地查询这些信息，以太坊设计了一种精巧的数据结构——Bloom过滤器，与交易日志（Logs）紧密相关的就是LogsBloom，本文将深入浅出地拆解LogsBloom的生成过程,揭示其背后的设计哲学与实现细节。

为什么需要LogsBloom？——高效的日志查询

想象一下，如果你想知道在过去的一百万个区块中，是否有某个特定地址（比如0x123...）作为主题（Topic）产生过日志，最直接的方法是遍历所有区块，读取其中的每一个交易，再解析出每一个日志，最后进行匹配，这种方法的计算成本是极其高昂的,几乎不可行。

LogsBloom的出现就是为了解决这个问题，它是一种概率性数据结构，可以快速判断一个元素可能存在或一定不存在于一个集合中。

• “可能存在”：如果LogsBloom告诉你某个地址/主题“可能存在”，你需要去实际的数据中（区块的日志部分）进行验证。
• “一定不存在”：如果LogsBloom告诉你“一定不存在”，那么你就可以100%确定该地址/主题从未在任何日志中出现过,无需进行后续的昂贵查询。

这种特性使得以太坊客户端（如Geth）能够非常快速地筛选掉大量不相关的区块，只对少数“可疑”区块进行深入解析,从而极大地提高了查询效率。

LogsBloom的生成单位：单个日志

LogsBloom并非在区块层面直接生成，而是由区块内每一个日志的Bloom值组合而成的,理解单个日志的Bloom值生成是理解LogsBloom的第一步。

一个以太坊日志由三个核心部分组成：

1. Address (地址)：产生日志的合约地址。
2. Topics (主题)：一个32字节哈希值的数组，用于对日志事件进行索引,第一个Topic通常是事件的签名哈希。
3. Data (数据)：日志的任意数据部分，这部分数据不参与Bloom过滤器的计算。

构建过程详解：从日志到Bloom值

生成一个日志的Bloom值,可以分解为以下几个关键步骤：

步骤1：初始化一个空的Bloom过滤器

我们创建一个具有2048个比特的初始Bloom过滤器，所有比特位都设置为0，这个大小是固定的,足以提供足够低的误报率。

步骤2：对Address和Topics进行编码

Bloom过滤器的设计思想是，将需要索引的关键信息（Address和Topics）通过一系列的哈希函数，映射到Bloom过滤器的不同比特位上，并将这些比特位置为1。

以太坊使用了一种名为 eth-abi的编码方式 来处理Address和Topics，这个过程可以看作是一种“标准化”的预处理。

1. 处理Address：

   • 将20字节的地址（0x123...）编码为 32 字节，编码规则是在地址前填充零,使其总长度为32字节。
   • 地址 0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B 会被编码为：

     0x000000000000000000000000Ab5801a7D398351b8bE11C439e05C5B3259aeC9B

2. 处理Topics：

   • 每个32字节的Topic本身就是标准格式,无需额外填充。
   • Topics数组中的每一个Topic都会被单独处理。

步骤3：应用Bloom哈希函数

经过编码后，我们得到了一组32字节的数据块（一个编码后的Address和多个Topics），以太坊使用三个不同的哈希函数来处理这些数据块。

这三个哈希函数分别是：

• Keccak256(Hash(data) + i)，i 分别为 0, 1, 2。

具体操作如下：

对于每一个32字节的数据块（无论是编码后的Address还是任何一个Topic）：

1. 计算该数据块的 Keccak256 哈希值,得到一个32字节的哈希结果。
2. 将这个哈希结果视为一个256位的无符号整数。
3. 使用这个整数的高11位（因为 2^11 = 2048，正好对应Bloom过滤器的比特位数量）来计算出比特索引。
   • 索引计算公式：index = hash_value & 0x7FF (0x7FF 是一个11位的掩码，即 2047)。
4. 将Bloom过滤器中计算出的 index 位置的比特位设置为 1。

注意：对于同一个数据块，因为 i 的值不同（0, 1, 2），所以会使用三个不同的哈希函数，生成三个不同的索引，并将这三个比特位都置为1。

步骤4：组合所有数据块的影响

一个日志包含一个Address和多个Topics，我们需要对每一个数据块重复步骤3的操作,也就是说：

• 对编码后的Address，计算3个比特位并置1。
• 对第一个Topic，计算3个比特位并置1。
• 对第二个Topic，计算3个比特位并置1。
• ...以此类推。

这个过程就像是把所有信息点“撒”到Bloom这张网里，每个信息点都会在网中留下三个“标记”（置1的比特位），一个日志的Bloom值,就是所有这些标记的总和。

从单个日志到区块LogsBloom

我们有了区块中每一个日志的独立Bloom值,那么整个区块的LogsBloom是如何生成的呢？

这个过程非常简单：按位或（Bitwise OR）。

假设一个区块有N个日志，每个日志都有一个2048比特的Bloom过滤器 Bloom_1, Bloom_2, ..., Bloom_N。

整个区块的最终LogsBloom值 Bloom_final 计算如下： Bloom_final = Bloom_1 OR Bloom_2 OR ... OR Bloom_N

按位或操作的含义：只要任何一个日志的Bloom过滤器在某个比特位上是1，最终区块的LogsBloom在该位上就一定是1，这完美地契合了我们的需求：只要区块中任何一个日志包含了某个地址或主题，那么该地址/主题就“可能”存在于这个区块中。

一个简单的示例

假设一个区块包含一个日志：

• Address: 0x1111...1111 (编码为32字节后记为 Addr)
• Topics: [Topic_A, Topic_B]

生成过程如下：

1. 初始化：创建一个全0的2048比特Bloom过滤器 Bloom_log。
2. 处理Address：
   • 对 Addr 应用三次哈希，得到索引 i1, i2, i3。
   • 将 Bloom_log 的 i1, i2, i3 位置为1。
3. 处理Topic_A：
   • 对 Topic_A 应用三次哈希，得到索引 j1, j2, j3。
   • 将 Bloom_log 的 j1, j2, j3 位置为1。（如果某些位置已经是