Trustless Log Index Breakout #1

Transcript

Hello. Hello, guys. Can you hear me? >> Yeah, we can hear you. >> All right. Yeah, it's 3 now. So yeah, I did not expect this to be a very crowded call, but yeah, it's fine. So all right. >> Uh will we wait or let's start like what do you say? >> Uh sorry. >> Uh will we wait for some more time for people to join? I guess so.

>> No, I mean uh it's it's three we can uh start. Yeah. So, so I I I I think it might be just us. Uh so, yeah, right now not a lot of people are uh working on this, but uh but yeah, uh we'll see. So, I do I I honestly had no idea how many people to expect, but I think we can start and yeah, people can join in. And also uh yeah I think I think let's just uh start with like uh yeah I already know

you are uh have familiar you are familiar with with with with the original EIP and yeah Mario is also here. Hello. And I'm honestly not sure uh how uh how familiar you are with it and uh what so yeah let's just start with who's do who who who who yeah who's where with this thing and yeah just a quick intro round. >> Sure then I'll go first. Uh I'm quite familiar with the EIP. uh I haven't looked into the newer gist that you have sent but I am pretty familiar with the original EIP I have been implementing it

in the in pockets of time for numbers uh yeah because from where I stand and like even this is also Ethan's view um we would both of us would like to have the normal let's say progressive list along with the normal binary SSD binary trees inside you can have more of normal spec like normal things which are already there instead of having the binary trees and stuff and also the proof format. Also another point of contention that has come up is when Ethan was running his um Raspberry Pi nodes with the log index apparently it

shows up it takes around 1.7 to 1.8 20 seconds to uh compute that is uh update the log filter. So the question would be uh is that time going to hurt us or anything like that. So that is a point of contention or does it need the delayed execution treatment maybe or also let's say when we are doing the hash computations so how does the time come up over there and stuff like that. Yeah. Okay. Yeah. Uh yeah, by the way, yeah, welcome Lucash. I'm glad you could also join. So yeah, um uh I will try to like quickly address

this. So uh yeah, uh the that's that's also something I didn't know what to really expect before I implemented it. So uh I I I do have uh like a kind of efficient implementation of the original EIP in go and uh what I can say is so yeah by the time I got there I I I also now I also so that there was a reason I started with this alternative proposal also because because yeah I mean I mean the complexities with this this this this is this tricky hashing scheme and all this

little progressive lists and everything. So yeah, it does blow up a bit and and I managed to implement it in a way that uh so like like like processing an average amount of uh logs per block uh takes like I don't know five to 10 milliseconds to rehash on a single thread and most of it can be parallelized. So I think this theoretically it would be possible to bring down the delays. So yeah, obviously delaying block uh every so like like like delaying uh the finalizing of or sealing of blocks by 10 milliseconds that's probably too much

but uh uh with with with with running so so when when when each uh log event is emitted uh we could already start processing or rehashing that those those branches of the tree and and it uh so so the overall delay could be minimized. But yeah, this this this is a this is a complex thing. So uh so I think this is where the the the new proposal uh is is is a lot better. So like I mean I mean I mean um there's there's there's a significant amount of um overlap. Uh yeah, welcome Alexi. So yeah um

so this the so the thing is that that a lot of the complexity is uh about uh like uh building building any kind of log index and and and assigning this this linear index space and and generating the proofs and how how do we uh I mean I mean how how how do the the logic of of of proof generation of verification and all of this. There's a lot of similarities with new proposal, but it's it's a lot simpler because it's it's not probabilistic and uh and and there are no false positives and yeah, so uh I I I I have not abandoned completely

the original uh idea yet. But yeah, I mean uh so far it's been only me who kind of implemented it in a kind of efficient way and even I say yeah by the time I got there it's it's it's it's like it would be a lot of work to make it like production ready. So uh so the the new proposal I'm I I don't think I should uh like Yeah. Yeah. Lucash. >> Yeah. So uh can we step back a bit? Uh because I this is the first time I I heard that there is a simplified proposal. So I'm a bit um like not not not in the don't have the full context.

