EIP-7745: 轻客户端和 DHT 友好的日志索引

一种高效、轻客户端和 DHT 友好的区块头布隆过滤器的替代方案

摘要

用一种新的数据结构替换区块头中固定的 2048 位日志事件布隆过滤器，该数据结构可以适应每个区块不断变化的事件数量，并始终保证足够低的假阳性率。

所提出的结构将所有日志条目映射到一个全局线性索引空间，并基于该索引将它们哈希到一个 Merkle 树中。它还包含每个固定长度的索引空间部分的 filter map，哈希到同一个 Merkle 树中。这些是二维稀疏位图，允许搜索日志地址/主题模式。与每个区块的布隆过滤器不同，它们允许仅通过访问整个数据集的一小部分来搜索特定事件，这也可以通过 Merkle 证明来证明，从而使搜索既高效又对轻客户端友好。它们还为潜在的命中提供精确的位置信息。来自 filter map 的潜在命中不是表明可能存在于给定区块中，而是指向索引空间，可以直接用于从日志条目的 Merkle 树中查找给定索引处的日志。

所提出的结构可以有效地用于本地搜索和远程证明生成/验证，从而简化了证明者和验证者的实现。它还允许对搜索或证明日志都不感兴趣的验证者通过维护一个具有相对较小（硬上限）大小的最小日志索引状态来生成日志索引根哈希。

动机

添加日志的 gas 成本显著降低，因此消耗的资源应低于写入状态。每个区块中布隆过滤器的原始设计实现了这一目标，因为没有像状态那样需要更新的复杂数据结构，每个区块中发出的日志都包含在该区块的头和收据中。日志主要只有长期存储成本。另一方面，在很长一段时间内搜索日志非常昂贵。

只有当布隆过滤器足够稀疏时才有用。假阳性率随着每个过滤器中的事件数量和过滤器位向量中 1 位的密度迅速上升。在当前存在的布隆过滤器中，每个日志地址和主题设置了固定长度 2048 位中的 3 位，这在最初导致了足够稀疏的过滤器，但随着区块 gas 限制的增加，假阳性率很快使过滤器实际上毫无用处。目前，主网区块平均添加超过 1000 个日志地址和主题，因此布隆过滤器的大小需要增加大约十倍才能再次实现可接受的假阳性率。这将使区块头大小增加到大约 3 千字节。即使每个区块的布隆过滤器的大小增加到足够的水平，日志搜索仍然需要访问整个头链。仅在最近一年的历史中搜索将花费超过 6 GB 的数据，还不包括访问布隆过滤器匹配的实际日志。目前的情况更糟，由于布隆过滤器的高假阳性率，需要访问大部分完整区块收据集。

规范

术语和定义

