Before, During, and After: The 3 Sides of Parallel Execution | Danno Ferrin - Hyperledger Besu |

e hello this is probably the most interesting title for a presentation it's titled before during and after the three sides of parallel execution this is danaren he's an ethereum core developer with hyperledger Bess yeah thanks for having me here um so this particular topic about um how best to bring parallelism into ethereum in a way that benefits your ethereum more than just speed has been something I've been thinking about for a while here's a tweet that I did from last June you can tell it's a real tweet for me cuz there's a spelling error in it but getting just simply speed out of parallelism is is a great Advantage but I think we can do much much more about it but we really need to change the way we think about parallelism and where we where we go into the execution so we need to think about parallelism before during and after transaction execution so that's that's the kind of the focus of this talk to go on the three sides of it so I'm going to talk about four things here first I'm going to lay down some some Base information about concurrency and some to to kind of set the foundation for where we're going to go then I'm going to talk about before during and after the transaction of how we can apply these principles um to apply parallelism into ethereum but like true multi-threaded ISM I'm going to do this out of order I'm going to talk about concurrency then I'm going to talk about what you can do during the transaction and then before and then after so when you talk about parallelism you go into an entire area of of computer science relating to concurrency doing multiple things at the same time in the interactions that go with it and it is a very Broad and deep area that you could easily fill hours and hours talking about there's stuff like amell's laws semaphor locks scalability threads context switching um transaction ordering and and all sorts of crazy things that could be impacting your concurrency but I'm going to be focusing on those just one aspect of it and that's about the transaction parallelism not even the op code parallelism so much within within a transaction but how you can take multiple transactions and do them in parallel without interleaving them so that's kind of the focus to kind of set the stage for what we're talking about now when you talk about transactions in parallel parallelization you need to step back and think well how do they handle this in databases and there's two common acronyms that go along with this acid and base the SQL databases usually focus on the acid acronym which stands for Atomic and consistent and isolated end durable these are transactions that have a very solid meaning and a very solid reference and and are very firm in what they mean and then you get into the nosql camp um databases like Cassandra and all those other no databases that keep stuff moving around you might think of data availability sampling when you think of the kind of soft things about that and the ba stands for basic availability soft State and eventually consistent now when it comes to a transaction and the balance in your wallet you don't want soft stay you don't want maybe it's going to work so you really need to focus on the asset side of the transactions so when we talk about parallelizing these transactions we really need to think about the aspects that that we get from the asset characteristics and the most important one of those is isolated and that's something I'll come back to um when I talk about after the transaction because that's kind of important to how we get parallelization to benefit end users now the three sides of the transaction I call it prefix infix and postfix parallelism talking about whether you are doing things before the transaction during it or after and the things I'm going to talk about are things like utxos and strict access lists those are things you might put in your transaction before executing it while you're executing it you might use optimistic concurrency control block STM and you might do some things with OP codes called Delta rights and then afterwards once you have that execution and you've executed it in a parallel fashion you can use that information to create parallel receipts and parallel to create isolated receipts and isolated proofs to where you can prove and get receipts for only what you did in that transaction without having to go through any more contortions so let's talk about during the transaction let's talk about infix parallelism now this is the sort of thing that that is being talked about a lot and is being executed to make it simply faster because it it very NE ni very nicely fits in the current models of the transaction two good examples of this are monad and Aptos and sui monad uses something called optimistic concurrency control and APS and sui created something similar but slightly different called block STM software transactional memory we'll get into that in a little bit but first let's talk about what OCC or optimistic concurrency control is when you think of parallelizing a a a list of tasks that you have to do this is like the simple obvious way of what you would do it you would take all those tasks and you would just do them in parallel and then afterwards you take them together and make sure they make sense so it's a bit more you know at the high level that's what it is so here on the left you'd have um a bunch of transactions you put them in a pool and you have a bunch of parallel executors that would take those transactions out of the pool some transactions go quicker than other transactions so you'll get them in a different order than necessarily that that you submit them into the pool so that's where the sort step comes in you take these transactions and you put them back in order some of these transactions depend on resources that are very order dependent and that's why you have this sorting process because then you got to check the conflicts if I've done things out of order and it matters and I need to do it over you take what you executed you throw it away you put it back in the pool and you bring it back through the process but if you can verify that there's no conflicts in what you've done then great we've we've executed our transaction in parallel we can put it in the block and we can go on with our life so here's kind of an example of how that might work let's say we have 10 transactions and each one of the characters represents a separate resource that they use and these resources are resources that you um have to have exclusive control over and that you have to have in the exact same order that you see them in the transaction so if I access the club um in one transaction and the club in the next transaction I have to do it in the same order so a simple way that you might just do the transaction parallelization is you just might say great let's do the odd transactions in One processor and the even transactions in another and if everything takes about the same time it's actually going to mostly work out except for some cases but these are computers and they do strange things and so you might give one core all the odds the other core all the evens and you might get them all back back odds first and even second even though you said do it in parallel it might do it all in line which isn't a problem until you get into the the parts where you have a resource that you are now using out of order that you've changed the values for so in this case if we do the odds first we're going to have a problem with transaction 9 um because four hasn't been processed yet so the way this would work is eventually it becomes correct in OCC so we take our initial order we start sorting it we go through the order we get to transaction number nine and we see that the Stars already been used by four so we throw that transaction away put it in the queue it gets processed after 10 and then it comes back at the end we resort it back in the in the same order and we get it again and the net effect is you've you've executed about six transactions of time to get 10 transactions and you've nearly trou you've nearly doubled the time it the efficiency and time wise it takes to execute this transaction block STM takes a slightly different approach to this rather than aggregating everything at the end while you're executing the transaction it would look out for these conflicts so let's say that you're executing transaction one and you start seven at the same time Seven's going to see it needs the club and realizes it needs to wait for transaction number one to finish so it will pause and let's say you start number two and then number eight does the same pausing routine but let's say you're starting transaction number three late well A's going to be executing it's been using the diamond it now knows that it's useless so it restarts and starts over with another transaction number eight and of course there's the same situation that in OC where you could have completed transaction 6 before you realized you had your conflict so you just have to pitch it out and start it over so block STM does about the same things that OCC does it just does it in line and gets about the same transactions so as far as doing it before the transaction you get great time Improvement computation if you're worried about counting CPU Cycles it could be quadratic when the user impact well what's great about user impact is you don't have to change a thing it just magically works if it's done right this parallelization it just goes faster and there's no no impact there's also Beyond wall clock time no benefit so let's talk about you know taking some steps before the transaction to try and provide parallelization and the two best examples that are actual live networks doing what we need are Bitcoin and fuel VM now when you think of Bitcoin you probably don't think of parallel execution because you know block times are so slow but the utxo model is surprisingly um friendly to parallel algorithms each transaction in Bitcoin consists of an unspent transaction output that you exclusively own and is only ever used once so there's really not going to be any conflict if another transaction tries and uses it the transactions invalid you just pitch it and you don't even re-evaluate it so you can execute all these transactions and parallel take all of this this computational time and you just take the outputs and you do take the inputs and you have new unpan outputs and the problem is it's not Dynamic you're locked into your inputs there's no programmability it's only useful as money and oh yeah one more thing I forgot um all these unspent transactions come from other unspent transactions that's that's the important thing you should look at here now what fuel does is they take this approach and they use approaches kind of like strict access lists um if you use it on an account based system but they use a utxo based system and instead of locking onto a specific State they lock onto a a slot number or a resource name some sort of an identifier of the state of the contract that is separate from the actual state held so in your transaction you would say I'm going to use the Spade resource and the club resource and fuel will find the most current utxo from that use it consume it and throw it away so you get a lot of the same benefits for parallelization parallelized parallelized execution that's parallel is a mouthful I really need to come up with a better word for that but for these parallel transactions it you can you can execute them in parallel and and and consider the conflicts really easily but the downside is the transactions get bigger you have to enumerate all of your dependencies up front and what's worse is if some of your dependencies are dynamic in a function of the code it's really going to be difficult for you to create transactions that do this effectively so it's it's fragile to to random things that your state contract might do like let's say you're calling a dynamic proxy and by the time between when you submit the transaction and execute it the the proxy might change address you could you know your transaction suddenly might be invalid because you don't have enough of the resources listed in your in your transaction list so when it comes to doing things before the transactions with utxos and strict access lists it's kind of a mixed bag but I think it's net negative you do get time Improvement almost as good as OCC and block STM um but the bandwidth is kind of not so much because you got to put all of your transaction information in your transaction and then you doubled down on that because you have to pre-execution figure out what resources you might need put those in the transaction and submit it so it's more work on the user for the same sort of a benefit that you could get just from going with you know block STM and OCC and you get basically the same parallelized return by doing stuff with dynamically generated conflict lists so before doesn't really quite work as well as the during and I think that's something that Mona has done some research on and they can actually back up with stats that strict access lists are actually a net negative so where does that leave us that leaves us to the third side of parallel transactions and that is what can we do after the transaction so we've executed in parallel Nirvana wonderful things have happened you know so what so just to warn you this is total loose Sky Zone there's no implementations from what I'm about to describe um this is this is hypothetical this is aspirational but I think it's truly what is needed to bring the benefits of parallelization into ethereum and make univ and make end users benefit from this so these were to create things called isolated receipts and isolated proofs by doing some changes in the process that not only make parallelization easier but make it more useful on the back end so to do those I would propose two separate changes the first one is to introduce a couple of new OP codes uh perer to S load and S St we'll call it sedit and S debit where as an atomic transaction it takes a storage slot and either adds or removes a certain amount from the number stored in that storage slot and we also enforce overflow and underfloor characteristics so if your storage slot represents a balance and you debit 500 credits from it and you only have 400 that op code is going to fail so that's why it's called sedit and S debit because it acts more like a bank credit and debit so we put the op codes we encourage contracts to start using those and then we wear those through into the state proofs um to reflect when you're using the sedit and S debit operations and that's we would need to add static rights and Delta rights to the proofs to show when a transaction updated a field not as setting a value but as doing a Delta change to the value saying I added an amount and I removed amount not just that I set it so to give you an idea of what sort of benefit we can see from these two changes we need to step back a bit and look at that same transaction um example that I set for for the OCC example and put it in the flow of a of a data dependency diagram as you can see a lot of these transactions have very few dependencies and they flow very nicely and what's interesting is if we change nothing in ethereum today we can actually get a somewhat decent um example of of isolated receipts you just get rid of all if you're interested in transaction number eight you'll need transaction number two and transaction number three because you depend on them but other seven transactions you could take them out and everything will still add up and you'll still be able to prove um that your transactions came from the right State and get the right outcome for the contracts that you're paying attention to so that's what's great about you know that the isolation of these is you can still at least get it today in ethereum but not all of the transactions are as good as that let's say you're a coffee franchise and you decide you want to pay all of your employees on ethereum so you take your balance you pay your employee you pay your next employee you play your next employee so on and so forth you got a million employees what happens if you're the millionth employee and you got over 900,000 transactions before you and all you want to verify is that I got paid now you have to verify the payroll of everyone else in the company just because you got paid last this is not really um something that's really going to be useful um to to typical end users I mean you know block block scan block scanners and and other things that aggregate all this data they're going to want all that but an end user only really cares about their accounts and they only really care about who's sending the money if they have enough to send it so this is where Delta lock Delta rights unlock um some of the potential problems that we have in parallelization Delta rights will allow us to share the storage slots across parallel executions where you can use the same storage slots on in multiple sides and reexecute it in any order and still get the same results so here's what happens today let's say you're going to a is going to send 200 to b and a is going to send 100 to C what you're going to see in ethereum is you're going to read 500 and write 300 in a see Zero and B and write two 100 and B and you're going to see in your next transaction 300 and WR 200 and in C you're going to see 100 and 200 now you can't change the order on those because you're not going to be able to read 300 if you're if you already have 500 and the state proof consists of listing that like a has 500 B has zero and C has 100 so it lists your start proof so to get your actual transactional legitimacy you have to execute the one prior to it to get your starting starting point but if you only care about the Deltas you don't care about the starting point what you're encoding is that a is losing 200 and B is gaining 200 or a is losing 100 and C is ging 100 there's also one other tiny bit you want to make sure the a doesn't get overdrawn so that's why we need to put a little bit more information into the state proof so in the state proof we would say a has 500 and all the other transactional ranges um have gone from plus 0 to minus 300 from that value so if you get them in any order um a is going to always be within that range similarly B has zero the good news is B is not being debited B's only being credited numbers only go up for B and C has 100 while C could spend it but C is not going to spend it so C could receive 100 so from the state proof when we encode the entire range of Deltas that the the field is going to have and the uh the starting amount something amazing happens you can do these transactions in orders and you can actually get validity that the instate is going to be correct and it's going to be able to execute so if your question is you know my check didn't come through Why didn't it come through did my bank run out of money or am I on the ofac list or did something happen with my smart contract wallet you can execute that just on your wallet and not have to worry about the rest of the block so basically take this isolated proof and all the other transactions that might have been in this long chain of payments just fall away you have your information you need to run it from the beginning and you can get it to the end and it all proofs there from crypto from the same cryptographic information that everyone uses you just take the transactions in the fields you care about from that proof and you can isolate it and get only what you need about it so what's the endgame for this the time Improvement it's kind of a mixed bag it is what the rest of your algorithm does it's kind of orthagonal to whether you use OCC or block STM or whether you require strict access lists so you get the speed up from the other systems that you would do before or during um the user impact is great because you only have you only have to see your information and the and the information that you need to download to verify just your transactions is much much smaller there is some downside though this is not compatible with the current way that dexes and automated market makers work they need to keep updating that number in line to keep moving the market around so if this were to be adopted there would need to be some research done in the defi Community to figure out if there's a way to get exchanges to work in a situation where the market maker might be shared across multiple transactions without being able to react to the other transactions in time sure there's a way just need to do some research on it so to summarize let me go back to this one slide at the beginning I have an old copy of the slides here so sum summarize the three different the three sides the parallel transactions are in fix see this is a problem with working offline with Google doc is it doesn't always get your information so we'll just do this so you have the prefix the infix and the postfix of where you put your information to make it parallelizable and the real value in the users comes and what you do after the transaction and how you can deliver that value to that user so I think we have the narrative wrong on ethereum parallelization the question that people are often asking is how do you use parallelization to make ethereum faster and that's a great question because faster is almost always better but we can we can go further than that we can use parallelization to make a theorum better not just faster but more useful and lighter on end users thanks you