So um so the original proposal I think it's pretty complex, right? I Yes. >> How long did are you working on it? Let's say probably already more than a year or something, right? >> Yeah. So uh so when I first uh like wrote down the idea that was uh like a year and a half ago but uh the actual uh so so yeah there there were like mostly two stages because first I implemented it in a non-conensus way I just implemented this data structure in g as a search mechanism and >> actually that wasn't super complex. So that's where I got my confidence to say that yeah it's not going to be complex

too complex if we just rehash it. Uh and yeah there's significant difficulties there but uh but so so the original thing I implemented in a few months and it was I think it's still in gs in g and the log search is is is I mean I mean for most cases very efficient but yeah that's a different story. So it's it's obviously easier to just do it offline but yeah uh with these with the with the tree hashing actually so the so generating these this log index root hashes this is something I started actively working on uh well I I did have some some some simple version

uh during the summer which was like not efficient at all and it was just a proof of concept but the but the actual close to production ready efficient tree hasher and efficient database rep representation. I started to do that uh in uh like early November I think and uh and and and after two months I I I now I'm I I just so what I realized this so one of the uh advantages of the original proposal was that uh this this this minimal state of the log index so that shouldn't be like excess excessively big so that's one of the points that it's not like the state it shouldn't be like the state And yeah

in a compact representation the state of the log index is 20 something megabytes with those parameters that I proposed and yeah I think those are reasonable parameters but uh when I worked out >> but that's only for the part of only latest locks right >> yeah so the thing is that this this this this so the original data structure uh yeah it basically can be imagined as uh 64,000 simultaneous uh trees being grown incrementally. So like um uh so one epoch that there's this this this this ep it's organized in epochs and uh one filter map is 64,000 rows and uh and

it's organized that so in a way that uh that that the same row index for for consecutive maps uh goes into like one like compact tree uh in the epoch. So it's it's like it's so it's it's a for for for for growing this this data structure, you always have to have a 10 hash long Merkel pass per filter row. So like 640,000 or 50 something thousand hashes. So that's basically the long index state and that's so that's that's uh the minimum amount of data needed to grow

the index. Obviously, you can also back fill and and back index, but that's not critical for consensus. So, yeah, this was a big idea. This this is why I thought that this is worth it. And yeah, it's it's a nice property, but uh now I uh I I ran the numbers with a significantly simpler structure and I think it might be feasible and uh yeah, so uh I think it's it's pretty recent. So I published it a week ago and so I don't expect anyone to be familiar with it. I'm just mentioning. So probably this should be like a next item. We should do that.

>> Can I add more questions? Ask more questions. Okay. Uh so now you're using this in GF uh for the whole history of receipts potentially, right? >> Yes. >> And it takes how many gigabytes? >> Okay. So the so this this this the filter map structure which is the original EIP that's >> what I'm using now and so what what is in what is what is on on on published I mean release master branch that doesn't have the three hash yet so it's just the filter maps and the filter maps take around 60 something or 70 GB >> so they

>> for for the receipts okay so they are quite big >> well the receipts are five 600 gigabytes. >> So 10%. >> So it's like like uh like uh >> 10%. >> 10 15% of the receipts. >> So yeah, I mean I mean I mean it's it's not prohibitive. >> It's also not negligible. But yeah. >> Mhm. And this so actually this is kind of what I think is uh re reasonable to expect from from an acceleration structure that restructures all the data but tries to not to replicate all the data. So, so the so the way it works and the new proposal

also shares this property that it uh can be represented just with the with the position indexes and the logs themselves don't have to be stored in the uh accelerated structure but yeah uh I think I think this can be acceptable so this this is not the blocking point it's >> Mhm. Okay. Okay. Let me let me ask more questions. Okay. And does the new structure compromise on on speed in any way compared to the old structure?

>> No, actually it mostly has advantages. So it can be simpler and faster. There's the only thing that uh where it's it's let's just say worse is the minimal amount of data required to just calculate the consensus hashes. Mhm. >> That's that's an important number and uh I think if we aim for a similar or slightly better performance than the original 7745 design then the minimal uh log index state is something like 2 GB with the new proposal which >> okay but what what kind of state does it

hold? >> Yeah. So the so okay let me just very just just give an idea rough idea of how it works. So because it's it's quite simple. So basically it uh it it generates uh lists of uh I call it index references which is basically the log value hash and and and the the the the position on this linear index space. So uh it's so the the mapping this this linear uh value mapping is the same. So I assign an individual index to uh each address and each topic and also these additional additional transaction and

