Scale By The Bay 2018: Wyatt Meldman Floch, Ryle Goehausen, Optimizing network topologies...
you so the title of the talk a little esoteric but we can really boil it down as basically a way that in which we were able to design sort of a new type of distributed consensus protocol that uses a game where no to try to optimize their topology as part of its kind of like work step and the pipeline that we're gonna show is sort of what will eventually become our monad so I'm my of element flock I have the chief technologist at constellation labs I'm a software engineer focused mostly on like machine learnings and distributed systems type problems I've started my career probably not like seven years ago at NASA at NASA Ames and after that I moved out to San Francisco and worked at three tech companies before I found a constellation all three which are represented here something to give everyone a shameless plug radius intelligence from which Nimbus is going to be speaking afterwards miles brother Jeff ventral at signal Labs is speaking in at 3 as well as Jeff me from Valley Health and after that I found a constellation my name is Rob cohousing before I was working at constellation I was a performance engineer at Salesforce working on sail sources spark based auto ml package transmogrify ai I worked on marketing cloud Einstein engagement scoring and sales cloud lead scoring some other transmogrify AI automail projects before that I was a data scientist at radius intelligence working on small business data and doing big data problems in SPARC with machine learning for marketing and sales a little bit about what we're gonna be talking about for those of you who are unfamiliar with cryptocurrency we're gonna start with a brief overview of you know how Bitcoin works and what is the history behind it and some of the scaling problems they've been having we're gonna go in detail on how our consensus model works and what we're planning and bundles and hypergraphs are the data structure that we're trying to design to scale Bitcoin more efficiently we'll talk a little bit about applications we're going to focus primarily on transactions because it's easier to explain some of the issues associated finally we'll discuss some of the limitations and why cryptocurrency has not been widely adopted and why the applications are not being used by a large number of users and what some of the problems in the ecosystem are so first up we're talking about Bitcoin as opposed to aetherium since it's the oldest and most popular it's maintained the largest market share they have some pretty impressive credentials in terms of sort of being the largest decentralized network with the highest success rate you know their uptime is better than s3 they have 10-minute block intervals which gives a huge long time for nodes to come to consensus on the proof-of-work it gives a large amount of time for this race to happen where nodes attempt to increment and nonce and find a hash with a certain difficulty target but it's a very simple structure and the devs don't like change this is why there have been Forks over disagreements in the codebase and they're not really interested in changing something that works even if that means sacrificing scale which forces a lot of solutions into level 2 channels like lightning the simple structure is exemplified it's it's basically a more complicated version of a linked list a sequence of transactions is dumped into a block hash and that block hash is incremented with a nonce repeatedly until it matches a difficulty target the basic idea of what we're proposing is a directed acyclic graph there are other currencies that are trying this approach but we're distinct from them in several major ways the right picture is a view of sort of what this data structure is you can imagine it is instead of having a single block that links to one single previous block you have many blocks created in parallel solving the problem of people trying to race and wasting resources in this race and you need some strategy for linking these things together over time the basic security assumption is guaranteed by layering data over and over and the more data is layered over the more difficult it is to rewrite history essentially cool so in the process of paralyzing this problem it can essentially be broken down to a partitioning type problem so think kind of like what's happening under the HUD inspark when you know we think about the locality of data on on your cluster if you look at the bottom here at the diagram I I see you see there's a snapshot that's our finality window similar to what's considered or called a block in traditional linear block chains so as nodes join and leave that gets added to or it is at added within that finality condition and we can read what was requested or asked from outside of that as it becomes sort of solidified and as you see after we move into the next state array partitioning happens such that once that next state is solidified the valid or the criteria for someone receiving validated rewards is whether or not they repartition themselves effectively similarly we use the same approach with reputation where you take the previous hash so on the left here you'll see a typical Bitcoin block which has a hash with a leading number of zeros that's how proof-of-work works you know you have miners that repeatedly hash values and they choose one that has the highest proof-of-work according to a target interval what we're trying to do is essentially replace proof-of-work with signature data by trusted authorities so in you know you might be familiar with like PGP x' web of trust or other web of trust style approaches where they collect node labels that delineate what node trust what other node and this information is much more representative of what you would actually want there's still trust in the ecosystem as it exists already even in proof of stake or proof of work systems you still need to trust where the code comes from you need to trust that the nodes are actually properly passing the data around there's already an enormous amount of trust in the ecosystem and proof of work is incredibly wasteful and it's sort of antithetical to the notion of trying to scale for performance the real work that should be done is in organizing the network so running machine learning in order to figure out who is the most trustworthy doing PageRank on web of trust data to figure out what nodes of the most influential and how the network should be arranged and it also allows you to incorporate off chain data if nodes can assign trust scores they can use IP information and other data to stop botnets and profile other computers on the network as well as perform community detection to figure out the best strategy for organizing cool so in traditional block chains the well pretty much any consensus protocol whatsoever is trying to solve some type of validation problems so in a traditional lock chain you typically just care about whether or not the balance that someone's trying to that the balance of a sender is greater than or equal to the amount that is trying to send to somebody else and since everything is linear everything is essentially can be redundant Lee copied on every note so every node stores the total state for us it's a bit more complicated it it actually takes into account something that we call programmatic validation or how we can actually add great more validation criteria than just making sure that someone's balance is is valid to send a certain amount so we use that in order to actually validate what the state of the network is and whether whether or not a certain node is doing the right thing so I'm gonna talk a bit more about programmatic validation as we keep moving the basic structure of what we're dealing with our address is this with an Associated balance application support is more complicated but relies on the same fundamental principles so you need double locking semaphores around accounts this is an interesting data structure problem we're inspired by our chain in a lot of ways they have a another Scala based cryptocurrency project but you basically need to ensure that accounts are updated safely and when you're dealing with a dag it's much more complicated than maintaining a ledger or a series of Ledger's for different Forks that you're dealing with you need hash duplication checks everywhere so larger data structures the hash should only be included for smaller data structures in the larger one only a maximum of once you need to make sure there are consistencies in the ancestors in a given piece of data we're talking about paralyzing data processing for transaction handling you could easily have imagined this node is like a surface of a graph this visualization is data that we've constructed to show off some of our tests the the graph grows across a surface and adds new pieces of information gradually on much in the same way a Bitcoin but in parallel a problem with this is if you're on one subsection of the graph you might not know about transactions on the other section in terms of your ancestors this is a totally different problem from Bitcoin because in this case you need to make sure each ancestor is internally self-consistent in order to deal with Forks on the graph you don't know for a fact even if your node knows about different parallel sections you don't know that those necessarily will stay consistent over time so each node can only reason about an execution context associated with one piece of data it must traverse through its ancestors calculate the diff on the partition and the accounts that it's looking at and ensure there's no double spends on that that makes sure that even if there is a transaction on some other distant part of the graph an isolated subsection cannot use that information to transact and send to a different address because you don't know the certainty of that other section so since that's our stuff is uh so since our stuff is a little bit more complicated than a traditional blockchain there is a couple of different components that need to be incorporated I'm gonna blast through these slides however and get it to the meat in the interest of time since we're at about half so in addition to validating things we also need to keep track of what's actually been observed because there may be many different versions of the same type of actual data that we need to actually decide upon when we want to commit that into our finality window so that process is called resolution it's essentially just a mem pool to cache stored like a try and any different kind of maybe not necessarily conflicting but alternative views on the state of the network are stored there and we use that in order to decide within once we've reached a finality window condition whether or not we want to decide a certain version of that unit of data this is very similar to problems and distributed hash tables like cada Maya consensus also is obviously a huge thing in the case where there's actually a serious conflict we need to kick off a real consensus round however since we hold poll our network is to make it asynchronous we need to make sure we have any synchronous consensus protocol fortunately there is a really big heavy hitter called the honey badger BFT which is an extension of asynchronous common subset you can find a lot about this online essentially it's just a utilization of threshold encryption so this gets to sort of the meat and potatoes of why we called this a well we described our talk as trying to optimize Network topologies using a magnetic execution context so what you're looking at right here is the actual pipeline for valor for processing data as it gets observed from a node and then as its gossiped and sent out to its peers so while this actually hasn't been implemented as a monad yet in our code base we are also I would like to mention less than a year old and you know just starting and hiring a lot we will eventually be able to put this into an actual monad and it can be reason about essentially the same way so this pipeline is easily parallelizable even though each one of these different process parts inside the pipeline of resolution validation and conflict detection might have the same maybe a actual like cache or a bit of data that gets accessed by you know different instances of these pipelines it's sort of similar to how we can make an actual API function of all the internals are are imperative in the instance of making things optimal so this pipeline itself is magnetic in the sense that the bias would go towards people gossiping information that they're unsure about because we want to make sure that the total state is known as quickly as possible by all the nodes and the last bias state would be like a conflict that's actually detected in that last part where we then kick off a consensus sub process so once it makes it to the end and let's assume that we're not in the case we needed to do consensus then we would take that bit of data and sign it we would use a previously accepted unit of data that is sort of on the surface of our graph we use that in order to sign the new data and send it out so we're essentially weaving data points together in the form of like a graph so the actual decision of how we choose what bit of data to sign with a new bit of data is boiled down and what we call the tip selection logic that essentially is how we maintain sort of a width and depth constraint in our graph because we don't want it to sort of span out crazily and it also is sort of indicative of the type of structure that our actual data dependency graph has which we're going to talk about it's called a hyper graph the basic topology of our network that we're trying to go after is organized differently than traditional cryptocurrencies usually they don't specify what peers that you connect to they don't really not not very concerned about how the overall layout of the peers is structured and what we're interested in is trying to figure out which peers are influential in terms of trust on the network this is a stochastic neural gas implementation that we're looking at for optimizing the topology mapping of a network in real time you can imagine it's sort of like finding highways for trust you know when you're talking about regular computing environments like spark or MapReduce it's very easy you don't really need to have much concern over where the nodes are executing when you're doing a batch process when we were dealing with heterogeneous computing environment where you don't trust any of the nodes there's a lot of malicious actors you really need to be much more careful about who packages what data so we would have nodes assign trust scores to one another which could incorporate off chain information that off chain information like if this node knows this other node or if it detects that it's an IP that's from a ddossing list would help influence what peers talk to what other peers the peripheral edges of the network would propose small pieces of data and they would gradually make their way up being bundled into larger and larger agreements towards the center of the network as the Senate the center of the network would represent blocks that are referenced more frequently by peripheral nodes in terms of building up that series of layers of security so we replacing the traditional proof-of-work layering technique with reputation layering oriented around when the data is proposed and how far it is spread through the network I also note that other reputation models typically just allow you to pick valid it's not very advanced and you can't really use that information very well for an authoritative mechanism for consensus so in addition to that we also don't want all of the nodes participating all the time so there should be facilitator selections done in such a way to minimize who is actually capable of compromising in network at any given time this is famously known as the the Byzantine fault tolerance problem or the Chinese generals problem determining how to prevent traitorous generals from stopping an attack on the castle or not it's done through a binary agreement and cross talk among a small subset of facilitators each consensus process would not scale to very large number of facilitators but if you keep each facilitator pool small that's operating on consensus it's very highly performant and you just run this many times over at different hierarchies of data organization conflict detection is huge if everybody agrees on all the data on the network it doesn't really matter what the network is doing it's essentially acting as a notary service for eventually consistent data it's far more important that we know when there are conflicts among nodes and then authoritative Trust becomes incredibly important because it essentially acts as the tiebreaker mechanism when you have to piece of two sides of a double spend you want the nodes to respond to that in real time and involve larger portions of the network in determining which piece of data to trust again this is another place where you can exploit off chain data nodes to determine how to vote using different software they can incorporate their own protocols in addition to this and and it would all be part of one consensus module cool so that brings us to our data model as a mint as we were talking before about the tip selection problem there is this sort of notion of reuse where data that came from the previous surface is then used to sign new data and incorporate it into the graph well we want to reuse the tips multiple times in order to create some notion of overlap or some kind of you know useful redundancy in order to make sure we can prevent you know we can really understand what's happening in sort of prevent some types of attacks but it's also really helpful for us in terms of community detection so this type of model actually ends up becoming something equivalent to like a hierarchical clustering if you take a look at this graph here this hyperbolic graph this knows of a smaller reputation would end up sort of on the the outside and nodes of a larger reputation would end up closer on the inside nodes of larger reputation have more responsibilities are sort of like the orchestrators in the network and that gives it this kind of like scale-free topology which makes it very you know very fast and able to optimize the resources it has available it's essentially the same thing that's going out and we have master worker architectures and a lot of the different tools that you guys are using and without getting too much into it that we also have the ability to create a space a space of all the resources available that is fractional in nature which we're not going to go into now but it's it's very cool and it also is very much a part of why and how we need that type of scale tree topology so the end result here is that our our actual dag is a directed acyclic hyper graph and the result here is that we have or that in itself basically orchestrates this type of hierarchy that our nodes actually assemble themselves on within or by using the actual data model itself so the data model is reflective of the network topology and vice versa and all of this as I mentioned as we talk about something like spaces is very much tied in to how we actually wanted to implement our operations and forming this graph so as you can see here we've done everything in terms of this MA node that we built using cats it is formed using similar group operations like adding different signatures together and it's really helpful for us to reason about the space and also model it and you know even even write code that that is very tractable so this is the hash signature we're using we're not really optimizing much the data structures right now we're focusing on just platform testing our edges right now are just to parent references to keep it as simple as possible during testing L&R are the left and right parent references and D is the data the key thing of importance that observation edge is just hashes signature data is just signing hashes so resolution is a very important process because nodes only need to resolve data that is part of the subset of the partition that they're interested in this keeps the entire network going fast and the real bottleneck is only resolving a small subsection of the graph and validating a certain sub partition of the account space we're basing a lot of this work also off of extended trust chain which is an implementation also referred to as check oh there are two common dag approaches in the space one is nano and the other is iota nano tracks dependency information and iota has cross linkages we can go into more detail later but we're running out of time basically dependencies are very important for validation for speeding everything up it's there's two distinct approaches and we're trying to combine the best of both worlds yeah I think we should probably can probably just cut this thing right here because I was going to talk more about programmatic validation and I'll just mention that right now here you can take a look at our actual data model which is these recursive bundles bundles of rank zero transactions checkpoint blocks or rank one essentially the whole thing forms this type of hierarchy and the real takeaway that we could have gotten to would have been that the actual ability to implement programmatic validation is sort of what we really want when we want to add a cryptographic security layer to your existing application the idea here is you're essentially have like a spark context and an RDD almost for a cluster that's performing consensus and you can map over it with your own application logic for the type of data that you need that's why we wanted to make this whole thing monadic and you can essentially implement whatever kind of application logic you need as like a partial function so thank you