BlockSTM: Scaling Blockchain Execution with Rati Gelashvili | a16z crypto research talks

Transcript

welcome everyone to today's uh a16z crypto research seminar I'm very happy to welcome ratty Gillis vealy he's going to be telling us about black STM I'm very excited because I've heard so much about this paper over recent months I really want to looking forward to learning more about the details so Roxy over to you thanks sir uh very happy to be here uh so yeah very very happy to talk about our paper uh this uh what is the terms work with Sasha Danielle George and the work started uh while we were I think all of us were working at Novi uh and now this is basically the engine that powers the execution of the upper

destruction so let me uh this is just a very uh very basic uh motivation flight uh as we all know sort of blockchain is a huge system and usually has this layered architecture so we sort of have a consensus part of it where we agree on a sequence of blocks once we agree on this points of blocks we sort of execute the trend they contain transactions uh like sort of this globally ordered sequence of transactions we execute this transactions we actually execute transactions in a block and then we sort of save them in storage but all we're trying to say here is that we we're trying everybody is trying to sort of

scale up blockchains make them as performing as possible but the weakest sort of basing holes because it's like a layered architecture if one of the components is very slow it's just going to be the weakest link it's going to be the bottleneck so that's basically the motivation to look at all the aspects of it and uh yeah I I believe uh Sasha talked about consensus right but yes we're basically trying to tackle all of these challenges and today is going to be about execution so in particular what happens here as I said is exactly we are our input is a block so we sort of received this blocks let's say like a tool here and then every validator this is very crucial sort of

requirements right like basically every validator has to execute the transactions in B2 and then the output of executing this transactions has to be sort of has to affect the global uh blockchain State and in fact it has to be a deterministic uh function sort of application that happens at the end of the sort of output of the block and there are a bunch of because there are many blockchains out there and there are a bunch of engineering approaches that we can take of course we can just take all the transactions in a block in the order they're given to us and just go and execute them one by one uh this turns out to be really slow I mean

especially as you start pushing the performance if you get stuck with sequential execution this will for sure be available uh so nothing sort of groundbreaking in the fact that in this at that moment you want to somehow use fireworks right because you have uh multi-processor architectures you like every computer has many cores you want to sort of you want to utilize it to the to the fullest to try to sort of alleviate the spot on it so in one of the one of the approaches that's pretty common is to sort of uh ask the users to declare either the dependencies or some sort of

hints for where this transaction what parts of the stage this transaction is going to write to and um I mean we will talk more about this this actually seems like this actually simplifies the problem quite a bit and allows some sort of efficient approaches but it's quite limiting so first of all it's not ergonomic if the user has to do all this work and moreover what if you make a mistake or if you can't know exactly where the transaction is going to write then the transaction may need to be broken up it may need to be retried oh yeah so so that's basically the the limitation here and so this this brain size mainly to the design goals that we

had in mind when we set out to sort of build this uh parallel execution algorithm the goal was to make it basically transparent to the users so we have transactions we want to compute the we want to execute them but we don't want to do we don't want users to do any extra work from their perspective we want it to be the same experience as if we were running sequential execution engine uh and on the other hand because we actually want to be practically motivated and in blockchains you want to be sort of uh you want to have considerations against adversarial behavior and also just all types of potential transaction loads it's possible that every transaction will depend on something that the previous

transaction writes it's like unavoidable and we want to build something that in this case doesn't isn't much worse than the sequential execution right and this is very critical uh design goal but on the other hand if there is parallelism we want to exploit it to the fullest so essentially it becomes like in try to extract as much of the inherent finalism as possible out of the out of the transactions that we're doing so what does transparent to users mean for you so this was I I remember I was discussing about this word and uh what it's supposed to mean here is that they don't need to they don't need to know uh

how the sausage is made they don't need to know that we're running parallel execution uh even if it was sequential execution they don't need to give us any hints if they just submit the same transaction as it was before right I would say invisible to use those invisible I think would be would be better yeah and maybe another question are you thinking about malicious malicious luscious users like somebody trying to exploit this to break the system or uh yes I mean in general sort of the the whole blockchain setting we uh we wanna uh we we assume sort of uh adversarial setting for this work it manifests itself in a few ways and why not one of which is because usually

like if transaction is broken we will see like there is a whole like execution environment for it and usually like that's in charge of making sure that like I think like sequential or parallel it has to make sure that like a transaction cannot do something that's like not allowed by specification however as it pertains to parallel execution for instance if there was a way to construct uh some sequence of transactions that would break the algorithm or make it run for a century we have to protect against that right and that's one of the motivations for saying no matter what happens we want to design an algorithm that is uh that is not much slower than the sequential

right so that's like we start there and we don't want to be worse than that it's like uh of course there's going to be some overhead like if you literally give us transactions there like just sequential uh we are we are we're dispatching all these threads we're doing a lot of extra work but as I will show you uh we managed to keep the overhead like pretty low uh great question thanks uh so so there is actually a lot of academic work in a lot of related topics which I'll try to sort of briefly overview uh one word uh is sort of called minor replay and this is actually exactly for the blockchain

setting so minor sort of kind of feels like proof of work but it applies universally like basically the idea is that there is someone so you can view this as a leader for instance right so there is someone that creates the block and let's say so as I said like and we will dive deeper into that but if we knew where a transaction was writing or if we knew which transaction had conflict with each other we can be smart and the problem becomes significantly easier the the point is we don't we don't want to assume it but so over here the the idea is that let's say the the leader that creates the block

