Trustless Log Indexing & Scalable Ethereum Storage

Transcript

Introduction: Trustless Log Index overview

I what I would like to talk about is uh so this has been my main project uh since uh quite a while now and uh it's called the trustless log index and it started out as a as a rather complex EIP that intended to make uh uh log events uh uh searchable and not just searchable locally but also like like provable to uh light clients. I also this is like um I'm um uh designing this new uh trustless execution API and this this uh uh I I I really wanted to make all the parts of Ethereum provable that are

currently not efficiently provable and uh like logs are the uh most problematic in this in this sense. So uh yeah but uh later I I I figured out that uh uh this uh this thing can be uh also uh relevant to like uh scaling like uh it could fit into like our current uh fiveyear plans of of of of scaling and uh well here uh what I have is uh a comparison between logs and state and uh yeah so logs and state are used being used uh in a different way now But uh so like state is visible through EVM and logs are just the output

Why logs are currently inefficient & unprovable

effectarium. But here uh I I'm just comparing them uh like uh in terms of of properties as data data structures and uh yeah so uh because uh I I now I think that uh logs can also or this data structure that now we call logs could also be very uh useful for for contract storage in the future. And um yeah so so um obviously these are uh like fundamentally different because state is a key value storage that's mutable changes all the time and the state tree is huge and uh yeah so this is this is kind of a a potential uh difficulty I'm not saying unsolvable but yeah it's a

difficult thing that state is already like several hundred gigabytes large and if we are talking about 10x 100x thousandx scaling, then it could grow even more. And it's nice that uh uh we can probably do uh statelessness with witnesses, but still uh some someone has to has to has to have the entire state and update it. And this is like a huge data set, very hard to sync, not not just because it's huge, but also because it's constantly changing. And if only a few uh big uh data centers can hold Ethereum state, that's an infrastructure capture risk. So um yeah uh and now uh but on the other hand, so logs uh the

State vs logs: structural comparison

way they are currently represented is that that's this is basically just a linear database uh very cheap to add new entries but uh extremely expensive to to uh to uh find or even or especially prove anything remotely. So basically you have to uh uh like iterate through most of the receipts. It has an on cost compared to all Oan of uh of the state tree. But uh uh yeah so with with this this trustless log index I would like to uh show soon u uh the read the the the read costs and and the and the trustless proof costs of of of a certain item are roughly log squared. So it's like a little bit more

expensive but writing adding items is uh well it's hard to exactly tell uh with this ip I have now uh it the protocol processes a limited number of uh blocks in the in the protocol and the the cost is I could say also login but uh it's mostly processed asynchronously and in memory and uh my initial estimates are it's about 50 times faster than the eight. So uh uh maybe this could be useful for scaling and um okay so uh what uh the basic uh uh key element of this trustless log index is

Infrastructure capture risk from state growth

called index tables and I will have some nice uh uh figures in the next slides uh showing uh how it works but uh just a quick overview so it's uh each index table uh uh contains events from a from a specific block range. So a number of fix some number of blocks and it has index entries which are searchable things. So it it makes block hashes and transaction hashes and log addresses and log topics searchable and uh yeah it's it's it's it's basically just a mer tree and uh and and these these uh these index entries are uh sorted in a certain way that I will show soon and u and

Index tables explained (block-range tables)

since uh uh an index table can be generated from one block and then um then multiple index tables can be merged together to bigger tables and and bigger tables allow more efficient proofs. So yeah, this is this is a very simple example uh where we have four blocks and very few u uh entries in them. Uh and on the right here is how these entries are represented. So each of them has a position like block number, transaction and log position and it has a type. Uh it can be like block hash, transaction hash, log address or one of the four log topics. And it has this the value and u the way the table is generated is uh

it's uh sorted first by uh event type and value and then uh by position and it's uh u hashed into a binary tree. Right now I'm using the SS list format but yeah so um and um yeah here this just details of how it's represented. not very important but the point is that uh uh an index table contains all all these events uh that happened in a number of blocks and uh it is uh easy to search and easy to prove the results of certain uh lookups and I will also show that how and since each table is generated for uh

Merging single-block tables into larger tables

uh for like like okay so here it how it works so uh we I have like index tables of single blocks and and this is this is how how uh four four single block tables are merged into a bigger table and then then they are merged into bigger tables and bigger tables and um and uh uh only the the single block table is uh generated during block block processing. The others are uh generated or merged asynchronously. So this allows uh quite a high performance of generating this index and uh uh in the in the protocol there

