DappCon 2023: You've Built an EVM-based Rollup: What's Next? - Toghrul Maharramov

Transcript

hello everyone my name is to girl I do research at scroll you can mostly find me complaining about things on Twitter well this week I was suspended for a few weeks now I'm back complaining and today we're going to be talking about evm based rollups so everyone is building evm based Roll-Ups these days but what's next like why do we even need them so you've probably heard about rollups everyone's talking about them these days and you've probably heard that there an Ultimate scaling solution how they scale etherum to gazillion transactions per second how they over for unlimited

scaling how they uh allow you to have arbitrary execution environments blah blah blah blah blah blah they even cure cancer apparently no they don't uh so yeah but rollups are actually exciting I'm a bit biased here because I'm working on a roll up but yeah uh but is everything that we talk about realistic or do we just get o excit too overly excited and forget about certain technical details that we have to mention when we talk about rollups so for now let's assume that ethereum has unlimited data availability so rollups are not Bott neck by uh data

availability and just to explain what data availability means means in this case regardless of how much demand there is to post data on ethereum ethereum can always handle it let's just assume that that's the case for now it's not but in an imaginary world that we're trying to describe there uh here it is so uh let's also assume that we've built an evm based rollup specifically it's even better if you're rollup follows the similar patterns to um ethereum in terms of State Storage EX execution etc etc and even better if your rollup client is based on a modified or of an Fork of G

Aragon nethermind or any other execution client for ethereum um so an example arbitrum optimism scroll polygon zvm Z casing era and etc etc you can think of Base mantle Etc uh so in this case polygon uh and ZK think have their own clients that are are similar but a bit different to the existing clients and arbitrum optimism and scroll fork and slightly modify gu and in case of optimism also arogan and breath I think but it's not live yet so um raise your hand if you think that ethereum is bottleneck by the

consensus good good glad nobody raised their hands because you would have been wrong and I presume that nobody works at Avalanche here that's why nobody raised their hands so ethereum is actually bottleneck by the read and write operations so what that means is ethereum state is stored in a structure called modified Merkel Patricia tree and just think of a state as a union of all the non-empty user uh accounts and also smart contract accounts so for example uh the account that displays your balance the the Unis swap router contract etc etc all of those accounts

that are deployed on ethereum all of them constitute this one state and it's stored in in this structure called Merkel Patricia tree and it's called the Merkel Patricia tree because it's modified so it utilizes hex Branch nodes so what that means is instead of having a branch that that points to two children it points to 16 children it's Merkle because it recursively hashes the child notes until we get to the root so think of Merkel trees it's Patricia also you can sometimes referred to as radic tree because it merges single child nodes with their parent nodes so think of it this way if you have a node and it

points only to One S child note then you can just merge them together and basically use an index to Traverse and Skip those single child nodes and it's a try because it utilizes the leaf position to define the associated key so in ethereum for example if you Traverse through the tree and get to the leaf uh the the leaf uh the traversal path represents the key uh where the account data is stored in this case or the specific SLO and this is a good good representation of how it works it's a bit confusing but you can see the the extension Noe is what I described uh in

Patricia tree then you can see the branch node has uh 16 values instead of two values you can see that the leaf can have a prefix etc etc and you can see that it has a value it's a bit simplified in this case and the value is basically uh what is referenced here through the keys to get to the leaf node so back to the subject at hand it was a bit we went on a bit of a tangent so uh read and right coasts rise as the state expands uh since there so the reason why that is is since there are fewer extension nodes as the tree grows in

size we need to get more um we need to go through more reads in order to get to the leaf and assuming that at some point your tree is completely filled your state is completely filled you get to the point where uh your reads and ride cost will be equivalent or double in case of ride because you need to rewrite it back uh to the depth of the tree so assume in this case the depth of the tree is 160 you'll need to do 160 hops through the storage in order to get to the leaf and for some affirmation rollups it's even worse because they start with

the worst case scenario so for example in Scrolls case we use a a structure similar to Merkel tree so for us your uh starting point is basically the worst case scenario when you have to do uh the maximum number of reads and the same is true for zking and polygon zkm and ethereum is purposefully rate limited to slow down the rate rate with which the state grows and rollups can set the of course rollups can set the limits higher but you can think of it this way uh you can increase the hardware requirements set the limits higher because you don't need

