Delegated Execution Sharding

Transcript

[music] [music] >> a sort of creative, creative research endeavor than like a really like uh you know technical sort of project as compared to the other ones. But um the title is delegated execution sharding, which if you know what execution sharding is, that might make sense, but the general idea is to instead of relying on something like a um very like heterogeneous main net that is not that scalable, but has a lot of like data scaling and then having like rollups that have their own sequencing to uh sort of add scale to the main chain.

Instead of doing that though, the idea is that in theory we can bring these kind of like computations onto main net itself and that can be more sort of in line with our values without relying on sort of centralized sequencing or parties external to the L1 to bring us scale. So for starters, I wanted to give like just sort of an like introduction to how I was thinking about Ethereum. So like Ethereum at its core is general purpose and should actually lack you know distinct structure or distinguishable features. And what that means is that not only is the computation like the computational model of the EVM, general purpose and when you include things like frame transactions, it actually gets even more sort of

abstracted behind like generality. But also we have um like on a philosophical level, you have this like lack of sort of um enforcement of a definition of who gets to participate. So in consensus, proof of stake means that we're not trusting any particular party we're defining as providing the definition of the chain. We're trusting something that is neutral. Um and then the the theoretical result of this is that like the the general idea is you get these uh general purpose actions that can take place over some definition of time we can all agree on um just to sort of provide this like um directed computational record in a way.

Um. So then the question is like what is scale? Um. And I mean scaling Ethereum essentially can just consists of having more computation on the like inside of what we consider Ethereum, the chain. So if you were to ask me how do we scale Ethereum and I said oh let's just turn Ethereum into a data center and then we increase TPS by like a hundred times uh that doesn't actually scale Ethereum because in a way like the thing stops being Ethereum. You know it stops standing for what it means to be Ethereum. So really the question is how do we scale Ethereum in a way that is aligned with our own values.

So the current model and this is the O one uh today we use proof of stake basically um like election to to delegate somebody to propose computation every 12 seconds. And every single node has to verify this sort of batch computation um so that we can all move forward like trustlessly in the consensus process. Um but this is like admittedly pretty terrible right because not only are you limiting the scale of computation to like what can one person do in 12 seconds. It's actually even worse than that because you have to do the computation way less than 12 seconds because everyone else has to verify it as well.

So it's like basically a Raspberry Pi executing for like 500 milliseconds every 12 seconds and sending it off to a bunch of other Raspberry Pis. It's it's like it's pretty bad. Um. So then then we have zero knowledge proofs and the question is what do zero knowledge proofs do to help? Well like a ZK EVM theoretically because you have this succinct proof you know you can have one proposer elected every 12 seconds to do a bunch of computation and then prove it really succinctly. Uh theoretically this is really great because we can have the the builder or the proposer of the block do much more computation in a longer period of time than everyone else verifies the proofs succinctly.

So that's great and it scale it lets you scale a lot. But the problem is that um you you're still limited to a single validator validator who has to do the computation. So if you're if you only if you have 800,000 validators and you elect one to do computation for 12 seconds, that's still really bad, right? Um yeah. Like we should we should be scaling Ethereum with the scale of compu uh computers in the network. And not only that but like uh conceptually you should only um you should only take computations that need to rely on interacting with one another and you should place them in the same block.

This is basically what parallelism is or what we were trying to achieve with sharding before rollups. You should be able to take, you know, computations that don't necessarily want to interact. Like if someone only wants to interact with Uniswap and someone else only wants to interact with um OpenSea, you should not put them in the same block and in you know therein limit the scale of that block even though they don't want to even interact. Um so then it's like the question is why can't we just have multiple blocks? Um I mean this is it sounds kind of like kind of almost sort of crude when you think about it but if we have you know zero knowledge proofs um and we have a single proposer who can propose a block that is proven and everyone can verify

it, why can't we just take 16 proposers have them propose 16 blocks and they're all you know proven and maybe one proposer has to aggregate all the proofs which is very easy and then everyone verifies the single proof and it's like 16 times scale. Uh well that would be that would be great but uh the the problem is you know some transactions do need to uh interact with one another and if you try to do things in parallel and you know two of these separate blocks have transactions that touch the same part of the state, you you need to resolve them serially.

