Keeping the Public Record Safe and Accessible

Transcript

[Music] see so we're interested in low latency ver instead of high throughput and we're interested about small pieces of information not like films uh so uh so from a application programmer's point of view uh what what it does for you is you ask you know the hash of some piece of information you ask for it and

you get it as fast as possible uh like preferably from the ram of your own computer slightly worse from the hard drive or the SSD of your computer and in the absolute worst case from the network but quickly so the design goals Integrity so you don't so the information stays immutable and uh and you can be sure that that's what what you you get what you asked for uh a measure of permanence so once something gets there it's it's impossible to delete it's resilient against both both

random failures and malicious adversaries where of course if it's resilient against malicious adversaries it's automatically resilient against random failures but we sort of keep both in mind uh speed is very important and by speed I I mean low latency and a utilization a optimal utilization of available resources so network storage and to some lesser processing power but mostly we're interested in network resources and storage resources uh how do we ensure Integrity each time you receive a piece

of data if it comes from any other source but your RAM you check you check the hash that's just the rule and because of that in order for that to be feasible there we need to make sure that there are no long unchecked uh downloads so if something H something is long then it needs to be chunked and the max we we should maximize the chunk size in something like 4 kiloby not more and there are two kinds of chunks there's a leaf data fragment and there's a Merkel tree node which has hashes of other chunks and this of course means that we the the the hash is really a merco hash

and I really recommend that and we should probably discuss it that everything in in when we say hash inside ether of of stuff that needs to be stored then we always have we always calculate this Merkel hash because even if you if even if you're not sto if even if the purpose is not immediate storage in this archive uh still calc ating a miracle hash in a uh multicore machine is actually faster and it's nice if the if the hash is always refers to the same thing and uh but the underlying assumption is that the vast majority of data that are is going to be stored here

it fits into a single chunk so we're thinking about things like uh uh parts of the State uh transactions contracts things like that which are typically not very long uh so how do we go about being resilient and redundant so this is where DHD uh comes into into play so so this is going to be a little bit of an introduction to what ADHD is and how they work pro maybe for some of you it will be a little boring so node addresses so the addresses of the machines that form the network

and the keys of the pieces of data the hashes they come from the same they are the same type of object so in this particular case it's probably going to be 256bit hashes uh because the addresses of the nodes are just the hashes of their uh public keys and there's a particular distance measure defined on this space and by distance measure I mean the mathematical definition of distance measure so it's symmetric the distance from A to B is the same as the distance from B to a it uh satisfies the triangle inequality and uh the distance from something from itself is

zero uh so what you get is that suppose so this is this is an illustration where the distance is like the alian distance on the plane the black dots are the machines uh they are randomly and uniformly distributed because the the the is the the address is a result of a hashing and the big black circle is the uh is the entire space uh so that's where the data can live so a piece of data can be anywhere and you know nodes are keeping the each node is keeping the information that is closest to them now of course as long as they can afford

to store something they just store it but when their storage resources get full first their RAM and then their uh background storage then they sort of delete what is furthest away from them so basically there's a radius in which they are responsible for the data and as the volume of the data inside the DHT increases then these radi they they get smaller and smaller and there are like two situations depicted here the green situation when the when these radi are fairly big they completely overlap the entire space and of course if the system

gets overwhelmed meaning that the total the total storage resource inside the system is insufficient then we get to this rep situation when they are uncovered places so this is when so this this is a failure mod it's a graceful failure but it's still it's it's a failure uh and this system provides a natural load balancing because uh since pieces of since both addresses and uh addresses and keys are result from hashes they they're uniformly distributed that it means that all the nodes are

exposed to roughly the same load so this is how we address uh address uh redundancy so in the normal situation which is depicted with green here if one node goes offline then its circle is removed of course but still all the other circles still cover the entire all the green circles still cover the entire black circle so that's that's how ADH every DHT works like that and basically the the difference between the different uh dhts largely boiled down to how these nodes are connected and what the distance measure