block delimiters. So like each of them has one lookup value one one searchable value and and one position in this linear space. and uh and I create sorted lists that uh are prim first sorted by by content by by search value and then by uh the actual position where the original log is located and and the way it's so I mean I mean the structure generate is super simple the only hard part is how to generate them and the way I'm doing it is uh basically a mer way of merge sorting them so let me just um actually.

>> Okay, I'm I'm still not sure if I understood how it worked, but okay. >> Okay, let me just Okay, I do have a pretty nice drawing. So, let me just I will try to share this here. Um well, okay. Yeah, I do have this gist document. I will share it. That's the easiest thing probably. Okay. So I will just here in the chat I will share this link and uh yeah also uh oh stupid laptop sorry.

Anyways, um I will also just paste the actual drawing here. Yeah. >> Yeah. I saw I saw this drawing, but it doesn't explain much for me. >> Okay. Okay. Let me just give the >> Okay. I I get I get that those are layers in some way but um I would like to understand like the the details of the index. Okay. The index entry types corresponding index values. Okay. So block transaction.

Okay. And how does it work further? >> So yeah. So so so this this horizontal dimension is is is this. So, so let's just say we generate these these uh these uh searchable uh log values assigned to >> Okay, what does that mean? What does that mean? >> So, so what it means is that uh okay, let's let's start it there. >> Yeah, let's start at the beginning maybe, right? Let's go through. >> Yeah, it's it's the core concept and it's so this is kind of the simpler part. But yeah um so uh so the way it works this thing works is that every time uh we uh add add let's let's just say the simplest

use case we add a log it has like an address and I don't know how many let's say three topics so uh so and there's this this global global uh pointer global index pointer that just keeps growing and every time uh so so we assign a new new uh position in the index for the address and the new position for topic one and new position for topic two and new position for topic three. So basically this this a log three op three operation will occupy uh four uh spaces in the linear index space.

>> Okay question mark already already a few question marks. Um, does the same topic reuse the same numbers and same addresses reuse the same >> uh by numbers? >> Okay, we have uh two two logs they have the same address. >> The same address correspond the same numbers. I I don't get it. I'm not sure if I get it. >> Okay. Uh so uh so uh there's there's this uh this uh index entries tree where we we we we reference all this this this uh uh events and uh each new event. So each new event will have a new position.

So in this linear space linear index space we assign uh incrementing in incrementing positions to every new event even if it's the exact same uh uh address and topic and everything. So like it's two searchable events if it happens then it's two events. Yeah. Uh, it's just so there's there there's position and there's content and there's there's one tree that stores the content or references the content by position and there are these uh sorted lists that uh help the lookup by value.

So it you can find the the position based on value. So that's that that that's >> the important thing and so so so pretty much what I do is uh is is is uh is I take uh this this short so so in this drawing on the lowest layer there are this small rectangles which is each of them is 124 uh uh positions in this this uh uh linear index space and these lists are sorted. So, and the once we have a list of the references, the value position pairs sorted by value first and position

second. >> Uh, and we have three hash them in a simple binary tree. So, it's it's it's it's a power of two length section and it's it's can be hashed into a perfect binary tree. And uh once we have this it's uh it's it's easy easy to generate uh inclusion and exclusion proofs and everything and and and yeah it's just uh uh that if we have all these little little sorted lists and we have to prove like the all the occurrences of a value uh in a longer section then you have to do one miracle proof per uh

small list. So it's still kind of expensive. So if we can generate longer longer sorted lists then the proofs will be more efficient but also we can't just instantly generate uh very long sorted lists in consensus because yeah I mean we can't expect the clients to just uh suddenly sort 16 million index references after finishing a block or something. Yeah. Okay. Sorry. Sorry. Uh you're going too fast to to the proving part. I want to understand more about the like position part like step by step slower a bit so we are on the same page.

Okay. So basically okay you have entry positions value positions whatever that means. So for each thing for block for transaction and each log and each address occurrence gets its own number basically index. >> Yeah. So let me just quickly explain this this this basic concepts. So uh so this this the the entry position and the value position because they are almost the same but still the importance is interesting. Uh so uh there are uh so the there are three things that we index. There are transactions uh block boundaries and then and actual log events and the transactions and block