I can execute the block you can see sort of what the what the behavior was what read what what road what or what depended on what and then there is all this work kind of deals with compressing that information making that information is like easy to transmit as possible is easy to execute as possible but the idea is that all the validators can replay the same block and they can be much more efficient because the data comes with this metadata that allows them to run it more efficiently right and it's a it's in fact for from their perspective the way these algorithms are designed they can really run a very simple for joining schedule uh based on this thing that the miner or the leader tells them what are

some of the sort of limitations of this approach and this is also where the adversarial thing comes into play right part of it so there is for instance a huge trust issue here right like uh why would they tell me the correct information like maybe they will give me adversarial information and then I will actually be slowed down I guess you can work around it and have a fallback that if it doesn't look like it's going very fast I will do training from scratch but there is also an issue of latency right because no matter what like we are reducing kind of the tone work because the validators are faster but someone still has to run it in blind right and then the latency still adds up and some of this uh extra

work actually we're trying to still rely on some static analysis on pre-computation to sort of uh make this uh dependency bag information as as like Compact and efficient as possible um the actually one of the most related work uh was from the databases literature there is the statements paper called phone uh so what they did was they built this system that executes a given set of transactions in a fixed preset order so the order is set in stone you're just trying to execute it as fast as possible this paper makes the following assumption it assumes that we can have a

and I will explain we can have a perfect over estimation of where the where the transactions are each transaction is going to write and what I mean by the perfect overestimation is again like not the best phrase probably uh you are not allowed to underestimate you are allowed to overestimate overestimation if you overestimate and not actually right there the the algorithm will deal with it it will induce some overhead but not dramatic but God forbid you underestimate you have to run the whole algorithm from scratch right and how do we how do we get this uh sort of overestimate becomes the same problem either a static analysis for execution

to be fair to this paper in fact they are in the databases setting and over there it's like stored procedures it's much more limited change so it's much much more reasonable for them to make this assumption uh sorry probably super question um so we don't talk about reading at all but is that not relevant so depending on an algorithm or approach it would be because at the end of the day it's all like actually how you design sometimes right right conflict matters sometimes it doesn't but at the end of the day you read write conflict is a is a key that you cannot run away from all I mean is that this algorithm relies heavily on the it manages the reads but it really relies heavily on knowing the rights it

doesn't really care if you know the reads or not and I think the engineering approach that I said is also similar so it just turns out that if you know the rights there is a lot of sort of things that you can you can do but I'm sure that like knowing the reads would also help but yeah um so then the idea here is that because we have this perfect overestimation uh we basically can pre pre-compute or pre-build a data structure where we allocate a slot for every right that we estimate is going to happen and then we sort of then what happened exactly like very good question right because now every read I know exactly what it is supposed to read

right so it can just go and either read it or it can wait there so there is still because we're dealing with overestimates it's possible that this location never gets written so you have to deal with it in the algorithm you have to actually mark it as like oh I actually didn't end up writing here and then you sort of do a traversal and Etc but we're not here to explain this algorithm but this is what it does right it's a it's a it's a really good algorithm it's it's highly efficient but again it has yeah the the way it has again this this drawback from our setting that we really don't want to require uh write estimates uh we want to assume that we want to let people write arbitrary smart contracts where they have secondary indices like I read something and based on what I read

I do something completely different like options whatever and here in any unestimated right is like very costly yes so how do you how do you think about locations so actually good good question so let me let me sort of fix some terminology and I can I can use it for the for the rest of the talk so it's uh we can we can basically have this abstraction that the whole sort of State consists of these slots like in like our location so let's call them rotations and every write and read is just sort of on on those right and if you happen to write somewhere that like some other transaction is reading and that

transaction is serialized after you they would have to read whatever that like the latest thing that God wrote to this location right and if I ever use a path it's the same thing it's just something that refers to a particular memory location so it an address would be a location is that how you yeah sure so our memory is also I shouldn't use right in shared memory that would be the but yes so there is this storage and let's say storage consists of this like locations and then we can identify like every transaction reads some of these locations and writes to some of these locations and can do like arbitrary logic expressed in a programming like language to do so okay

cool and and then there is this uh sort of Prior work it's like tens of thousands of papers I think with like uh in like award-winning uh sort of uh papers from uh uh from 90s which is called the software transactional memory so this work is very relevant right the setting is very relevant the idea was that uh the idea was that we're giving like arbitrary transactions and we want to atomically execute them and so um it was basically designed or intended to replace locks and make this very easy abstraction for people to write con

write programs and then if they have conflicts or not this would be dealt by the framework right um and there are many as I said it's a very very well studied topic and there are many different approaches and they're in particular the one that's relevant to us is uh called optimistic concurrency control so in optimistic concurrency control you execute transaction and then there is uh you execute it optimistically you execute it and somehow you execute it based on some states that you currently have like the details make better different from an algorithm to an algorithm but then at some point you have this extra validation set and what validation does is it basically checks uh whatever you

