On Jan 30, 2008, at 11:34 AM, Michael Rogers wrote: > On Jan 30 2008, Robert Hailey wrote: >> The two peers on the ends recognize that >> subnetwork inconsistency and route less/none into it (unless, as >> Matthew was saying, it fails in the current network). > > But how do they decide to route around it? Any scheme based on > collectively-agreed network IDs would require the attacker's > cooperation, > wouldn't it? > [...] > Right, so what happens if the nodes in China-freenet insist they're > part of > US-freenet?
No, in the way I am thinking this is even expected; a node can advertise whatever network-id it wants (just an integer), it is up to the peers to make sense of it. It is much like swapping (pick a random one to start, and behave intelligently for a useful effect), except that each node attempts to locate these routing inconsistencies by assuming it is the hub of several networks. There are at least three parts to this: (1) Identification of separate "networks" (2) Routing to avoid dungeons (or generally unfruitful "networks") (3) Routing to favor searching other networks on failure -- #1 -- Identification A node picks a random integer on startup, this is it's temporary network-id. Some time in the future, using (for example) routed pings it breaks up it's peers into groups. e.g. I can ping peer #3 through peer#2, so they are on the same network. Processing in order of largest-group first: for all these groups, we advertise the most-common network id in that group towards all of them; unless that id is taken by a larger group (already processed), in which case a random id is assigned to that group (or the next-most common?). Which is to say every 'group' has a distinct network id (assigned & advertised by-us) favoring what they are advertising already. Any nodes which appear in several of these 'groups' (e.g. ping failure, random rejects, etc) are eventually assigned "our" network id (to be determined). We choose our network id based on successes; I don't think it even matters specifically how... Since all peers are advertising (possibly- different) ids to us, we take the most-common id among peer's from which >50% of our successes come from (for example). I suspect it would work even if we simply took the network id advertised to us by the peer of our last successful request. This could be put in place w/o effecting routing, perhaps augmenting probe requests to determine if it properly labels dungeons/subnets. -- #2 -- Avoiding dungeons The only way I am aware of defining a dungeon is as a separate network whose likelyhood of success is effectively-zero, and even then only if it is not a substantial portion of our peers (which probably means we are in the dungeon). > As you say, it might be possible to use the fraction of DNFs to detect > dungeons, but then an attacker could request nonexistent keys from a > particular range to make that part of the network look like a dungeon. If we use "percentage of successes," or time-based... yes. I recommend a small constant instead; e.g. a given network-group (as assigned above) is NOT a dungeon if we have (say...) 2 successes from them (collectively). Or perhaps we should just make this the default behavior: routing groups ordered by collective successes, label the last several of them a dungeon (if they have less than... 4 peers to them). -- #3 -- Favoring other networks We would need (1) a routing table, and (2) to be notified of other networks somehow. I suggest such a packet following successes (like opennet path folding), saying "this success came from net=3 at htl=2, net=5 at htl=4, etc." And since there could be a *lot* of junk-network information, we just keep a psuedo-LRU of recently seen network ids (where multiple peers having the same network success: favoring the peer with the more recent success than higher htl? but probably promoting them both). Keep, say, 100-1000 network ids. Presuming that the identification algorithim stabilizes, certainly routing to a distant network given an id (or a counter-example set!) would not be a problem. We would have to be mindful that the routing information could be easily tampered with; so rather than telling a potential attacker "this packet is trying to find location=x on network=y", it would be more to the effect "location x, not on network=y,z,w" in which case if a node only knows about those networks it RNFs. -- Robert Hailey >> To the best of >> my knowledge, outside of the subnet, the other properly-connected >> nodes can (and will) have the same keyspace/location; that is what >> makes them routing obstacles (location=0.545... in US-freenet, or >> China-freenet?). > > > Cheers, > Michael
