Discussion topic for EIP-8304: Trustless log and transaction index
Note that this EIP is a result of the same “trustless log index” project as EIP-7745 but it is a new and different (much simpler) design.
4 Likes
We’re strongly in favor of this EIP at Willow. We’ve been working on this problem from the off-protocol side, so a few measurements from our prover may be useful.
From the draft:
any meaningful proof would include all block receipts since the last contract update. The cost of this would be impractical for API proofs and prohibitive for on-chain/cross-chain proofs.
That’s close to what we do today: prove log queries directly from receipts, without the proposed tables.
For one recent 2,048-block query, proving took 56 minutes on a single A100. The proof was verified on mainnet in 550,091 gas, independent of range length: transaction.
Across our profiling runs, 59% of the proving work goes to rebuilding receipt tries against receiptsRoot, 34% to scanning logs, and less than 1% to walking headers and checking blooms. In other words, most of the cost is proving completeness.
The tables change that. Once a block’s logs are committed, filters can be proven against that commitment instead of redoing the completeness work from receipts. For logs, the table already contains the address, topics, and position, so only matching receipts need to be opened to recover data.
The lexicographic ordering is especially useful here: matches are contiguous, so the entries immediately before and after the range can establish completeness. We would prefer to keep that property fixed.
We also see the bloom saturation described in the motivation. Across the same 2,048 blocks, the median logsBloom had 1,473 of 2,048 bits set. In our tests, even filters returning no logs could still require opening more than a third of the blocks.
On pre-fork history, I’m not convinced a proven table rebuild is prohibitively expensive with today’s hardware. Our rough estimate for one table level is about 25,400 A100-hours, or a little over $35K in GPU time at the rate we paid.
That estimate uses 3.72B transactions and our measured proving cost per receipt. The transaction-trie cost is unmeasured, so we assume roughly the same cost again. For table hashing, we estimate about 32B entries and use our measured Keccak cost as a stand-in for the SHA-256 specified by the EIP.
This excludes data fetching and sorting, and the EIP-7708 re-execution is a separate problem we haven’t priced. The estimate is rough, but it suggests a one-time proven rebuild is feasible enough to investigate.
If this gets to a devnet, we’d be interested in implementing a table prover for log and transaction-hash lookups, along with a history index contract, and publishing the actual costs.
Thanks for the response!
About proving pre-fork history: proving historic tables from already consensus-proven receipts sounds like the easier thing to me, and you are probably right, it might be feasible to do with today’s tech. What looks like a more serious undertaking though is proving the entire EIP-7708 re-execution of the chain. Anyways, this is something that will probably be cheap and easy at a certain point in the future, but my point is that this is not something that the viability of EIP-8304 should depend on. If we can trust a consensus change verified and implemented by multiple teams, we can also trust a hardcoded historic table root verified with multiple implementations, at least until we have a better solution.
Regarding the proofs of log and tx lookups: I already have a proof format defined, the verifier implemented in Go and some WIP documents written about the proof format and verification at my trustless log index repo:
I am actively improving the docs right now, also I want to check if the binary proof encoding works correctly on the provided test API endpoint, but you can probably already use it as a starting point. Building efficient ZKPs of log index proof verification would be very useful (my long term dream is to make these super cheap on chain with recursive ZKPs and have super cheap and efficient UTXOs based on logs and my index tables).
Another super useful thing would be to build the proof system that does a very simple thing: prove table merging on-chain, for historic tables bigger than 256 blocks. The operation itself is super simple, just verify the merging of ordered lists and re-hash both the input and output tables. Then the historic index contract would verify the proof proving for example that four consecutive 256 block tables with given roots merge into a 1024 block table with this and this root, and create an entry for the 1024 block table. And then continue this process with even bigger tables. For a table merge proof covering millions of blocks, this would probably require a recursive proof. Are you (or someone else here) maybe interested on working on this? This is a problem where I don’t really have the required expertise yet so attacking it alone would probably just take up too much of my time while I also have to push the EIP and work on specs and stuff.
Hi @zsfelfoldi we’d be happy to work on this. And we already went ahead and produced a first merge proof today.
We took four consecutive 256-block tables from mainnet, covering blocks 25,845,760–25,846,783, and proved their merge into a single 1,024-block table.
In SP1, wrapped in Groth16, it took 107 minutes on one L40S and roughly $2 of GPU time at the rate we paid. The proof’s public values carry the four child roots and the parent root, and all five match what your core/logindex implementation computes for the same tables, so the encoding, ordering, and SSZ roots are byte-compatible.
About 83% of the proving work is just SHA-256 re-hashing of the input and output tables; the merge itself is relatively cheap.
Next we can work on the recursive version for larger tables, along with a history index contract that binds the child roots and exposes the same get interface as the system contract.
Agreed as well on pre-fork history. A hardcoded root independently reproduced by multiple implementations seems like a perfectly reasonable starting point, and I agree EIP-8304 shouldn’t depend on solving the full EIP-7708 re-execution first.
We’re also interested in the log-index proof format you linked. Proving verification of those lookup proofs seems like a natural next step once the merge path is further along.
One tiny thing we noticed while building against your branch: core/logindex/table_rw_test.go imports fmt without using it, so go test ./core/logindex currently fails to compile.
We’ll keep building against your eip-8304 branch and post the code and measurements as the recursive merge comes together. I’ll also send you an email now too in case having mine is helpful for further coordination.