read is it still uh is it still if I if I read it now would it still be the same and then again sometimes there is locking involved sometimes not but the idea is that if validation fails it means well I try it optimistically but I I didn't get the right uh input so I have to discard it it's useless so I have to do it again but usually if you succeed you can commit so you say okay so I can I can use this execution result unfortunately software transactional memory is rarely used in practice uh because these libraries are sort of have limited performance they have to do a lot of bookkeeping and whatnot and for specific problems where you could apply

a software transactional memory people usually just design handcrafted like specific Solutions through that particular problem and it's more efficient also generally outcome is not deterministic because all they care about is having some serialization order but there is a line of research called deterministic software transactional memory where uh the extra environment is that no matter where and how many times you run it you arrive at the same output this would be applied applicable to us and we actually benchmarked against one of the deterministic software transactional memory libraries the thing here is that as I said like even sdms it's a known fact like they're not used in practice that much because they're

not very efficient and the line of research that does deterministic software transactional memories views determinism as an extra constraint to satisfy so they have even worse performance they compete against each other right and we want better performance we're like sdn performances like black box sdn performance was not for sure not good enough for us the glimmer of hope here is that it has been shown in the past that for special if you if you relax if you limit the scope to specific problems like linearizable cues texts whatever you you could sometimes design software transactional memory libraries for those domain problems and make that efficient so there is a way to view this is why we

call it kstm it's there is a way to view our work as sort of blockchain specific software transactional memory Library even though a lot of sort of I think some techniques that we uh come up with are are more General sure it's like a clinical example you're like suppose everyone's just pushing and popping on a comment share in queue that's all that's happening and uh I think there was more than that but uh yeah this was uh Sasha in the paper about that and there was some other papers the operations were limited I guess yes it was like I think it wasn't just huge it was sort of some generalization some obstruction over this kind of data structures but essentially is um I think you get deterministic and Etc

I'm not sure the other thing was deterministic but uh well the only point I wanted to make here is to be fair right like there are stms that are pretty performant but usually they've been shown in like limited settings um so this is actually so I this there will be a few sort of places where I hopefully demonstrate that our like blockchain use case allows us to do certain things that are that allow us to be efficient uh so this is a good example of that and it certainly like saves a lot of synchronization and makes our experiments more performing um I wouldn't say that this is like the make or break thing uh but but it's a

good example of a specific thing that uh blockchains offer where it is very helpful for Designing algorithms which is we in the blockchains as we described before right you want to execute a block then you want to execute the next log so in in software transactional memory you have this long potentially infinite like list of transactions that you have to process you have to deal with like garbage collection you have to deal with knowing what's committed at any given time we can we can just avoid worrying about it we can garbage collect at block boundaries and we can also just track when the block is committed we don't need to know when like transaction five is committed do you think there's a

discretization of time because of these blocks and it's like it comes naturally right there's a part of the problem and this saves a lot of synchronization actually right yeah um the other one which might be like a lot more powerful I think in terms of like designing algorithms for us is that um what uh especially optimistically concurrency controlled algorithm set to contend with uh software transactional memory algorithms is that they never they run in some statements and this state so here is an example like a user might have some invariants which are always satisfied in sort of sequential

executions but unless you take some extra precautions you might violate sort of uh this uh invariants while doing optimistic execution so for instance uh let's convince ourselves that no matter in which which order you run this transactions assuming also in the beginning X is bigger than what x x is always going to be bigger than y right if you execute these transactions like atomic but now if you're running them optimistically and just sort of just doing instructions concurrently with each other this can happen right like the green thread might write x two then the perk like then the blue thread might read it purple thread might write uh sort of do two more rights and write x equals three y equals two and then blue

will divide by zero and make everything explode right so you have to have a way to deal with this because you cannot just build an end like for form a sort of software transactional memory uh point of view and there are like properties called like opacity and so on that deal with it and then they have to make sure that this holds and that also adds a lot of like synchronization and work right and complication for us again our setting is much simpler because we know that we have a like smart contract programming language and it's running inside a virtual machine that executes that smart contract and in fact the aiming Behavior here that is expressible in the language is an allowed Behavior

it's vm's responsibility to catch errors right if you if so for instance like division by zero will just be like a transaction will fail and it will return an output that I divided by zero right and if it happened during psychology execution and this is not the real like it was just read the wrong thing it's fine because we're going to re-execute it later and it will give us the right answer right but we don't have to worry about uh sort of catching panics and like I don't know making sure this never happens um yes so we can continue running um and then the last one is really really key to sort of everything we do I

would love to say that sort of we made this observation first but it's not true uh boom like very explicitly made the same observation I guess we kind of we were inspired by bomb we were working on it we actually did realize it and then we were reading bomb and we were like wow they literally explicitly say the same thing which is which is great so the point is that there isn't there is this intuition that um if if I'm allowed to choose from all the possible serializations I will have more freedom I should be able to run more efficiently right and there is certain truth to that right like if uh there might be specific blocks where depending

on the ordering there will be more conflicts or less conflicts however uh notice like just this very sort of uh simple thought experiment right let's say we're just some software transactional memory library and uh the purple thread is trying to run transaction X the green thread is trying to run transaction y basically green thread never runs and just purple thread runs eventually sort of purple thread will commit x and x will be serialized before y if green goes first uh y will be serialized before X and if you've seen sort of this uh official Lynch Patterson kind of impossibility results for consent so it's it's very similar like essentially