boundaries they get one searchable value. So transactions are searchable but transaction hash blocks are searchable by block hash and they all get one search. So they they they get one searchable entry and in this case the the value position and the entry position are the same because each entry gets one searchable index value >> and in case of the logs which where where uh like a log log log three operation generates four values and it's searchable by address for each of the topics. So then the entry so it then it has four consecutive value positions >> and the entry position equals the first

value position. >> Okay, got it. >> Just just just I just wanted to make the terminology clear which Yeah, maybe >> two questions. What happens on reors? >> What happens >> on reorgarchs? >> Reorgs Yeah. uh with this new structure it's pretty actually much easier to reorg with the old proposal it was that was a weak point that you had to somehow regenerate the past states of the tree and everything with this sorted lists it's it's it's pretty easy to just remove uh a number of uh items from the index it I mean it is uh explained in this write up what you exactly need to

do but uh so the so the so the whole point is that uh we have the little sorted lists and then we we we merge sort them into higher sorted lists and everything and all these operations can be done in reverse. So you can just remove uh I don't know a few thousand entries from from from this index. Uh and even if you have already merged some of the small lower layer list to bigger ones, you can unmerge them because they are uh value position pairs and uh and and yeah, you can you can >> but basically basically my my answer was on the reorgs we are we are kind of

reverting this index. We are removing items from this index. Okay. >> Yes. But with this new proposal, it's it's it's possible to uh do all operations in reverse. Yes. >> Okay. Because the I had two two possible answers. We do nothing and we keep growing the index and we just want to use some values or we can remove the values from the index like from this uh from this consecutive counting index right whatever from this numbers. So that was >> Yeah. Yeah. So I mean I mean I mean the consensus rules uh for are for for adding stuff but obviously we have to just just somehow reconstruct an earlier >> uh yeah yeah but I I just want to okay how how do we search for stuff because

okay now we have this sorted lists of things which are basically numbers and those numbers uh do we have an index that kind of maps those numbers back to addresses and locks or what? I not not sure. >> Well, yeah. So, so, so this the the uh well well there there's there's one thing is how the data structures are hashed. So that's important for the proofs but obviously you have to locally you also have to represent them in an efficient way. Luckily that's not very different but yeah so the thing is that uh there is the there is the index entries tree which is position to entry

mapping. So yeah there's two-way mapping but uh probably locally if you already have the receipts then you don't want to uh store this index entries tree again because it's the same thing organized a bit differently. So it has all the logs of and of and all the transaction hashes and logs. So basically the same information that's in the receipts. So uh it is probably more efficient to just uh have some pointers to okay at this position this is this is this is so so uh the way I'm already doing it is I have this twoway indexing between block numbers and this this uh linear index

positions because yeah that's the somehow you have to make sense of all this data >> and Um and and the other way is like the how do you search is well once you have like this this this sorted lists uh you locally uh so this is this is this is quite new and I haven't implemented the search yet but um but but I mean it's pretty straightforward because you can store it locally in a way that probably not as a binary tree but I mean in two or three layers you can have like this this this this this intermediate index

chunks like probably for database efficiency it makes sense to store all these this this these pointers in bigger chunks and also have like this this lower level chunks and that that basically constitute a search tree. So uh so in each in in the in the local representation of the the sorted lists you just take a root chunk and see what higher layer chunks might have the item you you are looking for. And so it's it's basically so you don't actually have to do a binary search. It's going to be more efficient than that.

But uh but yeah you you >> okay but how do you search? Okay, I get I'm searching for logs with this address. And how how do I search that? I uh I can translate the address back to the number, right? Or or to many numbers? I don't get it. Okay. >> Okay. So, so so the so so you take the address you are looking for and and the list is s sorted. So the address is searchable by you. Actually, uh I do. >> I don't get it. How? Where's I give connect me the dots for me. I don't get it.

>> Okay. So, in this new document, it's called it the things that the things that are sorted are called the index references. And the index reference is a is basically uh uh a 26 by hash. That's the searchable value and six bytes local position. Don't ask for the reasons for the exact numbers but yeah uh those are just based on some estimates but anyway so the thing is that there there there is a searchable content hash and there is a number and once we you have a sorted list you can just uh well the I mean I mean in a sorted list you can you can you can

