Scalable Secure Scuttlebutt

I'm the total my talk was scalable secure scuttlebutt my name and my name is Dominic tower um so what is scuttlebutt scuttlebutt the - so-so scuttlebutt is a nautical term for gossip a but there's a barrel that water is stored and scuttle is to open the barrel so it's to make a hole in it so this why scuttle is also distinct ership because you open the dish up so the yeah so this means gossip for pirates and stuff like this so and that I got the term from a part of the Amazon paper there was a it was on paper called flow control for anti entropy projects it's like for anti in entropy protocols so it's eventually consistent gossip protocol that's used to a thorough trusted system and then I made secure scuttlebutt which took the same idea and then added security so the peer that ID of the peer is the of is its public key the data model is just append-only logs where each peer appeals to it has its own personal log that signed peers can relay other messages but they can't insert modify or reorder messages because the signatures would then be invalid so this gives you like a really simple data model they can use to represent a bunch of stuff but it's and it's completely like free to run like signatures you can make 12 you know thousands of signatures a second on an ordinary laptop you can the current implementation can receive like two thousand messages a second and validate them like it's it's very like it's not it avoids all kinds of bottlenecks that you do if you have a get if you have a consensus layer so this then there's a few it Maps quite closely to social media kind of models like Twitter and whatnot because you you follow the feeds that you want to replicate and this solves a whole bunch of neat problems so this solves civil attack because the human it bubbles up to the human layer and then they just unfollow the nose they don't want to talk to or don't want to hear from it also provides discovery so writing a crappy peer-to-peer Google would be really really hard but writing a crappy peer-to-peer social network actually can still be really awesome if there are awesome people on it and you can still discover new things so it's a way of like discovering things in a decent surance new decentralized way and then because it replicates misses just an order it's easy to think about building a database on top of this because the things happen you receive things in the same order that they happened so that was secure Scott Oberg and then my recent work has been to make it much much more scalable so scalable secure scuttlebutt is the same thing again but optimized for bandwidth and latency so the the big deal here is that the overhead the networking over here is proportional to the feeds updated and I'll explain why that's important so so part one is optimizing the network topology so the the like simplest most naive design would be just to connect to everyone and I have really cool animation of this that you can't see but perhaps I'll just like I don't know can see you wanna see something kind of happening yeah so this of course is like inherently centralized it goes out from one point but it's actually really efficient because each message is transmitted exactly once to to every node so the amount of people that receive messages is exactly the same as the amount of messages that need to be their assent and but the problem is this means that actually there's one node that does all the work and all the other nodes do nearly no work and then you know that's you know you know about you know about why centralization is bad so another solution is you just have a random Network just peers every peer connects to a couple of other random nodes and it's really easy to make a fully connected Network like this like if you connect to more than two peers to other peers the chance of being completely connected is like at as the network gets bigger increases so once you're past oh it's like the chance of being fully connected this like pretty much certain and but the problem is that it's a trade-off between bandwidth and latency depending on how many extra connections you have so I have another animation here so it's like looks like a noisy noisy mess and then you might say some like read that all the read messages that are flying around those are the extra redundant messages and if you have like I think this one has like five connections or something I've got a little table here yeah so once you have like five connections per pair things then you're getting like 10 times extra redundant messages that you don't need to see well you kind of need to seem to make sure they all arrive but you've seen ten times as much as you needed to but it's super robust they're simple and it's the in it's super simple to implement as well the role is just seen two new messages to everyone that didn't send it to you which is also being don't receive messages who really know so just your super message check if you already know about this message and if not send it to everyone that you're connected to and then that will flood the whole network pretty efficient I like very robustly like if some nodes get taken out it'll just be routed around otherwise so there's only like a couple of cases we need to handle think of here is like one peer sends it to another peer or the second peer sends it to the first peer and the other thing that can happen is they both send it to each other where there are two paths for that message to get to to Alice and to Bob and they both received it in a within the time that it takes to see to send one message that's the that's the only case where you get both peers passing the message well you'll get where you get a redundant connection and the bandwidth complexity is like it's proportional to the messages times the spanning connections plus twice the redundant connections because each redundant connection gets two messages sent on earth so the redundant connections are like much more expensive than the minimal set of spanning connections and once you've got 10 when you've got 10 connections to appear you have like 95% redundant messages so it means if we can get rid of the drownded messages week we can we can just transmit one message one one message per pair which is optimal so the better solution is a spanning tree network so spanning tree is like we get a graph and we just only have the connections we need to reach all of the nodes so we can take the flood and gossip and we can build use that to build a spanning network spanning network in a decentralized way by just whenever you receive a duplicate message you just say you just deactivate that connection I didn't say disconnect and I'll come back to that in a bit so you just deactivate that so now you're sending like just the number of messages the only problem is that trees are really fragile so it's because now you've basically just added a whole bunch of single you've made every single node into a central point of failure so there's one path between any two random nodes and if any of the nodes in that thing fail then the end those messages won't get through so the yes so it's odd bandwidth optimal but it's not robust but then there's this paper I discovered a while ago called epidemic broadcast trees and this combines the best parts of both flood and gossip and spanning trees so how it works basically as you have connections are in two modes there's eager and there's lazy and so the lays it the redundant connections get put into lazy mode so in eager mode when you receive message you transmit it immediately and when a connection is in lazy mode when you receive a message you just seemed a really short note that you know about this new message now so all of the main all of the spanning connections get the whole message sent across so that's that lets the message propagate as fast as it can and then the message the redundant connections they just have a very short message being sent across so it might only be so in the current implementation of secure scuttlebutt and the average message size is like 700 bytes and it can be could we go up to 8 kilobytes but the note would only be like 80 bytes I think and that could be like binary optimize down to probably less than 10 so the redundant connections still exist but you just seem to Whaley a starter on them and then um they also the robustness still exists because when a message when so when you receive a message for the first time you like rebroadcast and so on but if you receive a note about a message that you haven't that you don't know about you then you've seen dammit you send a request back to that back to that back back to that peer asking them to turn back into eager mode and then they'll send you the whole message and now the network is repaired so as the best of both worlds yeah and then there's only a small amount of state that you need to keep track of up here for per feed you just need the ID the local sequence number of the remote Cygnus number the local request the remote request and the local and remote modes so that's only debts you know if we're under like depending on how long that idea Stringer's would talk about like just like tens of bytes I'm debt is okay so then the other so they talked up that's all about optimizing the network so the second part is optimizing the handshakes so secure scuttlebutt had this so original scuttlebutt had this thing called a victor clog so a victor clock is just like a list of all of the things so pure so you have a whole bunch of a whole bunch of friends and when two friends bump into each other they say I win did you last hear from Bob I heard from Bob on Tuesday when did you last hear from Ellis I heard from Ellis on Monday and if I say that I saw Alice on Monday and you saw her on Sunday then I can then I know I just need to send you the messages from Monday what from after Sunday so it means we just exchanged this one thing and then I just know immediately what you don't have and by arranging the message isn't alone in your audio order it makes that comparison like completely simple if you have like more complicated orderings and they if you have some kind of common more complicated structure it becomes much much more difficult to do a remote set comparison but if you may have it alone your order it's like did simple so just like compromise towards the simplest structure that's easier to be optimal about so that but that has a problem and that if you're having like the original paper that describes this said that they're probably you know it was designed for used for one cluster within a data center so when you'd have like a dynamo DB instance that they said might have like 300 nodes which is maybe a lot for one you know cluster and a dot and a data center but there's not a lot for a peer-to-peer network we want to have thousands and thousands of nodes so if you have thousands of thousands nodes then just sending the victor clock like really adds up because you might it might just be like a public key in a sequence number so there might be like 80 bytes but then if you're sending this for like 3000 people that is like into like hundreds of kilobytes so that means like each time you can answer you've seen you might send like half a megabyte of data both ways and if you can reconnect and reconnect you could be sending like tens of megabytes a day just to keep the network alive like even if no messages are being sent so that's not really that's not very good at all but one of the other secure scuttlebutt contributors are cell shelves Lin who came up with this idea to skip some requests so what you do is you just remember the victor clock that the other person sent to you and then compare your new victor clock to the stored one for that peer and then just don't mention all the things that haven't changed so if I if we meet on Sunday and we exchange news about Carol and then we meet each other again on Wednesday and neither of us will have talked to Carol since then then we just don't mention Carol and because we know that if so if the other person did they would mention her so that means that you can just leave out most of the victor clog and you just don't mention most of the things that have changed that all the things that you think probably haven't changed and then if you find out if some fella person does mention it then you just reply with like your partial figure clock of the things that that didn't didn't change yep so I had yeah yeah this is this is this is really important because when when you have like a people using uni pretty much any kind of application you power laws are really typical so you're really likely to have some users that are like really active you know use every day or posting you know constantly you have like some users that are like daily a fair amount of light moderate users and then like heaps and heaps of like people that only use it occasionally or even signed up and never used it again and you don't want to be wasting bandwidth on people they haven't done anything in a while so this this simple technique allows you to completely cut out all of that stuff and that basically gives you an end so basic basic skill about the message over here per connection was like the messages plus the feeds and if no messages have changed the messages might be 0 but feeds could be thousands but secure scuttlebutt is messages plus updated feeds an updated feeds could be much much smaller number usually it would be like if you reconnect frequent like frequently number could be like will be close to 0 if you reconnect months later it will just be you might get individual users might have posted hundreds of messages but over here is just one for that updated fade which makes reconnections very cheap and the only time you have to pay the whole send all of the feeds as when you have a when you win the first time that to peers connect yes this for good and the light and the latency complexity is just you can you're replicating in either one or two round trips so one round trip if you've seen if you've sent the whole clock and they then seen the messages but if they send a putt if they or if they don't or if the messages that you haven't mentioned haven't updated then it's one round trip and if you send a message have you seen a partial victory if they send a partial victor clock and then you have to have seen one back you know it's two round trips but my back since now basically improvising so like I became interest in this because I was living on a sailboat in New Zealand and I was used to like like my normal thing was not having very good Anson it at the time when I first became interested this I didn't actually have any any aunts name of my boat and I was like why can't that be like why does that mean that I can't use my computer you should be a user view of computer I also grew up on a farm in New Zealand we are the best internet we have we had was like a satellite and snare that had like a one-second round trip which is like you know it shouldn't really take that by that long that long for light to travel but it has like I don't know lots of switching packets and that's that other stuff so I was really determined to like latency is really a killer like if you and if you live in like a fancy place that has fiber and that sort of stuff then latency you might not better notice it and a couple of each two round-trips might not be there bad but when latency gets bad it gets really bad and if you have a design with that scenes a lot of packets back and forth then it's going to be really really painful to use in that situation so it's determined to have like a constant number of round rubs so one or two round trips I think is like about how much you can I can tolerate for a replication protocol logarithmic round trips not not acceptable it's going to be really painful in in many cases so the part three is simply they've arrived comparison to ipfs I was sure people would ask about this so secure scuttlebutt basically optimizes for the worst case and secure in IP FES so secure scuttlebutt is designed for like long append-only chains and this would be like the pathological case and yes so they're trying to completely completely opposite things but similar and that they both replicate data without global consistency so they're kind of like an infrastructural role for if you're building like other p2p apps and so on so neither again neither have any like cryptocurrency or thing like to directly built into it but if you're building stuff like that you could move your data around using a combination of these things secure scuttlebutt streams updates in order to feed and ipfs has a pointer to the latest message and works back and if you want to have it relatively efficient you'd have some kind of tree or some sort of directory you find the things will just not have very deep structures have relatively shallow ones so IPS is probably better for like arbitrary partial data sets like wiki's and sort of static sites such things all like directories of data and that sort of stuff whereas SSB is designed specifically for like social applications or social applications with something strapped on the side so secure scuttlebutt is basically a graph database and IFIF this is file system yep okay that took this long because I didn't get to show you the animation stuff but I'm that's it okay um if you'd like to if you'd like to learn more you can go to a scuttlebutt don't NZ that's to tease and github.com slash uses bc / patchwork there's like a UI for like a real real working application that you can use today and if you go on that you'll meet lots of love lots of load lots of lovely people that will tell you all about how things work fortunately yeah so the slice doesn't work I've got about eight minutes see any questions or heckling or anything scuttlebutt ends it yep go thank you very much [Applause] [Music]