EIP-7745: Two dimensional log filter data structure

zsfelfoldi · July 17, 2024, 2:57pm

Discussion topic for EIP-7745

github.com/ethereum/EIPs

Add EIP: Two dimensional log filter data structure

master ← zsfelfoldi:new-log-filter

opened 02:51PM - 17 Jul 24 UTC

zsfelfoldi

+363 -0

An efficient and light client friendly replacement for bloom filters. This EIP p…roposes a new data structure that adds a moderate amount of consensus data that is optional to store long term, has limited processing and memory requirements and allows searching for log events with 2-3 orders of magnitude less bandwidth than what bloom filters allowed back when they were not rendered useless by over-utilization. It also inherently adapts to changing block utilization and maintains a constantly low average false positive ratio. https://ethereum-magicians.org/t/eip-7745-two-dimensional-log-filter-data-structure/20580

github.com/zsfelfoldi/EIPs

EIPS/eip-7745.md

new-log-filter

---
eip: 7745
title: Two dimensional log filter data structure
description: An efficient and light client friendly replacement for block header bloom filters
author: Zsolt Felföldi (@zsfelfoldi)
discussions-to: https://ethereum-magicians.org/t/eip-7745-two-dimensional-log-filter-data-structure/20580
status: Draft
type: Standards Track
category: Core
created: 2024-07-17
---

## Abstract

Replace the fixed 2048 bit log event bloom filters in block headers with a new data structure that can adapt to the changing number of events per block and consistently guarantee a sufficiently low false positive ratio. Unlike the per-block bloom filters, the proposed structure allows searching for specific events by accessing only a small portion of the entire dataset which can also be proven with a Merkle proof, making the search both efficient and light client friendly.

As an additional benefit, the new structure provides more precise position information on the potential hits (block number and transaction index) allowing the searcher to only look up a single receipt for each potential hit.

## Motivation

This file has been truncated. show original

An efficient and light client friendly replacement for bloom filters. This EIP proposes a new data structure that adds a moderate amount of consensus data that is optional to store long term, has limited processing and memory requirements and allows searching for log events with 2-3 orders of magnitude less bandwidth than what bloom filters allowed back when they were not rendered useless by over-utilization. It also inherently adapts to changing block utilization and maintains a constantly low average false positive ratio.

wjmelements · July 17, 2024, 10:12pm

Why SHA2 instead of SHA3?

zsfelfoldi · July 18, 2024, 9:40am

Because log_filter_tree uses SSZ merkleization which uses SHA2. I’m not sure whether and when the existing EL structures will be converted to SSZ but for this purpose a binary tree is absolutely the logical choice, Merkle multiproofs are nice and easy with SSZ hash trees, so I think that sticking with the old hexary MPT format would be really impractical. And if we use an existing format with existing tooling then I don’t see a reason to complicate that by not using the hash function it was specified with.

sbacha · January 10, 2025, 2:45am

Will there be a test net support for this? Very interested in using this

etan-status · March 24, 2025, 3:49pm

Have split the ProgressiveByteList to its own EIP: Add EIP: SSZ ProgressiveByteList by etan-status · Pull Request #9523 · ethereum/EIPs · GitHub

frangio · June 28, 2025, 2:36pm

Have any “explainer” articles or videos been published about this EIP?

greg7mdp · July 2, 2025, 9:26pm

See the mp4 here: Releases · etan-status/purified-web3 · GitHub

sbacha · July 18, 2025, 10:49am

This PR is #1 of a 3-part series that implements the new log index intended to replace core/bloombits. Replaces #30370

This part implements the new data structure, the log index generator and the search logic. This PR has most of the complexity but it does not affect any existing code yet so maybe it is easier to review separately.

FilterMaps data structure explanation: gist.github.com/zsfelfoldi/a60795f9da7ae6422f28c7a34e02a07e

Log index generator code overview: gist.github.com/zsfelfoldi/97105dff0b1a4f5ed557924a24b9b9e7

Search pattern matcher code overview: gist.github.com/zsfelfoldi/5981735641c956afb18065e84f8aff34

Note that the possibility of a tree hashing scheme and remote proof protocol are mentioned in the documents above but they are not exactly specified yet. These specs are WIP and will be finalized after the local log indexer/filter code is finalized and merged.

github.com/ethereum/go-ethereum

core/filtermaps: FilterMaps log index generator and search logic

master ← zsfelfoldi:log-filter-1d

opened 08:55AM - 27 Jan 25 UTC

zsfelfoldi

+4825 -0

This PR is #1 of a 3-part series that implements the new log index intended to r…eplace core/bloombits. Replaces https://github.com/ethereum/go-ethereum/pull/30370 This part implements the new data structure, the log index generator and the search logic. This PR has most of the complexity but it does not affect any existing code yet so maybe it is easier to review separately. FilterMaps data structure explanation: https://gist.github.com/zsfelfoldi/a60795f9da7ae6422f28c7a34e02a07e Log index generator code overview: https://gist.github.com/zsfelfoldi/97105dff0b1a4f5ed557924a24b9b9e7 Search pattern matcher code overview: https://gist.github.com/zsfelfoldi/5981735641c956afb18065e84f8aff34 Note that the possibility of a tree hashing scheme and remote proof protocol are mentioned in the documents above but they are not exactly specified yet. These specs are WIP and will be finalized after the local log indexer/filter code is finalized and merged.