is uh so let's first talk about the desirable Network topology how how how to connect these nodes uh oh before before we go there so suppose this node is interested in this piece of information then they need to need to follow the the path through the ne topology so that's that's why natur topology is important so we we we are building a scalable network of n nodes where n can grow indefinitely uh the first thing that we want is a low diameter that comes directly from our requirement of low latency so the theoretical minimum is uh

order one so for example if you think about a complete graph when every node nodes every other node there the diameter is exactly one uh for those of so the the uh definition of the diameter is the longest shortest path so you take every pair of nodes you find the shortest path between them and the longest of these across all the pairs of nodes is the diameter of the graph so theoretically it can be as low as one or order of one so it can be proportional to to it can be a fixed number uh and the acceptable maximum I would say that it's probably log n so you don't want the you don't want the

diameter to be longer than log n as the network grows the other thing that you want to limit is the degree of the nodes so how many other nodes a particular node is connected to again the theoretical minimum is order one so it it is possible to achieve even Logan diameter with a fixed number of nodes I will show you an example uh so that's the theoretical minimum and the acceptable maximum is basically something proportional to the size of the network for a while probably you know over a long time that would be less and less

acceptable and the problem of of course with a large number of uh neighbors is that the housekeeping overhead maintaining that network will become uh it will grow and it will become a sizable part of what the nodes do instead of performing their direct duties then another thing that you want is uniform centrality across all nodes so what centrality is centrality in a graph is defined as the number of shortest paths that go through one particular node or one particular Edge you can Define Edge centrality and note centrality as well actually this

property centrality was uh introduced in applied research which was interested in preventing uh sexually communicable diseases and the question was if we have a limited number of condoms whom are we going to give them uh so this sort of uh shows you what this centrality really means uh so if you take out the most Central nodes from a graph the graph will fall apart the connectivity of the graph will uh will be broken so the centrality needs to be uniform in order for there not to be some vulnerable nodes so for

the cost of Bringing Down the network would should be High because if the centrality is not uniform then there's a small subset of nodes that if you take out that subset of nodes then your graph is falls apart which is bad both against random failures and even worse against a dedicated uh adversary uh because all all the adversary needs to do is to map map out the the network calculate the centrality and then Doos the most Central nodes and of course you also want to keep the the housekeeping overhead low so you want some Network topology which is

easily maintained so I will show you a few examples of of how these tradeoffs can play out uh so for example we currently have a uh a pier selection algorithm which is that simple you connect to the nodes that you know you ask them about other nodes and you connect to those without giving it too much consideration perhaps you you stop after you reach a certain node limit so these completely at hoc networks they they go through a phase transition in the beginning they're they in the beginning they form a almost

complete graph every node knows a sizable subset of the network maybe even the majority of notes so it's almost complete so the number of neighbors is in the order of the size of the network the diameter is more or less fixed you can reach everybody in one or two hops the problem is that in this face the housekeeping overhead is ballooning because when you are so for think about just pinging all the other nodes you need to keep track of their addresses you need to see which one is alive so a lot of traffic on the wires is just

pings so the the the the housekeeping overhead is actually the the traffic generated by housekeeping is growing with the square of n until you trans transition to this other phase when the the number of nodes that one particular node knows the neighboring nodes is relatively small compared to the size of the network then what you get is what mathematicians call a scale free graph uh where you have a wildly different distribution of uh of degrees actually they follow a power law so it's a longtail distribution that's usually

how natural social networks work so if you look at for example whom people friend on Facebook so you look at so social networks like this or you look at front to front computer networks or you look at uh for example the social graph of sexual relationships then they typically they are typically these scale free graphs so in nature these scale threee graphs they're very common their diameter statistically is is pretty low so these are these you know this famous 6 degrees of separation so it's actually smaller than log n it's log n over log log n but that just statistically it so and the the other undesirable property of scale