always find any entry in a logarithmic time uh like the search the easiest way to imagine is it is a binary research, you can be way more efficient than that in an actual uh implementation. But uh yeah, if if if if you if you build build like a tree of uh chunks, yeah, probably I will I will also have to do a draw drawing about this later. So it's yeah, it's good to have this feedback of what what is hard to imagine. But anyway, so thing is that uh if you if you if you uh build a tree where so you you let's just say you have you have you have you have a a

higher like like top level sorted list which is 16 million. Yeah, I think with with this design is 16 million index references are hashedged into a tree and and and the and and in the database you just have to most store the positions sorted uh by by by content and uh and you can have these this this will probably be represented in the database in a in in larger chunks and and also uh on a lower level you can have a an intermediate level chunk that only contains let's say the the first uh uh

value hash the search first the first searchable value hash per chunk on the upper levels. So basically you have you have a tree of of of searchable chunks and you take the root chunk and you just do a binary search in memory to just see okay I'm looking for this value this address value and it's uh between I don't know index 105 and 106. So, let's just look up uh the and the the the chunk above it that might contain that entry. So, I mean I mean I mean it's it's it's I

think it's it's I I Yeah, it's hard to just >> Yeah, I think you need to actually work on how to you want to explain it and try to explain it like step by step really slower with more better examples because I'm still >> Yeah, I I think I >> I still don't understand what how it works. Sorry. I still Yeah, but I'm at square. We are here for half an hour and I'm still a square one. >> All right. Yeah. So So that's probably one of the >> And maybe maybe uh maybe other people understood more, but uh I I still it's hard for me to even uh assess your your design because I still don't understand it. You know what I mean?

>> I see. Uh yeah. So probably those who Yeah. Yeah, I mean I mean with the with this new design it's it's it's pretty new so probably no not a lot of people understand it besides me but uh with the earlier one also those who understood it probably spent a lot of time with it. So yeah it's it's uh but I think I think uh with with uh with with with nice drawing it will be really easy to to uh understand because it's it's still just I mean I'm in an sorted tree. It's pretty easy to look up a value. I mean it should be shouldn't be very hard but u but yeah anyway so so so if you have you have you have you have you have sorted

lists uh organized in a tree structure then it it it takes a logarithmic time to do a way you look up that's that's that's yeah >> yes well that that's that's fine that's that's easy but how do I translate the values I'm searching to the part of the trees that I want to search for example. Okay. >> Because basic >> Yeah. So the thing is Okay. So So uh maybe Okay. Maybe I get your question.

So yeah. Yeah. It's it's Yeah. hard. It's hard when I I already have it figured out in my head. But yeah. So thing is that uh that uh you will represent it uh locally in a way uh that that aids the search in the tree. So you you will have have like like like like a high level list and and and a lower level list that will tell you which chunk to look up in the higher level and and and and and so on and and and do this this uh [clears throat] so the prover will will have an efficient way of looking up the the actual uh position based on like the the search address

value and it can just uh prove like like create a miracle proof of the the entries in the sorted list before the searched address and after the searched address. So let's just say if the address is not in the list then you will have you can have an exclusion proof by proving the the last address uh the last index value that is smaller than what you are looking for and the first index value that is larger than you what you are looking for and you you prove two adjacent leaves in the in this tree and that's an exclusion proof. And

if there are actual occurrences so like this this this address does exist in the sorted list then still then yeah you will also have to prove the last uh smaller uh index value the actual occurrences and the first larger one and this will and we know that the list is sorted. So this is a proof of of of of all the occurrences of a certain index value in the list. But yeah uh >> okay maybe other people have questions and things to discuss first.

>> Yeah. Yeah. But I will draw this. Yeah. So now now >> if no I can hijack the rest of this meeting but maybe let's let's let's give other people some >> No. This is this is this is very good feedback. But yeah let's hang in. Uh does anyone have other questions or should I hijack it completely? >> You can hijack some more >> I think. I think yeah. >> Okay. Let's not focus let's not focus on the proofs yet. The proving part is icing on the cake. I want to understand how this is built and how it serves the current ETH get locks. Okay, let's just

focus on the current functionality of logs and we can talk about Okay, I can can I share screen? >> Yeah, you can. >> Okay, I'm sharing just simple notepad. This is what's uh I copied from from your uh from your doc. >> Yes. And uh potentially there are multiple layers but we are just starting out so we have probably only one layer because we are only at index 25 right >> um >> up to 25.

