Trustless Log Index Breakout #3

Transcript

Zsolt Felföldi: Hello?

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. And, and, and yes, I, I will, also present, there's this EF Day, on, on Thursday at Denver, so, yeah. I will also do… Oh, that's moved there, so yeah.

Tamaghna Choudhuri: Yeah, Lynn, did you get any, 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… Paying attention to this, because, like, it's, like… fairly technical, so, like, I think, 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. From, from various areas, and EOF. 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, harder for them to approach, but, yeah, at a certain point, it would be…

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. It's great that you could come. So… Cool. Oh. Alright, so, I think… Yeah, now it's 5 minutes plus 4… Or so, maybe we can even… start, and lah, yeah. Maybe someone else will join you later, but… 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… what… yeah, just to give some context, so first I will turn on… screen share… And… Says Desktop 1. Okay. So, you should be able to see my screen now. So, yeah, I will just use my, my, my Eat Border slides now. So, can you see? See my screen?

Kevaundray Wedderburn: Yeah.

Zsolt Felföldi: Alright, alright. So, so… This, this, so there's this, there's this, 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… show what it's about. So, basically, 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, 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

Like, either a single block or a… Certain number of blocks, and and… and the way they are generated is that, 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. Are merged together into bigger tables, so that's there. 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… later, bigger tables. So in this design, we merged, like, four single block tables into like, this second row at the… from the bottom, these tables are… represent, like, four blocks, and then there's another,

Chain of tables that is… is… each table, represents 16 blocks and then 64 blocks. 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. 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, And, and 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.

So it can be at the events of single block, or in this case, this is the events of multiple blocks. 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. So… 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 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

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. 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. There's these four red lines, these are the proven entries, and we, for example, if we want to prove 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

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 And I already implemented these tables in GoEthereum, and they are super fast to search, and yeah, so, this could be very nice, 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, Hash in a chain of single block tables, four block tables, and up to 64 block tables, but not bigger ones, because

Because… because with this design, it's, it's guaranteed that the block builders and validators only need the last 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… too high demand on every participant of the protocol to… for them to process tables of, I don't know. 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. And, yeah, so there's this… 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.

But so, so, 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. And so, yeah, it's… I think this is… this is… this could be a really good balance to just, Like… do a little bit of processing in protocol, and basically use the same data structures, just prove them, prove them with ZK prEOFs. for, for, like, bigger, bigger tables, and… And, in the end, we would have kind of, yeah, so this, this is this… 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.

So… 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. 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… very good. It's just… so the only, only, 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. And let me just open… now, these are not really good slides, this is just some drawings I did for today, and… oh, yeah.

Anyway, yeah. So, wait… Yeah, that… okay, okay, this is the right one. So basically, This, this, this first drawing here, these, 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, 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, Merging two tables works, so these numbers are the same here and here, and at the bottom row, they are merged into single Single, single, singles table, and and what I want to achieve is that,

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, 20-something billion entries. And, these… these don't all have to go into a single table, but, But, but, but at the, like, the older history would certainly, beef. built off. like, billions of entries, so… so, probably this is not provable with a single execution trace. That would be too expensive. So I wanted to design this thing in a way that, that even a single table can be proven recursively, slice by slice. And, so this… this is what this example is… tries to show. So, basically, what we… the way… 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.

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… 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. And, it also has to prove the corresponding, parts from the… from the two, merged tables, smaller, tables that are being merged. And, 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,

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. 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 Each end of the proven section. So, basically, we… we… we have to… have to provide a, Merkel prEOF of, of, of, of the merge sections, and… and that's… So, so that's how we would prove a single slice. And, but also, we somehow have to, like, recursively merge these things together, and not just single tables.

So, like, this is… this is kind of similar to… what I, yeah… 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. We want to merge these further together, so… 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, 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…

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, 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 are… have the certain hash, which we can verify from consensus, then the bigger tables. R, this, and this, and this. the merged version of the same thing. So this is how it would look.

And also… Like, this would be a partial prEOF. So when we are merging a bigger table, then we should somehow be able to also represent when 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. Yes? So… Yeah, the second and third row, so the block count is 0x200, and the last blocks… the last block is 0xFFF. 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, In this case, 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, 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.

And, well, the last block is… Now… it… I mean, the whole indexing starts at a certain block. probably, like, when, when, like, the EIP that generates the 64 block tables gets activated, then we can just call that, So, so that's, that's, that's, that's, that's where, where, where the indexing 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… simplicity… In this case, we only care about, like, the post-EIP activation chain, and And… and… but here, I just assumed that, that, the indexing starts at block 0. So, for example, like…

