Zsolt Felföldi:Hello?
Transcript
Zsolt Felföldi:Thanks for coming. Yeah, apparently not a lot of people.
Zsolt Felföldi:But… That's fine.
Łukasz Rozmej:Yeah, a bit of… not a crowd.
Zsolt Felföldi:Yeah, I mean…
Zsolt Felföldi:I know this is just the topic that might interest a few people, and also, yeah, I…
Zsolt Felföldi:I'm aware I really have to work on my presentation skills, but I think we can I… at least…
Zsolt Felföldi:I can, I can, I can show what I have, and that's good, so…
Zsolt Felföldi:maybe wait, like, I don't know… Oh, it's 4.05 now, so…
Zsolt Felföldi:Let's wait one more minute, and then, yeah, let's start.
Zsolt Felföldi:Until then, I will just… Trying to share my screen.
Zsolt Felföldi:Well, no.
Zsolt Felföldi:Whoa.
Zsolt Felföldi:It's just… Do a slideshow, okay.
Zsolt Felföldi:Wait, no.
Zsolt Felföldi:I just…
Zsolt Felföldi:Okay, can you see the slide?
Łukasz Rozmej:Yes.
Zsolt Felföldi:Alright.
Zsolt Felföldi:Okay, I think, yeah.
Zsolt Felföldi:Let's just… I, I will, I will, I will,
Zsolt Felföldi:Go through this, and yeah.
Zsolt Felföldi:I will… I think I will present this multiple times anyways.
Zsolt Felföldi:Let's just, you know… Okay, so,
Zsolt Felföldi:So now, now I, I, I, just, like…
Zsolt Felföldi:figured out the details of this new thing I want to propose, and I think I managed to make it
Zsolt Felföldi:Even simpler, and
Zsolt Felföldi:Yeah, so, so the basic thing is, the basic, basic, structure that I want to, show is… it's, I just call them index tables, and, so these are… yeah, and I will have some drawings that will show it better, but,
Zsolt Felföldi:These are an ordered list of events, and one event can be a block hash, a transaction hash, a log address, or a log topic, and this… this is all tree hashed, and I will also show why… how that can be used for searching and proving.
Zsolt Felföldi:And so one important thing is that an index table is generated either from a single block or a number of blocks, but they are always generated when, like, those blocks are finished.
Zsolt Felföldi:And, and, and they are not. I mean, I mean, I'm in, I'm in, this…
Zsolt Felföldi:So, the new tables are generated from new blocks, and since these are just sorted lists, they can be merged together, so that's how this structure evolves.
Zsolt Felföldi:The complete table is never modified. If the chain is rolled back, then some tables might be discarded and regenerated, but yeah.
Zsolt Felföldi:Those are just, small tables at the…
Zsolt Felföldi:And… and I was… yeah, okay, let's just, so this is… this is, this is a chronological order of, of, of, of, events in an example, and, yeah, I just…
Zsolt Felföldi:I have this… this… I have few events, like, there are four, so this is a… this is an index table that covers four blocks, and there's…
Zsolt Felföldi:there's some empty blocks, there's a block when there's a transaction with two log events, a WA transfer, and a USDT transfer, and the second transaction with a withdrawal, and another block with another USDT transfer, so this is…
Zsolt Felföldi:just…
Zsolt Felföldi:enough for some simple examples. And, yeah, as you can see. Now, this is the chronological ordering, so this is not how the table is hashed.
Zsolt Felföldi:So here, every entry has a block number, transaction number inside of the block, and log… index of the log inside of the transaction, and each entry has a type and a value, which is 32 bytes.
Zsolt Felföldi:And, the way the table is generated is that it's,
Zsolt Felföldi:it's sorted, and here I also reordered the columns so that it represents the sorting order, so it's sorted by event type first, and then by value, and then by block number, and yeah, so the position.
Zsolt Felföldi:And, the whole thing is, tree-hashed, the way I…
Zsolt Felföldi:imagine that now, probably the easiest thing is just use the SSZ list hashing, so…
Zsolt Felföldi:And since this is an immutable thing, and we know, like, in advance the number of items, so we can just create a list with an appropriate capacity. So this list has
Zsolt Felföldi:Yeah, I guess it has 5 levels of…
Zsolt Felföldi:nodes, and it has… it has a total capacity of 32 items, but now we have 22, so if we have more than 22… more than 32 items, then we are going to have a
Zsolt Felföldi:More, more, tree levels, and yeah,
Zsolt Felföldi:And, and the individual items.
Zsolt Felföldi:So now, maybe we are… maybe this could be optimized, but the way I imagine it now, we can just have a 64-byte encoding. We don't necessarily need 64 bytes, but but yeah, we need more than 32, so it's going to be two nodes in the binary merco tree anyways.
Zsolt Felföldi:And, I think the nicest way, probably, is to use an encoding.
Zsolt Felföldi:where the numbers are big and beyond. I mean, the event type is not really relevant because it's one byte, but maybe later we can have more event types for some reason. Anyways, but the position…
Zsolt Felföldi:Numbers are also encoded in big India, so the whole thing can be, just classically ordered the same way it is hashed.
Zsolt Felföldi:And, yeah, maybe.
Zsolt Felföldi:If the… yeah.
Zsolt Felföldi:this, this, this…
Zsolt Felföldi:Looks probably simple enough, and yeah, in some cases, the transaction and log index is not applicable, because we have entries for the block hashes themselves, there's then no transaction index, and also we have entries for the transaction hashes, then there's no log index, so these are just left as zeros in the encoding.
Łukasz Rozmej:Could we represent them with something else, and then we don't potentially need the type, right? If we have, like, optional, or a null, or whatever.
Zsolt Felföldi:So, what… I don't understand.
Łukasz Rozmej:Okay, so potentially, we could infer from, missing data on the transaction and log columns, the type of the…
Łukasz Rozmej:Row, and then we don't need.
Zsolt Felföldi:The type column? Maybe we could. Well, actually, we could, yeah, so, so we could do that. We could have,
Zsolt Felföldi:another column, which could be, like, the topic index inside of the log, and then probably… and yeah, we could use some other value instead of zero for the missing entries, and yeah, so this would tell all the necessary information, but
Zsolt Felföldi:I mean, this is not about some tight encoding, this is… or this is just for hashing, it doesn't have to be optimal, and also the important thing is that it is sorted,
Zsolt Felföldi:By type first, and then by value, so…
Zsolt Felföldi:I just assumed… I mean, I mean, we can have any kind of representation, hashing representation, and we can still have the same sorting. I just felt this is probably nice, because
Zsolt Felföldi:like the, the hashing format and the sorting, format, sorting, rules are, related, but yeah, I mean, if there's any reason to use another encoding, we can have that it will not fundamentally change anything.
Zsolt Felföldi:Anyway, so this is,
Zsolt Felföldi:This is the table. This is one table. And we have multiple tables, because one table is just… so this is just, like, 4 blocks.
Zsolt Felföldi:And so this is how this would go into, Consensus.
Zsolt Felföldi:So, we generate a single block table for every new block, and that goes instantly into the header.
Zsolt Felföldi:And I tried to do this drawing, so this arrow shows that we are now, like, at block 81, and then the table of block 81 instantly goes into the header.
Zsolt Felföldi:And we also, generate larger tables. This can be generated by merging the smaller tables, and
Zsolt Felföldi:And these are added to the header with some delay, so that we don't have to just… so this can be processed somewhat asynchronously, and maybe this is…
Zsolt Felföldi:Good for processing latencies. And these, tables are,
Zsolt Felföldi:hashed into a simple chain, because, I mean, this is good enough, we don't necessarily need, some, some other, hashing into… with some tree index, with some table indexes. We could do that, but, but, the thing is that, in practice,
Zsolt Felföldi:with the… with the small tables, we will only ever need the last few ones. So this is, like, yeah, for the hashing, these tables all…
Zsolt Felföldi:are hashed into the latest, tables, representation, but, if there's an… I mean, they… if…
Zsolt Felföldi:a provider wants to prove something, then they will not use the old single block tables, because they are less efficient. They will use, at most, 3 or maybe 4 small tables. They will use
Zsolt Felföldi:Like, and this, the, in the, in the, in the…
Zsolt Felföldi:16 block table row, so this is the third from the bottom. This asynchronous processing is also shown, so that, in this case, at block 81, we already have all the
Zsolt Felföldi:4 block tables, and they are being merged into the 16 block table, but it's not added to the consensus yet, because, yeah, let's leave some time to process it.
Zsolt Felföldi:And, therefore, it's possible that we have to use four, so we use, in worst case, four, four block tables, and then we can use 16 block tables, and, and, and 64 block tables also, and the bigger ones are always more efficient.
Zsolt Felföldi:And, in this proposal, I… I… I propose that we do not,
Zsolt Felföldi:hash bigger tables into consensus, because that would… so with…
Zsolt Felföldi:So with the requirements for generating this structure is that, I mean, the initialization doesn't even need any kind of extra wire protocol or anything. You just have to have the last, I think, 80 or 80 few blocks available.
Zsolt Felföldi:And, yeah, I think that's… that's a reasonable requirement.
Zsolt Felföldi:And and I don't want to require every, node to, have, like, a long chain history,
Zsolt Felföldi:And what we can do, and yeah, I will just get to that also a bit later, we can… we can generate bigot tables with ZK proofs.
Zsolt Felföldi:And, and this is… this is good because, I mean, with ZK proofs, if we want to generate the whole index for every new block, that's going to be really expensive and still going to have some latency, so I think… I think for the… for the recent chain history, having these tables in consensus makes sense.
Zsolt Felföldi:And for, for, like, the long-term history, it's probably better to just, like, some bigger info providers probably can do it even altruistically, or share the effort. Yeah, so this is, this is something that
Zsolt Felföldi:still needs to be figured out, but but we can use bigger tables also, but I think we… now I think we should not add them to…
Zsolt Felföldi:to the headers. And now I will also, show how the search and the proof will… will work, because that's interesting.
Zsolt Felföldi:And, yeah, so this, this, this example is, really,
Zsolt Felföldi:The most basic one, so the most basic kind of proof
Zsolt Felföldi:And this is for one table, so I just go back one slide. So the thing is, if we want to search the entire block history, then we will use multiple tables, like, bigger ones, and then at the end, some smaller ones.
Zsolt Felföldi:But this is just how we prove the existence or non-existence of something in one table.
Zsolt Felföldi:And the simplest case is when we are looking for something that doesn't exist, and we generate an exclusion proof. And yeah, usually this is the most important feature of this whole thing, because inclusion is usually easier to prove than exclusion.
Zsolt Felföldi:And, yeah, so this is the most basic case. Let's assume we are looking for a non-existent, some random transaction hash.
Zsolt Felföldi:And,
Zsolt Felföldi:What the prover does is it finds where this entry should be in the table, and checks whether it's there or not.
Zsolt Felföldi:And this can be done either with a binary search, or probably with a database representation. It's more efficient to just
Zsolt Felföldi:like, store the bigger table in chunks and somehow build a search tree within a chunk level, so, like, we just share the root chunk and then go up with loading high-level chunks from the database, but anyway, that's implementation detail.
Zsolt Felföldi:So the thing is that it is a sorted list, and we can say that there are these two red lines, and, we don't see this, this, this, this transaction hash, but, we can find, like,
Zsolt Felföldi:This would go between these two red lines, if it…
Zsolt Felföldi:If it did exist. So what we do is we prove these two entries with the Merkel proof.
Zsolt Felföldi:So, yeah, the red tree nodes are the proof nodes, like, the yellow ones are the reconstructed hashes.
Zsolt Felföldi:And so we have a middle logarithmic cost.
Zsolt Felföldi:we can prove… prove that… that something does not exist in the table. If it did exist, then…
Zsolt Felföldi:Well, in case of a transaction hash, then probably we don't even really need this table, we could just prove it from the block, but anyways, so, if we want to prove, yeah, I will just go to the next example that will be more interesting.
Zsolt Felföldi:So this is… this is where we also prove, like, things that do exist. So this is… this is a log pattern query.
Zsolt Felföldi:And we are looking for… for a USDT transfer from Bob to anyone.
Zsolt Felföldi:And that's… that's our search.
Zsolt Felföldi:And,
Zsolt Felföldi:Here in this… in this case, there is some room for optimization… heuristic optimization from the part of the prover, but
Zsolt Felföldi:The, the… I mean, generally, it's a good idea to look for, the least popular, item first.
Zsolt Felföldi:And,
Zsolt Felföldi:And actually, if you have a big search table, and now let's assume we are having search tables with hundreds of thousands of entries, and I think even for 64 blocks, it's realistic to talk about more than 100,000 entries. So, yeah,
Zsolt Felföldi:the… if we are looking for USDT, contract address or transfer topic, we are going to have, like, thousands of matches.
Zsolt Felföldi:But even those… so it is possible to just, look up the,
Zsolt Felföldi:range of each of these. I mean, we can also assume that the later topics are less frequent, but if we don't want to have such assumptions, we can just check with the logarithmic cost how many matches we have.
Zsolt Felföldi:Like, here are these… these two lines, it's… so, like, like, we look for address type.
Zsolt Felföldi:and the USDT value.
Zsolt Felföldi:And we can just do, like, this tree search for the first and last entry, and we can already, without reading all the entries, I mean, I'm talking about how the prover does now. So, yeah, the prover can determine the number of matches for USDT, address.
Zsolt Felföldi:For transfer, topic 0, for Bob at topic 1,
Zsolt Felföldi:And the prover can conclude that, like, the least frequent thing that happens is that topic one is Bob.
Zsolt Felföldi:And, and, and here in this case, these four, red lines, they prove that,
Zsolt Felföldi:that, there's exactly these two, cases, then topic one equals Bob, Bob's address.
Zsolt Felföldi:So, yeah, block… both of them in block 42, and one is in the transaction 0 log 1, and the other is in transaction 1 log 0.
Zsolt Felföldi:Which is, like, actually, the second one is the withdrawal, so this is not what… we don't want.
Zsolt Felföldi:So, yeah, and in this case, it's also good to talk… think in terms of exclusion proofs. So, in the end, we are going to prove the actual match, which is, like, this… this…
Zsolt Felföldi:Bob transfers USDT to Alice. This will be the actual match, the actual result, which is in… in transaction 0 log 1.
Zsolt Felföldi:And, we can prove this through the receipts.
Zsolt Felföldi:And this is also why the block hash is proven, because…
Zsolt Felföldi:Yeah, so we also proved that this is the block hash of block 42. This is a convenient way to prove the canonical hash, which might not be so easy if this is an old block.
Zsolt Felföldi:And the prover can use the regular, receipts tree to prove this actual match. And what we need to prove is that others are not matches.
Zsolt Felföldi:So, just checking topic one already leaves us two options, and we now just need to disprove the second one.
Zsolt Felföldi:Which is the withdrawal. So, yeah, an easy way is just to prove that at block 42, transaction 10, topic 0 is withdrawal, which is not what we are looking for. So, yeah, we ruled out the other match, and
Zsolt Felföldi:Yeah, this is all we need to…
Zsolt Felföldi:do a log query, in a single table. So, yeah, and, still… I mean, I mean, I mean, in case of these more complex searches, it's, it's harder to do exact numbers of how expensive a proof is, because it depends on some factors, but,
Zsolt Felföldi:the overhead, additional overhead over the actual matches, that is still more or less, I mean, usually logarithmic, so…
Zsolt Felföldi:So, even if we have to, You know.
Zsolt Felföldi:I mean, anyway, so, so the, so the bigger tables are, are, are always more efficient.
Zsolt Felföldi:And, yeah, this is just, some, some…
Zsolt Felföldi:reasonings about, why I think this whole approach is a good idea, so that we… we put smaller tables in consensus, and, and then we,
Zsolt Felföldi:prove bigger tables with ZK proofs.
Zsolt Felföldi:So, yeah, this is a new thing in this whole design, because originally, with the complex, original EIP7745, I really tried to achieve, that, we have a structure that's easy to update, but also
Zsolt Felföldi:Efficient for low-term history, but yeah, that comes with high complexity and still some trade-offs.
Zsolt Felföldi:And, and… Yeah, so, I mean, I mean, if, if,
Zsolt Felföldi:I think it's obvious that processing very big tables in consensus has some drawbacks.
Zsolt Felföldi:But also, if we… if we process everything with ZK proofs, then we don't have the last few blocks, or even last few hundred blocks.
Zsolt Felföldi:And,
Zsolt Felföldi:And for all of these, we have to just use the complete block receipts to prove anything, so…
Zsolt Felföldi:like, if we can generate a ZK proof, every hour, which is, yeah, probably still already kind of expensive.
Zsolt Felföldi:But then… then just proving the events in the last hour, that will be, like, 15 or 20 megabytes, which is already kind of expensive.
Zsolt Felföldi:And, and if we want to, like, use this whole thing for, for, for, off-chain or cross-chain, event proofs, which I think will be, yeah, an important…
Zsolt Felföldi:thing for future scalability, then this is… this is prohibitive, so even not having the… the last block indexed is bad. Actually, that's usually the most… most interesting block, probably, for these use cases.
Zsolt Felföldi:And, and yeah, so,
Zsolt Felföldi:But if we just process the big tables with long delay, then…
Zsolt Felföldi:These proofs can also be built in a collaborative way, like,
Zsolt Felföldi:I have no design for the proofs yet, but I think with this design, it's reasonably simple, because it's just lists of 64-byte entries ordered, and we have some smaller tables, and we have one bigger table, and we can just generate proofs that prove
Zsolt Felföldi:At certain smaller index ranges that the merging… the merge sort is performed correctly, so… so actually it's not going to be a super complex proof.
Zsolt Felföldi:also the ZK proof does not need to care about all the receipt encoding and all the stuff, because that's done in consensus, so I think this is…
Zsolt Felföldi:Also, with this approach, doing the proofs is also easier technically, and also a lot cheaper.
Zsolt Felföldi:So, yeah. And, yeah, that's pretty much it.
Zsolt Felföldi:Yeah, there's still a few things I think we can debate, like, I just said now that, okay, let's do 64 blocks, the tables in consensus, but yeah, maybe we could do more, and, and then we have even, like, this whole…
Zsolt Felföldi:The proofs will be even cheaper, because, yeah, we…
Zsolt Felföldi:we have even more time to generate them, but yeah, this is just… just finding the… about finding the optimum, and also the hashing scheme. Now I just, yeah, said that let's use the SSZ list localization, but we don't necessarily have to use it.
Zsolt Felföldi:And more specifically, I'm honestly not sure about,
Zsolt Felföldi:What are the most ZK-friendly hashes now? Maybe not SHA-2.
Zsolt Felföldi:But, yeah, so, so we can, we can, we can figure out,
Zsolt Felföldi:whether we should use another hash function that's efficient both on CPU and ZK proofs, and also, yeah, so this, this, this 64-byte encoding,
Zsolt Felföldi:In case of Shattoo, I think it's more efficient to use something that's, like, slightly smaller than 64 bytes, because, yeah, anyways, these are just minor details.
Zsolt Felföldi:But, yeah, so this is… this is… this is… this is my current proposal.
Zsolt Felföldi:The…
Łukasz Rozmej:Yeah, let me ask a question. So, this is now, with this design, not effective to store the whole history?
Zsolt Felföldi:Ugh.
Łukasz Rozmej:football history.
Zsolt Felföldi:Well, I mean, I mean, the tables are, effective. I mean, I mean, I mean, the way I imagine this is that, the cons, so the consensus is generating 64 block tables, and,
Zsolt Felföldi:And, and, and, yeah.
Zsolt Felföldi:if we… if we… if we can ZK approve bigger tables, we can create tables of a million blocks, or I don't know. I mean, I mean, I mean, I mean, this, this whole thing, if we just, always, merge
Zsolt Felföldi:two or four smaller tables into a bigger one. The tables does not necessarily have to be,
Zsolt Felföldi:power of two-sized. I mean, it's just the number of blocks and some events, and the number of events will just be some random number anyway, but but it's just, yeah.
Zsolt Felföldi:convenient to think about, but yeah, so we can… we can keep merging the tables, and in the end, we will have a logarithmic number of tables, and and… and… and we can even have, I don't know,
Zsolt Felföldi:One big table for, like, most of the old chain history, and a few smaller tables.
Zsolt Felföldi:At the end
Zsolt Felföldi:And, and, and, and this, so, so, so if we do have big tables, then this is, this is significantly more efficient than my original, proposal. So,
Zsolt Felföldi:I did some, I don't have… I don't have… don't have calculations in these slides yet, but,
Zsolt Felföldi:But, but, but in general, if we just, Let's just… Yo.
Zsolt Felföldi:Go back.
Zsolt Felföldi:On this? Why did I,
Zsolt Felföldi:Yeah, here I did some calculation at the, like, you know, at the end. So, proof cost per index table, and
Zsolt Felföldi:Yeah, for a bulkwork estimate, it's usually a good benchmark to think about just a single exclusion proof per table, and obviously more complex searches will be a few times that, but,
Zsolt Felföldi:But yeah, so this can be our baseline estimate.
Zsolt Felföldi:And, yeah, so proving… one exclusion proof is… requires proving these two red lines. So, with a compact encoding, one… one entry can be 40-something bytes.
Zsolt Felföldi:And also, we have, one proof node per, tree level, so this is… like,
Zsolt Felföldi:This is a very small table, so we have, like, 5,
Zsolt Felföldi:Five levels, and if we generate a huge table that covers, like, most of the history.
Zsolt Felföldi:then… and… and, I mean, it's a merge sort, so it can be efficiently processed in database and everything, so it's… it's not… I mean, it has some costs, but it's… it's… it's doable that… to… to… to generate most of the… put most of the history in one table, then…
Zsolt Felföldi:then the single exclusion proof will be, let's just say, I think, I think the number of, these entries is…
Zsolt Felföldi:Somewhere in the 20 billion range now, so the logarithm of that is, 35 or something?
Zsolt Felföldi:So, like, a single exclusion proof is somewhat, like, like, little over 1KB. I mean, it's not so bad.
Zsolt Felföldi:And, that cover… can cover, like,
Zsolt Felföldi:more than 10 million blocks, or I don't know. And and… and actually, the more expensive thing is… is… is…
Zsolt Felföldi:Like, like, if we have, have these, these, these, these, exponentially smaller tables, then, then…
Zsolt Felföldi:The proof cost will increase roughly logarithmically, so…
Zsolt Felföldi:Let's assume we have, like, one 35-level table, and one 34-level table, and so on and so on, and we have smaller tables, and the full history proof can be, like, somewhere around… somewhere around 40 kilobytes.
Zsolt Felföldi:And, I mean, this is… this is a single exclusion proof.
Zsolt Felföldi:more complex proof can be a few hundred kilobytes, but yeah, I mean, for a full history proof, that's still better than, I don't know, 600 gigabytes, so yeah.
Meek Msaki:Wait, can I ask you a question?
Zsolt Felföldi:Yes, sure.
Meek Msaki:So, so, are you saying, like, this is more efficient than foam filters?
Meek Msaki:I just had to ask that, like…
Meek Msaki:the lookup, because I think my understanding of, like, bloom filters.
Meek Msaki:They kind of allow you to, like, see if…
Meek Msaki:like, you know, it's, like, kind of like a lookup thing. I'm not sure on, like, the exact technical details, but I was just wondering, like, is the improvement here in terms of, like, more storing or lookups?
Łukasz Rozmej:This is… this is less efficient than big enough bloom filters, the whole thing here is about proving.
Meek Msaki:Oh, it's about proving, like, inclusion, or just…
Zsolt Felföldi:Wait.
Meek Msaki:Okay.
Zsolt Felföldi:Yeah, so inclusion is usually easier. So, so, so, this is, this is mostly about proving the complete set of, matches for certain criteria. And, well, if…
Zsolt Felföldi:if you're asking about bloom filters, so the… well, I mean, it depends on how we… how we use bloom filters. I mean, the bloom filters we have now are practically useless, so yeah, it's definitely better than that.
Zsolt Felföldi:I did some, calculations of, I mean, I mean, I mean, if you, if you, if you, if you have,
Zsolt Felföldi:No, I really don't think you can even come close to this efficiency with any blow-filter-based design.
Zsolt Felföldi:I mean, I mean, I mean…
Zsolt Felföldi:you could have some, some, some huge room filter for, for, for, like,
Zsolt Felföldi:many block region… I mean, I mean, if you have one bloom filter per block, then you're already way worse, because… because… so right now, with…
Zsolt Felföldi:if we just used bigger bloom filters instead of what we have now in consensus, so, like, instead of using a 2,000-bit bloom filter, we could use something like, I don't know, 100,000-bit bloom filter.
Zsolt Felföldi:So… then we would still have, like, 100,000 bits per block. I mean, yeah, that's… that's way worse than…
Zsolt Felföldi:what we have here. So, here we can have one table of, like, 10 million blocks, and we can prove something in it with just one kilobyte. So, yeah, I think…
Zsolt Felföldi:This is, this is, this is, this is the most efficient… version.
Zsolt Felföldi:I could think of until now, so yeah.
Łukasz Rozmej:Do we have to sort by type?
Zsolt Felföldi:Well, you don't have to, I think it makes sense.
Zsolt Felföldi:Yeah, so the previous version did not do that. I did that since then.
Zsolt Felföldi:One option is to, I mean.
Łukasz Rozmej:Well, why I'm asking that? Because I'm asking, can we… Have this kind of structure.
Łukasz Rozmej:And use it as our main log,
Łukasz Rozmej:storage too, right? So don't have to duplicate this data from the receipts.
Łukasz Rozmej:But kind of unified with the receipts, and store it just once.
Zsolt Felföldi:Well, okay, so yeah, this is an interesting question, and, and, and,
Zsolt Felföldi:The thing is that,
Zsolt Felföldi:Yeah, the receipts, they… they… so it's… it's… it's… it's maybe… probably, we have to hash the same data in two different ways, anyways. So,
Zsolt Felföldi:So this design… I mean, in this version, I dropped that linear log value index thing that I had in previous designs. I mean, it has some efficiency advantages, but, but in this version, if we use
Zsolt Felföldi:ZK-proven tables and everything, then maybe it's not so important to be the most efficient, so maybe simplicity will help. But anyways, in those designs, I used a separate index entrust table. Now, I don't have that, so I just, propose using the actual receipts for inclusion proofs. So the thing is that,
Zsolt Felföldi:with the… with… so the receipts are, organized chronologically. And,
Zsolt Felföldi:And probably you also need that. So, in this case, now, now these, these, these, search values are, organized, yeah, by content. And,
Zsolt Felföldi:You can look up this… so there's this example, like, like, USDT transfer bulk to anyone.
Zsolt Felföldi:And yes, you can look up.
Zsolt Felföldi:you can look up USDT, you can look up Bob, you can look up transfer, you can match them together, but it will not be easy to find out that it… topic 2 is Alice, so this… this actual… so… so it will not be easy to reconstruct the actual log, because this hashing
Zsolt Felföldi:It's organized by content, and now…
Zsolt Felföldi:now finding something by inclusion position is hard. So, I think,
Zsolt Felföldi:We do need to, hash
Zsolt Felföldi:Hash, hash, all the events, both chronologically.
Zsolt Felföldi:which the receipts do. And, and also, by content.
Zsolt Felföldi:And it's an implementation thing, whether we want to deduplicate the actual content. So, it is possible to
Zsolt Felföldi:store these tables locally in a way that you don't actually store the type and the value. You do the sorting, and you just store the position information, and you can look it up from the receipts.
Zsolt Felföldi:So,
Zsolt Felföldi:It's still some extra data to store, because it's a different ordering, and yeah, that's what you have to do if you want to… more efficiency, but you don't necessarily have to duplicate the actual contents.
Zsolt Felföldi:But I think, in any reasonable setup, we do need to…
Zsolt Felföldi:Hash it, hash, hash them, both.
Zsolt Felföldi:In, in, in a, in a content,
Zsolt Felföldi:address way, and also… or content-ordered way, and… or… and also a chronological way. So, yeah,
Zsolt Felföldi:with this design, I think it's best to, keep the receipts.
Zsolt Felföldi:I mean, I did have this other version where I had the index entry street, which does… did the, chronological hashing, so in that case, it would be possible to, drop the receipts and,
Zsolt Felföldi:And have, like, a different, tree representation, but it will still be another way of tree hashing. So, yeah.
Zsolt Felföldi:I mean… This is… this is, this is, this is probably the smallest change we can do, and
Zsolt Felföldi:But anyways, yeah, I, I think, I think, I think, I think, I think it's important to have the two hashings.
Meek Msaki:Also, quick question, this… are these, like, different tables, or is this just one table?
Zsolt Felföldi:So, what I show in this example is one table. So, yeah, but this is…
Zsolt Felföldi:So this is, this is, this is this, I had this example with blocks 40 to 43 with this, like.
Zsolt Felföldi:or events, and this is… this is what I used in all examples.
Zsolt Felföldi:So, this is the table, and yeah, if I just…
Zsolt Felföldi:switch back and forth between these two tables, then it's obvious. It's just… Yeah.
Zsolt Felföldi:The difference is what we prove from that.
Zsolt Felföldi:Let's yell.
Meek Msaki:No, I was saying, like, in terms of, like, let's say, every single, like, height, is it almost like looking up into a new table?
Zsolt Felföldi:Wait, so yeah, do you have multiple tables, so, Yeah, there's…
Meek Msaki:So you have the block number table, mem is a table for log index.
Zsolt Felföldi:Oh, no, no, no, no, not necessarily. No, this can be in one table. So, yeah, I mean, I mean, I mean,
Zsolt Felföldi:I think, I think it makes sense. Now, if we do have an index, it makes sense to do all these things, and I think, there's no advantage of putting them in separate tables. We could, but… I mean, I mean, I mean, putting the type first.
Zsolt Felföldi:this will mean that block hashes will occupy a continuous subtree, and transaction hashes will occupy a continuous subtree, so efficiency-wise, it's almost the same as having separate tables for the different types of entries, but I see no reason to really, like.
Zsolt Felföldi:create many tables per block, you know.
Zsolt Felföldi:It's just, I think, easier.
Meek Msaki:So it's… the duplication is not, like, a problem, because, like, there's a lot of, like, duplicated values and stuff like that.
Zsolt Felföldi:So, sorry, I mean, I mean, every, every value is duplicated here, but, yeah, in the database representation, you don't necessarily have to
Zsolt Felföldi:have them… store them twice. It's just, yeah, let's… No.
Zsolt Felföldi:Okay. It's just… just the position information that you have to store,
Zsolt Felföldi:When it's, sorted by content, yeah.
Meek Msaki:After sorting it by content, yeah.
Meek Msaki:Okay, so did… okay, alright.
Zsolt Felföldi:Yeah, still, it's, I mean, I mean, probably,
Zsolt Felföldi:For, for the, for the, for those, for the infra providers who want to, generate, proofs.
Zsolt Felföldi:They will probably…
Zsolt Felföldi:I mean, I mean, I mean, I would, I, I, I, I would, I would, actually duplicate this…
Zsolt Felföldi:this, these, these values, which is, like, I mean…
Zsolt Felföldi:it has some cost, but if you're running an infra provider node, then what you want is to be efficient, and yeah, if you, if you deduplicate the, the values, then,
Zsolt Felföldi:Yeah, you want to generate a proof, and, you have to, like, like, look up all these, these,
Zsolt Felföldi:these values from very different places, and it's not super efficient, so if you want to be efficient at generating proofs, then I would say probably it's best to just duplicate it, but I mean, if you are running a node for this purpose, then, I mean, it's an affordable cost.
Zsolt Felföldi:And for those who don't want to generate, like, long-term historic proofs, just, I don't know.
Zsolt Felföldi:generate the consensus stuff, they really don't need to deal with big tables, so those who just generate the consensus can mostly just keep those tables that have non-finalized
Zsolt Felföldi:parts, so all the finalized tables can be discarded if you just want to generate the consensus, so then… then the storage efficiency is really not an issue.
Zsolt Felföldi:And yeah, if you want to use it, then… Then probably, you don't.
Zsolt Felföldi:You, you, you, you can just duplicate.
Zsolt Felföldi:Maybe if you want to use this structure locally, just for local search, then you can… because you're running your own full node, and you just want to,
Zsolt Felföldi:search for yourself, then you can… you can… you can… you can generate these tables for… for yourself, and… and you don't even need ZK proofs, because you know they are correct, because you generated them. And then, maybe, maybe for local use, it might be a good, compromise to,
Zsolt Felföldi:to store the final tables with just the position info, and then the lookup is a little bit more expensive, but the whole structure will not cost another 600GB, more like, I don't know, less than 100, so… yeah, I mean…
Zsolt Felföldi:the index does have some costs if you want to index the entire history and do quick lookups, I mean, it will have some storage costs, but yeah, it's optional.
Meek Msaki:Alright, thank you, I think I'm gonna hop off.
Zsolt Felföldi:Alright.
Zsolt Felföldi:Okay, thanks for coming.
Zsolt Felföldi:Yo.
Zsolt Felföldi:Okay, anyways, this is…
Zsolt Felföldi:pretty much what I wanted to do.
Zsolt Felföldi:Talk about today?
Zsolt Felföldi:Any more questions?
Sixto Palacios:Oh, thank you.
Zsolt Felföldi:Okay.
Zsolt Felföldi:Then I think we can call it a day, and yeah, by the way, just for the quick feedback,
Zsolt Felföldi:Do you… how… how do you relate to the complexity of this? So, does it sound very complex, or now this… does this sound like something manageable, more manageable?
Sixto Palacios:No, I don't know, complex, is, is, put…
Sixto Palacios:Some attention, but it's so comprehensible.
Zsolt Felföldi:Okay.
Zsolt Felföldi:Alright.
Zsolt Felföldi:Okay, so,
Zsolt Felföldi:Okay.
Zsolt Felföldi:So, should we call it a day, then?
Sixto Palacios:Nope.
Zsolt Felföldi:Do you have more, Chris? Alright.
Sixto Palacios:Thank you so much, bye-bye.
Zsolt Felföldi:Thank you, bye-bye.
Chat Logs
00:14:44
Łukasz Rozmej:we potentially don't need Type as we can infer it from Block/Tx/Log data (null or Optional)?
00:23:01
Łukasz Rozmej:how big the tables should be to have efficient search in whole history?
00:31:12
Łukasz Rozmej:Can this be effectively used outside consensus for long history?
00:32:28
Meek Msaki:How do the log indexing currently work?
00:47:40
Łukasz Rozmej:sorry, need to go
Summary
12 highlights
· 2 action itemsExperimental
Summary
12 highlights · 2 action itemsExperimentallog index proposal
- Simplified log index proposal: ordered event lists (blocks, txs, logs) tree-hashed by type then value00:09:26
- Index tables generated per block or merged from multiple blocks; never modified after creation00:10:42
- Single block tables added instantly to headers; larger tables added with delay for async processing00:17:23
- Tables hashed into simple chain; small tables (last ~80 blocks) required for initialization00:18:43
- Bigger tables (>64 blocks) generated with ZK proofs; not added to consensus headers00:20:58
technical details
- 64-byte encoding per entry; SSZ list hashing proposed with big-endian numbers for sorting00:12:43
- Exclusion proofs: prove non-existence via two adjacent sorted entries (~1KB for 10M+ blocks)00:22:02
- Log pattern queries: prover searches least popular item first, proves matches via Merkle proofs00:24:44
- Full history proof ~40KB using exponentially sized tables; vastly more efficient than bloom filters00:38:49