Methods for deterministic parallelizing message processing

hi everyone I'm Martin BZ I'm gonna talk about methods for deterministic Aliyah paralyzing message processing says hope sounds like a really fun title so I'm really going to talk about Crimea and Lapera mia is a sort of a prototype of me experimenting with this idea of deterministically paralyzing message processing so an overview of the talk [Music] talked about the history of you awesome kernel and premiu problems with current blockchain computers potential and hopefully potential solutions so the roots of premium really started in you awesome days and it builds extensively off the ideas used in you awesome so if you're familiar with you awesome the idea was to adopt the web assembly instruction set for usage in the etherion blockchain another important part of this was to add metering to web assembly to run this modified webassembly binary we created something called awasum kernel which just provided the methods to link the ethereum blockchain to the web assembly binary and shortly after that I used the awesome kernel to prototype something called nested contracts which I'll talk about in a bit um after that it was sort of a branching point so webassembly solved several problems it was more performant than EVM and more expensive and had a larger ecosystem you compile C or C++ or any LLVM compatible language to web assembly but thinking about starting from the virtual machine layer and going up the next performance bottleneck was in parallelization currently the way things are structured in etherium we can't run transactions or messages in concurrently so Premera was focusing on prototyping ideas with concurrency and it moved towards using the actor model which I'll talk about more a bit so a brief overview of what premia is it provides inter process communication for contracts it has a microkernel like design I use that term very loosely though it's concurrent it's deterministic there's a JavaScript prototype on github and currently it's being developed in conjunction with Definity and hopefully will be useful in aetherium once we have sharding so Crimea you can think of it as the layer that sits above the virtual machine instruction set but below consensus and it's totally decoupled from both it can support heavier genius instruction sets too so in other words it's totally agnostic to in the structure side you can even mix and match instruction sets if you like you'd run the web assembly JavaScript or x86 an ideal EEPROM you could provide inter process communication across those heterogeneous instruction sets so watching computers according to Google Images search this is what a blockchain computer looks like it's like a star going supernova with like quantum entanglement or something but you could also make argument a blockchain computer currently looks like this a fairly early computer or maybe an ID cellphone a few a few problems that we have right now are it's not very performant compared to like a server we haven't really accomplished scalability yet the design is still fairly ad hoc it doesn't borrow much from what was learned from previous designs of operating systems for example it's hard to extend and because I believe it's also hard to interpolate with existing systems so F have our program running on a server it's fairly hard just to move that program to running on a blockchain computer you have to rewrite it so scalability so the skill would be de lui D is like really hard to subject and I don't have any solutions but what I want to try to accomplish is to observe some properties the scalability might have and how to express these properties in inter-process communication so I think a fundamental property will see in scalability is a need to impose locality so what do I mean by locality in the physical world if we have two objects separated by some distance that are communicating locality is sensed by the time communication takes to happen between those objects and the time it takes is going to be how far our part they are times the speed at which the communication happens speed here is kinetic energy essentially the mass of the object times the force that was used to push it so in the world of incentivize computation we can use this as an analogy and the wirless and vise computation a mass in objects is the size of it and bytes or bits and how much force we push it with you could think of it in terms of maybe gas price so how could we oppose locality on contracts essentially what that means here is that contracts further away will have to will sense distances via longer communication times or higher costs are both so currently it's Miriam has a flat namespace for contracts right all all contracts exist along a single tree if you will my first idea for imposing locality was the idea of sub contracts the idea would be that each contract could create sub contracts that it only had access to now this idea is a few problems but let's explore it a little bit more so a parent contract can delete it sub contracts move it sub contracts and send and receive messages from a sub contracts and if we take that tree of contracts and subcontracts and look at it from the top we you could flatten that tree into a set of nested circles like here where the top circle would be the global blockchain then the circles inside that would be more contracts and the circles inside of those would be sub contracts and further so this is also analogous to membrane computing which was I which has inspired off of actually biological modeling biological things like cells any communication happening within one of the membranes going outside the membranes must pass through a member the membrane here is yeah the circle so having this membrane type system we can impose locality so if contract a wants to talk to contract B for example it would have to go through the membrane of its parent a prime and then have to go through B Prime and then finally to a so locality here is sensed by the extra message passing contract that are further away in terms of parent contracts have more cost associated with them because there's more messages right and then you could use the same structure for shards right a and B could be charted easily and you could maybe have an recursive nested charted scheme using this you know you have sub contracts and the sub contracts have sub contracts and some of those would be shards in reality I don't know if you need more than maybe two layers of charts though so it's dubious and whether that's necessary so problems with nested contracts so are there a bit inflexible it's hard to arrange if you have a bunch of contracts that communicate quite frequently that are distributed across a bunch of different parent contracts then it's hard to rearrange things to provide optimal communication so that yeah they're also inefficient because of that you have bacteria messes passing so that was the first iteration and you awesome Colonel experimenting with this idea so the next stop was okay let's solution the restriction of message passing up and down in a tree subcontracts what subcontracts were just connected by a graph but we still want the property of imposing locality and finding a nice way to build shards around our contracts which you can do here the tree just becomes the shard boundaries in this case but we still have a more efficient way of communication since contracts can be arranged in an arbitrary graph so this structure interesting enough I think is represented very well by by graphs by graphs are something created by algebra created by Robin Miller to model communicating agents in space and time so I find it a nice fit and so here the the shard boundaries would be the place graph or the forest and in the communication lines of communication would be the hyper graph and we put those two graphs together we have a structure called a bi graph and that just gives this sort of a nice nice hollow spot to work with to express these things so communication here it's bit different than the way communication and contracts work now for you so as a stance now any contract and send a message to any other contract you might notice here communications more restricted you have to have a line of communication but this does have some benefits it allows us to build isolation groups of contracts that we know cannot be contacted by the groups of contracts and therefore this allows us to build modularity and I'll talk about this a little bit more later also this makes it fairly easy to build concurrency so the first idea to sort of express these lines of communication or graphs of contracts those channels if you're familiar with CSP you should be this should look familiar to you so a channel is just a bi-directional line of communication there's always one to one and inside the contracts channels are addressed by ports ports have names internal to the contract so this blue contract here might call the yellow contract dog the blue one cat and you know orange one something else but it's only relative to that contract the yellow contract might have a different naming but these ports are also mobile so the graph can rearrange for example if C can talk to B or eight yes if C wants to talk to B or B wants to talk to C and but only a can talk to be right now I received then a can send E the port to see in a message so now B can talk directly to C therefore we can now define messages as two things data import references in this might be you might observed that ports are also capabilities here as in the terms of capability systems so it's a capabilities to send a message and it's on its opaque reference it's unforgeable you can't create ports they're maintained by the system if you're interested in capabilities to check out he writes it was a pre blockchain language used to express smart contracts essentially and they're also transferable would which I talked about mobility so now it probably should be apparent how we can build isolation and how'd it so for example you might have a set of three contracts one does a syndication object ACL right the other does some sort of business logic then we have another contract that might provide a database like interface and no external communication can happen to the contracts in yellow everything has to pass through a ten occasion I think this helps us a lot reason to reason about security because now we can just plug and play contracts like logic business logic contracts and data based contracts without having to worry about security implementations because all communication has to pass through the sonication era ACL contract so if you were to audit the system you would really just have to focus on the authentication and you could just use off-the-shelf parts for everything in the isolated area isolation also helps us build concurrency so knowing who can talk to who allows us to find neutrally exclusive sets of contracts and we have if we have mutually exclusive sets of contracts then we can run them in parallel so there's a few problems with ports and channels from the point of view of CSP that and there that that is there's a system overhead associated with it since there's always by D a bi-directional communication happening for every channel whenever you move a port then the system also has to update the other port on the new location at the port also I think there's too much restriction because we still think it's still useful to have etherium style message in wear a condom track and just send to a synthesized address not an opaque address maintained by the system so if we loosen the restrictions on channels we just have addresses but we still can maintain the idea and all the good things with channels of like isolation and whatnot if we have opaque addresses and opaque addresses were just like ports opaque address is something maintained by the system you can't synthesize it you just get a reference to it in your contract and as where ports and channels are bi-directional addresses are not and they are unidirectional so if you if I have an address to a contract I can send that message to it and I also can send the address to another contract and then that other contract can send a message to the contract they maintain the same properties as capabilities so yeah it has all good properties unless system over hood especially with regards to mobility because now when we move addresses around in messages we don't have to update the corresponding contract that it points to on the system level also we can layer synthesizing addresses on top of this you have theorem to represent a theorem style contracts where a contract could take in a string and didn't use that string to send a message to address so now we can really talk about synchronous calling after we have all the prerequisites so synchronous calling currently works like this a B and after it calls be asked to pull off it can't do anything let's say a has like 100 bytes allocated in memory well we have to just keep that there and then now B's running and it allocates another 100 bytes so we have to keep 200 bytes in memory and they still can't do anything now we call see now B's paused so as you can see we sort of get this linear growth in resource consumption where only the act of contract can use resources but none of the other contracts can there frozen's is sort of like going to waste also atomicity and the sudden thing is really expensive it's not only do we have the resources in terms of memory and computation like frozen and going to waste reverting adds a lot of overhead or atomicity so for example when a calls be now we need to keep pace modified state and these modified State then 1c wouldn't be called C we also have to keep a it's modified state B's modified state C's modifies the state and then when C's done running we still have to keep around C's modified State and B's and A's and then when B's done running we have to do the same for a so if you loosen this restriction and have just contracts running concurrently well what would happen is from a system restore point of view it would run I would have a hundred bytes located in memory and then it would be freed and he would run and C and so on but one problem with this is you still might want to represent atomicity and you can do this using something called a two-phase lock and we can provide some system primitives to make this easier so essentially how this would work is we'll say be performing two phase lock a would call B then B would return to a and lock would basically give a lock then a would do something and then return to be until it to unlock and that's the important thing here is that the commit or the revert can be enforced by the system so we don't have to implement a full two-phase protocol I think I'm out of time but okay so that was the gist of it yeah yeah there's more stuff we can talk about later all right [Music]