Zsolt Felföldi:Hello?
Transcript
Tamaghna Choudhuri:Hello, how are you?
Zsolt Felföldi:Great. Yeah, a little bit tired, I might eat Denver now, so it's morning, but yeah.
Tamaghna Choudhuri:Oh, yeah. Oh, well, you just said that you'd be presenting this stuff at it then, so, like, is it today or some other day?
Zsolt Felföldi:it's on Thursday, so, I presented, also, so there was Eat Border, last week, and I also, did the presentation on Saturday.
Zsolt Felföldi:And, and, and yes, I, I will, also present, there's this EF Day, on, on Thursday at Denver, so, yeah.
Zsolt Felföldi:I will also do… Oh, that's moved there, so yeah.
Tamaghna Choudhuri:Yeah, Lynn, did you get any,
Tamaghna Choudhuri:feedback from the devs, like, let's say the wallet devs, or the daps devs, so how do they feel about this thing? So, did you… were you able to get something like that from them?
Zsolt Felföldi:So right now, it's mostly the… the core developers who, are, really…
Zsolt Felföldi:Paying attention to this, because, like, it's, like…
Zsolt Felföldi:fairly technical, so, like, I think,
Zsolt Felföldi:Maybe at eDenver… in Denver, maybe there will be more people, so at… at Border, it's a really small conference, so this was, like, a room of, I don't know, 30 people, maybe 40, and, also.
Zsolt Felföldi:From, from various areas, and EOF.
Zsolt Felföldi:Yeah, so it would be good to… it would be great to hear from someone from the, like, user side, but it's still, like, so this is… this is the EIP, and it's not even the API specification, so I think maybe at this point, it's,
Zsolt Felföldi:harder for them to approach, but, yeah, at a certain point, it would be…
Zsolt Felföldi:nice to get their attention, too. But, yeah, so right now, I'm mostly.
Tamaghna Choudhuri:Yeah, discussing that.
Zsolt Felföldi:testing with, like, core devs, because, yeah, I just want to get the EIP in. Oh, Kev is also here, hi.
Zsolt Felföldi:It's great that you could come.
Zsolt Felföldi:So… Cool.
Zsolt Felföldi:Oh.
Zsolt Felföldi:Alright, so, I think… Yeah, now it's 5 minutes plus 4…
Zsolt Felföldi:Or so, maybe we can even…
Zsolt Felföldi:start, and lah, yeah. Maybe someone else will join you later, but…
Zsolt Felföldi:I think, I think, I think we can, we can start this now. So, by the way, Kev, you weren't here at the previous one, two weeks ago, right?
Kevaundray Wedderburn:Yeah, exactly.
Zsolt Felföldi:because of the context, yeah, yeah. Okay, so, okay, just, then I want to do, like, a really quick recap, of…
Zsolt Felföldi:what… yeah, just to give some context, so first I will turn on… screen share… And… Says Desktop 1.
Zsolt Felföldi:Okay.
Zsolt Felföldi:So, you should be able to see my screen now.
Zsolt Felföldi:So, yeah, I will just use my, my, my Eat Border slides now.
Zsolt Felföldi:So, can you see? See my screen?
Kevaundray Wedderburn:Yeah.
Zsolt Felföldi:Alright, alright.
Zsolt Felföldi:So, so… This, this, so there's this, there's this,
Zsolt Felföldi:lead us to design this 7745B, which maybe will get a separate EIP number at a certain point, but not yet. Anyway, so this is, this is, this is, this is currently probably the best approach, and let me just quickly…
Zsolt Felföldi:show what it's about. So, basically,
Zsolt Felföldi:there are these, so, so the way it works… let's… maybe I will go for… for this, this, this, this figure first. So it generates, search tables, and yeah, we can go… I will go into how they work exactly, but, right now it's, it's,
Zsolt Felföldi:It's not even very important, so the… so the interesting thing is that, so this… this… this latest version of the log index, it, it, the way it works is that, it generates, so-called index tables, and index tables contain the events of
Zsolt Felföldi:Like, either a single block or a…
Zsolt Felföldi:Certain number of blocks, and and… and the way they are generated is that,
Zsolt Felföldi:with the head block, with the current currency process block, a new index table, a single block index table is generated, and, and later, these tables.
Zsolt Felföldi:Are merged together into bigger tables, so that's there.
Zsolt Felföldi:form, like, a bigger search tree that is more efficient, and… and… and so the thing is that only… so there's… there's a single block table that's generated, like, during block… block processing, like, synchronously, and then…
Zsolt Felföldi:later, bigger tables. So in this design, we merged, like, four single block tables into
Zsolt Felföldi:like, this second row at the… from the bottom, these tables are… represent, like, four blocks, and then there's another,
Zsolt Felföldi:Chain of tables that is… is… each table, represents 16 blocks and then 64 blocks.
Zsolt Felföldi:And so these higher level tables, they are generated asynchronously, so they can be processed when there's no block processing happening, and probably this is the smallest amount of burden we can put on the protocol.
Zsolt Felföldi:And, and… and so this is, this is, this is, this is how this index is generated, like, from a high-level overview, in the consensus. And,
Zsolt Felföldi:And, and
Zsolt Felföldi:Yeah, so… so the way… let me just quickly… so this is… this is one of the tables, this is how it looks, and what it has is, basically, it's an order list of the events, and it's… it's three hashed.
Zsolt Felföldi:So it can be at the events of single block, or in this case, this is the events of multiple blocks.
Zsolt Felföldi:And they are ordered by content first, and then inclusion position. So, there's also an example of how we use it for prEOFs. Like, the simplest example is, like, an exclusion prEOF.
Zsolt Felföldi:So…
Zsolt Felföldi:For example, if we want to look up an entry, which is, in this example, a non-existent transaction hash, then we look into this table, which is… either we can do a binary search, or
Zsolt Felföldi:if it's locally stored more efficiently, it can be a more efficient search tree. Anyway, so we look up the position where this entry should be, if it's present, and then if we find it's not present, like in this case, then we do a merger prEOF that proves the entries
Zsolt Felföldi:Before and after the non-existent event, so… and we know that this list is ordered, so this proves that this event doesn't exist.
Zsolt Felföldi:or there's an… I have another example, yeah, which is a bit more complex, because it's… it's a log pattern search, and yeah, I don't want to spend a lot of time with this now, but for example, here, at this, at the… at the bottom.
Zsolt Felföldi:There's these four red lines, these are the proven entries, and we, for example, if we want to prove
Zsolt Felföldi:all the instances where there is this topic 1 equals a certain, value, like this is the sender address of, of a USDT transfer, and the sender is called Bob, and we find the two occurrences of this
Zsolt Felföldi:topic, and then… so the prEOF also goes similarly, so we prove the actual matches, occurrences, and we prove the two adjacent entries to… in order to prove that there's no more matches. So this is… this is how these tables work, and
Zsolt Felföldi:And I already implemented these tables in GoEthereum, and they are super fast to search, and yeah, so, this could be very nice,
Zsolt Felföldi:But the thing is that, there's a reason, so in this drawing, this is… so this is, this is, this is, what I… I would, want to, put in the protocol. So, so in the, in the, in the, in the block headers, basically, I would,
Zsolt Felföldi:Hash in a chain of single block tables, four block tables, and up to 64 block tables, but not bigger ones, because
Zsolt Felföldi:Because… because with this design, it's, it's guaranteed that the block builders and validators only need the last
Zsolt Felföldi:80-something, 80 few blocks to generate or verify new blocks, so… so it's, it's, it's manageable, but, but, I don't want all the… so, so, so, so that would be a…
Zsolt Felföldi:too high demand on every participant of the protocol to… for them to process tables of, I don't know.
Zsolt Felföldi:hundreds of thousands of blocks, and yeah, so… so this, this, this, this, so bigger tables than 64 blocks should be somehow, proven off-chain. And so that's, that's the basic idea, and that's, why I want to use ZK prEOFs now.
Zsolt Felföldi:And, yeah, so there's this…
Zsolt Felföldi:I even made, like, one of the slides where I, just explained why I want to use both in-protocol processing and ZK prEOFs, but I think it's, like, kind of obvious.
Zsolt Felföldi:But so, so,
Zsolt Felföldi:with the… for the four latest blocks, it's very good to process the things in protocol, because otherwise anything between the latest generated ZK prEOF and the current head, all the search would be unindexed, and unindexed search is extremely expensive.
Zsolt Felföldi:And so, yeah, it's… I think this is… this is… this could be a really good balance to just,
Zsolt Felföldi:Like…
Zsolt Felföldi:do a little bit of processing in protocol, and basically use the same data structures, just prove them, prove them with ZK prEOFs.
Zsolt Felföldi:for, for, like, bigger, bigger tables, and…
Zsolt Felföldi:And, in the end, we would have kind of, yeah, so this, this is this…
Zsolt Felföldi:drawing shows, like, so this is how these index tables would cover the whole chain history. So we would have, like, small tables, bigger tables, and for the order history, even bigger tables, and we could basically cover the entire chain history with a logarithmic number of tables.
Zsolt Felföldi:So…
Zsolt Felföldi:So, an inclusion or exclusion prEOF of an event, or combination of events, that would be roughly log squared, because there's a logarithmic number of tables, and the Merck prEOF in a table is also logarithmic.
Zsolt Felföldi:And I calculated that with the current mainnet data, a full history lookup for a single event would be something like 40 kilobytes, which is…
Zsolt Felföldi:very good. It's just… so the only, only,
Zsolt Felföldi:question that we still have to figure out is whether we can really prove these tables with ZK prEOFs, and this is where I will certainly need some help, but I tried to already kind of imagine how this would work.
Zsolt Felföldi:And let me just open… now, these are not really good slides, this is just some drawings I did for today, and… oh, yeah.
Zsolt Felföldi:Anyway, yeah. So, wait… Yeah, that… okay, okay, this is the right one. So basically,
Zsolt Felföldi:This, this, this first drawing here, these,
Zsolt Felföldi:these, these, these numbered little boxes, these are, like, simplified representations of the index entries, so the index entries, they have, like, multiple fields, but still, they are basically 64 byte,
Zsolt Felföldi:binary entries, and they are ordered lexicographically. So, like, for simplification, now I just use two-digit numbers, but 64-byte entries can be ordered the same way. So… so this is how,
Zsolt Felföldi:Merging two tables works, so these numbers are the same here and here, and at the bottom row, they are merged into single
Zsolt Felföldi:Single, single, singles table, and and what I want to achieve is that,
Zsolt Felföldi:So these tables can be, very large after time, so we… I think… I think right now we have something… so mainnet has something like,
Zsolt Felföldi:20-something billion entries. And, these… these don't all have to go into a single table, but,
Zsolt Felföldi:But, but, but at the, like, the older history would certainly, beef.
Zsolt Felföldi:built off.
Zsolt Felföldi:like, billions of entries, so… so, probably this is not provable with a single execution trace. That would be too expensive.
Zsolt Felföldi:So I wanted to design this thing in a way that, that even a single table can be proven recursively, slice by slice.
Zsolt Felföldi:And, so this… this is what this example is… tries to show. So, basically, what we… the way…
Zsolt Felföldi:I want to generate a prEOF is… so locally, I can… the prover can generate the tables, so it already does have the smaller tables that it's merging together, and it already has the bigger table, and it can already calculated the table root, it just wants to prove that it's the correct table root.
Zsolt Felföldi:And and and in this example, these green… green boxes, this is… so this is the section that the prover wants to prove that it is correct. So…
Zsolt Felföldi:So, basically, for… for this, what it needs is… is to… to prove the, from the target table, it has to prove this… this section of entries with a Mercer prEOF, so that would be a witness for the, for, for the private input of the CK prEOF.
Zsolt Felföldi:And, it also has to prove the corresponding, parts from the… from the two, merged tables, smaller, tables that are being merged. And,
Zsolt Felföldi:Also, like, in this example, this first entry is 33, so in the left small table, we do have the 33 entry, but in the other one,
Zsolt Felföldi:We also have to, prove, like, one entry before that, in order to prove that before 36, there's no 34, or something like that.
Zsolt Felföldi:And also, at the end, like, the last entry we want to prove is 48, and in the left, smaller table, like, upper left table, we also have to prove the next entry. But basically, we only need to prove, at most, one extra entry at the
Zsolt Felföldi:Each end of the proven section. So, basically, we… we… we have to… have to provide a,
Zsolt Felföldi:Merkel prEOF of, of, of, of the merge sections, and… and that's…
Zsolt Felföldi:So, so that's how we would prove a single slice.
Zsolt Felföldi:And, but also, we somehow have to, like, recursively merge these things together, and not just single tables.
Zsolt Felföldi:So, like, this is… this is kind of similar to… what I, yeah…
Zsolt Felföldi:ruin my, my, my, my presentation slides. So, in this case, we have, we have, we have, so in this drawing, the smallest tables, these, these little blue rectangles are, are the 64 block tables that are, generated in protocol, and, basically.
Zsolt Felföldi:We want to merge these further together, so…
Zsolt Felföldi:somehow I would like to construct the prEOF in a way that, once… so, for example, once we have, like, this, so this is… this… this prEOF somehow already proves that, that,
Zsolt Felföldi:These are the, the, like, we have, we have, we have, we have the 128 block, tables, and 256 block tables, and so on, and… and this is, this is… these are all…
Zsolt Felföldi:basically chain hashed together, so they can be proven. So, so this, this would be pretty much a similar, similar structure than what the consensus has, it's just, yeah, so this is, this would be the… the public part of the prEOF, that the prEOF actually proves, that,
Zsolt Felföldi:And the reason the button tables are different, they are called the reference table chain, that's why they are blue, is that, in every prEOF, so this would be the assumption, and the prEOF would prove that if these tables
Zsolt Felföldi:are… have the certain hash, which we can verify from consensus, then the bigger tables.
Zsolt Felföldi:R, this, and this, and this.
Zsolt Felföldi:the merged version of the same thing. So this is how it would look.
Zsolt Felföldi:And also… Like, this would be a partial prEOF.
Zsolt Felföldi:So when we are merging a bigger table, then we should somehow be able to also represent when
Zsolt Felföldi:So, in this case, the reference table chain would be probably, Certainly. Even, like…
Kevaundray Wedderburn:Yes? Sorry, I think I missed something on the previous slide.
Kevaundray Wedderburn:Yes?
Kevaundray Wedderburn:So…
Kevaundray Wedderburn:Yeah, the second and third row, so the block count is 0x200, and the last blocks… the last block is 0xFFF.
Kevaundray Wedderburn:And the block count is 0x800, and the last block was 0XFFF. I don't understand why we have these two…
Zsolt Felföldi:Okay, oh, yeah, yeah, yeah, maybe, maybe, yeah, I wrote that those for a reason, so maybe I should also, yeah, explain those. So, yeah,
Zsolt Felföldi:In this case,
Zsolt Felföldi:we… I… I… so we should also store in the prEOF that, that, what is the last block, and… so basically, basically, the block count is… I used hacks so that, yeah, it's just easier to see how it doubles and everything, but,
Zsolt Felföldi:Yeah, maybe, maybe, yeah, I messed up one of the block counts, so in the second row, the block counts should be 0x400, but anyway, so it should double from, like, like, 40, 80, 100, 200, 400, 800 as we go upwards. So, yeah, they, they are, like, always double in size.
Zsolt Felföldi:And, well, the last block is… Now…
Zsolt Felföldi:it… I mean, the whole indexing starts at a certain block.
Zsolt Felföldi:probably, like, when, when, like, the EIP that generates the 64 block tables gets activated, then we can just call that,
Zsolt Felföldi:So, so that's, that's, that's, that's, that's where, where, where the indexing
Zsolt Felföldi:with the IP7708, which also generates the logs for ET transfers and everything. So, yeah, so that's going to be a whole other story, and for…
Zsolt Felföldi:simplicity… In this case, we only care about, like, the post-EIP activation chain, and
Zsolt Felföldi:And… and… but here, I just assumed that, that, the indexing starts at block 0. So, for example, like…
Zsolt Felföldi:Yeah, like, at the highest table, which is… the block count is 800, so it starts from 0, then the last block is 7FF.
Zsolt Felföldi:Logically, and also, in, below that, yeah, the block count should be 400 in the second row, and 4 times 400 is… is 1000, but yeah, so the last block is 1000 minus 1, so FFF.
Zsolt Felföldi:And, yeah, this is just…
Zsolt Felföldi:Just to… so, and in the consensus, there's, so in the protocol for those four table chains, we always exactly know which is the last one, because there's… there are protocol rules to when to
Zsolt Felföldi:Add the new table hashes to each chain.
Zsolt Felföldi:But, in case of, like, these higher tables and ZK prEOFs,
Zsolt Felföldi:we should be a bit more flexible, because, yeah, it… all of this happens asynchronously, so… yeah, we should just store it also in the proven data structure, what is the last block? And also.
Zsolt Felföldi:Yeah, also, just probably store the block count too, because…
Zsolt Felföldi:yeah, we… we should not set it in stone how many chains we should have. We could be adaptive, and… yeah, anyway, so this is…
Zsolt Felföldi:This is why we have block count and last block for every chain of index tables.
Zsolt Felföldi:Yeah, so, so, so the… And the way these new tables would be constructed.
Zsolt Felföldi:So this is this, this, this last slide. So, so first, we would, we would start to merge together two tables. So, one of them is, like, I just switched back, so this is the second row, these, 4 times 400 block.
Zsolt Felföldi:Tables, and here, they are the blue ones, because they are used as reference, because the 800 block table is being merged from two 400 block tables.
Zsolt Felföldi:And… and only a certain section is being merged, but so this is… this is something that also has to be
Zsolt Felföldi:Represented in the… in the… in the prEOF.
Zsolt Felföldi:And, and in this case, I don't want to, enforce to prove the entire state of the other table chains, because recursively proving… so recursively verifying,
Zsolt Felföldi:An existing prEOF also has a significant cost, so… why? So it's probably better to not…
Zsolt Felföldi:start with merging it into every, every, every small prEOF, every partial prEOF, but first do this partial prEOFs, merge them together, and when we have a full table, then we can, merge them to the big, big thing. But I want to… so this is this example.
Zsolt Felföldi:I just wanted to show that the data structure can be… so the way I specified it, and I will also show, like, some drafted specifications soon.
Zsolt Felföldi:So this is, like, it can show… it can store any number of food tables, and also.
Zsolt Felföldi:like, it can, it can, it can also,
Zsolt Felföldi:partially proven tables, and they can be merged in any combination. Even multiple sets of food table chains can be merged together. If in one prEOF one table chain is proven further, and in another prEOF another table chain is proven.
Zsolt Felföldi:Further, and this is because… so this, so this prEOF, so generating these prEOFs for the large blocks, this will be probably
Zsolt Felföldi:big effort for one prover, but, but, but, for many provers. So, so I, I wanted to…
Zsolt Felföldi:actually what I wanted to achieve is that, even… the… so the…
Zsolt Felföldi:the work… all these works can be merged together, even if we don't have absolutely perfect coordination. So, yeah.
Zsolt Felföldi:and… and this is pretty much what I want to achieve.
Zsolt Felföldi:And also, the way I started to…
Zsolt Felföldi:specify this. I, I really, really didn't…
Zsolt Felföldi:So this is… this is really… just should be considered a draft, but
Zsolt Felföldi:here it is. So I just started to write these type definitions and verifier functions in Go, because, yeah, I can… I'm familiar with Go, probably we will have to… I will have to rewrite this in Rust.
Zsolt Felföldi:Or, yeah, yeah, probably Rust, I guess, but, the way I imagine this, so this is, like, in my table-prEOF branch.
Zsolt Felföldi:In gologin deux table prEOF.go, it doesn't really do anything, this is really, really just, just some…
Zsolt Felföldi:code, go-code-shaped specification.
Zsolt Felföldi:So, the table prEOF.
Zsolt Felföldi:We consist of a public and private part, and so the public part, the thing that is being proven, is a set of, or list of table chains.
Zsolt Felföldi:And the table chains are represented by the head, so as I've shown in the drawing, block count, last block, and the head hash. So these table chains are hashed in a way that each table has a table root.
Zsolt Felföldi:which is the Mercker root of that list of entries, and, and the tables are chain hashed, so they had…
Zsolt Felföldi:previous head hash is hashed together with the new table root, and that's the new table chain add hash. So, yeah, that's…
Zsolt Felföldi:That's how I imagine this. And so, yeah, we do have a list of… list of completely rendered and proven tables, and we can also… and or we can also include partial tables.
Zsolt Felföldi:Yeah, and in this table chains list, the first one is always the reference, so that's also a rule, because we can only merge upwards, so yeah, it's obvious, and we always need one reference, so… so table chain 0 is always the reference, and even if we are just merging partial tables, we do have, like, the one reference chain.
Zsolt Felföldi:And the partial tables are, yeah, they also have block count and last block, and they already have the table root, because the prover already knows the table root in advance, it's just… it's, like, partially proven.
Zsolt Felföldi:It also, yeah, has the full entry count of the table.
Zsolt Felföldi:And, this, this, these proven ranges, this range set, it's basically
Zsolt Felföldi:a subset of 0 to entry count minus 1. It can… can be, like, a continuous range, or… or multiple continuous ranges, but yeah, it's… it's… it's just a subset.
Zsolt Felföldi:of, of the… Proven entries of the table.
Zsolt Felföldi:So this is basically what I want to prove, and then this is the private part, like, the witness is how we prove it.
Zsolt Felföldi:So, they would conti- Optionally, they could contain,
Zsolt Felföldi:Recursive prEOFs, which would be the same type of prEOF.
Zsolt Felföldi:just… Zip.
Zsolt Felföldi:Proven stuff is being merged together.
Zsolt Felföldi:Well, there's this stable root prEOFs that's just a technical thing, so… because the public-public part only proves the chain head, and for example, for merging together.
Zsolt Felföldi:Multiple tables, we do need the individual… last few individual table roots, so these table root prEOFs can prove the last few table roots.
Zsolt Felföldi:Of any of the table chains.
Zsolt Felföldi:And there's the merge prEOFs, which is the actual thing.
Zsolt Felföldi:actual, actual merging of, of table sections, and yeah, let me just scroll down a bit.
Zsolt Felföldi:So yeah, the entry is just defined as a 64 byte, so here in this miracle prEOF, we really don't need to care about the internal structure of the entries, because they are just simple lexicographical ordering.
Zsolt Felföldi:And, where's the merge?
Zsolt Felföldi:Oof, yeah.
Zsolt Felföldi:Table Merced prEOF.
Zsolt Felföldi:Yeah, here's it.
Zsolt Felföldi:Oh, oh yeah.
Zsolt Felföldi:So, yeah, the table merge prEOF is… is, consists of table range prEOFs, and the table range prEOF is…
Zsolt Felföldi:yeah, basically there's the entry count, and the first entry, and the number of entries fully stored, and the left and right side Mercer branches. So, yeah, it can be… so this can be verified against the table root.
Zsolt Felföldi:And, yeah, for the merge prEOFs, we have multiple ones for the input.
Zsolt Felföldi:The smallest tables being merged, and one for the output.
Zsolt Felföldi:is being proven.
Zsolt Felföldi:And, yeah, so this is pretty much, I, yeah, there's also some code of how it works, and I don't really want to just go into those now, I even have to work a little bit on documenting those, but yeah.
Zsolt Felföldi:So… so this is… this is my idea of how those prEOFs would work, and now I…
Zsolt Felföldi:will just need some input on whether this whole idea is workable, could the prEOFs be implemented in this way, or am I just thinking something completely wrong?
Zsolt Felföldi:So…
Kevaundray Wedderburn:Oops, sorry. Yeah, so I might need a bit more time to catch up on the general…
Kevaundray Wedderburn:log index structure to see if anything's, fully changed from when I last looked at it. But from the ZK part, the prEOF that you mentioned, I think it all makes sense. The recursive prEOF part,
Kevaundray Wedderburn:Hmm…
Kevaundray Wedderburn:Yeah, I guess it's unclear if you do need it, to be honest. Depends on how big the input is, because ZKVMs also do a sort of recursive prEOF internally. If the thing being proven is, like, too big, it would, like, break it up internally.
Kevaundray Wedderburn:Okay.
Zsolt Felföldi:So how much is too big? Like, for example, if… so the inputs are, like, let's assume, at most, like,
Zsolt Felföldi:Like, it could be, like, 100 gigabytes, so that's probably too big for a single prEOF.
Kevaundray Wedderburn:Right, right. Yeah, I mean, too big hair just means,
Kevaundray Wedderburn:how much your hardware can handle, essentially, because the circuit for ZKVMs has, like, a limit, let's just say…
Kevaundray Wedderburn:100 million cycles.
Kevaundray Wedderburn:So you can always break down your prEOF into, like, chunks of a hundred… sorry, you can always break down your program into chunks of 100 million cycles, and it's just on, can the hardware do it, and can the hardware do it in a reasonable amount of time?
Kevaundray Wedderburn:So I think it depends. There might be other memory limits that I can't remember for, like, certain ZKVMs, but I think in general, it's unclear if you do need the recursive prEOF part.
Zsolt Felföldi:Well, so one reason I might need the recursive prEOF is that even if, if, if, if it… so maybe, maybe, maybe for most of the tables, proving one table maybe could be done in a single prEOF, but the thing is that, we have, like, this… let's just…
Zsolt Felföldi:Yeah, somewhere. So, in the end, this is what I want to achieve. I want to… so I… I don't want, like, 30 prEOFs for all the different chains, so there's going to be, like, lots of…
Zsolt Felföldi:these chains, and they will all keep changing, and and I don't want to redo all the work, like, re-prEOF everything every time, so every time I will… I just want to do a prEOF of
Zsolt Felföldi:of merging two head tables into a bigger one, and two head tables into a bigger one at a higher level, and… and… and… and I want to aggregate this knowledge. So that's the way I understand it, so that's done with recursive prEOFs.
Kevaundray Wedderburn:Yeah, exactly. Yeah, I mean, if that's the constraint that you have, then I think the recursive prEOF approach works.
Zsolt Felföldi:Yeah, by the way, is there any difficulty with the recursive prEOF? So, is it… is it does… does it… is it, like, an extra thing that needs some… some special tools, or… I don't know.
Kevaundray Wedderburn:Not really, some teams have implemented it. I'm not sure if every, team
Kevaundray Wedderburn:has implemented it and applied… and gives you an API for it, because you need recursive prEOFs, but you also need to be able to access it in the Rust or Go program as well. Like, you need to have, like, a verify prEOF method.
Kevaundray Wedderburn:And I'm not super sure that everyone exposes it. Everyone ha- everyone roughly has it because of the… the idea I talked about where you need to, like, chunk, the program into, like, 100 million cycles, but this is an internal thing, so,
Kevaundray Wedderburn:I think, yeah, the only… Downside might be that not everyone has it.
Kevaundray Wedderburn:oh, sorry, not everyone exposes it.
Kevaundray Wedderburn:But… Yeah, I'm trying to think who doesn't, hmm…
Kevaundray Wedderburn:Yeah, let me get back to you, I'd have to double-check.
Zsolt Felföldi:Okay, yeah, yeah, this is not something, I expect you to answer right now, but, so I'm just, just, just wanted to present that these are my… this is my problem, and this… this is… this is what I will need some help with.
Zsolt Felföldi:And yeah, so, or actually, you already sent me this, this, this example of this succinct, succinct, demo, and I did, like.
Zsolt Felföldi:Try that, and ran the demo, and yeah, it looked really cool that it can…
Zsolt Felföldi:prove the, like, Fibonacci numbers.
Zsolt Felföldi:And I also tried to understand a little bit the other examples, and I… even there, I saw some… some recursive,
Zsolt Felföldi:PrEOF examples.
Zsolt Felföldi:So, I'm not sure, which
Zsolt Felföldi:To… tool chain, and which technology would you recommend right now?
Zsolt Felföldi:Or, or, or, or this is also something that… is, it's like… Depends.
Kevaundray Wedderburn:Right. Yeah, for ZKVM, at least the optional prEOFs, or EIP8025, we have, like, a framework that we've applied on top of the ZKVMs.
Kevaundray Wedderburn:Which means that you can sort of abstract away each, ZKVM, That you're dealing with?
Kevaundray Wedderburn:So I can paste a link to that… Air…
Kevaundray Wedderburn:In that sense, I think…
Kevaundray Wedderburn:all of the technologies probably work as good. The only issue that you'd probably have is that most of them
Kevaundray Wedderburn:work with, like, low-level languages, so Go might not be… a feasible…
Kevaundray Wedderburn:Alternate feasible, language to…
Zsolt Felföldi:yeah, it's not such a big problem, so right now, I kind of implemented this thing, and maybe I need to publish a little bit, but the whole thing is, like, for… with comments and everything, 400-something lines of pure code, so it shouldn't be very hard to implement it in any language, so that's not really a big constraint.
Kevaundray Wedderburn:Okay.
Kevaundray Wedderburn:And… just pasting it in the chat.
Kevaundray Wedderburn:So this is what we use,
Kevaundray Wedderburn:Just pasted it in the chat.
Kevaundray Wedderburn:And…
Zsolt Felföldi:Let's just allow the extract away.
Kevaundray Wedderburn:Yeah, so, yeah, I mean, I don't suggest any particular toolchain at the moment. If you're, like, still experimenting and trying to check what works. I'd probably suggest to use this, or if you're familiar with Sysynct already, then maybe just continue using that, and then…
Kevaundray Wedderburn:Once you want to productionize it, we can abstract away the succinct, particular details.
Zsolt Felföldi:Yeah, actually, I'm not super familiar, I just, yeah, try the demo and try to just understand what I really need to…
Zsolt Felföldi:Lou, but, yeah, so… And by the way, so, this is another thing I wanted to ask, is, so there's…
Zsolt Felföldi:That sounds… one thing what I understood from Succinct was that, it can, generate, like,
Zsolt Felföldi:like, big prEOF starks, which are, like, around a megabyte or something, so… so they are… they are kind of big, and for… and if you want to… if I want to, verify these prEOFs on-chain, which I don't necessarily want to do.
Zsolt Felföldi:maybe… maybe the prEOFs can just be transmitted to the clients, and they can verify it themselves, so these prEOFs don't… I'm not sure if, it's worth,
Zsolt Felföldi:verifying them on-chain, but there's an… there's an alternative, some other prEOF system, which is probably SNAC, if I understood correctly, which is, like, really small, like, hundreds of bytes.
Zsolt Felföldi:So…
Zsolt Felföldi:what is the main difference between these? Is it, like, quantum security, or… or why are these… why are they there, like, very large and smaller prEOFs… prEOF systems?
Kevaundray Wedderburn:So, so yeah, the… yeah, as you notice, there's, like, a Stark proving system and a SNARC one. The Stark one basically has a log… it scales logarithmically in the complexity of the thing you're proving, roughly.
Kevaundray Wedderburn:So it's about 1MB. We can probably get it down to 300 kilobytes or less, but it means prover time, it takes longer to prove the thing.
Kevaundray Wedderburn:The benefit of this, stark prEOF is that it is post-quantum safe. It basically just relies on hashes.
Kevaundray Wedderburn:the SNARC approach, which is a GROF16 or Plonk, their prEOF sizes are roughly constant.
Kevaundray Wedderburn:So it's gonna be, like…
Kevaundray Wedderburn:Maybe, like, 1 kilo… I can't remember GROF16, but, like, 1KB, or maybe even less, for Graph 16.
Kevaundray Wedderburn:The annoyance with Graph 16 in particular is that it is circuit-specific, meaning you're gonna need to do a,
Kevaundray Wedderburn:this thing called a trusted setup per circuit, so you probably just don't want to use it, but succinct probably has a Planck proving system somewhere.
Kevaundray Wedderburn:And those prEOF sizes are a bit larger than graph 16, but you can think of them as also roughly constant. The disadvantage of this is just that it's not post-quantum.
Kevaundray Wedderburn:I think it's the Ganark-based punk one. I can't remember the prEOF sizes for succinct, but yeah, the main disadvantage there is that it's not post-quantum.
Kevaundray Wedderburn:I don't know, does that honestly?
Zsolt Felföldi:Yeah, so…
Zsolt Felföldi:Yeah, yeah, I think this is… this is… this is… well, mostly confirms what I understood from the documentations. Yeah, I just wanted to, like.
Zsolt Felföldi:No, for sure that I understand correctly, and I assume that, for, like, the future plans, like, like for Lin Ethereum, I guess, the, the, the, the execution proves those would be quantum secure, starts, right?
Kevaundray Wedderburn:Right, so, the plan is for them to be 300 kilobytes, initially, and then we're gonna go down to 128 kilobytes, and then that should be enough for the networking layer to handle.
Zsolt Felföldi:Alright, yeah, but for my use case.
Zsolt Felföldi:basically, these, these, these index tables, I mean, I mean, these, these index table prEOFs, if, if, if, if, like, every, I don't know.
Zsolt Felföldi:256 blocks, we would generate a new
Zsolt Felföldi:table merge round, so… so roughly, like, even if… if… if someone is willing to generate, a new prEOF for, like, as frequently as it makes sense, that would be, like, one new prEOF per hour or something. So for… for… for someone, like, who…
Zsolt Felföldi:for some client, it's… it's totally acceptable to just, download, even a several hundred kilobyte, stark, from the prover, like, every hour, if the… if there's a new prEOF. So, yeah, I think… I think,
Zsolt Felföldi:For my use case, probably…
Zsolt Felföldi:I can, I can, I can live with, with even, like, hundreds of kilobytes, or one megabyte,
Zsolt Felföldi:PrEOFs, and they don't necessarily have to… Go and chain.
Zsolt Felföldi:But… but if I want to do something on-chain, then… then I would have to… I mean, for some reason, I would have… I would want to verify a prEOF on-chain, that… that would have to be a SNAR, right?
Zsolt Felföldi:So… so stocks are not possible to verify on-chain. That would be too expensive, right?
Kevaundray Wedderburn:Yeah, currently it's pretty expensive, but, it's likely that if everyone moves to post-quantum, we're gonna have to put something… we're gonna have to change something to make it not as expensive.
Kevaundray Wedderburn:I don't know what the cost is right now, I believe Starkware probably does it currently.
Kevaundray Wedderburn:But I don't know how much they pay for their stock prEOF.
Zsolt Felföldi:Well, but I think, by the way, I also do have this, this idea that, yeah, maybe, maybe I also will show you this, because…
Zsolt Felföldi:Now that we are talking, this might be interesting for me. - wait.
Zsolt Felföldi:Did I open… New ones, it's not what I wanted.
Zsolt Felföldi:Okay, yeah, anyways, this is what I needed.
Zsolt Felföldi:So… yeah, this is… so this is… this is just this drawing that I have, like, like, for one of my talks.
Zsolt Felföldi:So, this, is something, the way I kind of, like, imagined… so this, this, this is, this is…
Zsolt Felföldi:This is how maybe transaction, could work in the future. So, so Vitalik already, like, wrote in this account, initial account, account abstraction EIP draft.
Zsolt Felföldi:that, that, certain pre-checks, like, like, like, like, authorization, signatures, witnesses, those could be, proven pre, with ZK, ZK prEOFs, before the, the transaction reaches, like, the, the mempool. So this…
Zsolt Felföldi:This is something like, for example, if we add witnesses to transactions, then the provers could create transaction batches.
Zsolt Felföldi:And, and, and, and basically, the witnesses wouldn't have to go into the…
Zsolt Felföldi:into the chain, and also additional ZK prEOFs could be, like, recursively mashed into one prEOF, or a few prEOFs. So,
Zsolt Felföldi:So, yeah, maybe, maybe it would be possible in the future to just…
Zsolt Felföldi:So I think, I think, I somehow assumed that, even for, for, for, like, post-quantum signatures, so those would be bigger than elliptical signatures. Probably, we would do something like this, and in the end, we would…
Zsolt Felföldi:Like, put, ZK prEOFs, like, in the… in the… in the input of the…
Zsolt Felföldi:rock building, too. So, yeah, maybe, maybe then, then putting extra prEOFs.
Zsolt Felföldi:So, so what I want to get at is that maybe if we can just verify, like, like, one or a few, starks, per block.
Zsolt Felföldi:Then, basically, we can verify as many as we want, as long as some provers are capable of doing recursive prEOFs.
Zsolt Felföldi:So, do you think, like, this is realistic?
Kevaundray Wedderburn:I think some of it is a bit TBD.
Kevaundray Wedderburn:So I can't say for a certain, right now. Though one question I do have is I don't understand what's happening with the first, prover column.
Kevaundray Wedderburn:So they get multiple transactions with witnesses, and these witnesses prove that the transaction is valid, or…
Kevaundray Wedderburn:Yeah, I guess.
Zsolt Felföldi:Well, yeah, so, so this is this, yeah, I just really quickly jumped into this without context, but, what I wanted to,
Zsolt Felföldi:One, prove with this, this, this drawing is that,
Zsolt Felföldi:witnesses, like, if we add witnesses to transactions that… that are basically, so verifying the witness has basically one bit of output, like, is the witness correct, or… no, no, it's not true, because we also have to add water witness prEOFs, but basically, if we have a large witness of
Zsolt Felföldi:Of, like, a state read.
Zsolt Felföldi:Then, then we can… Verify that witness off-chain, and the witness doesn't have to go to the chain.
Zsolt Felföldi:So that's what I wanted to prove here, and I… so the reason I wanted this is that, yeah, I… I also… this is another drawing where, so… so this… this is just a crazy idea of mine, that, with the new log index, but this is not something we should,
Zsolt Felföldi:get a conclusion on now, it's just, just the way I imagine…
Zsolt Felföldi:A possible future that, maybe we could also use… use the log index for, for,
Zsolt Felföldi:for, like, contract logic, and it… I think it would have some advantages. One of them is that it's
Zsolt Felföldi:my, according to my estimates, about 100 times cheaper to add an entry to the log index than to the state tree. So, yeah, so maybe, maybe for some applications, this would be viable, but the thing is that for the log index, the width size is not logarithmic, but log squared. So, yeah.
Zsolt Felföldi:putting the… putting… putting log index, witnesses on-chain, is… would be probably expensive, but maybe if we can just do this, that, we, we, we, we take the… these witnesses.
Zsolt Felföldi:And, I mean, like, this, this analog index widthness can be something like 50 or 100 kilobytes, so, like, like, kind of big. But, but if we just,
Zsolt Felföldi:prove the… ZK approved the verification of these witnesses, then maybe they could be also proven on-chain. So yeah, this is… this is this…
Zsolt Felföldi:This is something that, maybe, yeah, we can discuss at a later point, but, but this is just my latest idea of a future use case for the log index.
Zsolt Felföldi:It's not something that I need now for the current use case. I'm just thinking about…
Zsolt Felföldi:That, once we can afford to have, like, like,
Zsolt Felföldi:one Stark, or a few Starks in a block, then we can have basically as many Starks and witnesses in a block as we want, and it will have a cost, prover cost, but it will not have an extra on-chain cost. So that's my assumption.
Kevaundray Wedderburn:Do you think this can be true?
Kevaundray Wedderburn:I think it can be true.
Kevaundray Wedderburn:I probably need to think a bit more before I say anything, like, actually.
Zsolt Felföldi:Yeah, yeah, alright.
Kevaundray Wedderburn:In case I'm missing, some details here.
Zsolt Felföldi:Yeah, yo.
Zsolt Felföldi:Anyway, this is just, just something I wanted to…
Zsolt Felföldi:Quickly show, but, anyways, if we know, yeah, we can just first focus on, on, on, on…
Zsolt Felföldi:Finding a suitable,
Zsolt Felföldi:prEOF system to just prove the table merging, so that's… that's the highest priority. And, so yeah, this is the link, and yeah, I will… I will definitely check this out, and yeah, I think, I think,
Zsolt Felföldi:I know most of what I wanted to know. I have my answers. Actually, there's one more thing, there's one more thing, which will probably be a simpler one. So,
Zsolt Felföldi:I… I was thinking about the hash function, because, so there's… there's…
Zsolt Felföldi:the hash function I use for tree hashing the tables, because these tables, generating them and verifying them.
Zsolt Felföldi:The cost of it is… will mostly be hashing cost.
Zsolt Felföldi:And it would be nice to have a hash function that's reasonably efficient on a CPU, so, like, the table generation is also efficient, but also it's reasonably efficient for…
Zsolt Felföldi:for the… for the… for the ZK prEOFs. Someone suggested Poseidon 2, which I never used, but…
Zsolt Felföldi:I don't know… Well, maybe if you have a suggestion for hash function that… That would also be useful.
Kevaundray Wedderburn:I would probably just start off with Ketchak, just because each ZKVM has,
Kevaundray Wedderburn:like, accelerators for things like Ketchak, because when you prove an Ethereum block, you potentially do a bunch of Ketchaks already. So I'd probably start with Ketchak and see what the worst cases are, before, like, going to something a bit like Poseidon, which is, I guess, less,
Kevaundray Wedderburn:It's… it's less, I guess, Lindy, or, like, Ketchak is pretty…
Kevaundray Wedderburn:it's pretty a safe choice if you put it into, like, the consensus algorithm, or in Ethereum at the moment.
Kevaundray Wedderburn:So I'd probably start with that and see what the worst cases are, and then if it's, like, too bad, then switch to something like Poseidon.
Zsolt Felföldi:Okay, so, so, so, so, so Ketch might be reasonable, in a ZKVM, you say.
Zsolt Felföldi:Okay. Also, by the way.
Kevaundray Wedderburn:Yeah.
Zsolt Felföldi:So right now, I started using, actually, not… so Catchback is SHA3, but I started using SHA2, which is, for CPU, it's, like.
Zsolt Felföldi:3-4 times faster. So, is it also efficient on the heavy AM, or catch-up is better?
Kevaundray Wedderburn:I think it depends on how they've accelerated it, but usually they have SHA-2 accelerators as well.
Zsolt Felföldi:Okay, so… so SHA-2 or SHA 3 might be a good choice to start with.
Kevaundray Wedderburn:Right, but you need to sort of use the accelerator, version of it.
Zsolt Felföldi:Okay, and what, yeah, so, so, so yeah, obviously, I, I don't…
Zsolt Felföldi:you have to prove the execution trace of, like, the dump, implementation of the hash function. But, so how do these… how…
Zsolt Felföldi:do these accelerators work? If I read this link, is in this framework, is there something for hash acceleration included?
Kevaundray Wedderburn:In that link in particular, no, but roughly how they work is that you have, like, a particular circuit for Ketchak, so you implement catch-ac as a circuit.
Kevaundray Wedderburn:And whenever the Rust program calls Ketchak, instead of calling your normal catch-acc dependency, you have a particular mechanism for calling this circuit instead.
Kevaundray Wedderburn:so the naive way is to prove, like, the execution, all the, the naive dump of, like, Ketchak, which is, like, a bunch of RISC-V instructions, but the smart way is to call this accelerator, just like how CPUs have, SHA-2 accelerators, for example, or AES accelerators.
Kevaundray Wedderburn:You just need to know how to call it, and at the moment, each ZKVM has a different calling mechanism, but we've just standardized it, so they should be implementing the standardization soon.
Kevaundray Wedderburn:With the standardization, they're basic… you basically just need to call a C header, and then you're done.
Kevaundray Wedderburn:But… And sender…
Kevaundray Wedderburn:I don't know if that makes sense, so let me know…
Kevaundray Wedderburn:Can you hear me? Oh, one sec.
Zsolt Felföldi:Yes, yes, okay?
Kevaundray Wedderburn:Yes, yeah.
Kevaundray Wedderburn:So yeah, basically, you just need to know how to access those accelerators.
Kevaundray Wedderburn:I can probably talk to you about it offline for when you do get to it, but the ZKVMs usually provide a library that does all of the Excel… that does the access in itself, so you just call it like a regular library, and it won't do the naive thing, it will do the smart thing.
Kevaundray Wedderburn:But I can definitely talk to you about it off… offline.
Zsolt Felföldi:Okay, yeah, so, yeah, ATPL definitely needs some pointers to, yeah, implement this logic in a provable way, but, okay, so, so for now, the important thing is that
Zsolt Felföldi:So this should be possible, basically, yeah, so all those things that I need is… yeah, so I do need recursive prEOFs, and I do need hash acceleration, and yeah, that's pretty much…
Zsolt Felföldi:what I need…
Kevaundray Wedderburn:Yeah.
Kevaundray Wedderburn:But you can do it in two separate steps, right? Like, the recursive prEOF is, like, a separate program you can think of.
Kevaundray Wedderburn:That just does the merging.
Kevaundray Wedderburn:Of prEOFs, whereas you have your core logic that just, does this table indexing.
Kevaundray Wedderburn:So it's, like, two days.
Zsolt Felföldi:Wait.
Kevaundray Wedderburn:rooms.
Zsolt Felföldi:Oh, so, so, so you're saying that I shouldn't mix these two logics together?
Kevaundray Wedderburn:Yeah, I think it might be easier to separate it, as in you have your core logic, and then you have a thing that takes in, let's say, two prEOFs, and just merges them together, so all it does is just prEOF merging.
Zsolt Felföldi:Ice…
Zsolt Felföldi:So, so, like, I would have, like, two, verifier functions, and one of them would just have these, these, these Mercker prEOFs as, input, this index antimer prEOFs, and the other one would just have the…
Zsolt Felföldi:The recursive prEOFs as input.
Kevaundray Wedderburn:Right, right, exactly.
Zsolt Felföldi:And…
Zsolt Felföldi:Okay, okay, let's maybe, yeah, simplifies things a bit.
Zsolt Felföldi:But still, like, if I merge together ZK prEOFs, like, recursively, I still need to somehow access the public part of those prEOFs, so that I know what…
Zsolt Felföldi:what, content time merging together, so… but I guess that should be possible.
Kevaundray Wedderburn:Right, right. Yeah, you just make it a public input, and it should come with the prEOF. You can think of it as…
Zsolt Felföldi:Yeah, well, I… pretty much how I imagined it. Anyway, so yeah, this is…
Zsolt Felföldi:this is… so yeah, this would be the public input, either full table chains or partially proven tables. And, yeah, so basically, I would have one function that takes two of these.
Zsolt Felföldi:And,
Zsolt Felföldi:somehow we also assume that the prEOF part would be requestively verified, but yeah, so what I need to care about is merging two of these together.
Kevaundray Wedderburn:Right?
Kevaundray Wedderburn:Right, right, exactly.
Zsolt Felföldi:Okay, and the, in the other, other, other case, yeah, generating, this from, from, like, the…
Zsolt Felföldi:three prEOFs. So, yeah, okay, I, I will, I will read, read, read upon, on the links you sent, and,
Zsolt Felföldi:And yeah, let's… let's continue this offline. But yeah, this was really useful, and I think we already…
Zsolt Felföldi:Past 1 hour or so, yeah.
Zsolt Felföldi:Okay.
Kevaundray Wedderburn:Sure, thanks.
Zsolt Felföldi:Yeah, it was really useful, so yeah, thank you very much.
Kevaundray Wedderburn:Okay.
Kevaundray Wedderburn:No worries. Alright, see you, Joel. Thank you.
Zsolt Felföldi:Okay, thank you, see you, bye-bye.
Chat Logs
Summary
10 highlights
· 2 action itemsExperimental
Summary
10 highlights · 2 action itemsExperimentalzkp architecture
- Index tables generated synchronously per block, merged asynchronously into bigger tables00:07:40
- Protocol will hash only up to 64-block tables; larger tables proven off-chain00:12:40
- Full history lookup estimated at 40KB proof size with log-squared complexity00:15:22
- Recursive proofs needed to aggregate work from multiple provers without perfect coordination00:26:00
implementation approach
- Draft specification published in Go; will need Rust rewrite for production00:29:20
- ZKVM can internally handle recursive proofs; unclear if all expose public API00:35:19
- SHA-2 or SHA-3 recommended as starting point; ZKVMs have accelerators for both00:56:36
- Separate proof logic: core table merging vs recursive proof aggregation01:00:09