[Tech] Solution to churn problem and possibly to the Pitch Black attack

Matthew Toseland toad at amphibian.dyndns.org
Tue May 24 13:56:07 BST 2011


On Sunday 15 May 2011 06:14:31 Pierre Abbat wrote:
> I read the Pitch Black paper and I think I've figured out a solution. Instead 
> of trying to fit a circular keyspace in a graph that's spread over the 
> surface of the earth with some long-distance links, I think it would be 
> better to make the keyspace have more dimensions. Here's my proposal:
> 
> Break a key or location into four equal parts. These are coordinates of the 
> point on a four-dimensional torus. Distance is measured in 8-space by 
> embedding each torus dimension as a circle.
> 
> Every 1024 times a node adds something to its store, it performs this 
> calculation: First it adds all the keys in its store as vectors in 8-space, 
> then reduces that to a 4-dimensional point on the torus. Then it adds all its 
> neighbors' locations and again reduces it to a point on the torus. The result 
> is its new location. The location will be close to its neighbors; if the 
> surface containing locations is curved, more of the store will be on the 
> outside of the curve. Young nodes with few keys stored will be pulled rapidly 
> toward their neighbors; old nodes will remain stably located near their data. 
> Unlike the current method, where the product of distances rewards nodes for 
> having locations next to each other, in this system nodes next to each other 
> will be pulled apart, spreading more evenly over the keyspace.
> 
> The number of dimensions could be any divisor of 32 (the number of bytes in a 
> hash). More than that and the notion of averaging in a dimension becomes 
> problematic. I have a hunch that the optimal number of dimensions is 4, where 
> two represent the surface of the earth and the other two different social 
> classes in a region. Could someone who has a Freenet simulator run some tests 
> and see how well this method performs for various numbers of dimensions?

You should simulate this. There are a few simulators but you might have to write your own.

The main difficulty I see is that greedy routing only works if most of our connections are close and a few are distant. If they are all distant, a request will get to roughly where it should be quickly but will not be able to get to a specific location in a reasonable number of hops.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20110524/0cb29091/attachment.pgp>


More information about the Tech mailing list