what we're saying here is that if serialization has to be determined during runtime we are solving this very consensus-like tasks for basically every transaction that's running concurrently because we are also trying to decide we try and get serialized first and consensus is not an easy problem to solve uh there are ways to solve it but it inherently needs like synchronization right and this observation that Bob made and I I believe we really pushed it to the limit is that if I just fixed the order I avoid having to worry about what goes before what and I can I can sort of I can do a lot of things now that will make my problem significantly easier you

mean given that you want this humanistic if we didn't want deterministic well the preset order will also be a blessing this is even this is even stronger exactly this is even stronger we're not so if you just want deterministic well I guess if I if I don't care about determinism like if I care about determinism like I understand it's like all the audio arguments can make total sense uh but if you're saying that's what that's a blessing of it if you don't need determination then I'm confused I would even go that far except with an asterisk that of course there is uh this choosing the order element of it right so if you choose the order uh it's it might be possible that I

pre-commit to this preset order that's just bad and you happen to get lucky and somehow run it in the order that allowed you to run it parallel and like maybe you beat me but let's uh but in like but let's say we were if the order was if other than that right like if somehow you made everything equal or like it's your preset order was like reasonable representation of all the ordiners available uh yes This Will Destroy any possible sdn Library out there that will not even if they don't need to be deterministic but if you don't want to be determinister why do you tell like

glucose first fine because you have to decide right you have to decide the algorithm is not explicitly solving consensus right the algorithm is sort of running things and validating and running the game but inherently it's uh trying to decide who goes first because if you abort me you want consensus and I have to agree with you that you were first or some sort of leader election right and and person said if if my right aborts you then somehow iv2 and and we are we are paying all this overhead to decide who goes before who uh that's the intuition but uh as I said this is this is something that we exploit a lot and I'll show you at least two ways how this is very very very beneficial but the the

observation was made very exclusively by bone exactly this observation so just uh make sure I understand that discussion so this preset notion of the order it's not about deterministic or randomizes about the fact that this ocean is this order is pre-committed to before you look at the transactions that you're ordering you can even look at the transactions but it is one point that you make is is crucial is it is even stronger than deterministic it's like deterministic would be like a deterministic STM would be just give me the same serialization every time and this says give me a serialization that I pick like somehow we pick ahead of time like this is gonna like your output has to be the same as if you executed this transaction

sequentially in this order that we like that is committed to ahead of time um yeah so the fact that it's ahead of time means it can't depend on the specific transactions that you're ordering or you can uh so you could have a like a different component that looks at transactions and determines an order and then then we all execute it in that order right uh that would be that would be a way to use this system but what we do right now is is is what you're saying like basically we just we just say let's take the order that like the transactions are are in the block and let's just do our best right so this okay so we're all committing to a recipe

a recipe that results in us all reaching consensus over the ordering we're aiming for yeah we're just we're just increasing yeah we just we just agree we just agree on in order transactions but we like a group what the function is beforehands uh it's it's a bit confusing to phrase it that way right because at the end of the day the order means nothing it's still the transactions that will determine everything right but you could say it will it's always the order you can and you can use it in any way as long as we have a deterministic way to agree on the ordering it can be some function that we can all run and gives us the order and now that's the order

right uh as I said for us right now it's very naive we just take like the the validator proposes a block it contains transactions ordered somehow we will just take that right but actually it's a really interesting future direction to either find like try to quickly guess what order would be good and use that as long as you have a deterministic way or like have a like unpredictability to something like this um so the Black producer fixes the linear the serialization and then it's just now your job does speed that up as much as possible right okay and actually another so the paper

just got accepted that people can in fact we like one of the very useful feedback we got from the reviewers was uh like I already mentioned like three almost separate lines of research that had connections right and there is also this thing called thread level speculation that like threads doing like computer architectures where you're just you're trying to execute sequential code but you're trying to guess right so and and exactly and they're like also the the order is fixed and you're just trying to do your best so there is also like basically some similarities there um so maybe maybe I'm going too slow but yeah so this is a high level overview of sort of how the how the system looks uh we have uh we have exit like we have

executor basically where all these like threads lead and we have a scheduler that uh is the brains behind like what uh it schedules tasks and tasks are either execute this or validate this so and when you get the task so you like a thread so the way it's designed is basically threads just constantly do the like repeat uh a loop where they try to get a task let's say it gets an execution pass then you go then the third goes to the VM with the particular past like like a transaction that it was given and says execute this for me uh while in order for execute that the VM needs to make reads uh reads will be

from this multiversion data structure that I'll explain that basically wraps uh storage right but it also includes some speculative things that other transactions might have written so it will run it in this weird whatever optimistic uh sort of view of the world it will never write it will just produce the right set and the output and will return it back and then we can apply the rights to the to the multiversion data structure and sometimes like actually everything needs to be validated it's still like an optimistically optimistic concurrence controlled algorithm so a validation simply just goes and checks that reads are still valid and then every time you do a task you

just have to go back and update the scheduler based on like what happened in your like like with this task like the validation fail did it succeed like yeah it's like and at the end of the day uh when we're done we can basically apply uh what we have in this multiversion data structure back to storage and we we continue right and we can also if there is more to the output than just rights uh we can just take the sort of last every execution output but for Simplicity we can assume that it's just a global State it's only reads and writes and basically what you need to at the end of the day the multiversion data structure will contain the final rights which are consistent

