Challenges of Parallelizability under Ethereum's Execution Model by Péter Garamvölgyi

foreign [Music] get up early and come to this talk so my name is Peter and I'm gonna talk about uh our work that we did at the Shanghai blockchain Research Institute and what we did was we investigated how hard it would be to execute transactions in Peril on the evm as you might know the evm is designed in a sequential manner usually you execute all transactions you know block one by one so the question is can we paralyzed that well we found um what I want to talk about today is two challenges that we identified and the first of those is transaction dependencies you're probably all familiar with how ethereum Works basically we have a global share state which is the state tree theoretically a transaction could access any point any entry in this state tree that is where it can access a slot or not that's defined by the contract code so for instance if you have two transactions from two different accounts and both of them call the same contracts and that's contract reads or writes the same entry then these transactions will have a conflict or a dependency on ethereum this is not a problem now because we execute transactions sequentially but if you paralyze them then this will become a problem because you cannot concurrently execute such transactions so we did some evaluations basically what we did is we collected some storage traces for a few hundred thousands of blocks from you know historical data on ethereum and we did some simulations with some OCC scheduler and what we found is that the theoretical maximum speed up is as little as four times so even if you have eight threads or 16 threads at least on the VM level if you don't consider storage you cannot do much much better than four times and that's kind of an underwhelming result so some examples some simple examples of these dependencies for instance if you have two transactions to the same erc20 token uh if they send from the same senders to the same receiver then they will conflict on the balances mapping or if you have two transactions swapping tokens on uni swap swapping the same token pair then both of them will modify the reserve variables so that's also another kind of conflict or if two transactions are minting and nft then for instance they can conflict on total Supply if the contract is keeping track of that we identify this and this is an issue I think this severely limits the paralyzability of evm transactions as they are today and we have some suggestions how we could improve this this is kind of early just some ideas to to throw in there the first idea is to use a sharded counter so from the examples before you saw that many of these conflicts are on complex on a single storage slot which is like a an integer or some counter and yeah two transactions read and write the same slot so the idea would be to Shard it into multiple slots so one int is represented by three five seven slots and then we could route transactions based on some heuristic to different slots let's say we take the last byte of the hash of the sender address so two transactions from different senders would probably with a higher probability they would modify different slots in the contract and the second idea that we came up with is a lazy ad op code so for in this example we have a very simple function that's just incrementing a counter but when you compile it to evm byte code what you have is a storage load operation then you do something with that value and you store it back so to concurrent transactions uh we'll have a conflict on this like concurrent storage load storage store operations and uh you know we cannot paralyze them the idea here is to maybe introduce a new kind of semantics for addition lazy ad or commutative ad and that would be evaluated lazily so these transactions can execute in Peril and then we basically batch those two updates together into a single update at the end and that could be executed at the end of the block for instance the second challenge that we identified is that of determinism so as you might know in parallel execution there's a you know there's a lot of non-determinism and we can make sure that two transactions have the same result or two executions but there are other types of non-determinism for instance here we have two executions of three times three different transactions and let's say transaction two depends on transaction one so in this case on node a one and two are executed concurrently so two has to abort and be re-executed because there's an update that it could not see and on node B the execute is sequentially so no transaction two can commit directly our idea is that if we have parallel execution at some point we have to introduce some incentives because if you can trigger some aborts that kind of opens up the door for some denial of service attacks and if we do associate some incentives with aborts then to these two executions in the example they will yield the difference final state so that is going to be an issue two nodes will diverge so for this we kind of came up with a new scheduling framework called optimistic concurrency control with deterministic aborts and the idea is very simple instead of deciding these abort comment decisions during runtime you made this decision prior to running those transactions in a deterministic way so the these decisions will be deterministically you know the same on all nodes and this way even if you attach incentives to these decisions the final states that different nodes will arrive on will be the same so this is the OCC da framework just to summarize kind of the takeaway from the stock so it's pretty hard to get parallelization done on the evm because it was not designed with this in mind but I think it's going to be worth it for instance if you manage to scale ethereum on layer 1 or layer 2 with a higher transaction transaction load per execution will have a very big impact on the overall uh yeah efficiency of the system so if you're interested in this uh you know research Direction I would encourage you to you know read up on it think about it and we actually have a publication about this topic so if you're interested in a much detailed discussion about the ideas that I talked about here you can go ahead and scan the QR code and read the preprint that kind of concludes my talk today thank you very much for coming thank you very much Peter we have time for one quick question uh I was wondering uh what your thoughts are on parallelizing just balance transfers uh which are much simpler instead of contract stuff just like ethereum bounds transfers like certain transaction types are radically simpler than contract execution and I wonder if you had any thoughts on that yeah that's a good question so here we only considered con contract storage conflicts but actually there are different kind of conflicts you know another part of the state trees the account with the nouns and the balance so yeah simple transfers are expected to be much easier to paralyze and even with contracts with access lists you get much more information that you can use to paralyze but I'm not sure the majority of transactions I think are contract calls so I'm not sure about impact of this but I think that's certainly something to to look into thanks again okay thank you very much Peter and Applause for Peter please