Why only small tables live in-protocol

are only four levels of tables one for 16 and uh uh 64 block tables uh and I will also tell why that is and the bigger tables that allow even more efficient search can be generated and can be proven with zk proofs. So uh there's a yeah I will get also to that soon why I'm proposing it like this but first let me just show how this thing really works and how it is suitable for for proving anything interesting. This is a simple simplest case which is uh which is an exclusion proof uh an exclusion proof of a transaction hash

that does not exist at least not in these four blocks. And um and the way it works is so uh we are uh we know the event type which is transaction hash and some some index value which is which is the actually actual hash and we can look up in the table where this uh entry would be and it would be between these two uh red lines and it doesn't exist. So uh so the local representation where the pro how the prover locally represents this table is some kind of a search tree. So it can be efficiently looked up and if the entry exists then the result is yeah that entry and if it doesn't exist then uh the two adjacent

Exclusion proof example

entries and since it's a it's a sorted list uh creating a merkel multiproof that proves these two uh leaves of the tree uh uh this this proves that u that this entry does not exist in this table and um yeah so so so the so in the simplest case But this is quite a typical case. An exclusion the cost of an exclusion proof is logarithmic in the size of the table and the number of entries in the table more exactly. And here's also uh a little bit more interesting example which is uh which is a log pattern search.

And um uh yeah I will also like get to the more interesting things soon but uh yeah let's just get through this details. So yeah this this this this pattern search is is is the typical way it works is it we are looking for a certain address a certain topic zero a certain topic one and and the wild catch for topic two. So in this case like uh this is a a uh ERC20 transfer so of of a USDT token from Bob to anyone and uh uh the way we can prove the results of this search uh is that uh well uh here the prover might apply certain heristics to optimize the

Log pattern search example (ERC20 transfer)

search performance because such a proof can be constructed in multiple ways but in this case an efficient way is to prove like uh the least uh popular uh entry or or uh item in this this pattern which is the sender Bob. So topic one equals Bob is what we are looking for and we have two two occurrences here. So there are this this uh four red entries in the bottom and these are two actual matches and and just like with the ex exclusion proofs two extra entries two extra adjacent entries pro proving that these are all the uh cases where topic one equals Bob and we have already

narrowed down our possible result set to two entries and uh actually this table does not necessarily prove everything uh about the actual results. because the actual results will be proven through the receipts. So the actual inclusion proof is is simple and that's uh possible even now. But uh the interesting thing is that uh these index tables can prove that this is uh the complete result set. So like this is the actual result block 42 transaction 0 log one and what we really need to prove is that the other match potential match where uh topic one equals Bob is transaction one log zero. But then we can also prove in this this single red

line that uh that in this particular log the topic zero is is not uh uh transfer but withdrawal. So it's like a different uh different uh uh thing and this is not a potential match. So with these five entries five proven uh entries of the table we have proven that uh block 41 transaction zero log one is the only possible uh match and the actual in for the actual inclusion proof like so for proving the uh actual match from the from the receipts we also prove the block hash of block 42. So from the block hash you can prove the receipts and from the receipts you can prove the log. So yeah this is how it works and

Proving completeness of search results

this was like mostly the boring part and yeah this is uh all all this problem is uh I would say it was like a attack that from since the beginning because yeah we had the the for for for uh searching logs we had the bloom filters which became practically useless in basically after two or three years of Ethereum's operation. So yeah uh since then uh actual trustless proofs of loqueries was an unsolved problem and uh with this uh with this trustless log index project they become provable but there's like a another uh interesting aspect of this thing

Bloom filters & historical limitations

um yeah but first so now I'm going to talk about zika proofs and from this uh uh we get to the more interesting part but uh yeah First, let's just talk about why I want to uh prove uh smaller tables in the protocol and larger tables with ZK proofs and why not prove everything with ZK proof. So, that's a tempting uh option because then we don't have to have an EIP and push it through the EIP process and everything. But the thing is that uh uh for for uh for lo searches the most interesting at least usually the the head head blocks and the recent blocks are are the

