Introducing RAM to the world computer | guiltygyoza, Topology | ETHTaipei 2024

hello everyone I'm guil GZA um co-founder of topology um I'm glad to be here today to propose a new kind of decentralized program that is different but complement small contracts on the blockchain so um what we really care about at the end of the day is to build better work computers and we think there are three properties that characterize a good work computer one um it needs to operate on a credible neutral protocol stack because if it doesn't then it's a centralized operated computer that's rented to users and that doesn't really um shouldn't be characterized as a work computer um the second property would be it needs to accommodate as many concurrent users as possible because people should be able to interact with the same computer concurrently around the world and the third property would be it needs to operate on an open world programming model meaning that people can deploy and use programs um and when program crash is it shouldn't crash the underlying system so the programming model should be designed in a way that assumes open world assumptions so we have blockchains and um blockchains basically operate um a replicated State machine over visiting consensus right so we're all familiar with how Bitcoin Works Bitcoin uh relies on um nodes voting with their CPU power um on state transitions um and ethereum relies on uh Capital put at stake uh uh for V um blockchain as execution environment is a single-threaded environment it's a single-threaded environment to include and Order transactions and for use uh take ethereum for example it has store procedures and people can invoke these procedures which may change the state of a blockchain and these uh procedures can in initiate cross contract calls to interact with one another now we have uh scaling problems and we have been concerned about scaling problems in throughout the industry so one um dominant approach or Philosophy for scaling would be modularity right so we are familiar with the modular thesis um which basically is about operating many many single threads on top of a shared um mother thread or parent thread and these application threads basically settle their traces on the state space or the memory space of the parent thread um while the problem with this approach would be lock which is common to all blockchains right because single thread execution um basically relies uh requires people to lock each other out when transacting against the same thread um so we can look at etherum block time about 12 seconds 99% of which is spent on consensus or reaching consensus now another approach complimentary to modularity will be verifiable Computing so that gives you the ZK rollups um verifiable Computing basically allows these application threads to deploy uh to deposit um traces but compressed mathematically by the by the ZK proof um on the parent thread and additionally this sort of justifies that okay sequencers can Now operate in a Central Way um provs can also operate in a central way because math never lies and so nothing wrong can be ever deposited to the parent thread so that is the Assumption well the problem with that approach is that there we we then have a bottleneck in liveness so although the upper threats cannot deposit bad things to the parent thread the the the upper thread can lock people out can censor certain users from other users so it becomes a bottleneck in liveness and censorship and also it basically increases the complexity of the already very complicated uh uh protocol stack and finally for each application thread we are still operating on a single thread so the question will be how can we break break away from single thread um well we can basically look at the assumptions of all blockchain which is they all operate on the strict sterilizability model which means that operations do not overlap and operations are put in a single total order so that's the total ordering property um Bitcoin relies on CPU voting to decide on the ordering um Pro stake blockchain requires um basically uh voting by their stake to to order the transactions um a weaker consistency model called causal consistency model um is the model that we really care about because causality is the upper bound of the kind of consistency guarantees you can get while you don't you do not need any coordination and coordination is voting is consensus is what really takes up the majority of the time for for these distributed systems so in short if we stick to the causal consistency model we can skip the voting and consensus entirely but still guarantee that all replicas uh reach consistency at the end of the day so the fundamental building blocks here will be a hash graph a hash graph um we have to talk about the the the basics um um System model assumption first so the basic model assumption is we have a distributed system of many many processes and every process is a single thread and these process will generate events whatever kind of events that they might generate and these process communicate to one another via passing messages and this message carries the information about the events and they do this without locking each other out so um message passing is uh performed in a as synchronous manner now for a hash graph the message takes the structure of the event payload followed by causal dependencies followed by signature so signature is just standard way of basically identifying who is sending the message uh the causal dependencies is for a message to basically uh report what messages prior to me is uh uh is the messages that that that I'm depending upon so for example if you look at this hash graph um the message C2 on the very right has the dependency of A2 and B2 because these two messages uh uh precede C2 and is the dependencies reported by message C2 um and we further require that when you generate an event uh locally you need to report your dependencies at as the heads of your graph which is the most recent notes in your graph so if we have hash graphs we can start merging them so imagine a system of many many processes all doing events asynchronously and so they have different hash graph now if we have Divergent hash graph that's not very interesting because everyone is who say he says she says but if we can merge these graph into consistent graphs then now we have synchronization and synchronization is good so if you look at these two graphs on the left they can merge into the third graph on the right where all the cality relations are still preserved so that means that you can merge these hash graph that all originate from the same state original state and you can merge them whichever way and they they will give you the consistent graph that still preserve the causality relation and the way to merge graph or to basically transmit information across the network would be you have the pole model which is that these replicas basically perform anti-entropy among themselves and they reconcile their graphs um and there's a push model which means that these processes sort of Gossip messages over the PDP Network okay so why do we care about hash graph because there is a property called invariant Confluence invariant Confluence is a property about distributed system that says if a program is invariant confluent the program can be executed in a distributed manner without relying on any coordination and if we look at the hash graph we can see that if you can merge hash graph arbitrarily and still get a valid hash graph then hash graph itself is a invariant conflent program and so what this basically means is that we can run a distributed system that basically communicate and synchronize on their hash graphs and there's no consensus mechanism or any voting required but everyone is still able to operate correctly and the property for Byzantine false would be this has the property of being cyber immune and so if you look at blockchain there's basically U assumptions about majority right so uh Bitcoin traditionally uh um assumes 50 50% majority to be honest um and um ethereum basically relies on 66% of AK being honest to be able to progress uh and to be not uh basically revert on their finality and if you have 33% of ethereum node corrupted then the blockchain can be uh uh stalled but for this kind of operation you will be immune to cyber faults which means that even if your network is 99% cable as long as your the rest of the correct notes are still connected in a continuous graph then the correct notes can still operate correctly uh regardless of how many Cy noes are present in the network so with all these properties as programmers what should we uh how should we leverage these properties so there is a data type called crdt or conflict free replicated data type which is a data type that basically abstracts all of the properties above and it basically gives you the common API that programmers are familiar with apis like the the register API or the set object array object or map object furthermore these object can be composed uh among one another so that basically gives you Json or recursive uh recursive Maps so uh these crdts are composable and they allow programmers to express arbitrarily complex behaviors furthermore we can have bft crdt which means that you can have these replicated data types that are concurrently operated upon by many many replicas and they can be immune to CYO actors in a system and so on the below you have a very basic crdt called TWP set or two-phase set a two-phase set is a mathematical set that allows people to allows you to add elements to the set and then allows you to remove element from the set but once the element is added you cannot it cannot be uh removed once once an element is removed it cannot be readed therefore it's a two-face set and you can see that from the left you have an empty two faace Two-Face set and in the middle we have a hash graph that transport a bunch of operations that are being performed on a two-face Set uh where the the uh the the a events are the add operations and the r events are the remove operations so following this graph you will have a new Two Face set on the right which has element two and element 9 remain in the set right so the summary for here will be we have these wonderful properties about uh uh I Confluence and about having a Distributive system without any consensus mechanism required and so on and then we can abstract all these as a uh abstract data type for programmers to create programs and that is the BF crdt so we want to propose a new kind of decentralized program called life object um for blockchain you will have small contracts for this new paradigm you will have live object so live object is an object so it's uh following your uh common object oriented programming um objects are stateful and they expose methods for uh manipulate their own States and we call them live because uh these object will have very low response time because they operate locally as local replicas that allows you to transact against the local replica instantly and basically you can read after your read and you can write after your write and write after you read instantly um these are actors furthermore so these this is the actor model where different live objects that are each one of them is a BFC rdt they can communicate via asynchronously passing messages to one another um um just for some terminology so live objects basically is an instance of a blueprint which is a class and these class are composable so you can have class compositions um every blueprint will have States and states are typed by crdts or maybe typed by other blueprints so you can comp post blueprints um every blueprint will have an interface that specifies the set of signals that this particular object respondes to uh it will have obviously handlers or functions that handle signals when when they're received and it will furthermore have um it will have a view function a materialized view function basically allowing you to cre the state of the object and it will have a merge function that specifies if if I have two replicas of the same object how do I merge them together the affordances of Life object relative to Smart contract will be one it is default free because there's no consensus mechanism required so transacting against life object does not require paying transaction fee to pay for consensus whether that's paying for CPU power or whether that's paying for uh the in in terms of proof of stake you're basically paying for the yield uh that is expected by the capital uh uh at stake in the system um so it's basically free transactions and furthermore it runs at local speed so imagine every replica running at 60 hertz locally so 60 Fram per second which is commonly what video games uh uh run on um the system will be horizontally scaling which means that for every new user added to the system they can transact at 60 hertz without slowing everyone down and the third property will be they are Loosely coupling meaning that these objects do not interact by function calls they interact by passing messages so they do not lock each other out furthermore um this will be discussed later uh each object can be synchronized on the individual basis right so if you operate a full node for ethereum you basically have to synchronize the entire state which contains the universe of all smart contracts even for a lot of smart contract you actually do not care about but for live objects you can basically subscribe in terms of a popular subscribe U uh uh pattern to a particular object and you will only synchronize up to that object which allows you to not care about other objects and to be able to run a Lo locally so this is the Pud code for um um uh social graphs so we are probably all familiar with forecaster um what well we may be less familiar with is how the forecaster Hub Network actually works the Hub Network of a forecaster actually operates a set of crdts so the forecaster social graph is composed of roughly eight crdts that basically record people adding post and remove post uh people reacting to posts and people following other people so a social graph can be represented as a live object as a result you can make social network um as live objects um another example would be a multiplayer simulation so all video games or all um metaverse like application basically is in multiplayer simulation um you can have a multiplayer simulation uh uh structure as a live object and uh the question here will be how can we do Collision because if you are in a virtual world where nothing collides with uh each other it's not really interesting right um Collision can be achieved by basically endowing each rigid body with a field and when these rigid body collides or when you're emerging these replicas you will reconcile these overlaps of the field and you will basically push the rigid bodies apart from one another so this is a proof of concept we did last year where um we have um about 10 different users U each operating from their own browser and this is purely peer-to-peer um synchronized between browsers by representing the underlying World in a crdt um and as you can see these penguins do not overlap so that's not very interesting so the next proof of concept will be actually implementing Collision so um a penguin is operating from taipe while the other penguin uh is operating from um somewhere in the United States and as you can see these two rigid bodies actually Collide and the these sort of rules are are all encoded in a crdt so now we're ready to introduce the ram concept um Ram or Random Access Memory um we find we find it as a very interesting uh analogy for three reasons So Random Access basically means that I can access uh particular data from the memory space right um at constant speed so for Life object you can subscribe to particular live objects and disregarding other um other objects uh and contrary for blockchain you have to synchronize uh up to the entire State machine um another property will be caching so because these replicas operate locally is very close to comput so that basically mirrors the idea of a ram very being very close to CPU and have Fast Access time for CPU and the third property will be ephemerality so we imagine these live objects when no is using it it will basically exist as a snapshot on ipfs and when someone wants to use it the snapshot will be re will be rehydrated and becomes uh operating as replica and synchronizing among replica so an object can be in active form and it can also be in dorant form when it exists only in a snapshot so we can talk about interaction because if these objects do not interact with one another there's no interoperability um we can have interaction by passing messages but um um in order for this message passing to be trust minimized um the receiver object basically needs to verify um the incoming message and the ca the causal dependencies of the incoming message so if you look at this diagram um the uh we have three object XYZ and the message X9 basically initiates a signal uh that creates a message y5 in the second object and so the y5 Cal dependency has both its own dependency in object Y and also the dependency of the center objects dependency uh X8 and the same applies for y7 signaling to Z and generating Z5 message you would have dependencies on both your own object and also the standard object so we have talked about the basics of live objects and how to interact now we're ready to talk about some intuitions behind how we may construct a protocal stack so we have to start with global snapshots Global snapshots are basically uh we can talk about why so uh for example if you play games you will want to periodically save your game so saving a game is a SN snapshot of the state second for these asynchronous object to sort of gear shift and transact with a blockchain you have to take a snapshot of it and then you will commit transactions on the blockchain because transactions on the blockchain are irreversible so you have to um for these different replicas you have to find a common ground and then you interact with the blockchain and third is if you want to come compact these grabs you have to first take a snapshot and then decide what part of the grab you can prune away and pruning is very important because for a blockchain that may grow over years uh these live objects with people transacting with them at very high speed the graph can go very fast and so if we don't prune the graph this is basically impractical um if you want to do compaction or pruning you have to take a snapshot first so snapshot is important um for objects that may have been permissioned or for objects which leader basically leader noes that are asymmetric from other nodes the leader noes The Trusted nodes can perform uh the the basic Global snap algorithm such as the chenny Lamport algorithm but if we are moving towards open um Open Access live objects where these replicas are all on an equal basis then the problem it's becomes a problem because okay we can say a global snapshot is the merging of all the replicas of the object but the notion of all is very problematic because on the open per Network people can come can join and leave and so gather information from everyone can be very impractical and also as you're merging these replicas what is good and what is bad and who to decide what is good and bad so basically this means that we need to introduce consensus consensus means that we need to agree on given all these replicas of the same object which uh which replicas are to go into a snapshot okay so we can talk about compaction a little bit compaction basically means pruning the gra graph so on the left you have a large graph if we assume that uh message f and g in the middle are stable meaning that no future events will will have come before FNG then we can prune away the messages before FNG basically saving space otherwise these graph grows um uh indefinitely and you will have a memory bound problem so um the topology prot protocol stat can be understood as a layer architecture from the bottom you you will have P2P messaging on top you would have a hash graph that gives you caal consistency and then on top you can have a threshold witness which is basically the threshold logical clock that will basically allow you to say okay um I am um I am assuming that this information is known by everyone or at least known by two-thirds of everyone and that two-thirds of everyone acknowledges that I know they know the information so then you can basically operate a synchronous clock on top of which you can operate consensus and consensus may be important if we want to operate a pro stake mechanism um since time is um time is up I will um I'll be quick on the last few slides and there's a paper at the end so for those of you that are interested you can read the paper at your own pace so we can do a threshold merge hash grab which means that okay if we cannot say let's gather all the message graph uh hash graphs we can say let's gather 2/3 of the hash graph and because we don't want to be CYO attack we can say the 2/3 requires to be the two3 of the stake uh protocal Stak in the network once you get all these hash graft you merge them together together that is your Global snapshot and you can compact the way the snapshot so compaction works like you would get agreed upon snapshot of the graph and you would compact the way by basically transitioning the state uh with the graph of the messages and in order for these graph to be suent and also trust minimized similar to how the Mina blockchain works we can say okay whenever you're transitioning the state you're also performing a validity proof or recursive uh recursive snark or recursive Stark over the state transition and you will keep that proof in your grab so that people can basically fast sync on your object without having to Traverse all the way from the beginning um the status of the project would be uh we are currently on paper draft version 7.3 this is a QR code that will bring you to the paper draft PDF um on the engineering side we're doing a vertical prototyping uh we hope that by summer this year we can give people uh non bft version of live objects and people can play with it um on the research side there's a lot of open problems that need to be figured out and we're setting up a office in in um some open problems include that we need to figure out a consensus protocol that minimizes the complexity of communication over the network that keeps these objects succinct otherwise they grow very fast um that have a suitable proof of State mechanism um and so on and um there's problems with crypto crypto economics that need to be figured out um there's problem with the underlying broadcast algorithm because it affects how efficient information transfer on over the PDP Network and it affects how fast these objects can synchronize information um and so on and we're looking for um engineers and researchers uh who have experienced in go Rus programming uh P2P networking distributive system cryptography and cryptoeconomics um if interested um feel free to contact me on email or on Twitter or on faster thank you and now we have five minutes Q&A time does anybody have questions hi hello I've seen a similar using hcraft systems like ha or some uh dech systems like Iota Phantom so how are how is the ram protocol difference from those already existing uh graph based systems thank you yeah so there are many D based blockchains um being proposed and we have the um Su and Aptos which operate on uh sort of the um um the uh Tusk consensus mechanism and bosar consensus mechanism I think the difference between uh crdts and and them is that they still operate touring complete smart contracts and for touring complete smart contracts the transaction ordering really matters like who writes to a particular State variable who gets there first really matters but for crdt we're basically saying okay let's not do tour in complete let's do a subset of the possible programs that can operate without having to order things and so by doing this we can skip the ordering part so if you look into the borar consensus mechanism you'll find that they basically have to um total order the the transa the blocks in a dag and total ordering is needed because because they're operating on a touring complete model any more questions any more questions okay then thank you gu GZA for the talk thank you