• log value：address value 或 topic value。每个 LOG 操作码添加一个 address value 和 0..4 个 topic value。log value 由一个 32 字节的哈希表示，该哈希计算为 sha2(address) 或 sha2(topic)
• log value index：值被全局映射到一个线性索引空间，并且为每个添加的 log value 分配一个单调递增的 log value index。log values 按照 EVM 执行的顺序添加（首先是 address value，然后是 topic values），因此每个区块和区块中的每个交易中生成的日志在索引空间中占据一个连续的范围。block delimiter 也被添加到区块之间，它有自己的 log value index 并被添加到 log entries 的 Merkle 树中，但没有添加到 filter maps 中。
• log entry：一个带有位置元数据的 SSZ 编码的日志事件（一个 LogEntry 容器）被添加到 log_entries Merkle 树中，位于分配给事件的第一个 log value index（分配给 address value 的那个）。分配给 topic values 的索引处的条目留空（所有字段都为零的 LogEntry）。位置元数据包含区块号，但不包含区块哈希，因为在刚刚添加日志发出的区块仍在构建时，区块哈希尚不知道。如果需要，可以在给定区块中发出的日志之后（除了尚未有_区块分隔符_的头区块，但其哈希始终预计会被证明者/验证者知道）放置的 block delimiter 中找到区块哈希。
• block delimiter：log value index 空间中的一个特殊条目，放置在每个区块发出的日志之间。为了适应固定形状的树结构，它的 Merkle 树形状与 LogEntry 容器相同，Log 部分为空，元信息部分是一个 BlockDelimiterMeta 容器，而不是一个 LogMeta。两者始终可以根据 dummy_value 字段进行区分，该字段代替日志条目的 log_in_tx_index，并且始终具有 2**64-1 的值。它通过编号和哈希引用该区块。每个 block delimiter 都放置在引用区块发出的日志之后，当添加下一个区块时（当引用区块的哈希已经知道时），在该区块发出的日志之前。这使得证明所搜索区块范围的 log value index 边界变得容易，并且还允许证明发出匹配日志的区块的哈希，这是填充 RPC 响应的位置元信息所必需的。
• filter map：一个 MAP_WIDTH x MAP_HEIGHT 大小的稀疏位图，旨在帮助在 log value index 空间的固定 VALUES_PER_MAP 长度部分中搜索 log values。每个 log value 在地图上标记，其中一位设置为 1，该位取决于 log value index 和 log value 本身。行以稀疏方式编码为标记的列索引列表（严格按升序排列，这也与出现的顺序一致）。每个地图最多包含 VALUES_PER_MAP 个标记，因此将假阳性的概率保持在恒定的低水平。
• filter epoch：一组连续的 filter maps，大小为 MAPS_PER_EPOCH，以这样的方式存储在哈希树中，即可以有效地在单个 Merkle 多重证明中检索具有相同 row index 的相邻 filter map 的多行。log value 到 row index 的映射在单个 epoch 期间是恒定的，但在 epoch 之间会发生变化。

共识数据格式

区块头

从执行时间戳 FORK_TIMESTAMP 开始，执行客户端必须将头架构的 logs_bloom 字段替换为 log_index_root，它是添加给定区块中发出的日志后的 LogIndex 结构的根哈希。

因此，生成的头部的 RLP 编码为：

rlp([
    parent_hash,
    0x1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347, # ommers hash
    coinbase,
    state_root,
    txs_root,
    receipts_root,
    log_index_root,
    0, # difficulty
    number,
    gas_limit,
    gas_used,
    timestamp,
    extradata,
    prev_randao,
    0x0000000000000000, # nonce
    base_fee_per_gas,
    withdrawals_root,
    blob_gas_used,
    excess_blob_gas,
    parent_beacon_block_root,
])

容器类型

这些定义使用了 EIP-7916 中定义的 ProgressiveByteList SSZ 类型。

class LogIndex(Container):
    epochs: Vector[LogIndexEpoch, MAX_EPOCH_HISTORY]
    next_index: uint64                                                # 下一个要添加的日志值的索引

class LogIndexEpoch(Container):
    filter_maps: Vector[Vector[FilterRow, MAPS_PER_EPOCH], MAP_HEIGHT]
    log_entries: Vector[LogEntry, MAPS_PER_EPOCH * VALUES_PER_MAP]    # LogEntry 容器位于每个日志事件的第一个索引处，否则为空