with the rights that would happen if you executed everything sequential what is the value how do you validate so there is an implementation detail to make it more efficient by like stamping everything but essentially we're validating that uh whatever you read during this optimistic execution you have your reset which means like I read this memory location and this is what I read I read this location this is what I read like we reversion them so that we don't actually have to check the whole data right but that's a decal and then you just go back and they re-read the same locations and you make sure you just check whether it's the same or not

if everything is the same you save our vision succeeded if anything fails you say validation failed and what happens after failure what if multiple of them fail do you like kind of go the same you so every what is similar to what I've described before is that when a validation fails it means you this transaction needs to be re-executed so when you go back to the scheduler you tell validation failed it will internally update the state and Mark this transaction abstractly as it needs re-execution does this mean that the commits that happen the rights that happen in the execution of that transaction we will clean the rates we

will clean the rates and actually we'll do something more than that which is one of the one of the key pieces actually but uh yeah we'll actually mark them as estimates but I'm getting ahead of this trailer is really is a bad thing or is just like a overly broad check uh so so then yeah so the failure just like failure is obviously bad because we have to re-execute this transaction well I I'm not I'm not sure I understand this but it's about so so if I don't know just like like background but like it kind of it may be that in the sequence like something should change after the transaction yes and like maybe this transaction should still go first like why do you need to push it later but we

don't push it later what would we say but but there is just one dependencies that's the so two things uh first we like because we have a fixed order things are a bit different than just saying like oh just basically for us a failed validation means more than just a re-execute this transaction yeah because because actually we it's we cannot just take this transaction and serialize it somewhere else right it has a fixed order so if some other transaction was successfully validated but now this one is before and I had to re-execute it it also means that the next transaction I also have to

revalue it right but then we do but but actually that's exactly what I was kind of getting oh actually yeah I'm gonna talk about it like 10 ways yeah but so one one piece here that uh hey I hope we'll be like it's it's relatively simple because especially I also mentioned that Bond uses a similar structure but Mom assumes that basically you have this overestimate so you can statically create the data structure for every estimated rate we have a similar data structure it's a multi-version data structure this is also a very common thing in general right where the idea is that different transactions do not override each other's data they just write to the same data structure and they just say on transaction five this

is what I wrote right and this is the general technique that lets you avoid right right conflicts and then what you do is like okay so transaction write by transaction six happen you just put it there and it's ordered because we have an order so that's convenient and then a read will just have to like basically find the highest transaction that's lower than it in order to read that right and if it doesn't find anything it has to read from Storage uh but and okay so this I also mentioned but uh um it's it's relevant for the for the like technically Noble things that we do to understand so the way the scheduler works it has this global global queue obstruction of course it's not

implemented as a queue of tasks but it's basically the the interfaces that every thread just keeps going eventually the scheduler will tell if your time but before that is just like give me the next steps give me the next steps give me the next step the scheduler is in charge of deciding whether it has to do an execution or validation and if it has and which transaction right if you have to do validation it will tell you uh here is the read site goal validated still valid right if you have to do an execution it will tell you uh go go to the VM execute transaction file but internally it has to have all this logic to to dispatch these things right and so it has to essentially do two things one or it's very desirable that we do two

things because we have preset order we want to make sure that we run the lowest task that there is available to us right uh early transaction yes because if like transaction five kind of needs re-execution or validation it's useless for us to do 100 because uh most likely this is like not going to be useful work um and the validation must logically occur in sequence meaning if we executed these three transactions and then we validated them and validation of two failed we know that two has to be re-executed but actually actually three needs to be revalidated because two

might change something and because we fix the orders they will have to reread this so this is just like we can go through this quickly uh essentially this is what scheduler does right it basically uh oh and an important thing exactly from the previous example is that successful validation for us doesn't mean it's safe to commit uh there is like a predicate that we use in our proofs to show that like eventually everything's committed to the state that it needs to be when the block is committed but we don't even track what's safe for me right there is a predicate that lets us know when everything is ready but a successful validation is just nothing but a failed validation is means that you need to re-execute and possibly Mark other

things uh to require revalidation and we also in the scheduler also manages dependencies in fact if a transaction tries to read a location where another transaction is estimated to write we suspend it we mark it as a dependency and when that transaction re-executes we continue and at this point you must be asking me how the hell do you you just told me you don't have estimates you don't want anybody to give you estimates like what why how are you chilling right and so this is actually one of the one of the key ideas uh in the paper which is okay so where do the estimates come from and what we and it's actually really really really simple idea and it's kind

of changed like as I will show you it actually changes uh it improves something that people have been doing for like many many many years so essentially what all we do is when a transaction fails we know what it wrote before so we just go and Mark all of them as estimates right we're saying look I mean you're running to I mean you might need some states that wasn't quite the state you wanted but this is what you produced I'm gonna assume that the next time you might it's not for say like we're just assuming that you might write to the same location so if another transaction so let's say transaction three aborted we marked the previous thing as an estimate now if the transaction five

comes I see an estimate essentially the default process here is I know I have to re-execute three previously three rows here so there must be likelihood that three rights here so let me not go ahead Let Me Wait Until fee runs again and then run right and this is really important because one of the things that till uh SDM performance is this cascading of words where like you sort of something changes and just Cascades out of control uh and let me say why this is actually important right it's a very simple idea but but but why is it powerful there is this concept called so there is all this static analysis work right to get the like or user provided things but but a

