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 [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