the same level of decentralization as you have an L2 but there's always a limit to it so and you can ask the the validators from binance Smart chain how well that goes when you just raise the limit and just don't think about the uh the the outcome of it so just to give the context here at some point a binance marchain used a fork of G and at some point because the limit was so high per Blog the validator nodes couldn't catch up with the tip and so there was at some point there were literally almost no nodes in the network could that could catch up no matter how high end the

hardware they used and so at some point they switched to Aragon and now it's better but it's still but they lowered the gas limit because they realize that it's not very tenable and so what is the solution well there are a few Solutions here one of one sort of a solution it's not a complete solution is stateless clients stateless clients Outsource statefulness to specialized operators so think of it this way you have a few nodes in the network that store the state and the rest don't the way it works is basically with every block produced those notes that have the state just attached to openings to the tree that have been written or read and then every other

note that doesn't have the state just has the state route can just trustless verify that this state is correct and the advantage here that stateless clients are still completely trustless as long as you provide them with the witness data and there's no trust additional Trust assumptions Etc but there are a few problems here one it requires a switch from Merkel Patricia trees to for example workl trees and the reason is with the way Merkel patricius work uh trees work the data requirement to propagate the witness in the worst case scenario will be impossible in the current network settings which means that you'll end up with a network that

would just stall at some point and not work and another disadvantage oh sorry there are no other disadvantages here so uh another option that you can use is State expiring so uh State expiry is in its current form there are a few different versions of it so in the current form once per Epoch uh you just prune the state start with the new state and then uh store only the state roots for the previous Epoch the currently proposed at least the latest variant that I've read the epoch last around the year so it's different to the epoch in the ethereum consensus and you can revive the prune State later

so essentially you can include a transaction that says here's the opening to this route in this previous prun state that you have the root to please add it to the new tree and then you can just revive it and transact but the problem here is that so sorry the advantage here is that it limits uh the state required to stored uh by the full nodes to a certain fixed amount so let's say you you can assume that you can set a certain gas limit and you can have the state of a maximum size per this EPO I don't know let's say 60 gabt or one terabyte or whatever whatever you can think of and it can never grow larger than this

because you just prune the state have it uh stored somewhere and then if any nodes need need them they can access the archive nodes or use some kind of an infrastructure provider like infu etc etc to fetch the data and then revive the state if needed uh but there are a few disadvantages here so the main disadvantage is that it requires the extension of the addresses to 32 bytes and so which is not really an option for ethereum right now because ethereum uses 20 20 by addresses and therefore it it will break a lot of the contracts and and and the reason why you need 32 bytes is because you need to store the epoch

at which the the certain account was stored so let's say if the account was first stored at the current Epoch the next when the next Epoch come around you by looking at the address you just know that you can prune it and you could do it in another way but it's sort of a problem and that's why it's at at least at the moment it's difficult to see how be implemented by ethereum and then another problem here is that it requires changes to the evm so think of it this way so for example you're executing a transaction and the transaction tries to touch the slot that was pruned and it's not it's hasn't been revived yet which means that it's

inaccessible to the full node and therefore there needs to be a way to handle those errors and and a few other things as well and so we need to change how evm behaves in this scenarios and there's another possible solution which is just using some clever tricks so for example in salana the state is merized only once per Epoch and again this EPO here has nothing to do with etherum consensus you can think of a different number I think in salana is like once every two days but whatever so essentially it makes the realtime read rid Co cost constant

whereas in ethereum the read ride costs are uh o n where n is the depth of the tree or the the the particular slot that you're trying to touch and that means that you get really fast storage in real time well there it's it sounds like a perfect solution but it's not it one it makes light lines and state state clients almost impossible to build and the reason is because you meriz the state later the light client cannot trustly access the latest data the latest data in the state which means that it either has to wait or salana does this weird thing

where you can send the transaction to check whether a certain slot is is equivalent to a certain value which basically asserts it and if the transaction returns true then you you're actually good and you know that it's but it's it's a workaround and I don't think it's a deal because as long as your transaction is not lost in the last block that you read there's always a scenario where that slot could have been modified later on and another problem here is that you can't really build provs for that nor fraud proofs nor validity so zero knowledge provs and the reason is because for for uh for to construct