lot of systems what they do when they need some sort of estimates for performance is they do like pre-execution so you take all your transactions you run them from the initial state embarrassingly in parallel and and then you take whatever they write and whatever they read as estimates it's some sort of estimate right and this is this is from the initial State you see from the initial State and the idea is okay this is not perfect but we just we just waste this one thing but uh but it's literally embarrassingly paralyzable right um and this is this is a very own Paradigm right it's called pre-execution and you can view what we do as just a strict improvement over pre-execution uh

why is that because um in a good case where we didn't have any aborts we did not need to execute everything one more time we just didn't and when there are aborts yours your meaning pre-execution so pre-executions estimates where from the initial stage but here every time I've worked I am running in a more fresh State and my quality of my so basically I generate estimates when I need them and the quality of them keep improving if I keep aborting right uh so this is basically this is basically the idea here and for in contrasted with bone our estimates are just best efforts right like if they're good they're good but if we miss

something it's not a disaster and in the other approaches if you don't if you underestimate you have to like run from the beginning I was just wondering so this other task that saves an estimate stops and waits until this is updated so could it happen that all of them got stuck waiting somehow in a in effect so that's when we prove that that's not possible the idea there is simple because there is essentially boils down to the fixed order and just a decent rate because you can only get stuck on someone that's lower than you so you cannot like infinitely descend makes sense or because like

it's like a weight for something that you would have read which would be something right estimated rate by a lower strictly lower transaction and then if that transaction is also waited for someone then again again should I roughly think of it like the old solution unestimated right here to go back to the very beginning but here you just have to go back to like the sort of deepest unestimated rate and go from there instead of the beginning I said how you think about it or yes uh I guess the so so at the end of the day you're just using uh the only or using the estimates from is to like the worst that a conflict can do is to

trigger you to re-execute because like execution is much much more expensive than validation or anything else that we do so any knowledge that you know that someone might write their read here all you're trying to use it for is to sort of avoid this mistake right and this is also usually how pre-execution is used but it can also be used in other contexts in other situations but yeah so but but here you're essentially saying I will start blind I mean if you actually this is this is another good point where if someone gives our algorithm some estimates we can start from there we can just mark them as an estimate right but we just start blind but if we happen to abort now I'm gonna like now I'm gonna use this as estimate

so I have at least like a set of things that I will will avoid me making the same mistake and then we'll keep going right and it does and there are also two ways to build when an estimate happens like one was to just like crash and do it again I think what we do currently is just really just wait at that moment and then then restart and funnily enough we were really surprised like sometimes we would run sequential loads faster than sequential execution and we were like what the hell is this like what did we mess up and then we realized what was happening because if you do it this way it's possible that some prefix was useful no and you got lucky and you waited on this

dependency and then you could so even though it's sequential load usually just means that the transaction has a read that depends on it right from here right but it might be like in the middle or in the end of this transaction and then you could have done useful work here and then reused it and this actually happened way more often than we expected and every time we forget and then we say it again we're like what I have events yes that's so the other so this was one thing that I think allows our sort of system to be really fast and I think this is not it's it's kind of Novel and the other thing is also a novel thing which is a game very heavily dependent on the preset order

so how the idea is how do we take the tasks with lower transaction index because this is also really really crucial for system performance um so in fact like my advisor has a bunch of papers about it and this is also a very well studied topic right concurring data structures concurrent priorities concurrent ordered sense uh the big problem there usually is that if you do a priority queue uh you ever like you want to extract the lowest index like lowest element or highest element highest priority element everybody is kind of contending on the same element and it's it's hard to parallelize but they have ways like they usually like relax the semantics so you can take one of the one of the highest priority ones and you can kind of scale it it's it's

pretty decent but actually for the performance that we were intending given that was not good enough or we we wanted to push it further and what we do is we again rely on the fact that our priorities are not arbitrary they're they're indices and they're like very well compact indices from one to zero to block size right so what we do is essentially I mean you know counting the sort so we do basically accounting based concurrent order itself right so essentially the idea is that even though we don't track what's committed usually some prefixes like usually the threads are working on some dense interval like they're like executing invalidating right like

everything here even if we don't track it from God's view is committed and everything here we haven't even started yet so and this is a very dense like set of indices so inside my assumption you can only depend on things before you all right uh yes yes and the reason right but like but but for here even that's not like as long as we just keep a status per index just looking what's looking for the next one it becomes the traversal right you're just traversing the indices and you're looking like oh doesn't mean Foundation doesn't need execution so you just track an index you like reset that index the worst thing that happens is you have to walk over a bunch of empty slots right uh and then we we optimize it a little bit like you can you can

have either one index or you can have one index per for validation tasks one index for execution tasks uh but these are all details so if I take if I have uh K and all everything before okay got commit got executed and validated already and I validate k then I can commit k if it's committed yes but we actually never we are experimenting with these things but in the current version of the system yeah yeah no that's true that's true so if you didn't get like are you using this property or like no you're not using it yeah but but it's true but it's true so uh if if if the case things are committed and you happen to successfully