free graphs is that their centrality is not uniform at all like some typically scale free graphs have a very small number of very Central nodes uh which is interesting uh this fact is uh widely used in all sorts of social engineering from marketing to politics that there are these influencer people that if you find the right people to influence you can you can spread information or disease or whatever uh fast or when you want to bomb a railway Network then a few well-placed bombs can bring a an economy to health so it's

well studied uh propert and it's a well-known property of scale free graphs so basically this is another argument against this kind of at hoc infrastructure that uh in addition to the large housekeeping cost costs uh it we will have centrality problems the network will not be resilient there will be some some nodes which will have high centrality because of their high centrality they will have a high load a disproportionally high load and uh okay yep here we are uh they will have a disproportionally high load and uh and they will be the network will be

vulnerable and there's another problem which is not mentioned here that okay we have a distance measure which follows the triangle inequality but in a athoc graph like this there's no there's no guarantee whatsoever that if you go you know along the gradient like you always take the Hop that BR that brings you closest in one hop to the to your destination then you will actually follow it shortest path there's there's no guarantee for that at all actually in practice it's not that bad so there is a upper upper bound that in the majority of cases the

number of hops will still be fairly low so it's not catastrophic but uh but it's it's not it's definitely not optimal and you you you can have rare but very painful searches so okay uh but the basic the basic uh so I would not like to uh change the basic strategy of uh of connecting to a network so we can keep the the pattern that you connect to one node you ask about its neighbors and then by some clever algorithm you select

to which ones to connect further and actually when somebody asks you about your neighbors you can also be clever and not tell them everything so by by tweaking these two things you can even stay compatible with the original peer peer finding algorithm but be somewhat more clever and uh and and and and achieve some completely different topology so here's here's another example these are the quazi hierarchies so they are similar to hierarchies but not completely so just so this is an illustration of course if you are doing it in a real world scenario it will never be this nice and

regular but this this is a good example of the kind of graph that you you will achieve if you have a limited small number of neighbors so this graph is for example three regular it can grow indefinitely and it's still will have a logarithmic diameter uh so what it is is that there there's this Central node it has three neighbors these neighbors grow binary trees and the leaves of those binary trees are connected so this is a three regular graph uh logarithmic diameter constant uh neighbor number you can achieve this the problem is this with

this is also that the centrality of the nodes is highly variable but the housekeeping overhead on the other hand is really really really short so if you just to to tell you how these kinds of graphs are maintained it's very similar how real armies maintain their chain of commands so if a generally skilled the Army does not does not collapse immediately so there's always you know all all the soldiers have a rank they always know that you know if two soldiers who have not previously met this subordination is immediately established and you know they have some site connections about like where where to connect in case some some nodes fall out so it's it's

doable so you you can build in a decentralized fashion by each node only caring about its own surrounding you can build grabs like this but I think that they're still too vulnerable and they place a they place too high a load on some Central nodes I'm unfortunately if you keep the uh degree of the uh nodes low then and and you want to maintain a logarithmic diameter you cannot avoid this that's a mathematical result so what I propose is and what uh gab also proposes is taking a page from cadamia cadamia is not optimal in the

sense that it doesn't take so for a logarithmic number of Neighbors it has a diameter that is larger than necessary and for the logarithmic diameter it has a number of neighbors that is larger than necessary so it's not it doesn't take anything to the extreme but it like both both values are sort of acceptable and for this like this is an example it's a hyper Cube uh hyper cubes are also like that so cadam results in hyper Cube hyper Cube like topologies so here every note so there are 16 notes here and everyone each one

has 4° uh cadamia has a low housekeeping overhead it has a perfectly uniform centrality and I think what's most uh convincing is that it already operates in a highly hostile environment because cadamia is used as the DHT for big torant for the uh tracker lless for the tracker lless torant and you know there are many highly funded organizations trying to disrupt that Network and they don't don't generally succeed so it it it it looks like a good idea uh so we we would like to take uh

many ideas and maybe quite a bit of code from kademlia it has the notion of the routing table the routing table is basically how the how the node structures its neighbors so it has short Li lists of live neighbors uh the length of each list is maximized at some small number which is typically between five and 20 so it's it's not really a large number and for each bit of the address they have have at most one list uh so the bits means that so for each each