mo more most interesting ones. And uh even if we assume that someone is willing to generate a zk proof of of of the long index tables like every 10 minutes or so or every hour still uh uh for the rest for the unindexed most recent history we only have uh uh the unindexed search which is extremely expensive because we need basically all the receipts or most of them. So yeah uh this is this is why I think the smaller tables should be in the protocol and uh larger tables should not be in the protocol because then we would place a burden on every Ethereum node to uh process uh several gigabytes of of of

Why ZK proofs alone aren’t enough

index tables and we just don't want that. So uh if I just circle back a little bit here uh like uh the tables are generated with a little bit of delay which is so like for us for for the 64 block tables we have a we have a 16 block uh asynchronous delay to generate the tables. So in the end uh at most the nodes will need at most uh 80 blocks of history to properly generate the the the consensus part the the in protocol part of the of this index.

State tree vs immutable index tables

And now uh yeah, so this this drawing shows like like again the difference between the the state tree and and these index tables and uh and and and it's this this comparison that so like the for the state this these states are like these are these two rectangles because they are huge and uh and there's a version of the state for every single block and and and the state is already like half a terabyte or something like that. Uh but yeah, it's probably going to get even bigger and um and yeah, so so uh having having having having uh the entire Ethereum state in a single tree

does have it its advantage because it's the smallest possible witness size. It's a log n in the number of of of state entries. But uh otherwise the index tables have most of the other advantages. they are much cheaper to append because u uh during block block processing you you really just need to collect the events of the currently process block and sort them and that's very cheap and and most of the processing is is is uh offchain or asynchronous and uh yeah so and and also uh a very very important thing is that uh uh with this uh with this data structure most of the history is stored in uh in uh tables that are immutable able. So once they are

Advantages of immutable distributed storage

finalized, they will never ever change. And uh and even if they are big, they are much easier to distribute. And uh if we it's it's it's not it's it's not only uh available for like like bigger and bigger uh data centers, but uh they can be stored in a distributed way even single tables can be distributed because they are three hashged and everything. So uh I think I think uh this over the long term if we really scale Ethereum like thousandx 10,000x then uh this is huge advantage and and and and we are taking a lot lot smaller or or we are avoiding a big risk. Let's just phrase it this way. we

are avoiding a huge risk uh uh with this data structure uh and um also also with the state uh uh the the the growing state size and uh and and and state expiry and resurrection. Yeah, there's been lots of research about this and lots of great ideas, but uh I think we can all agree that it's hard uh it uh it looks like it cannot be uh done in a really backwards compatible way. So in any case we are going to need some kind of uh some kind of let me just check my time. Yeah. Uh so we are going to need some kind of u uh optin new architectures that uh uh contracts can

State expiry challenges

or or contract developers can start using know in order to be able to really scale. So probably legacy state will become more expensive. There's already at the state or uh gas repricing talks it we are we are already talking about yeah we we have to repric everything that then that but then state rights will be uh more and more expensive and then yeah it's just uh so so I think I think I think an alternative will be more and more uh useful over time and now uh okay so this is a big step but now I'm going to

ZK future & transaction pre-authorization

talk about why I think that the the ZK proof the ZK future will uh make this data structure uh suitable for uh for even contract storage. But uh so this is this is this is one way of actually the way I currently imagine how this I mean transactions and uh wheel will reach the chain in the future. uh Vitalik was already published this new EIP, new account abstraction EIP and uh in this EIP it's also mentioned that uh transaction pre-checks authorization witness verification they can be uh processed offchain. So it's possible to

take a transaction and have some separate witness part and also I could have added authorization and uh and this something like this I'm not sure exactly this uh topology but something like this will be necessary probably for postquantum signatures because they are bigger and and also they can be so they they can be uh verified offchain and and and uh pre-authorized pre-verified transaction batches can uh go to uh block builder But uh if this is the case uh then um then uh uh a little bit bigger weaknesses are not uh are are uh probably okay to deal with. So yeah I

will just circle back here. So we had this this one advantage of the state tree that it uh can uh work with smaller witnesses but uh but maybe maybe witness size will not be an issue at all if uh if these witnesses do not need to be uh like broadcast throughout the entire network but uh only uh processed by a few provers. So yeah uh and uh and uh here's another topology the way I imagine how this whole thing could work uh if we use the logs and log index tables uh for uh contract storage and uh yeah so it's it's not as complicated as it looks yeah

Off-chain witness verification topology