validate K plus one it means that K plus one is can also be considered Community but we don't track it uh we just yeah but yeah that that property is technically true the reason we don't even trade it like it allows us sometimes to even not do that sequentially like you can have five validations that all succeed and that all happen concurrently and now technically all five of them are are essentially committed um because if one of them one of them failed it would Mark all of them for revalidation right so but but yeah what you said for short for short correct and so I guess yeah so this is just an example so we are at this index and

essentially you can do fetching increments and like some light synchronization another thing that we observed is like so essentially what this index does it just tricks the minimum of all things that we know requires validation or execution and we just have to maintain that environment right but but the funny thing that happened also is that so let's increment everybody touches the same counter so that counter is kind of contended but it also gets amortized because in between you do the task and whatnot but uh but once you do that such an increment then these instructions are implemented in Hardware they're relatively like they're very optimized but once you do that it also acts as a load balancer on

individual statuses right because everybody gets a different index like if I do a fetch an increment and you do a fetch an increment it's a moment like we get two different indices so in the beginning we were doing some crazy like block free things to sort of do build these statuses and then in the process of productionization we're like just replace the everything with locks it's same performance because such an increment is basically a load balancer uh I will not go into this it's just some uh sort of uh details that you have to deal in implementations and proofs uh with that we have like 12 pages of proofs to actually prove that the algorithm is correct in terms of what it

will like it will terminate and it will produce the same output as the sequential execution of the fixed order um and there are some optimizations that are really useful but I will not go into them because they're they're important for performance but it's not like very fundamental the only one I can mention is like sometimes it all becomes a question of how how early can we start validation because the earlier you can start validation the earlier you catch potential Awards and the avoid the cascading and also how still how how can I avoid doing users work because when the validation fails you re-execute that

transaction but you dispatch everything else for validation validations are cheap but if you sort of do this wave after wave after wave it will become it will end up so we have ways to sort of like if you executed before and you have your set of wary roads and you get re-executed and you write to a strict subset of it we can prove that you don't need to revalidate anything because they would have seen the estimates and like things like this right but they're neat but they're not like uh some foundational thing right there in the context of the algorithm and lazy commit I mentioned it basically has to track how many tasks are ongoing and where the indices are has to do that often like atomically so we do it by essentially

doing a double commit double double collect you read something you really gain if it if it's the same you we can prove that the block can be safely committed um we prove correctness and finally I can I can show you the graphs so the way we Benchmark this is we benchmarked it uh we also know that it helped the system influence performance it's running in uh production but for to demonstrate like academically what this thing does we had to isolate the execution component so uh and that means we sort of we get a block that's ordered right we don't do consensus and we don't go to actual personal storage because that's like

expensive so we we have like some in-memory representation of all the states and we just we just execute it in memory and we have sort of implementation on on the DM code base and also on optos and we compared it to bomb uh in order to be able to compare to bomb bomb needs per like estimates right so we just gave it perfect estimates for free uh so that's sort of an like because sometimes it will beat us right but it's because it knows this thing that it would have to work really hard for or would be impossible to get and then there is little which is this uh recent deterministic SDM algorithm uh which basically came out a few years ago

and has comparison with other deterministic algorithms and outperforms them so we chose like it as a good candidate and um we tried it on peer-to-peer transactions so this is we thought it's like I will show you like this usually people might think that this is just a very straightforward transaction it's not like this transaction is very complicated but it's also not very trivial it does a bunch of reads and writes uh and uh I think at the DM days it was for some uh a lot of uh uh checks that it had to do about like accounts and whatnot and even adaptos it has to do a few extra reads like sequence number what not so it it's non-trivial

but what's what's a good thing about this kind of load is because it's peer-to-peer we randomly choose who transfers to who and by controlling the number of accounts we have a very good control on the number of conflicts that we have to Benchmark on so for instance if we do take two accounts it's going to be a fully sequential load uh because every uh because like every transaction will modify the same involves it's right read and write and then we try incremental like 101 to 10K and we also tried different block sizes uh so one way which it seems favorable for you to take those transactions it's like this seems like the worst super algorithm is something that changes outputs depending

on the reads because it said suppose you rolled to some address ax I'm gonna guess if you were to address X and the worst kind of algorithm like maybe is like if yeah some position right to X otherwise right away I agree I agree that's a that's a very good point yes uh that's a very good point I think it would be great to also quite Frank on that uh although uh it would also demonstrate this adaptivity of uh getting pressure estimates so I would be actually very curious that's a that's a really good point uh so this was also the transactions that were like yeah but we can write our own transactions so that's a really good point yes no thanks a lot so let me show you

though for these ones what we observe so first interestingly for Block size 1K uh we the first thing to notice is we scale as we increase the number of threads for uh which which is always a good sign if you're designing sort of a concurrent algorithm the the y-axis is thousands of transactions per second or yes yes and and so the number of threads and I guess these are the the lines themselves are like sort of it's tried four thousand and uh 10 000 accounts here and the black line is a sequential Baseline so a few things to notice

actually so the lithium it scales with uh sort of 10 to the four but it's like I maybe I don't know if that's order of magnitude but it's like still significantly slower than us um as you create more conflicts it starts being worse than the sequential right and this was something that we really wanted to avoid now against bomb what's really interesting is uh in uh in the on the left hand side we actually big bomb uh which should not be possible because it has Perfect Right estimates so how and for 10K it actually beats us so this might also be our implementation artifact even though we try to do a good implementation but the point there is that bomb has to create pre-create these