type FilterRow = ProgressiveByteList[MAX_BASE_ROW_LENGTH * log2(MAP_WIDTH) // 8 * MAPS_PER_EPOCH, LAYER_COMMON_RATIO]   # 假设 MAP_WIDTH 是 256 的幂

class LogEntry(Container):
    log: Log
    meta: LogMeta

class LogMeta(Container):
    block_number: uint64
    transaction_hash: Root
    transaction_index: uint64
    log_in_tx_index: uint64

class Log(Container):
    address: ExecutionAddress
    topics: List[Bytes32, MAX_TOPICS_PER_LOG]
    data: ProgressiveByteList[MAX_LOG_DATA_SIZE, 4]

class BlockDelimiterEntry(Container):
    dummy_log: Log        # 零地址和空列表
    meta: BlockDelimiterMeta

class BlockDelimiterMeta(Container):
    block_number: uint64
    block_hash: Root
    timestamp: uint64
    dummy_value: uint64  # 2**64-1

日志条目和区块分隔符

带有位置元数据的日志事件被添加到 log_entries 树中，位于分配给日志的 address value 的 log value index 处。这允许对 eth_getLogs JSON-RPC 响应的所有字段进行简单的 Merkle 证明，除了 blockHash，它无法在区块处理时哈希到 log_entries 树中，因为尚未知道已处理区块的哈希。在添加下一个区块的条目之前，还会添加一个 BlockDelimiterEntry，其中包含前一个区块的编号和哈希。

下表显示了将日志条目和区块分隔符映射到 log value index 空间的示例：

Filter map 行编码

filter map 的每一行都编码为一系列以小端二进制编码的列索引。使用建议的 MAP_WIDTH = 2**24 值，这将导致一个简单而有效的编码，如一系列 3 字节值。一行中索引的数量可能在很大范围内变化。完全填充的 filter map 中索引的总数为 VALUES_PER_MAP 减去未在地图上标记的区块分隔符的数量。虽然行的平均大小约为 VALUES_PER_MAP // MAP_HEIGHT，但单个行长度的上限为 VALUES_PER_MAP。

建议的常量

构建过滤器映射

为 log value index 空间的每个 VALUES_PER_MAP 长段生成一个 filter map。 这些是固定大小 MAP_WIDTH x MAP_HEIGHT 稀疏位图，并且每个 log value 在地图上被标记，单个位设置为 1。 区块分隔符未在地图上标记，但否则地图的密度接近恒定。 行中的标记数（稀疏编码的行长度）称为“行长度”，不要与常数 MAP_WIDTH 混淆。

设计目标

所提议的数据结构旨在表示添加项目成本与访问旧项目成本之间的平衡。filter maps 具有固定的树形结构，易于实现内存中维护、Merkle 哈希和 DHT 分布。过滤器条目根据内容和位置进行排序，从而可以快速线性数据库访问和大小高效的 Merkle 证明。某些类型的事件比其他事件频繁得多所产生的困难也得到了缓解。

更新和维护成本也受到限制，因为树节点最终会完成，并且未完成的非空节点的数量始终受到硬限制，从而确保适度的内存需求。链上任何点的初始化数据结构的成本也受到限制。filter maps 的额外数据库存储成本约为实际日志大小的 15%。 Merkle 树结构还可以轻松丢弃整个 epoch 以及相应的 Merkle 子树，从而简化了日志索引的历史到期实现。

Epochs 和映射层

为了允许在较长历史范围内高效搜索某个 log value，filter maps 被组织成 epochs，每个 epoch 由固定数量的 MAPS_PER_EPOCH 的映射组成。 在最常见的情况下（当行密度在平均值附近或低于平均值时），行映射在整个 epoch 中保持不变。 数据库和哈希树都应以这样一种方式组织，即不是将单个地图的所有行彼此靠近放置，而是将整个 epoch 中相同 row index 的行彼此靠近放置，因此访问和/或通过 Merkle 证明证明成本较低。

为了减轻人口稠密的行中的冲突，引入了 mapping layers 的概念，这意味着如果某个行已经有一定数量的条目，则行映射会发生变化，并且非常频繁的 log values 会映射到多个行中。 最初，当地图为空时，每个 log value 都使用 mapping layer 0 或“基本层”进行映射。 如果一行达到 MAX_BASE_ROW_LENGTH，那么在基本层映射中映射到该行的任何进一步的 log values 将改为使用第 1 层映射。 在第 1 层上，将不同的行分配给相同的 log value，并且行长度限制增加到 MAX_BASE_ROW_LENGTH * LAYER_COMMON_RATIO。 如果此行也达到其限制，则使用第 2 层映射，依此类推。 行长度限制呈指数增长，直到达到 MAX_BASE_ROW_LENGTH * MAPS_PER_EPOCH，然后不再增长。 请注意，在某个 mapping layer 上填充的行可以在更高的层上进一步增长。 在较高层上在同一行中冲突的不同 log values 可能在下一层中映射到不同的行，这意味着非常流行的值可能会填充多行（也很长），而不幸的是，在基本层上与其冲突的较不受欢迎的值可能只需要向上移动一层。 搜索过程类似，如果搜索者发现根据基本层限制，属于搜索值的那一行已满，那么它也必须检查下一层，依此类推，直到找到非满的行。

如果一行长于搜索者正在查看的层根据限制，那么它可以安全地忽略额外的条目，假设它们是由另一层上的另一个值添加的。 即使同一行中添加了更多数据，ProgressiveByteList 容器也可以有效地证明属于较低层面的行数据。

行映射

虽然基本层行映射在整个 epoch 中保持不变，但较高层映射更改的频率更高。 每次映射更改都会产生数据库访问开销和 Merkle 证明大小开销的成本，并且 epoch 大小的确定方式是这些开销与访问实际有用数据的成本相比保持足够低。 在行较长的较高层上，可以更频繁地重新映射，因为每个映射的有用数据大小也更大。 此外，希望不那么频繁的 log value 只会在更短的时间内遭受与较长行冲突的困扰。

row index 和最大行长度的计算如下（请注意，from_binary32 和 to_binary32 使用小端编码）：

def get_row_index(map_index, log_value, layer_index):
     layer_factor = MIN(LAYER_COMMON_RATIO ** layer_index, MAPS_PER_EPOCH)
    row_frequency = MAPS_PER_EPOCH // layer_factor
    return from_binary32(sha2(log_value + to_binary32(map_index - map_index % row_frequency) + to_binary32(layer_index))[0:4]) % MAP_HEIGHT

下图显示了如何在不同的 mapping layers 上将 log values 映射到行。 每个点代表一条地图行，数字表示行已分配给给定 log value 的 mapping layer。 请注意，可能会发生较高层映射与相同值的较低层映射重合的情况； 但这不会造成任何问题，因为该行只是在更高层面上得到了进一步的增长。 如果需要，搜索算法还可以简单地重新访问更高层面迭代中的同一行并处理它最初忽略的行的其余部分。

map index        111111 1111222222222233 3333333344444444 4455555555556666
       0123456789012345 6789012345678901 2345678901234567 8901234567890123
      +----------------+----------------+----------------+----------------+
row 0 |2........2......|2...............|...2............|........2.......|
row 1 |........1111.2..|.....2..1111....|1111.....2...2..|2111..2......2..|
row 2 |0000000000000000|.2..2....2..2...|....2111....2...|..2.....11112...|
row 3 |....2..22...1111|..........2.1111|2.......2.2.1111|.......2...2....|
row 4 |.2..1111..2....2|1112..2.2....2..|0000000011110020|...21111.2....2.|
row 5 |...2........2...|...............2|.2...2.........2|.2...2..........|
row 6 |1111.22....2..2.|0020000000020000|.......2...2....|..........2.1112|
row 7 |..2.............|....1112......2.|..2...2.........|0000200000000000|
      +----------------+----------------+----------------+----------------+
            epoch 0          epoch 1          epoch 2          epoch 3

Fig 2. 不同 `mapping layers` 上单个日志值的行映射

MAP_HEIGHT = 8
MAPS_PER_EPOCH = 16
LAYER_COMMON_RATIO = 4

列映射

列映射假设 MAP_WIDTH 是 VALUES_PER_MAP 的倍数。 column index 的计算如下：

def get_column_index(log_value_index, log_value):
    log_value_width = MAP_WIDTH // VALUES_PER_MAP                      # 常数
    column_hash = fnv_1a(to_binary64(log_value_index) + log_value)     # 64 位 FNV-1A 哈希
    collision_filter = (column_hash // (2**64 // log_value_width) + column_hash // (2**32 // log_value_width)) % log_value_width
    return log_value_index % VALUES_PER_MAP * log_value_width + collision_filter

如下图所示，此映射实际上为每个 log value index 分配一个 log_value_width x MAP_HEIGHT 矩形，并确保每个 log value 在其自己的矩形中精确地放置一个标记（字母 A-D 代表不同的 log values）。 此属性还确保 log value index 可以从 map index 和 column index 恢复，列索引永远不会冲突并保持 log value 索引的原始顺序，从而允许对长行中的某些 column indices 进行有效的 Merkle 排除证明。

column             11 1111 1111 2222 2222 2233
       0123 4567 8901 2345 6789 0123 4567 8901
      +---------------------------------------+
row 0 |.... .... .... .... .... .... .... ....|
row 1 |.... .... .... .... .... .C.. .... ....|
row 2 |.A.. .... ...A .... A... .... ...A ....|
row 3 |.... .... .... .... .... .... .... ....|
row 4 |.... .... .... .... .... .... .... ....|
row 5 |.... .B.. .... ...B .... .... .... ....|
row 6 |.... .... .... .... .... .... .... ..D.|
row 7 |.... .... .... .... .... .... .... ....|
      +---------------------------------------+

Fig 3. 具有 4 个不同日志值的 8 个条目的单个过滤器映射

MAP_WIDTH = 32
MAP_HEIGHT = 8
VALUES_PER_MAP = 8

更新日志索引

以下伪代码显示了如何将新区块的日志数据添加到日志索引：

# 将该区块中发出的所有日志值添加到日志索引；即使该区块为空也应被调用
def add_block_logs(log_index, block):
    if block.number > 0:
        # 添加区块分隔符条目
        block_delimiter_meta = BlockDelimiterMeta(block_hash = block.parent_hash, block_number = block.number-1, timestamp = block.parent.timestamp, dummy_value = 2**64-1)
        block_delimiter_entry = BlockDelimiterEntry(meta = block_delimiter_meta)
        log_index.epochs[log_index.next_index // (VALUES_PER_MAP*MAPS_PER_EPOCH)].log_entries[log_index.next_index % (VALUES_PER_MAP*MAPS_PER_EPOCH)] = block_delimiter_entry
        log_index.next_index += 1
    # 在过滤器映射上添加日志条目并标记日志值
    for tx_index, receipt in enumerate(block.receipts):
        tx_hash = sha3(block.transactions[tx_index])
        for log_in_tx_index, log in enumerate(receipt.logs):
            log_meta = LogMeta(transaction_hash = tx_hash, block_number = block.number, transaction_index = tx_index, log_in_tx_index = log_in_tx_index)
            log_entry = LogEntry(meta = log_meta, log = log)
            log_index.epochs[log_index.next_index // (VALUES_PER_MAP*MAPS_PER_EPOCH)].log_entries[log_index.next_index % (VALUES_PER_MAP*MAPS_PER_EPOCH)] = log_entry
            add_log_value(log_index, address_value(log.address))
            for topic in log.topics:
                add_log_value(log_index, topic_value(topic))
    block.log_index_root = hash_tree_root(log_index)

# 在过滤器映射上标记单个日志值
def add_log_value(log_index, log_value):
    bytes_per_column = log2(MAP_WIDTH) // 8   # 假设地图宽度是 256 的幂
    map_index = log_index.next_index // VALUES_PER_MAP
    epoch_index = map_index // MAPS_PER_EPOCH
    map_subindex = map_index % MAPS_PER_EPOCH
    column_index = get_column_index(log_index.next_index, log_value)
    row = []
    layer_index = 0
    while True:
        layer_factor = MIN(LAYER_COMMON_RATIO ** layer_index, MAPS_PER_EPOCH)
        max_row_length = MAX_BASE_ROW_LENGTH * layer_factor
        row_index = get_row_index(map_index, log_value, layer_index)
        row = log_index.epochs[epoch_index].filter_maps[row_index][map_subindex]
        if len(row) < max_row_length * bytes_per_column:
            break
        layer_index += 1
        max_row_length = MIN(max_row_length * LAYER_COMMON_RATIO, MAX_BASE_ROW_LENGTH * MAPS_PER_EPOCH)
    row.append(to_binary32(column_index)[:bytes_per_column])
    log_index.next_index += 1

def address_value(address):
    return sha2(address)

def topic_value(topic):
    return sha2(topic)

查找可能的匹配项

确定在与搜索的 log value 相关的行中找到的 column index 是否可行，方法是恢复 log value index，然后再次从中计算 column index，以检查准随机冲突过滤器部分是否与给定 log value 的预期值匹配：

def get_log_value_index(map_index, column_index):
    log_value_width = MAP_WIDTH // VALUES_PER_MAP                        # 常数
    return map_index * VALUES_PER_MAP + column_index // log_value_width

def is_potential_match(map_index, column_index, log_value):
    return get_column_index(get_log_value_index(map_index, column_index), log_value) == column_index

迭代所有相关的 mapping layers 和相应的行类似于添加新的 log values 的方式。可以使用以下功能过滤所有来自所有相关行的潜在匹配项：

def get_potential_matches(log_index, map_index, log_value):
    matches = []
    epoch_index = map_index // MAPS_PER_EPOCH
    map_subindex = map_index % MAPS_PER_EPOCH
    layer_index = 0
    while True:
        layer_factor = MIN(LAYER_COMMON_RATIO ** layer_index, MAPS_PER_EPOCH)
        max_row_length = MAX_BASE_ROW_LENGTH * layer_factor(layer_index)
        row_index = get_row_index(map_index, log_value, layer_index)
        row = log_index.epochs[epoch_index].filter_maps[row_index][map_subindex]
        for column_index in row:
            if is_potential_match(map_index, column_index, log_value):
                matches.append(get_log_value_index(map_index, column_index))
        if len(row) < max_row_length * bytes_per_column:
            break
        layer_index += 1
        max_row_length = MIN(max_row_length * LAYER_COMMON_RATIO, MAX_BASE_ROW_LENGTH * MAPS_PER_EPOCH)
    return matches

初始化和最小状态

可以使用要添加的下一个叶子的 Merkle 分支来初始化使用严格单调递增密钥更新的 Merkle 树。 如果密钥不是完全单调的（可以多次更新同一叶子），那么也需要先前的叶子值本身。 在 LogIndexMinimalState 的情况下，epochs 是完全单调添加的。 log_entries 树也是完全单调的，而属于每个 row index 的 MAPS_PER_EPOCH 大小的子树是按非严格单调方式更新的。

class LogIndexMinimalState:
    next_index: uint64                                                              # 将添加先前头的区块分隔符的下一个可用索引
    epoch_branch: Vector[Bytes32, log2(MAX_EPOCH_HISTORY)]                          # next_index 指向的 epoch 的 merkle 分支
    filter_map_rows: Vector[FilterRow, MAP_HEIGHT]                                  # next_index 指向的过滤器映射的行
    filter_map_branches: Vector[Vector[Bytes32, log2(MAPS_PER_EPOCH)], MAP_HEIGHT]  # next_index 指向的过滤器映射的每一行的 merkle 分支
    log_entries_branch: Vector[Bytes32, log2(MAPS_PER_EPOCH * VALUES_PER_MAP)]      # next_index 指向的日志条目的 merkle 分支

此结构由 log2(MAX_EPOCH_HISTORY)+MAP_HEIGHT*log2(MAPS_PER_EPOCH)+log2(MAPS_PER_EPOCH * VALUES_PER_MAP) 分支哈希组成，并且总共最多在 MAP_HEIGHT 行中有 VALUES_PER_MAP 列索引。 假设每个过滤器行的可变长度都用两个字节编码，使用建议的常量，这相当于 32*(24+65536*10+10+16)+3*65536+2*65536 = 21300800 字节。 此数字可以被认为是初始化链上任何点的日志索引数据结构所需的数据量的最坏情况硬上限。

需要在同步协议中添加在请求时提供 LogIndexMinimalState，以便允许新同步的节点进行引导。 不想生成历史日志索引数据证明并且只想在保持内存开销最小的同时验证或生成共识的验证者/区块生产者也可以在更新后丢弃旧的 Merkle 树节点，并将此结构用作其日志索引状态。

请注意，也可以在 epoch 边界上进行初始化，在这种情况下，日志索引的初始化成本非常低（仅需要 epoch 分支），但在这种情况下，需要边界和当前头之间的所有区块头和收据才能生成最后一个未完成的 epoch。

理由

日志值索引空间

在每个区块中，都会发出数量不等的 log values。 除了低效的搜索之外，每个区块固定大小的布隆过滤器的另一个缺点是过滤器利用率的变化，导致过度使用的过滤器在某些区块中产生许多误报，并/或在某些区块中浪费地未充分利用的过滤器。 区块 gas 限制也往往会在长期内发生显著变化，因此任何面向未来的解决方案都必须能够适应每个区块的 log values 的不同数量。

将 log values 映射到它们自己的线性索引空间可确保结构相同的 filter maps 的统一过滤器利用率。 与不断更改自适应过滤器大小的替代方案相比，这种方法极大地简化了存储和树哈希方案以及覆盖较长区块范围的 Merkle 多重证明的构建。 它还允许将每个地址和主题值单独映射到连续索引并实现特定的地址/主题模式过滤器。

日志条目树

将整个日志与位置信息一起哈希到树中极大地简化了远程证明/验证过程。 无需单独证明区块头的规范性和其中引用的收据，可以使用单个 LogIndex 结构的 Merkle 证明和属于同一区块号的 BlockDelimiterMeta 来证明一切（如果需要区块哈希）。

以建议的 merkleized 格式将 log_entries 子树直接存储在磁盘上实际上效率不高。 对于想要维护最小状态的验证者来说，这不是问题； 对于他们来说，更新 log_entries 子树的成本非常低，因为他们只需要维护指向下一个 log value index 的单个 Merkle 分支。 证明者可以通过存储 Merkle 树节点的一个子集（那些靠近每个 epoch 的子树的根的节点）来有效地实现 log_entries，并根据以更紧凑的形式编码相同数据的收据按需生成其余部分。

考虑的替代过滤器结构

在不断增长的数据集的搜索结构中，通常需要在添加新数据的成本和搜索现有数据集的成本之间进行权衡。 一种极端情况只是线性存储数据，这实际上是现在日志的情况，而布隆过滤器几乎没用。 另一种极端情况是一个大的 Merkle 树，其中所有曾经使用过的 log values 作为键，所有出现情况的列表（可能以更进一步的 merkleized 格式）作为值。 预计在这里添加新条目的成本与状态相似，其中包括在数千兆字节的数量级的数据库中的多个查找以及在随机位置的修改/插入。 另一个与状态相似的问题是，删除旧条目既困难又昂贵。 添加日志应该比写入状态便宜，因此考虑了这两种极端情况之间的解决方案，这在实践中可能是可行的，并定期生成多个较小的结构。

考虑的一个问题是，是否为在给定期间内发出的每个唯一 log value 添加单独的键，或者使用更压缩的固定大小树格式，其中不同的 log values 可能会冲突（尽管最好不要太多）。 第二个选项还可能包括一些小的概率过滤器信息，这些信息可以帮助过滤掉冲突 log values 的出现，而无需访问/证明属于它们的所有日志。 此决定主要归结为数据访问效率，包括本地磁盘访问和远程 Merkle 证明大小。 结构相同的树可以有效地排列在更大的单元中（此处称为 epochs），其中同一键中的值位于 epoch 的后续树中彼此靠近。 这提高了数据库访问速度。 它还允许更小的 Merkle 证明，其中一系列叶子以高效格式编码在一起，而内部节点仅位于两个边界分支上。 数据库写入也很高效，因为添加树条虽然某些 日志值 的发出频率可能远高于其他值，因此 行索引 的分布可能不完全均匀，但周期性地重新映射行并使用多个 映射层 可确保在足够长的搜索时间内，与更频繁的 日志值 发生的随机冲突会得到平均。映射层 确实还有另一个后果；如果任何行至少有 MAX_BASE_ROW_LENGTH 个条目，则搜索逻辑需要查看在下一个 映射层 上映射到搜索的 日志值 的另一行。这种行的最大可能数量是 VALUES_PER_MAP / MAX_BASE_ROW_LENGTH，因此在最坏的情况下，随机命中其中一个的几率是 VALUES_PER_MAP / MAX_BASE_ROW_LENGTH / MAP_HEIGHT。在这种情况下，必须处理额外的行，并增加发现误报的机会。但是，在某个 映射层 上与常用值发生冲突并不表示在下一层上发生冲突，因此该行中的预期条目数与第一行没有区别。必须处理第三行将假定第二行至少有 MAX_BASE_ROW_LENGTH * LAYER_COMMON_RATIO 个条目。在预期误报的情况下，第一次巧合发生后，这种情况发生的几率实际上可以忽略不计。

对于单个 日志值 搜索，误报的预期数量可以估计为每个 过滤器映射 VALUES_PER_MAP ^ 2 / MAP_WIDTH / MAP_HEIGHT * (1 + VALUES_PER_MAP / MAX_BASE_ROW_LENGTH / MAP_HEIGHT)。按照建议的常量，这大致等于每个映射 0.0044 个误报。截至 2025 年 3 月，主网区块中发出的 日志值 的平均数量略高于 1000，而一个 过滤器映射 由 65536 个 日志值 组成。这粗略估计为每 14000 个区块出现一个误报，这会使搜索者在 log_entries 树中进行额外的查找。整个链历史记录中误报的预期数量约为 1200。

请注意，这仅适用于单个值搜索，而典型的模式搜索需要在多个位置上具有某些值，其误报率呈指数级下降。例如，如果模式是 [Addr, Topic1, Topic2]，则执行三个 日志值 搜索，并且仅当第一个搜索产生 N，第二个搜索产生 N+1，第三个搜索同时产生 N+2 时，才需要实际的日志查找。如有必要，可以通过使用更高的 MAP_WIDTH 来轻松降低速率，但代价是增加编码行的大小。

向后兼容性

现有的日志过滤器 API（eth_getLogs、eth_newFilter、eth_getFilterLogs、eth_getFilterChanges）可以使用新的过滤器数据结构来实现。依赖此 API 的应用程序可以 बिना किसी बदलाव के، 以更高的性能运行。在进行基准测试后，可以考虑重新定价 LOG 操作码，但额外的处理成本并不显着，而额外的存储成本约为 15%。除此之外，EVM 不会以任何方式受到影响，因为它仅发出日志，而不直接访问它们。

安全考虑

使用远程证明者的安全访问

为了证明在给定的区块范围内与给定的搜索模式匹配的完整匹配集，证明者需要

• 通过证明 first_block - 1 和 last_block 的 区块分隔符 条目，证明与搜索的区块号范围相对应的 日志值索引 范围
• 基于 映射索引 和 行索引 证明 过滤器映射 的相关行（验证者可以根据搜索模式中的 日志值 和相关的 日志值索引 范围提前确定相关行）
• 证明属于任何潜在匹配的 日志值索引 的实际 日志条目，如果需要日志位置信息的 blockHash，则还需要证明具有相同区块号的 区块分隔符 条目

由于所有三个步骤都可以通过区块头中引用的相同 LogIndex 结构的 Merkle 证明来实现，因此任何具有删除证明者的搜索都与客户端对链头的了解一样安全。

故意制造误报攻击

该设计保证了误报率在几个 epoch 中统计上会趋于平均，即使在与非常频繁的值发生随机冲突的情况下也是如此，确保过多的误报不会使搜索的带宽和处理成本过高。但是，所有这些仅适用于随机冲突，而不适用于故意创建的冲突。不能完全排除对某个重要的 日志值 进行故意攻击以提高其误报率的可能性，因为对于每个 日志值 生成的少量过滤器数据，始终可以“挖掘”另一个生成冲突过滤器数据的值。但此处使用的列映射使这种攻击变得更加困难，因为 列索引 取决于 日志值 和确切的 日志值索引，使得这种攻击仅适用于区块创建者，他们可能会因对交易集进行更有利可图的操纵而获得 MEV 奖励，而不是使某些日志事件的搜索成本略有增加。

版权

版权和相关权利通过 CC0 放弃。

Citation

Please cite this document as:

Zsolt Felföldi (@zsfelfoldi), "EIP-7745: 轻客户端和 DHT 友好的日志索引 [DRAFT]," Ethereum Improvement Proposals, no. 7745, July 2024. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7745.