>> Yeah. Yeah. Yeah. Okay. Okay. In this case yeah it's just just >> so basically we have a a list of numbers from 1 to 25. That's our index. I don't get it. Blah blah blah. Right. Up to 25. That that's is that correct? I I don't get it. What's what's what's the numbers are here? >> So we we mapped the block to entry zero. We mapped transactions to entry one. Transaction one. Log one to entry two. Uh log one 01. I'm not sure what that means. Uh this is transaction. >> Yeah.

>> Block. This is block transaction. Okay. Log. Okay. Second. >> Okay. Got it. Got it. So I have this mapped. And now let's say uh are those same addresses or different addresses? >> Um I mean can be same or different. So it's it's it's it's this is this is just just the just the explaining this this so this this table was just explaining how the positions are assigned and yeah this is how the so the for these entries uh the this >> okay let's say let's say for simplicity this uses address one topic one topic two topic three >> okay

>> um this reuse the same address one it has here same topic but this is topic four topic five I mean this is like different hashes right this is the I'm I'm I'm using that this this is the same value right this is the same hash here and this is the same address uh let's say okay this we has one so this let's say uses address to uh topic six topic seven let's have something like more readable okay this will use uh let's say address one again just to have and say topic uh eight different topic and this this again has to use let's say address one this and let's use

topic one topic two topic three topic whatever uh nine something different right so this is basically the same thing emitted here and here this is some also similar in terms of address it raises the same address and okay what happens now I this is I don't understand I numbered it I have different numbers now what those numbers mean what what do they give me how do I search it and now I make a search and let's say my ETH get logs would be uh for address uh address one um okay this is like from to like so

from uh okay we have block zero and block one so from from block zero to latest right so to latest Let's say it's it it scans everything and we're searching for address one and let's say and the list of topics is topic one right so uh it should probably pick up uh this three right topics and how does this work how does this accelerate it because I I completely don't get it >> okay yeah this is this is this is now we have like actual pairs so Yeah. So, so what what what what happens here is that uh uh so so now we have like at position

two the the index value is A1. It's actually hash of A1 but anyway so let's just say it the content is A1 >> hash of A1. >> Okay. >> Yeah. So so the so the so the so the index reference generated will be uh value uh A1 position two. So let's it's it's just it's it's just a just a couple. Let's just say it's it's A1 and two and and then we have A1 at position 6 and we have A1 at position 14 and we have A1 at position 21. Right.

>> Uh-huh. So this is this is a list of for A1 we have a list of 2621. So yeah in the sorted list all the occurrences will be like uh adjacent in the in the sorted list. >> So so yeah first first we have >> okay so so for each topic address and block and transaction we have for each of them we have a list of indexes where they occur. >> Okay. Okay. That's the missing point for me. First missing point. Got it.

>> Okay. and and you do this if you do this get logs then you do the same thing for T1. So you will have occurrences of T1 at three at seven and at 22. >> Mhm. >> Okay. Got it. >> Yeah. Um you can just match these together. So basically you the T1 you are looking for at is is is is it has one offset compared to the occurrences of A1. So you if you just subtract one to from these positions then you have uh 2 six and 21. So you can just match the two uh lists of

positions against each other. >> Okay. How do I know they are in the same log? >> okay here it's easy because it's only off by one but if they were off by let's say three they might be in different log right but they might be the same log >> theoretically they can yeah so they can be in different log or same log but the thing is that uh so one thing that usually so in the end what we will do is uh uh you have you have you have the the position Okay. Now, now where to start?

Yeah. So, so one one thing one uh so >> with all the data structures we are using. Okay. I didn't know we using >> so we have you have the the the the forward mapping the index entries tree which is the position to entry mapping. So you have the potential uh positions 2 6 and 21. So then you can look up in the index entries three positions 2, 6 and 21 and you will find the log entries there. Uh and if you are looking for an address then you will never miss because the addresses uh are hashes of 20 byt values. So they can never be exactly the same as the hashes of 32 by topics. But it can be so it's possible that you are