of these lists correspond to nodes whose address is the same up to that bit so the first list doesn't require any uh it differs even in the first bit uh and the the the last address is one the last list which is where it is almost always empty of course but the last list contains nodes which contains the node which differs in only one bit of course it never happens in practice that even that list is has something in it so cadamia has a very peculiar uh distance measure it's the exor Matrix so

they take the xort of the two addresses and treat it as a binary number uh say good exercise to check that it's really a distance measure uh when a node asks another node about the neighbors that they know you don't tell them the entire routing table you tell them only one list uh so for each lookup you try to for each each lookup that another node uh makes lookup request makes at you what you do you try to place that lookup on your lists so which list corresponds to that lookup and you reveal only that

list you don't upload your entire uh table and when you are updating your routing tables because some new nodes come come in you learn about some new nodes then what you do is when a list gets full then if the list is for longer matching prefixes is so there there's some space in longer matching prefixes so the the list so for example you you have a list for three matching bits but you don't have a list for four matching bits then what you do is you split this list into two uh and you start a new list

for for the longer prefix uh otherwise if the list is if the list is full and it's on the the new node is on the far end then what you do is you simply forget the node that you know that is the worst by some criteria what cadamia does is it regularly pings the nodes and from whichever it heard last it will delete we might do something similar or we might have some other uh criteria by which to rank the notes it doesn't really matter all that much but it it provides some way to control the quality and the resilience of the of the network so how do you join

a network like this you you learn about one bootstrap node you connect to it you register with the bootstrap node so basically the bootstrap node adds you to the list where you belong then you do a self lookup with the bootstrap note you try to look up yourself so you download that particular list in which you have been uh to which you have been placed you download the entire list uh and then you insert those you insert those nodes one by one into your routing table and you know handle it the way they should be

handled and then you generate a random address in the range which is one bit further than the bootstrap node and you make a lookout for that address and that also gives you some and this way you you you you have joined the network and you have established yourself as a equally Central node as everybody else so the point of this uh exercise is that when you join this network it's not that you're going to be somewhere on the outskirts of the network but you will establish yourself with deep enough connections so that you're just as Central as any other node so it it it provides a uniformity uh and there's some big open

questions about what we do so first there's this thing that are we going to do this over UDP or TCP now since all the packets that we are sending around they're short and since UDP is much easier to to sand around uh sand through firewalls and nuts and things like that I'm actually leaning towards UDP and that means that maybe this thing should have a separate uh separate layer uh with uh a separate Network layer from the peer-to-peer uh protocol that has been uh presented two talks ago then there's this second

question these two are somewhat related so not tunneling when you're tunneling through n it you you either do it by routing your traffic through some third node which is really bad or you you you really try to burrow a hole through the nut nut firewall you do that by spraying each other with udps with random uh source and destination ports and rely on the uh birthday Paradox uh on one of the requests being an answer to to another request and from that point on the routers will pass those two uh that specific Source port

and that specific uh destination port right through the N firewall but the problem is that in this case uh the establishment of a connection is slow so it's really not something that you want to change so in this case instead so the what cademia does and what the Boran implementation of it does is that it never routes data through nodes it always gives you an address but if you're interested in this particular piece here's an address go go ask that guide but if if if we're doing net tunneling then this is an expensive and slow step so we might not want to do that maybe we want to pass around

information and maybe we even need to be somewhat adaptable like distinguish between nodes behind not firewalls and other nodes which have a public IP address another good question is what are we going to do with Spam because if we implement this directly then anybody can uh you know force it to store forever uh information to which there's uh to which it knows the hash but whether this information is useful or not is anybody's guess and this also gives us uh this also leads us to the question of incentives which uh which

really depends on what this thing is going to be used for uh and you know there are many other open questions so I think that at this point we start the Q&A session and uh and maybe uh on Friday we should have a a discussion about what to do okay yeah so a little bit to to elaborate about how I join to network and what what information they feel that I join to should provide me like maybe the level of the of the it it has like is it the general or so no no no in this case when you're in cadamia there there's no rank