it's it's more mostly just that from the EVM uh the main output is logs uh in this case probably we would also have to uh put uh a a recent log uh search in the EVM. So yeah uh so the so the contracts could uh see the most a few most recent blocks uh uh or the logs emitted in the few most recent blocks and the rest could be proven with witnesses. So yeah the this this is we generate the uh small index tables and then the small index tables are being merged with zk proofs into bigger tables and bigger tables and uh and from the tables uh uh the witnesses would be uh put into like the transactions looking

Using logs as contract storage

into uh chain history and and again these witnesses would go into the private inputs of of zikk proofs so they would not uh burden the chain and also the the proofs of the the the table merges themselves could also be recurs recursively uh proven in the in the blocks. So like uh every new uh merge table could be could be like uh signal with a new log entry in the chain. So yeah uh and uh and uh yeah this is this is this is this is just to summarize uh why I'm saying that uh this is all relevant for

Recursive ZK proofs for table merges

for like like uh maintaining the core values of Ethereum and avoiding like uh uh infrastructure capture risk and and and and centralization. So yeah uh I think I think uh that trustless operation of of everything we have is that goes without saying we also need healthy incentives and that's a non-trivial part. So if we imagine uh uh like provers uh actively part participating in the chain generation process then yeah we have to have some kind of incentive systems but I think in case of transaction pre-authorizations this is not very hard uh it's also not something already figured out but um

yeah uh I just go back here and say that yeah so like one user sends a transaction And then it might go go through a few layers of of of batching and and all these provers could somehow be paid with a conditional payment and probably also in order to encourage uh like some redundancy and ensure censorship resistance. We should also have some kind of a dduplication enshrined in the protocol and also uh so and also make sure that uh that uh transactions proven in two batches do not pay the chain cost twice. So or or the onchain cost twice. So yeah, this is

Incentive design for provers

this is something that still needs to be figured out. But the my main point is that uh that uh we can ensure low entry barriers uh at uh all fronts. So we have the provers we need we have witness providers and we have blog builders alms or sequencers whatever and um and and uh so either I I mean I if if if we if we if we require super nodes for any of these purposes that's either a bottleneck or or if we allow like uh very big uh data centers to fill that role then it will be a risk because then we we will see that okay we can scale

Avoiding data center centralization

and we can scale higher and higher but all this requires bigger and bigger data centers and that's not what we uh wanted in the beginning at least and I still think this is not the path we should take if there's another one and I think there is so yeah uh uh so the for for for for proving the uh transaction witness checks and pre-authorizations we don't need like huge provers because smaller approvers can create smaller batches and they can be rec recursively uh batched into bigger batches and also the these index table merged proofs uh can be designed. I already working on this. So yeah, this can be these proofs

Execution sharding & cross-chain proofs

can also be designed in a way that even the biggest tables can be proven with with recursive proofs and even like they can that that can be like a collective effort of many provers to prove a very big table and also uh for the witness providers uh for for the if if we use these im immutable tables then it's a much much easier problem and it's it's much easier to always ensure that this data is available and accessible. And uh and uh also uh well for for the for the sequencers or or block builders uh we we should eventually have some kind of

execution sharding which will need crosschain communications and uh and this data structure this this trustless log index structure is I think ideal for this ideal for uh for proving uh uh events. So this is this is basically a message based architecture and if uh there's going to be contracts using uh using logs for their internal logic then I believe it's going to be even more even simpler for them to go like multi-chain because uh it's uh they could look into the re events of of of of other chains almost the same way as

Message-based architecture via logs

looking into their own chain. It's just there's a bit more delay because because yeah the finalization and everything. So uh yeah that's pretty much it. And uh and uh here's uh here's my uh GitHub repo of the project. And uh so currently uh there's there's an old EIP. It's called E EIP7745 which was a very big EIP and that it has been DFI for glamsterdam because yeah I also have to admit it's quite complex but there's in this repo you will find uh a much simpler proposal so this this what I just presented is this is the new design and and u uh so I I I believe this is realistically doable in the near

New simplified proposal vs old EIP-7745

future and this is a path uh where we can uh start working on without making any big decisions without like making big commitments. So this is this is something that I think should happen anyway and uh and we will see if uh if it could be meaningfully also used for contract logic and whether it could make uh things more efficient. But yeah, I'm pretty sure it would. So yeah, that's it. Thank you.