data structures and that's not for free even though we gave and and so I think sort of that overhead was why for smaller block size we could bid it for larger box size of course uh it performed better but it had these perfect estimates what does it matter whether the block size is 1K or 10K oh this is the only for only for one uh and also as an asterisk yeah it's like our implementation of bomb but in no matter what you do you have to create this data structure ahead of time that contains like a slot for every estimated right and I believe the cost of that was somehow yeah because like for for 10K the the

rest of the thing is faster and it makes up for the cost that you pay even though like for 10K I guess the data structure will also be larger but they don't grow at the same rate right the the amount of time you spend some amount of time to build the data structure but for 1K it was in such a way that this was actually significant compared to how much time it took to execute that many transactions but once you go to 10K the execution time became large enough so I said it wasn't important anymore but anyway that's like an implementation artifact uh the more important thing is that we are basically in the same ballpark and that algorithm has Perfect Right estimates and we don't right I'm seriously what uh growth rate should I have in mind for the number of conflicts

as block size increases for like real load or yeah I that is an open question I I don't yeah but uh but there is this is a really good question because I think uh there are at least like I mean probably it's still early days for blockchain adoption right so uh I believe it happened on many blockchains when some project came alive and it like dominated the load for extended period of time and then uh it can lead to a slowness or like whatever so this is also the case when things might become more sequential but you would hope that in a sort of in the case

where there are lots of uh different applications running and lots of different users submitting transactions there would be a lot of transactions that would just be completely independent of each other it's like square root maybe sorry oh I was saying maybe square root in a very uniform yeah like energy adopts very bad like can you give us a benchmark of uh suppose we're not in blockchain setting suppose you were doing this for DMO Visa or something like that with the same technology applied with those numbers being comparable uh I think like if you are in the setting where you can so we like

whatever the assumptions we made about the blockchain right like we're in the we have blocks we have like we can take a preset order we have a virtual machine that executes the smart contracts under these assumptions we can we can sort of like I'm kind of thinking Visa probably needs to be with more than that I think it is Visa scale because I I think it's like I've heard 60 I've heard 100 I think that's the order of magnitude the transactions that they're doing so theoretically this engine can do that uh now again the whole blockchain will not have that throughput right because it

was a possible server right just doing execution right uh yeah this is a single server doing execution and we use uh a lot of threads right so it's also non-trivial I think like requiring 32 cores is probably a bit too much uh but maybe like 16 8 is quite reasonable and I think we currently run with the default configuration parameters eight I think uh so the thing that I wanted to demonstrate here so Aptoide transactions are a bit lighter uh so it has like eight reads uh five rights um it has um again one one one thing is like uh showing the uh just the scalability with

the number of threads but also I think the important Point here is the the line here right so even fully sequential load it's like 10 20 if I remember correctly like slower than the sequential execution and actually to to answer your question I think it's it's this world where you hope for the best so you want to be really really performant when things are nice and distributed and very few conflicts but you want to be really safe and also not worse than sequential when let's say someone adversarially submits to you like a fully sequential node right so you want to interpolate it like this as smoothly as possible here

once you have a guess wouldn't something that's just like maliciously like adversarily just violates all your guesses being making new worlds in that particular instance I mean it's a big design space you have to think about it yeah so so this is this is my last slide I guess there is a bunch of extensions this was we wrote long time ago we now know many more things that can be combined with where you've been experimenting with actually tracking the community with like as as little overhead as possible for instance uh and uh and and many other many other aspects but these are some immediate things that

one could think about like um sort of a concept of nested transactions because right now the failure granularity is a whole transaction and maybe you want to have like sort of sub blocks where you you just have to avoid something smaller uh like you have a loop that internally means many things and one of them fails you you know that it's fine uh you don't have to re-execute the whole look you could combine this with minor replay maybe right because uh this is just the way that the miner could do it and then you can extract stuff from the multiversion data structure and send it to others and those the numbers that are reported there and it's very believable like once you know the dependencies you

can be faster than us right it's like not not a question but again you would have to overcome this uh trust in other assumptions uh we explained we didn't optimize for non-uniform memory access that means like machines where you have multiple sockets like so you can have like 32 cores here and 32 cores here in total you have 64. but the but things then you data oncology becomes the main thing in those algorithms and you have to sort of design your algorithm specifically to scale Beyond out of out of socket but first because it's the blockchain setting and we don't we're not necessarily trying to just require this very expensive machines so it's but it would be it would be interesting

research space to to generalize it it should be possible but it doesn't what we have right now doesn't doesn't scale out of socket and the same about hyper threading because like usually some architectures has like two threads that run on the same core uh but but we we disabled like only one of them makes uh progress at any given time but it can you can amortize some like uh sort of i o and and things and benefit from but again we didn't we didn't design our algorithm in such a way to take uh exploit this thing it's a it's an interesting Direction actually even in our setting because we the experiments here a bit from uh read from in memory

but in reality things are coming from Storage right and in general I guess we have many other problems storage is a huge problem which I don't know if like yeah there is authenticated storage obviously for blockchains it's like a huge source of uh performance bottleneck and in general I think uh the biggest open problem out there in the blockchain space is charming which we have to solve if blockchains had to get to uh sort of the promise line uh which we believe in we're working hard on it but uh yeah I think some of the open things [Applause]