Yeah, like, at the highest table, which is… the block count is 800, so it starts from 0, then the last block is 7FF. 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. And, yeah, this is just… 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 Add the new table hashes to each chain. But, in case of, like, these higher tables and ZK prEOFs, 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.

Yeah, also, just probably store the block count too, because… 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… This is why we have block count and last block for every chain of index tables. Yeah, so, so, so the… And the way these new tables would be constructed. 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. 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.

And… and only a certain section is being merged, but so this is… this is something that also has to be Represented in the… in the… in the prEOF. 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, An existing prEOF also has a significant cost, so… why? So it's probably better to not… 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. 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.

So this is, like, it can show… it can store any number of food tables, and also. like, it can, it can, it can also, 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. Further, and this is because… so this, so this prEOF, so generating these prEOFs for the large blocks, this will be probably big effort for one prover, but, but, but, for many provers. So, so I, I wanted to… actually what I wanted to achieve is that, even… the… so the… the work… all these works can be merged together, even if we don't have absolutely perfect coordination. So, yeah.

and… and this is pretty much what I want to achieve. And also, the way I started to… specify this. I, I really, really didn't… So this is… this is really… just should be considered a draft, but 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. Or, yeah, yeah, probably Rust, I guess, but, the way I imagine this, so this is, like, in my table-prEOF branch. In gologin deux table prEOF.go, it doesn't really do anything, this is really, really just, just some… code, go-code-shaped specification. So, the table prEOF.

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. 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. which is the Mercker root of that list of entries, and, and the tables are chain hashed, so they had… previous head hash is hashed together with the new table root, and that's the new table chain add hash. So, yeah, that's… 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.

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. 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. It also, yeah, has the full entry count of the table. And, this, this, these proven ranges, this range set, it's basically

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. of, of the… Proven entries of the table. So this is basically what I want to prove, and then this is the private part, like, the witness is how we prove it. So, they would conti- Optionally, they could contain, Recursive prEOFs, which would be the same type of prEOF. just… Zip. Proven stuff is being merged together. 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. Multiple tables, we do need the individual… last few individual table roots, so these table root prEOFs can prove the last few table roots.

Of any of the table chains. And there's the merge prEOFs, which is the actual thing. actual, actual merging of, of table sections, and yeah, let me just scroll down a bit. 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. And, where's the merge? Oof, yeah. Table Merced prEOF. Yeah, here's it. Oh, oh yeah. So, yeah, the table merge prEOF is… is, consists of table range prEOFs, and the table range prEOF is… 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.

And, yeah, for the merge prEOFs, we have multiple ones for the input. The smallest tables being merged, and one for the output. is being proven. 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. So… so this is… this is my idea of how those prEOFs would work, and now I… 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? So…

Kevaundray Wedderburn: Oops, sorry. Yeah, so I might need a bit more time to catch up on the general… 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, Hmm… 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. 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, 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, how much your hardware can handle, essentially, because the circuit for ZKVMs has, like, a limit, let's just say… 100 million cycles. 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? 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… 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… 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

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 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. 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, I think, yeah, the only… Downside might be that not everyone has it. oh, sorry, not everyone exposes it.

But… Yeah, I'm trying to think who doesn't, hmm… 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. And yeah, so, or actually, you already sent me this, this, this example of this succinct, succinct, demo, and I did, like. Try that, and ran the demo, and yeah, it looked really cool that it can… prove the, like, Fibonacci numbers. And I also tried to understand a little bit the other examples, and I… even there, I saw some… some recursive, PrEOF examples. So, I'm not sure, which To… tool chain, and which technology would you recommend right now?

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. Which means that you can sort of abstract away each, ZKVM, That you're dealing with? So I can paste a link to that… Air… In that sense, I think… all of the technologies probably work as good. The only issue that you'd probably have is that most of them work with, like, low-level languages, so Go might not be… a feasible… 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. And… just pasting it in the chat. So this is what we use, Just pasted it in the chat. 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… 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… Lou, but, yeah, so… And by the way, so, this is another thing I wanted to ask, is, so there's… That sounds… one thing what I understood from Succinct was that, it can, generate, like, 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. 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,

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. So… 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. 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. The benefit of this, stark prEOF is that it is post-quantum safe. It basically just relies on hashes. the SNARC approach, which is a GROF16 or Plonk, their prEOF sizes are roughly constant. So it's gonna be, like… Maybe, like, 1 kilo… I can't remember GROF16, but, like, 1KB, or maybe even less, for Graph 16.

