Hi again everyone, I want to dive into a little bit more detail about how a fractal addressing space might provide consistency without taking a major hit to performance.
Based on the system I described in the previous post, I want to talk about how fractals might be combined with small world routing. There are basically 2 possibilities that I see: 1) A strict fractal lattice is obtained via Metropolis-Hastings MCMC. Each fractal generation continues swapping locations in our (0,1) space with Sandberg's original acceptance function until a small world network is created. This means search performance turns into Log base2 (n) + log^2(n) on average. 2) A small world fractal lattice is obtained via Metropolis-Hastings MCMC. If we know a proportion of how many long range links each node *should* have, this approach may still resist Pitch Black. I am still experimenting with this possibility. When a node joins the darknet(I am not considering any opennet cases), we may simply decide to choose a location in a generation that fits best with our fractal neighborhood. At that point we may pick a location within that fractal generation at random and swap until we have our desired distribution of neighbors. I would like to release more information about scalability but this work is still being reviewed. It looks promising at the moment. Unfortunately I had less time to write this than I had originally anticipated. I will make my best effort to continue posting an informal explanation but I will be occupied for the next 5 days or so. I will attempt to release a draft of the paper to the list by the end of the week. Thanks again. On Fri, Jun 3, 2016 at 6:41 PM, Michael Grube <michael.gr...@gmail.com> wrote: > Hi everyone, > > Before you read this, I am writing the results more fomally in a paper. > I'll be using some informal language and making some assumptions about your > knowledge in this post. I really just wanted to get the concepts out there > in case I'm hit by a bus or something. > > I wanted to share some experiments I've been doing. I think they may have > interesting applications for Freenet, especially in terms of scalability, > churn and the pitch black attack. > > Pitch Black is a severe problem for darknet routing. The heart of the > exploit is that we have no way to check our neighbor's honesty about who > their friends are. There have been some valiant attempts to solve this > problem including an interesting attempt to abandon swapping altogether and > use local markov chains. A problem with this is that the distribution of > the keyspace responsibility becomes uneven and so we can naturally expect > data loss. > > What if the addressing space were fractal? If our space becomes fractal, > we have a large(theoretically infinite) number of discrete buckets that we > can partition our space into. The self-similar property of all fractals > also means that we should have a local way to check the distribution of our > neighbors while maintaining a global structure. If a swap is proposed, we > should simply be able to ask if it brings our neighborhood closer or > further away from a fractal neighbor distribution. It also turns out that > greedy routing in a fractal can achieve small world performance > <http://arxiv.org/pdf/cond-mat/0612326v1.pdf> if we want to go that > route. > > In my example, I will be using the complement of the cantor set, which is > also a binary tree. This is not a coincidence - I'd like to demonstrate > that using a fractal addressing system can still allow us to keep decent > performance. > > Let's map our keyspace with the complement of the cantor set. This means > that instead of removing 1/3rd of the space at every iteration, we will > fill space instead. Iteration 1 is 1/3rd of the keyspace, iteration 2 is > (1/6) and so on. We now have a 2-dimensional address for every location in > the network - the generation of the fractal that a position corresponds to > and the value between (0,1). > > To make this easier to parse, here are some examples of node locations: > (0.359465966, 1) > (0.740859445, 2) > (0.981788632, 9) > > The thought behind this is that if every node assumes a position in a > fractally addressed space, there can be an expected local distribution of > neighbors with respect to a given generation. So how do we calculate the > fit of our neighborhood against the the fit of a proposed configuration? > > For a strict fractal lattice, we want the distribution of our neighbors to > be: > > Fd -The fractal iteration distance - 1/3d where d is distance between > generations > Gn - The global probability of that neighbor, 1/3n where n is the > generation our neighbor belongs to > Gs - The global probability of us being in our generation 1/3s where s is > our generation > > We calculate what our local distribution *should* be for a neighbor in > some generation by using: > > (Fd*Gn)/Gs > > We can then ask our neighbors for the location of their neighbors, which > gives us a picture of our neighborhood. Since an attacker knows who our > friends are, but not necessarily our friends friends, it is hard for them > to manipulate us into accepting an arbitrary position in the fractal > dimension. > > I will write a second post tomorrow explaining these concepts in greater > detail and include some graphs and code. > > Thanks and bye for now. > > _______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