everybody's equal so what you do is you you connect to one node that is is already a member that's that's how you you bootstrap then you register with that node so you give your address to that node and that node puts it into the appropriate list where where it belongs then it gives you back the entire list so it will you will have a list of addresses of valid nodes from the boot from the bootstrap node you insert all those addresses into your own table and then with this routing table you do a lookup of a random address which

differs from the so it you look at the prefix which you share with the bootstrap node and you take the bit you flip the bit uh that comes afterwards to the one that you have but not the bootstrap node and you fill up the rest of the bits with with some random binary values and you make a lookup now how a lookup looks like with a lookup you go to a node to the nearest node that you can find in your routing table and then you you ask that next node to uh to give you the corresponding list

you insert all those nodes into your routing table and then uh and then you keep continuing until you find the nearest node uh and of course if along the way you find the actual content then you download that content you don't you don't continue but with a random lookup the chance of that happening are negligible so that is nice visualization of look it's like Circle everybody standing in circle right so x no it's not a circle it's it's a hyper Cube so what you do when you're looking up a node is that you're a lookup is basically you you always go one bit closer right and you always go along the

bit Which is higher like has a highest uh so higher order bit so it's always like let's suppose this direction the vertical direction is the high order Direction so whenever you go from this node to this node you always go along one dimension closer but you always follow the same order of bits that's how you do the lookup and you're guaranteed to have a logarithmic number because with each with each hop the uh number of common bits increases at least by one so it it gives you a guarantee on the diameter okay next

question what is the strategy against SP well in case of bit torant since they have uh since they it's mutable so it's not the same as here it just overwrites the key and it forgets gracefully old keys so when so in in in case of in case of the bitor rent the information is not really valuable so it they just throw away information that hasn't been queried for a long time that's all they do and it's it's sufficient for their purpose and it might be sufficient for our purpose as well I don't know it depends on really what we're going to

use it for so what are we going to use it for yeah most of the um the life use it you order to query things like transaction receipts for the only one no but you can even even store the state in it so if if the like if you have a full node but you don't have the storage space for storing everything that a full node needs to store it might dump you know things that it that don't fit into its storage into this DHD so it's kind of public utility forish

yeah if the bo well you need to find one so for example there are some bot nuts that also organize themselves into caman like networks and what they do is they just probe random IP addresses until they find so you need some type of watch well or you download a recent list from a website it's and you know you go through it and the first Noe that you find is okay so it's really you need to find one Noe that is member of the network and then you're done and don't forget it's on the same network as ethereum whisper so yeah the CH if you know an ethereum node you'll

eventually find a you remember from connections yeah of course you save you don't forget your routing table so when when you're switched on then you renew your routing table but you you use the one that you had okay the second SL you already have a bunch of yes how muchy proportionally is Network to a scale free network it really depends on how much information you store so this the latency in this uh

setup really depends on how large your diameter is uh but uh and after how large your radius is but once your radius has been exhausted then it depends on the diameter and actually cam is slower like on a general scale free network the diameter is Logan over log Logan whereas here it's log n so it's slightly slower but you know the log log is not that big a deal are you going to talk tomorrow uh no because I it's it's it's the same talk I didn't realize that this talk was also me can you

elaborate because you mentioned a lot of times before that mutable and non mutable dhds kind very different yes the there's interesting about so about this the interesting thing is that you never need to revisit you don't need to keep querying like you don't need like flooding the network with with new information is not an issue so here you can get away with if something is asked of you that you don't know then you find it and you store it for later reference and you know how to flood the network with uh with with new information is not an issue here because

it never gets overwritten you know know it propagates slowly and and it's okay basically any any any any stupid tactic for example if you if you get some piece of information you you send it to the nearest two nodes that you can find that's good enough because that will flood like it will go in the general direction where it needs to be and it's okay for you so you don't have to be very clever about how to make sure that new information propagates through the it it it it like it's half of the code of the of cadamia you can safely leave that out yes