not looking for an address. you are b maybe just looking for a combination of topics because I don't know yeah multiple contested and in that case it is possible that uh you have a potential match but uh but but but you find the top the same topics at different positions in a different log with different meaning so yeah you have a then you will you will have this this this entry position possible entry position and you will look it up in the index entries tree and if you don't find the log there. So let's just say that you are just looking for a combination of t1 and t2 then yeah you will have

positions for t1 and positions for t2 but uh you will reconstruct the address position from those. So you would sub subtract one from the t1 position then you will subtract two two from the t2 positions and uh and those are the pos possible entry where you could find the actual log in the index entries tree and if you don't find the uh the log don't find the log entry in the index entries tree then then maybe it those those topics appeared at different positions in a different kind of log then yeah it's It's then it's not a match.

>> Okay. Still complicated. I know more but I not I still don't think I understand it fully yet. [laughter] >> Okay. I think >> there's there's some progress at least. >> Okay. Yeah. Yeah. I have to definitely improve. >> You need to you need to include more examples how this looks. >> Yeah. Yeah. Yeah. Yeah. I I hope >> how how the lookup is going step by step. >> Yeah. How this is being combined. Yeah. Drawings and everything. Yeah. >> Uh yeah, >> I think there's a question ta.

>> Yeah. Uh so my question is basically I I was familiar with the previous version of how this worked. So over there if I'm not wrong, we would get this mappings and then we would produce uh the filter maps. So with the new design has the filter map been completely revamped or dropped or like how how is this looking space look up? Because the previous filter map I liked it because I could chunk it and I could only bring the chunks which were let's say the most popular or stuff like that. But like how is it working now with the new design that part so this this so this this this thing that uh we just uh uh walked through with with with how we determines positions by values and how we match the

patterns that's the same. So, so uh it's just uh the core thing. So, instead of the uh filter maps, we have these these merge sorted uh lists. But the thing is that uh in the end, what you will uh be able to prove from these is also a list of uh of positions for any value. So that's that's kind of similar, but with the filter maps, you sometimes had false positives. So sometimes even for a specific address or topic, you you reconstructed a position and maybe there

was nothing there or something else was there. So yeah and uh and and and with other design the alternative design uh so that's not probabilistic and and and and it's a little bit simpler but uh in the end what it's it's kind of the same that you you can reconstruct possible positions based on each address and topic separately and you can match them against each other and if each I mean I mean a each search uh position matches is then then you have you have a potential match. So it's so from the this aspect it's the same.

It's just the the data structure that has to be maintained. So that's that's that that's that's a lot simpler now. So with with the with the with the with the with the with the merge this merge sorted lists it it's it's uh very easy to guarantee the amount of processing that has to be done and it's easy to guarantee that uh it will not uh like slow down block processing and and everything. So yeah but um but otherwise there's still a lot of overlap between the two designs. So I did not throw away everything. I just yeah this this uh this filter I I replace this filter map

trees with with with with something with with with this this list merge sorted list which is yeah um it has this one disadvantage that uh you have to just keep around uh like three or four list at every layer in order to update which is something like 2 gigabytes or something. So it's a bit more expensive to initialize but uh but actually yeah otherwise it's it's it's a lot simpler. So yeah, a followup question like what was the size to update and let's say do

everything with the filter maps because two GB is quite the size on the RAM right to keeping the >> uh if I want to keep the entire lists in my RAM let's say it's 2 GBs right so how what was the similar numbers for the filter maps so like do you have any numbers or >> yeah yeah Yeah. Um so with the filter maps uh yeah this is uh so this this uh the minimal amount of data. Yeah. This is al already yeah try to explain this but this is also maybe hard to imagine by just or or or explain just by talking but anyway so the so in

the in the in case of the filter maps you you you had so the minimal amount of data uh to initialize this the state was 20 something megabytes. So that's that's that's a like like one point for the filter maps definitely that it's it's uh very cheap to but uh actually um with the with the with the sorted lists uh it's more data but you don't have to download all the data separately. So if you just have the re the receipts for this this uh recent

uh history. So basically you you have to have like uh 2 GB worth of receipts then you can locally generate the the the uh the log index state the so this this partially is sort of this everything. So yeah it's it's it's not like you have to download an extra 2 GB of data. It's just you have to you have to have two gigabytes of receipts which yeah probably most clients do. I mean I know most clients don't want to keep around a very long history but it's it's not a very long history. So yeah, this is this is what you require and then you can just uh uh uh locally