Um which is which is why and it because it's unpredictable to to tell when where transactions will interact with in in a block um we just fall back to doing this really sort of naive way of doing it, which is just having a single block. So my sort of attempted solution to this, um, I called it delegated execution sharding. Uh, so basically in May I wrote an E3 research post about like principally how we could recursively aggregate block computation happening in in execution committees. So this is basically what I was talking about. You take uh committees, you use committees instead of a single proposer to execute and then you you know recursively aggregate proofs of these valid executions of blocks and then

everyone verifies a single proof. Um, and I I basically like defined a number of like sort of core constructs that would be needed in this model, but the problem of course that I I I I I hadn't really resolved was that dependencies predicting dependencies is really difficult. Um, because the like the EVM is non-deterministic and you can't really tell where like which part of the state transaction is going to to execute before actually executing it. Um, so yeah, the the kind of my like partial solution to this was something called a virtual mempool, uh which is actually I I recently learned it was actually a term that was already used, but I sort of rediscovered it. Um, and the idea of a virtual mempool was to sort of you combine nodes

local mempool views and you you let them vote on vote on them in committees and you do the same aggregation of their views. Um, and it gives you like in the block before you know the block we're talking about executing, it means that you can get a like rough estimate of what are all the transactions that nodes see that they might want to execute in the next block. And the idea would be that you would let these transactions uh declare what they want to access and enforce that they can only access that uh once they've declared it and then in the next block you I'll actually go and explain this. Uh in the next block you create something called an execution

column or you know you create execution columns which are essentially uh the result of running an algorithm that sorts the transactions into certain boxes that are distinct from that are non-intersecting from another based on what part of the state they want to access. Um and once once you run the sorting algorithm, you get like uh distinct segments of execution that you know can be done in parallel and can be proven and aggregated uh recursively using delegated execution charting. Um and then the execution committees are the actual elected proposers who are uh delegated to execute this computation in parallel.

That's why it's called delegated execution charting. And the execution tree is what I would call the structure by which you're actually aggregating uh recursively. Um and part of this involves the fact that uh at the bottom of the tree you have these execution columns that are you know being executed and proven in parallel. But the idea would be further up in the tree uh at higher layers you can also have committees who execute transactions that maybe need to depend on multiple parts of the state within execution columns. Um and if that doesn't sound great as a model, it's because it's it's actually not. Uh and this is kind of what led me to this uh simpler solution that I started working on in um

it would have August in in August. So uh the the problem with the delegated execution charting model is that you know predicting the like as I said predicting these state access is still really hard. And um you can't rely on like you can't really rely on a transaction to type two declaration of dependency because they can you know change their dependencies midway like all albeit with a higher gas price. So it's not it it it you're relying on in the worst case it's really bad and it basically doesn't work. Um so I kind of departed from the delegated model and I moved to uh a model that

actually relies on the mempool as a way to uh resolve dependencies before inclusion in the block, which uh is not delegated, but happens um locally for every single node in the mempool before a single proposer basically aggregates the recursion that's already occurred. So so the intuition was that um if you can delegate uh execution in parallel, you can uh do it in mainnet on the mempool without enshrining delegation because you know part of the idea is that uh you know Ethereum is general purpose and you don't want to rely on uh implementing like enshrined rollups or implementing sharding. You want to be able to have a model that will uh sort of derive its own scale without relying on this sort of distinct

functionality. So uh two proposals sort of made it clear to me that it was possible to rely on uh this uh this idea of mempool uh look mempool-based aggregation. The first one was and this is actually funny because in the previous presentation this was also mentioned, but Tony's UTXO EIP research post and EIP 828 which previously was had a EIP research post uh titled uh recursive shark-based mempool aggregation. And just to sort of uh give a basic example of how this would work um if nobody sort of 828 it essentially consists of in the mempool we will recursively aggregate uh post-quantum signatures.