thise ENT exp and removed when uh for with to uh good question because keep it there you have refresh or refesh well refreshing the spam costs right you need to query it continually so do do look up so if if you want to spam that way it's probably doable uh like I don't know it it really depends on what we're going to use it for how how do you incentivize uh like this is like this is an open network

basically it stores anything you give to it it doesn't even have to fit into 4 kiloby you can split it up you can you can store anything in it there's no yes but the question to put something in this network then you can keep it alive and I don't think it costs too much you keep it no it doesn't so basically what what happens is is shown here so this is the relevant uh figure that you know if there's too much stuff and the notes can keep up then there will be some blanks here and then you need to decide what to throw out because if you throw out information then these circles will grow again so basically you need to decide what to

throw out when when you're full uh I mean when you're really full when when when things get really bad so when when not only are you full but your radius is is is is too small can you can you detect that this is happening yeah you can detect because the again because the uh cont the key value pair is not arbitrary so it's a it's a hash so it's a uniform Randomness it's uniformly randomly distributed so from that you can be sure that the density of information in your neighborhood is the same as the density everywhere else and from that you can

make very accurate assumptions of how much information is stored in the whole network but it still doesn't tell you whether there's no you can you can make educated guesses about how bad the situation is so that that's another thing just referring back to your question that because of that because you can be sure that the the keys are distributed uniformly and it's immutable you can actually from a local point of view of a node has a fairly good uh uh good of how full the whole network is yes how does with e Road SW so it

first be switch over to this or I think so so I think that it will not be in uh in in the next proof of concept it will not be there but in proof of concept number eight it might right that's that's that's where it belongs that's that's that's entirely feasible so I think the target for this is mons of eight yes just use case if you want to have a stud website with a big movie on it couple gabes but if I always store them they would always be there for other one to download right that's how I would do this like I the server of my website store the stuff and even if no

one's using it it's always there it's kind of a use case for this yeah you can use static content there actually it would be like cou gabes yeah yeah sure but that's also kind of spam kind of but I thought for me at least so they can drop it out from time to time but it's yeah it's it's it's it's possible it is actually I'm thinking about adding a HTTP interface just for fun that when when you enter a hash in the in the URL then it will collect the corresponding PES and you know uh push out the the entire

content one idea for but only for the local node so it's only no no no it's only accessible from 12701 it's not accessible from the other side so one idea for span prevention is we just use Pro work and keep the highest work stuff in the table and Target kind of like not overflowing and that way blocks will always stay in there because they always have a good work of course and transaction receipts and so on will always be hosted by AR because they will they will store the data anyway because they use it that's kind of the definition yeah they well if the proof of work is such that they need to look it up so if a Hashimoto style in Hashimoto style proof

of work you you need to so full yeah there's a bit of weird so there's full nodes which you know which keep this stuff for the last end blocks there's super light nodes that don't keep anything really and then there's archive nodes that keep everything and the idea is that the foundation runs a few archive nodes and maybe some but actually with this you don't even need archive nodes because with this in place uh you you have a common archive and as long as you keep keep randomly checking the past it will stay up to dat and it will be fairly distributed and you know this this kind of proof of

work can be actually a contract so you can actually offer ether in exchange for for for checking the thing for for for provid for making spot checks so it can be done on top of ethereum that you here's a contract that if you if you maintain if you know you you sweep around the archives then you're going to get paid and that's it you don't even need full archive nodes what's the behavior if you if you have like two concurrent uh request for for writing the same Ash but you will write the same thing there that's the point that the here the the the value sorry okay but

what if what if it's a mutable time if it's mutable it's a lot harder okay it's not it's it's it's it's not designed to be mutable so we going to use we might but it will be a thick layer on top like that's a lot more work than an immutable one and actually for a mutable one I would probably just use uh bitor and cadamia because you know it's already there and it's mutable and they have solved all the problems e