# Rollups, Shards & Fractals: The Dream of Atomically Composable Horizontal Scaling by norswap

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2023-10-07
- Duration: 22:17
- Watch: https://streameth.org/watch/yt-AIkavv9wlQs
- YouTube: https://www.youtube.com/watch?v=AIkavv9wlQs

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/rollups-shards-and-fractals-the-dream-of-atomically-composable-horizontal-scaling/

Rollups allow blockchain to scale vertically, while preserving their trust properties. But what do we do when we reach the limits of vertical scalability? It might also be desirable to accomodate multiple rollups with different operating rules, virtual machines, or security trade-offs. Horizontal scaling solves these issues, but doesn't allow atomic composability. In this talk, we review approaches to horizontal scalability & ways to get as close to atomic composability as possible.

Speaker(s): norswap
Skill level: Intermediate
Track: Layer 2s
Keywords: sharding,scaling,atomicity

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

foreign [Music] talking about essentially is scaling and there's some lag but basically there's two kinds of scaling vertical scaling which is when you have a huge machine an horizontal scaling when you spread the load between multiple machines so yeah scaling so basically I mean I can wing it without the slides by the time they come by so in this talk well it goes great um I want to conceptualize um you know vertical and horizontal scaling I want to show you a cool new idea I have for a shorting scheme which has Atomic growth short transactions and we're going to explain exactly what that means and but more importantly what I want to do is demonstrate some research process so like hey can we do this there's a problem there's a solution maybe it's at the then we need to go in our Direction so can I restrict the process and generally what I want is to Foster interest in this kind of research and I want to I want people to collaborate with and and to work with me and with us at optimism on this stuff because this is the kind of stuff we care about this is not something that's really on the roadmap it's a complete side quest and so like I said this is a nurse knife like this is supposed to be brain candy super interesting stuff but if you want to work on it if you talk to me so like I said vertical skating big machines horizontal scaling many machines spread the load and in terms of ethereum vertical scaling has been done by Roll-Ups right roll-up enable vertical scaling because if you're a validator you can validate the Roll Up by validating The Atrium main chain there's only one extra assumption is that there is one honest L2 valid errors that can also Supply data for the roll up but the question is okay we can scale vertically and we can probably scale ethereum 10 times maybe 100 times if we start pushing some buttons like skilled database and things like that what if we need extra scalability um and and there's multiple reasons we might want that so one is that sure we could like require a data center for L2 sequencers but we want to have a healthy um very Data Network and not everybody can get a data center not even not even every company or every Dao so we might want to spread the load so that you can validate a subset really of the chain other thing is that we might want many different roll-ups this might be Roll-Ups with different security assumptions and different parameters like different fee different paid tokens in a different pay fees in a different token increase the troll output change the value rules maybe use a different VM all that stuff you might want to do but you might still want to have multiple Roll-Ups talking to one another okay so there's two main approaches to horizontal ability one is parallelization and in that approach you can have a big blockchain lots of state and you can spread the role between machines two options to do that optimistic you just try to do things in parallel and you hope they don't touch the same state if they do you just throw away one of them and you start again if you do this the pitfall is that you can't increase the throughput because um basically you can't charge more for transactions are not paralyzable that's because you don't have a clear criteria of what is parallelizable and what is not our option is to use a strict access list some fancy people call this utxo but I think strict assets list is clearer and so basically that's shipping every transaction with a list of either all the contracted touches so you can have a lock on the contract or all the storage slots that touches so you can lock this specific storage shots the polarization approach Stills assume that you have one entity that's why it is everything just now it's spreading things across cores and across machines so it's still high cost of ideas if you want to reduce the the load and validators you may want to do sharding and then values can value a single chart so a short is basically a small sub blockchain the only thing was that that apps not need to think about um on which chart they want to deploy which might not be great but the great thing is that we can do it eterogeneous roll up so like I said you can customize roll ups to have different VMS different view models and things like that and they can all talk to each other uh the problem with shorting is that if there is no way for shards to talk to one another in a way that's effective that's a bad solution so I'll explain what you know an effective way means but as you guessed it from title this is about atomic composability so this is an example I will use for a cross chart transaction it's a transaction that swaps Bitcoin for either on chart a then Bridges The Ether to a short B and on chart B will buy nft for either so this specified in a single transaction that you send either to a system or to short a depending on on your architecture so one very desirable property is atomicity if any part of this reverts everything reverts and in this case in particular if you come by your nft for either then you also don't want to swap your Bitcoin for either sometimes you can achieve this via application Level atomicity but in this case it doesn't work because sure if you you know if you can't buy your nft for either you could swap back your user for Bitcoin but now you've paid two swap fees and you've been exposed to bitcoin either volatility but there are sometimes cases where you can revert the action on chart a and if you can do that then you can do okay I was standing in the wrong area so [Music] um yeah so in some cases you can do application Level automaticity if you can roll back the thing on chart a um so what do we have today today we don't have Atomic composability but between pretty much any pair of chains you can do um eventual delivery of messages okay so imagine you have a chain a that chain B you can use systems like um layer 0 I think Wormhole does this Nomad to exchange messages between chains and what you you have is that the guarantee that if you do the action on chain a eventually you'll do the action on chain B detection we can fail and there's nothing you can do about reversing the action a that's what we have today I just implemented ideally with like Clans and ziki proofs but maybe also a good old multi-sig uh that happens so getting to the fractal part of the talk we can do a little bit better with roll ups and especially with ZK Roll-Ups we can at least ensure a bound on this right this was eventual delivery could mean if I go back to the previous slide it could mean many blocks sorry didn't mean to do that you could go back like many blocks in the future go you know forward main blocks what you could do is say well we're going to do this on the next block okay one scheme to do this roll ups and so basically you have this architecture where uh you have a apparent roll up here the cover up one it has child draw UPS you give up 11 and 12. and basically it's a fractal structure because the roll up one rolls up to the layer one but the layer 11 and 12 they roll up to the uh to the role of one and if you assume that there is Ezekiel proof boosted every single block then now what you can do is do um instant delivery transaction between say this one 11 and one so for instance you could do your swap here and then buy your nft here it's still not Atomic because you can't revert but now at least you know it's going to be done like in the next block or one block apart that's good but that's still not what we want so what about uh crush or atomicity so I'm going to propose a solution for this um and we're going to assume that we're slicing our system into one blockchain block which is going to comprise one block for every charge so every chart Advance at the same rate and we want to have some form of atomic crochet transactions to enable this sure need to be able to send messages to other shards so let's just take the most nice possible idea which is eager enter chart blocking so you just process all your transaction at some point you hit onto a transaction I want to send a message to another charge you just literally call that chart you wait for the answer and then you continue so this is less coincidence sounds and it's somewhat equivalent to what strict access list do because at do in the worst case you have the same throughput as a synchronous blockchain in theory but you can charge fees because you know exactly which transactions are crossing the shards the great thing is you don't need to specify the access list but the really really bad thing in practice not in theory is that you're assuming that all these shards are being validated by different uh entities and so the latency for one chart to talk to one another is really high and so in reality this is not feasible because the latency will just kill any throughput that you may have let's try to instead reduce the number of exchanges between charts right let's try to bound this very tightly and so the idea would be to divide the the block time into multiple slots in the first slot every Shard executes its own transactions and also collects messages to send to other shards in the second slot all the shards extension messages and then they run the messages that they receive optionally you can keep this going so you can have many many slots you could say all messages can send our messages etc etc I think in practice you don't really need this you can have a lot of expressivity with just like one hop just one short talking to one to another shark so this is still a bounded message delivery though you can't revert uh you can't revert part A If Part B fails and that's because other transactions rely on the result of the a part okay so this is very unclear so there's a graphic here so say I'm saying a I'm doing my local transactions I'm doing the a part of a cross chart transaction and let's say that's you know that's a swap so both of these will be swapping and then on video will be buying an ft so this transaction here the a part depends on the a part of the first one because the first one swapped uh say Bitcoin for either so it moved the price so this one will use the price from from that was moved here so there is a dependency link and because of this dependency link you can just revert uh you can just revert this transaction if this one fails because this one uses the result so this is the problem that we're dealing with and the general properties that atomicity requires synchronicity basically local transaction can still be processed separately but we would like all the crocheting transaction to be executed as though it was a single person executing them right um so we have a problem which is we don't want chart to talk to each other too much solution to that is to create a special chart and I'm going to call it the atomic shard that will execute all the cross-shar transactions and we have a second problem is that to execute all the crosstalk transaction you need to state from all the charts right and this is this removes one of the big points of shorting which is that you can separate the the state between all the shards so uh the solution to that is to make the execution in the atomic chart stateless and that means you will supply all the state that's being accessed by the the transactions for the atomic short so uh This sounds too good so where's the poop the poop is that you need to simulate transactions um on each chart individually so in general I need VM given that you're not sure the state it's impossible to collect all the storage slots accessed by a transaction you can approximate and the easiest way to approximate is just to run a transaction against the current state and just assume that the transaction before it will not revert so you know here it's easy you just run the state of the first transaction against the state after all the local transactions for this one you just assume this wall this one will revert and execute and simulate but maybe it will revert so maybe your simulation will be incorrect everything you can do with anything so you just um tell The Shard well um this transaction is going to touch this slot or you can give him some logic to find all the slots are being touched and there's many ways to do this that can be explored it could just be some evm code that just touches the slots could be some kind of infrological information or even out of protocol information that is not being validated but that's being sent to the to the sequencers so I want to make things a little bit more clear so here's a Crosshair transaction very abstract it computes things be on some State and this state might change right we're not exactly sure what it is then he's going to send a message to short B and this message is going to depend on the result of the computation uh that message will have a result when I compute something based on that result and we're also going to send the results to sort C and then do some more computation so this shows you like sort of the dependency we have right we can depend on the results from one chart we can send to our chart things that have been computed and so this will be important to understand later so to rephrase what I'm proposing before we dig deeper into the problems like I've showed you only a small part of the poop a lot more poop coming up um but the scheme is this phase one uh the short execute the local transaction and the simulated cross-star transaction when they do this they will collect all the cross shot messages and all the access storage slots in phase two we do the exchange and the short simulate the messages and similarly they collect all the search slots all this oh sorry if history all this stuff that we collected here and there we ship it to the atomic charge and this will atomically execute everything and normally you should have all the stated needs and if it does then it will just basically fail to execute transactions so the big problem with this scheme is that the simulation restrict the expressivity right so we can only safely Express a transaction where the simulation will be deterministic in some ways because otherwise you you know it might change and you might not be able to execute things so you might sometimes take the risk um that transaction won't work say well I'm gonna try if the sales doesn't change it's gonna succeed but if the state changes it's not going to succeed uh we'll see that sometimes that doesn't work uh by the way this is exactly the same problem as building strict access list or you take so for slots same thing you need to collect all the the storage slots that have been accessed so this problem is uh is pretty similar so the the problem you know what gets worse is that crucial messages may depend on uncertain States and we derive all the messages during simulation and that's why we want to be deterministic um we can also want an answer from a chart and so we absolutely need to have a hint for the answer so let me illustrate because this is very abstract so what I was saying was that this parameter here x depends on the result of computation so this we need this to be always the same otherwise we just asking the visual to compute something that might not be what we want so we absolutely need X to be uh to be known and you know that the message sends an answer and we're going to send this answer actually directly to C so we absolutely need to know the answer already also um I've actually Illustrated these constraints so here we need the computation to be deterministic in the storage class that accesses here we actually need the computation to be deterministic so to always return the same result here if we use y just in a computation we need to hence the result approximately just to get the correct shot but if we send it to another chart then we need to know exactly what Y is like no no guessing otherwise we're just asking C to do some and we don't want that um so open questions is this reasonable is this a good idea are these restriction um feasible do they give us a powerful model that is useful in practice another question is can we aesthetically guard against some some cases of the non-deterministic execution that we want to avoid or do we just say well it's a user responsibility and maybe some people will build some tools to detect some of these cases uh this is for sure a foot gun right like if you're going to make a Crosshair transaction and you don't expect it you expect it to be deterministic but isn't there's definitely there are a lot of possibility to make bugs but is it worth the cost our question is what is the correct abstraction level for all this if we don't enshrine static checks we can simply add like a cross short call up code to the evm and then just on the back end it will do what I explained but from the point of view of DVM this is the new up code this has been my presentation we have five minutes for questions I'm sure some of you have burning questions you should have a lot of questions because this is very questionable um yeah do you think sharding is maybe just fundamentally kind of impossible and like kind of like when you're trying to deal it's like you have all these different systems it's almost like they shouldn't be able to interact in this way it's a really dumb question um I mean in a certain way you're right like we're yeah do ideas like you can paralyze what you can but then sometimes you don't want to paralyze and you're just trying to build this abrid like a synchronous synchronous system uh so yes I know someone else someone comes from some wacky idea there's not a dumb question yeah in your model the regarding the new OP code that is aware of sending message cross charging does that mean like smart contracts need to be aware of calling another smart contract that is in another chart yeah how do we envision those things and also in charting without the New Hope code our smart contracts being aware of calling something that is in another chart because that brings friction to Smart contract Developers so yeah the model I've been assuming is the model of sharding as like small sub blockchains um there are some proposals of shorting that I would classify under parallelizations you just pretend you have a big blockchain and then on the back end you just put things in short and you move things around but for the user they don't see that here the model is explicitly you have multiple sub blockchains and they talk to each other um this I think simplifies the implementation a lot but not everybody agrees uh actually my good colleague car does not entirely agree with that [Music] um but that's at least my point of view and there are other advantages which is that you can have multiple Roll-Ups that do things slightly differently as I mentioned um so that's an advantage does it okay so regarding the the shutting in itself is it possible for instance to imagine a system where the accounts who dynamically move across the shards to try to reduce as much as can be the internship exchanges on so to simplify the whole process or is it like completely deterior use it is possible I know there's research on this I don't really know anything about it but yeah I think this was more related to the models where you just like rebalance The Shard and like you would you necessarily be aware of the charts um yeah it exists it's definitely feasible it wasn't really thought through here in this simple model um yeah I think this sort of needs some like like a balance chain where you have all your coins that will probably uh or at least have your balances be accessible by every Shard that would probably simplify design a lot and in practice when we see things like Avalanche they have like a special like chain for like payments because it's so special and so important um so that might be one part of the answer hey um my other question was um could we use things such as like AI or sort of predictive behavior in combination with this to sort of like just automatically optimize or is somebody working on on stuff like that to sort of predict the interactions between the smart contracts and how to kind of optimize across charts uh I'm sure some people are working on it I know I know there's a bunch of research with that even on payment chains so things like Bitcoin and stuff I don't know why it was very hot academic like academics are like lagging behind uh the stuff we do a lot and they've been like very like I've been to a workshop this year and they're very interested in exactly this problem and I'm like does this change the smart contract and we're like no I'm like What's even the point like just put it on a big server and be done with it um but yeah you could do it's sort of didn't assume that model here but it's doable okay thank you very much foreign [Music]