The annoyance with Graph 16 in particular is that it is circuit-specific, meaning you're gonna need to do a, 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. 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. 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. I don't know, does that honestly?

Zsolt Felföldi: Yeah, so… 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. 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. 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. 256 blocks, we would generate a new 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… 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, For my use case, probably…

I can, I can, I can live with, with even, like, hundreds of kilobytes, or one megabyte, PrEOFs, and they don't necessarily have to… Go and chain. 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? 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. I don't know what the cost is right now, I believe Starkware probably does it currently. 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… Now that we are talking, this might be interesting for me. - wait. Did I open… New ones, it's not what I wanted. Okay, yeah, anyways, this is what I needed. So… yeah, this is… so this is… this is just this drawing that I have, like, like, for one of my talks. So, this, is something, the way I kind of, like, imagined… so this, this, this is, this is… 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.

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… This is something like, for example, if we add witnesses to transactions, then the provers could create transaction batches. And, and, and, and basically, the witnesses wouldn't have to go into the… into the chain, and also additional ZK prEOFs could be, like, recursively mashed into one prEOF, or a few prEOFs. So, So, yeah, maybe, maybe it would be possible in the future to just… 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…

Like, put, ZK prEOFs, like, in the… in the… in the input of the… rock building, too. So, yeah, maybe, maybe then, then putting extra prEOFs. 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. Then, basically, we can verify as many as we want, as long as some provers are capable of doing recursive prEOFs. So, do you think, like, this is realistic?

Kevaundray Wedderburn: I think some of it is a bit TBD. 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. So they get multiple transactions with witnesses, and these witnesses prove that the transaction is valid, or… 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, One, prove with this, this, this drawing is that, 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 Of, like, a state read. Then, then we can… Verify that witness off-chain, and the witness doesn't have to go to the chain. 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,

get a conclusion on now, it's just, just the way I imagine… A possible future that, maybe we could also use… use the log index for, for, for, like, contract logic, and it… I think it would have some advantages. One of them is that it's 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. 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.

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, 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… 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. It's not something that I need now for the current use case. I'm just thinking about… That, once we can afford to have, like, like, 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? I think it can be true. 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. Anyway, this is just, just something I wanted to… Quickly show, but, anyways, if we know, yeah, we can just first focus on, on, on, on… Finding a suitable, 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, 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, I… I was thinking about the hash function, because, so there's… there's… the hash function I use for tree hashing the tables, because these tables, generating them and verifying them.

The cost of it is… will mostly be hashing cost. 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… for the… for the… for the ZK prEOFs. Someone suggested Poseidon 2, which I never used, but… 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, 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, It's… it's less, I guess, Lindy, or, like, Ketchak is pretty… it's pretty a safe choice if you put it into, like, the consensus algorithm, or in Ethereum at the moment. 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. 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. 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… you have to prove the execution trace of, like, the dump, implementation of the hash function. But, so how do these… how… 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. 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. 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. 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.

With the standardization, they're basic… you basically just need to call a C header, and then you're done. But… And sender… I don't know if that makes sense, so let me know… Can you hear me? Oh, one sec.

Zsolt Felföldi: Yes, yes, okay?

Kevaundray Wedderburn: Yes, yeah. So yeah, basically, you just need to know how to access those accelerators. 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. 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 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… what I need…

Kevaundray Wedderburn: Yeah. But you can do it in two separate steps, right? Like, the recursive prEOF is, like, a separate program you can think of. That just does the merging. Of prEOFs, whereas you have your core logic that just, does this table indexing. 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… 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… The recursive prEOFs as input.

Kevaundray Wedderburn: Right, right, exactly.

Zsolt Felföldi: And… Okay, okay, let's maybe, yeah, simplifies things a bit. 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… 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… 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. And, 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? Right, right, exactly.

Zsolt Felföldi: Okay, and the, in the other, other, other case, yeah, generating, this from, from, like, the… three prEOFs. So, yeah, okay, I, I will, I will read, read, read upon, on the links you sent, and, And yeah, let's… let's continue this offline. But yeah, this was really useful, and I think we already… Past 1 hour or so, yeah. Okay.

Kevaundray Wedderburn: Sure, thanks.

Zsolt Felföldi: Yeah, it was really useful, so yeah, thank you very much.

Kevaundray Wedderburn: Okay. No worries. Alright, see you, Joel. Thank you.

Zsolt Felföldi: Okay, thank you, see you, bye-bye.

Transcript adapted from ethereum/pm, CC BY-SA 3.0.