And this means that you don't have to um rely on a single proposer to execute all of these expensive signatures in a serially. You can have it resolved on the mempool at uh lower levels. And this only works because these signatures don't have dependencies in the block. So they can be uh aggregated by some part of the mempool who's not the builder uh and then that aggregated uh construct can be sent off to the proposer and maybe other parts of the mempool send send in aggregated uh signatures and then the proposer might aggregate the three of them and then include them in the in the uh single block. And if we if we use UTXOs uh as a transaction construct. Because UTXOs are atomic and don't touch any

other part of the state, you can rely on this same level of aggregation to occur in the mempool and it essentially gives you like infinite UTXO throughput bounded by data because everything is being done like optimally in parallel. So yeah, I call this sort of generalized version execution abstraction because the actual transaction construct is generalized such such that it represents like an atomic unit of computation with certain dependencies rather than sort of a distinct like frame transaction or transaction construct.

So this means for example a single unit of computation can either represent a single transaction from user or can represent three that touch the same part of the state and were batched and turned into one. And this sounds really simple but it results in essentially what I was trying to create which is the ability to include an arbitrary amount of scale on the main L1 without relying on rollups, without relying on sharding, without even without even relying on delegation. So just if you think about it inductively, let's say a single block is a generalized proof object. Like that's what the execution block is and it has all its dependencies in a proof so that it accesses them correctly.

Now let's say the actual underlying construction of that involves you know a thousand transactions that resemble these same just proof objects with dependencies. Then you have a thousand transactions in a block. Now let's say one of those transactions, say the first transaction is a batched computation that represents all the transactions that touch the Uniswap. That means Uniswap is all of the Uniswap activity gets collapsed down to a single transaction worth of compute for the for the root proposer. And this this scales such that you can upload a program on Ethereum and you can call it a rollup and you can sequence the transactions yourself if you want to and you can prove them all and you can send them off into a block and then maybe the mempool can

resolve the fact that some other people tried to access the rollup program, but also touch other parts of the state. And this all gets aggregated recursively. Um, so it basically what I was trying to say there is you can program rollups into the chain without them needing to be hard coded. Um, and that's disregarding data availability by the way. But um so this works better because aggregation actually happens in the mempool rather than being heterogeneous to mainnet. So it's far more robust in its ability to adapt to the shape of the mempool. Uh, and it doesn't rely on the central delegation. But for example, like you could every node if it really wanted to, could pretend they were using delegation or pretend that they were um

like using rollups if if that makes sense. You can have uh because you're relying on mempool policy which is not enforced, the mempool can decide which way it wants to aggregate and the protocol supports that. Um, which is which is obviously better because it's the more general way of doing things. Um, okay, so so so what now? Um, part of the way I went about this was that um this is sort of a scaling proposal living in a post quantum world. So um like the sort of I didn't go too deep into actually like concretely implementing the like the the underlying sort of um like model for this, like the EVM model

for this, um like as an actual like technical implementation. So it would be nice to actually get something like a testnet or and I was working with a few other people on this like something like a testnet that would actually test like how well this should work in practice. But another like nice thing is another like important thing is that like currently the actual like zero knowledge proofs are just not advanced enough to really support something like this. And I think that's true for many sort of scaling proposals that involve ZKVMs. So that's another thing that's important. Um, but just like from a conceptual point of view, I I like to believe that this is a very sort of like positive direction. Um, this is a quote.

And it makes sense to anyone? Yeah. Yeah, you probably Archimedes probably said that. But that's Thank you. I I I forgot to Thank you to Scas, uh, but my name is not your name, just for the record. >> Of course, my name is Wait a sec, bro. We might have questions, okay? Let's see if we have any, then you're free. So let's see if we have anything, any comments, questions, thoughts about Connell's talk, folks. Feel free to raise your hand. Goes for one, goes for two and three. Okay, I don't see any questions. Too bad. Anyway, uh, Connell, thank you so much. Really appreciate it.

Um, very exciting, uh, research, many thoughts. Honestly, I mean, I haven't heard about execution shorting since like 2018 or something, like since way before the merge. And, uh, it's just so interesting to see a fresh take on it. So appreciate >> [music]