proes you need a succinct way to prove inclusion uh into the storage and there's just no way of doing it here which means that do you have a system that cannot be a rollup essentially and let's assume that we solved uh the state related bottleneck we managed to use the clever trick that I described somehow figured out uh State expire etc etc what's the next uh bottleneck that we need to solve the next Bott like is sequential execution so in ethereum the transactions are executed sequentially so what I mean is you pick a set of transaction you execute one you wait

until that one is executed then you pick the next one executed wait for that to finish executing apply the state and then go on go on forever which is not really problem ethereum because the gas limit is so low that it never really affects uh the speeds per se because you never required that amount of execution but assume that we solv that problem so now your gas limit is very very high and then you actually need to paralize execution so what are the the solution here here so you can optimize it through paralyzation and there are couple of ways you can do it one you can do it optimistically or you can also do it deterministically so an example of

optimistic paralyzation is block stdm so think of it this way it optimistically picks the transactions from a m pole executes them and then if two uh and if it discovers contention so for example two transactions are trying to write to the same slot it reverts to sequential so in in the best case scenario you get a significant Improvement and essentially you can scale with the number of cores in your system and it requires no to minimum changes to the state transition function because it's done outside so if it fails it fails you just revert back to sequential uh but the problem is that in the worst case scenario or even average

case scenario where a lot of the transactions touch the same slot so for example if a lot of transactions in a given uh block uh try to use the same Unis swap pool this will just fail and it'll add even additional overhead relative to the sequential execution which is not ideal but is is there really an ideal solution and uh the second option is deterministic where you require the application to declare uh the transaction to declare all the slots uh that you've read and written to Via an access list so ethereum introduced this thing called access list it's currently

optional so you don't have to use it but you can make it mandatory as well and essentially you paralyze by picking the transactions that declare non-overlapping access list so for example if transaction a declares that a touch slow X and then transaction B declares that it touch slow y you know that they'll never overlap and therefore you can trivially execute them in parallel uh so it introduces no overhead relative to sequential execution the worst case scenario because in the worst case scenario you just execute it the way you would execute the sequential but in in in the best case scenario it scales with

the available cores in the system and basically the more cores you have in the system the more transactions you can batch and paralize and but there's a downside here as well unfortunately that the transaction outcome has to be deterministic at the time of its creation because you have to declare the slots and they have to be declared in advance it's impossible for you to later touch a different slot which means that let's say if you're transaction re uh execution path relies on some conditional statements that touch different slots it would it will just fail in this case and you would have to reset the transaction

again which means that you either have to be lucky to have your transaction included or just uh compute multiple transactions with different paths which can get very complex in case your transaction has a lot of your execution path has a lot of conditional statements so unfortunately not ideal as well so yes rollups are great but there's still a lot of work the ahead of us that we need to make for us to make them actually scalable and so thank you for listening to my talk and feel free to ask any questions if you have [Applause]

right we we have time for a few questions of course um over here uh we have a microphone for you just one second sorry sorry problem um hi thanks for the talks um just have a quick question so when you were discussing the cost of you know iio um you were really talking about the cost of updating the state three I guess

right and uh you were mentioning that this is proportional to the depth of the three and uh then my question is regardless the stateless client wouldn't you have a similar scaling maybe not in IO cost right but in computational cost in the sense that as your state grows then the computation need needed also grows um logarithmically in the same way right um no because you can just because the witness size is relatively small you can just put it into the RAM and access it really quickly whereas with the state if it grows really large you cannot store it in memory so you have to put it at least parts of the state on the desk which means that it's not

very fast and on top of that uh the problem here is that you basically have to jump through the uh slots in the memory even even if in the ideal case scenario to reach the point where where you can read the SL uh the the leave whereas in this case you would just load everything uh in one batch and we just read it sequentially so you don't have to go through different points on the dis etc etc so while there is certain overhead here as well it's not even comparable to having a stateful client another question for

TGO all right if not we'll wrap it up there thank you so much to Round of Applause