Felföldi Zsolt zsfelfoldi

EIP-7745 wire protocol extension

This document specifies the extensions to the Ethereum Wire Protocol required to initialize the log index.

Proposed new messages

GetLogIndexProof (0x12)

[request-id: P, referenceBlockHash: B_32, proofType: P, proofSubset: P]

Log index proof format

A log index proof is a Merkle multiproof that fully or partially proves the contents of certain filter map rows and index entries. The proof format specified here can be used to prove the results of log queries, transaction and block hash lookups, and also to initialize the log index state. The root hash of any proof can be calculated and validated against the expected log index root regardless of its contents but the required contents (the proven subset of filter rows and index entries) depend on the use case. These use cases and their conditions for proof validity are detailed in separate documents.

The general format of a log index proof is defined as follows:

class LogIndexProof(Container):
    filter_rows: FilterRows
 index_entries: IndexEntries

EIP-7745 implementation guide and progress tracker

This document gives a high level overview of the tasks related to EIP-7745 (Trustless log and transaction index). It does not go into specification details, it builds on the EIP, the Python EELS implementation and also some Geth code pieces (both production and WIP). It is intended to organize available resources, track the progress of unfinished tasks and address practical issues related to actual client implementation.

Minimal consensus implementation vs. proof generation

Minimal consensus implementation can be based on the EELS implementation which maintains the minimum subset of the log index tree required to add new entries and calculate the log index tree root. If the client also wants to use the log index either for local acceleration or proof ge

Log indexer overview

This document gives a general overview of the new log indexer implementation.

mapDatabase

This structure is responsible for database access. Unlike the old implementation, this database structure only stores fully rendered maps (the last partially rendered map is simply re-rendered in memory at startup, takes a fraction of a second). It can also mark certain maps dirty, allowing the layer above it to clean up asynchronously. Similarly to the old implementation, it handles four types of database entries:

map range: a single entry that contains information about existing map entries. If it is missing then the database is considered not initialized and everything in the filtermaps key range will be deleted before initializing.
version: database is uninitialized if it does not match the version known by the client.

Trustless execution layer API

This document is a draft proposal for a new trustless execution layer API that uses REST API format similar to the consensus layer API instead of the current JSON RPC. Note that the fully trustless implementation of certain endpoints is very inefficient with the current consensus data structures. EIP-7745 provides an efficient solution for these use cases. It is indicated in the document which endpoints are possible to realize now and which ones depend on the mentioned EIP.

Data format

Similarly to the consensus layer API, by default all requests send and receive JSON data while some request types might also allow binary (RLP) format. The sent and expected data format should be specified by setting the "Content-Type" and/or "Accept" HTTP headers to "application/json" or "application/octet-stream".

Note that the JSON response format is typically more verbose in order to ensure human readability and easy debugging. The binary ve

Finding potential matches for a single log value

Rows of the filter maps are encoded as list of column indices in strictly ascending order. These column indices are 24 bits long according to the current EIP-7745 specs, with the higher 16 bits representing the lowest 16 bits of the log value index of the matching log value entry while the lower 8 bits are calculated from the FNV-1a hash of the log value index and the log value hash itself, providing an additional probabilistic filter strength to the row index assignment that is also calculated from the hash of the position and the log value hash (though this hash changes less frequently as it only depends on the map index, and in the most typical case it is remapped once per epoch, which consists of 1024 maps). Row mapping can also change not only depending on horizontal position but also on row length as if the number of entries in a row reaches a certain threshold, the entry is placed on a higher mapping layer

Log index search implementation overview

The purpose of the log index search mechanism is to return a set of logs that might potentially match a given pattern. The main search function GetPotentialMatches receives the following parameters:

block range
a set of addresses one of which has to match the log address (an empty set is interpreted as a wild card)
a set of topics for each of at most 4 topic positions, one of which has to match the topic at the given position (an empty set is interpreted as a wild card)

GetPotentialMatches constructs a pattern matcher based on the given addresses and topics and translates the block range into log value index range. Then it runs the pattern matcher on the filter maps covering the searched range, running multiple workers in parallel, each processing one epoch at a time. After evaluating the matcher it looks up the actual logs at the resulting potentially matching log value indices. Parallel worker results are collected and returned in chronological order.

FilterMaps data structure explanation

FilterMaps is a search structure that maps the log events of an Ethereum blockchain in a way that allows the implementation of pattern matchers with reasonable amount of data access. It is suitable both for the acceleration of local lookups and for generating reasonably sized trustless proofs for the complete set of results for a certain match pattern and block range. The latter assumes that the structure is tree hashed and the receiver of the proof knows the root hash of this tree. Note that the tree hashing scheme and the proof format are outside the scope of this document.

Linear log value index space

Log values are defined as the SHA2 hashes of log addresses and topics. FilterMaps maps all log values onto a linear index space as shown below:

Block number	Transaction index	Log index	Log event	Log value indices

Log indexer implementation overview

The purpose of the log indexer is to maintain the log index data structure and keep it consistent with the canonical chain. This structure has four components:

information about the currently indexed range
actual filter map data for a consecutive series of maps
pointers from each indexed block number to the first log value index it occupies in the linear index space
pointers from each rendered map to the number of the block that occupies the last log value index of the map

Last block of map pointers and the corresponding reverse direction block to log value index pointers are also stored for the last map of each epoch before the indexed range. During initialization these pointers are added based on a set of hardcoded checkpoints for the given chain (which is a workaround solution until EIP-7745 is passed and these pointers become provable from the latest head). Later if an indexed section gets unindexed then these pointers are retained. Indexing can be started

	==================
	WARNING: DATA RACE
	Write at 0x00c01d5a80f0 by goroutine 226941:
	github.com/ethereum/go-ethereum/p2p/discover.(*revalidationList).schedule()
	/home/zsfelfoldi/go/src/github.com/ethereum/go-ethereum/p2p/discover/table_reval.go:221 +0x193
	github.com/ethereum/go-ethereum/p2p/discover.(*revalidationList).push()
	/home/zsfelfoldi/go/src/github.com/ethereum/go-ethereum/p2p/discover/table_reval.go:227 +0x155
	github.com/ethereum/go-ethereum/p2p/discover.(*tableRevalidation).nodeAdded()
	/home/zsfelfoldi/go/src/github.com/ethereum/go-ethereum/p2p/discover/table_reval.go:59 +0x8a
	github.com/ethereum/go-ethereum/p2p/discover.(*Table).nodeAdded()