On Thu, May 18, 2006 at 07:59:03PM +0100, Michael Rogers wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Matthew Toseland wrote: > > - Any other ideas? > > I was going to suggest slowly spinning the network: each node increments > its location by a tiny amount each day (mod 1), so each key slowly > orbits the network (maybe once per year). If a given key hits a black > hole node today, it will hit a different node in 365/n days (less than > an hour if there are 10,000 nodes). But after thinking about it, > spinning the network is starting to seem more like a possible attack.
I don't think the problem is that a few nodes are black holes; it seems more likely to be a routing glitch. > > There are a few reasons why a spinning network would be undesirable. > First, data would have to migrate as the network rotated. Right. There is a strong suspicion that the network's routing varies enough to cause a problem anyway, without making it worse! > It's hard to > say exactly how much migration would be required, because there's > probably a significant overlap between the datastores of neighbouring > nodes. But the rate of migration per node would grow linearly with the > number of nodes, so it would eventually become a problem for large > enough networks. We don't have any explicit migration at present, however it will probably be needed as the network grows - unless our location swapping is far more stable than we have any reason to expect. > > Second, rendezvous at a key would become more difficult: tunnels would > have to be rebuilt periodically as the keys migrated, and again the rate > of turnover would grow linearly with the number of nodes. > > Third, statistical attacks on greedy point-to-point routing would become > easier. As discussed previously, each node along the path knows that the > source is (approximately) further from the destination than itself; as > the network rotates, the set of possible sources will shrink, and - more > importantly - malicious nodes that weren't previously on the path will > get a chance to appear on the path and gather samples. > > (By the way there's a paper in this year's PET workshop about hiding the > source of Chord lookups using fuzzy routing, which sounds like it might > be relevant to greedy routing in Freenet.) Interesting. > > So, is it feasible for a malicious minority to spin the network, and how > fast can they spin it? If a few (say 1%) of the nodes increment their > locations periodically, will their honest neighbours be dragged along by > the location-swapping algorithm? Is there a speed limit beyond which the > malicious nodes will just tear away from their neighbours, and what > determines that limit? I doubt it. But all sorts of attacks are possible on location swapping, and will remain so until we implement some means of enforcing swaps, probably via exposing a good deal of the network topology. (This would also enable premix routing). > > Cheers, > Michael -- Matthew J Toseland - toad at amphibian.dyndns.org Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20060519/bd8801b4/attachment.pgp>
