IVC for scalable trust-free Ethereum logs

Today, Ethereum logs are in a strange position. In theory, Ethereum is designed to make it easy for user nodes to scan the chain history and quickly identify all logs that are relevant to a given topic: scan block by block, do a bloom filter check, and if the bloom filter check reports a collision then go into that block and identify any matching logs. To facilitate this, Ethereum has sophisticated protocol features - notably the bloom filter - and the LOG opcode has significant gas costs to charge for bloom filter congestion. In practice, however, this history scanning is far too slow, and so almost no one actually uses it: almost everyone that needs to query historical logs uses a centralized or semi-centralized provider.

To get past this issue, I propose that:

1. At the protocol layer, we decrease the gas cost of LOG to a minimal value (eg. 10 plus hashing costs) and remove bloom filters.
2. Implement an extra-protocol decentralized and secure mechanism for querying logs

The rest of this post proposes a concrete mechanism for (2).

Incrementally verified log tree

When processing a chain, we maintain a “parallel state”, with the following rules:

• The parallel_state is a key-value map hash32 -> hash32, where a key being empty is considered equivalent to that key holding the value zero
• When a LOG is processed, for each topic t in the log, we set parallel_state[t] = hash(parallel_state[t], block_number, hash(log))

For each Ethereum block, we can compute its “parallel post-state root”. Furthermore, we can compute an incremental proof proving that:

• Either the slot number is the initial slot of the scheme, or incremental proof of the parent block is correct
• The provided parallel post-state root is the result of starting from the previous block’s parallel post-state root and applying all logs in the block’s receipt tree

If a client sees a single proof providing a parallel post-state root, and uses their local Ethereum node (possibly a light client) to verify the latest Ethereum block containing the “regular” post-state root, they can be sure that the provided parallel post-state root is correct.

Users interested in the topic can now query for a branch in the incremental proof tree, and then query for the hash chain starting from the leaf and going back as far as they need. This querying is completely trustless.

If desired, we can extend this to automatically log all ETH transfers. This could be done either by an Ethereum protocol change by which any ETH transfer creates a log, or (more expensively) by having the proof walk over the EVM computation of the block.

Maintaining accessibility into the tree can be done via a decentralized p2p network, eg. the Portal network. Generating proofs can be done by a small number of redundant altruistic nodes.