just generate these index references and and sort them and yeah so it's it's it's it's not prohibitive. It's just yeah this is where it's more expensive. Hey, I need to go. But just judging by the audience for this meeting, I don't and complexity of this of this topic because I think it's way more complex than than than it appears. uh or I think this is like this would need to be a headliner

in my opinion to to go in and I'm not sure if this will be a headliner. >> This is bigger than this is on the size of BS right in terms of work. >> This is few months work for a senior person >> to get it right. Well uh yeah um okay so uh so the thing about yeah if if if if I if if I propose anything as a headliner then yeah I the problem is it has very slim chances because yeah account abstraction as headliner forces as headliner like like lots of lot of lots of headliner >> is true so yeah I I I I

know this this is a problem. So this is so so let's just say uh I will try to make the simp this this this this new uh design more approachable and uh probably it will be easier to discuss this meaningfully whether I mean we can even move forward with this if uh if if if that's understandable because I think I think the new design Yeah. So that's that that's that that's significantly easier to do and and um >> okay maybe but I need I need like stepbystep examples of everything how it's working.

>> Yeah. Yeah. Yeah. So so my part it's it's it's like yeah some some glance at it I see I see how what I do on newb block how I build the index. I see how what needs to be done on search and I see how what exactly how proving works right because those are kind of three parts right because they're somewhat overlap of course for them but I need to see how this maps like exactly and then maybe if it's well documented well uh explained maybe this you know at least makes the complexity manageable for me but at this moment moment. It's

scary. Really scary. >> Yeah. Um Yeah. I mean, and what you said, it's probably right that it it would take like like a month or two from a senior person. So, yeah, that's that's right. Probably. Uh but uh but I mean I it's also it could be like I think really useful and and and I think we >> I I'm not saying it isn't. It might be useful especially if you like um go with other provable uh EIPs. I think there's u Eton I think right from Nimbus uh is is trying to push that and this could be part of that headliner even right to to make all things provable.

>> Yeah. So so so there was this this this idea. Yeah. Ethon really liked this angle that that Yeah. He he let he he called it the purit. Yeah. Purit. Yes, proposal and and everything. And yeah, we did talk a lot about this. Even I think in Thailand, in Bangkok, we we had a lot of discussions about this. And yeah, he really liked the original 7745, not because he wanted to implement it. Yeah. So, so the thing is that he liked it because it it it did fit his narrative, but um Well, I'm not opposed on on on for the cap on any like uh merit stuff, but for now it's still it's really hard to

understand how it works internally for me. Uh and maybe I'm just stupid or I just don't want to read through it enough and understand on my own. Um and but in my opinion, it's not selfexplained in in in this in this in any way. >> Okay, I get it. And uh actually thanks a lot for this feedback because yeah now I mean I mean uh it's it's it's also if I already worked on something for a year then it's just hard to see how approaches how approachable it is from the outside. I'm sure you're not stupid or anything. It's just yeah uh but but yeah this is this is valuable feedback and uh okay so I think we this this one

hour is mostly over already so yeah let's just agree that uh somehow we I have to uh provide like like like easier to approach examples and everything. So yeah, I think you had another question. >> From where I stand, it would be best like let's say uh I also need to read this more because from where I stand, from my perspective, even with a rate of false positives, the previous data structure seemed to be better. But to understand the differences, I'll need to

read up on this one more. So like uh in 2 weeks time then let's come back. then I think that's the best thing to do right now. >> Okay. Yeah. So, so honestly I I I I'm I'm I I just proposed this this alternative thing but I did not like like discard I mean the OD IP is still there. I we we have some I mean I have some some implementation you have something for it. Yeah. So I mean I mean it it it might uh be worth uh discussing further but uh yeah uh now I feel this this this new one is probably simpler to make it like like like safe and production ready and everything but uh

but yeah let's just uh read it through and I will also improve on the documentation and and um yeah let's see how we can make it more approach more approachable. Yeah. Anyways, thanks guys for coming to this meeting and let's also like like discuss it between meetings if you have any like suggestion. I I will definitely ping you if if if if I have some some new new material for it. But yeah, anyways.

Yeah, I think it's it's it's it's for now. So So yeah, let's continue from here. Okay. Thank you guys. >> All right. Thanks. >> Okay. Bye. Bye. Right.