On Feb 2, 2008, at 10:24 AM, Michael Rogers wrote: >>> what am I missing? >> >> That following the algorithm will eventually color the entire >> network/subnetwork/dungeon with the same network id, which is >> presumed necessary for any sort of distant routing. > > OK, I think I see what you mean now - the network IDs aren't just > private labels used by each node to colour its private map of the > network - they're used for routing, so there needs to be a rough > consensus about which label applies to which area of the network. > > I'm still not quite sure about how that consensus is reached. Agreeing > on an ID for the local subnet doesn't seem to be a problem, but what > happens if (for example) an attacker creates a subnet with the same ID > as an existing subnet? Any searches that have visited the attacker's > subnet and failed will be marked "don't look in subnet X" and > therefore > won't visit the 'real' subnet X, right?
I think that this is the beauty of this approach, that it handles that quite well. The short answer is that (for any routing purposes) we *only* take into account the network ids which we assign to a node, so if they advertise a network id which our peers have (and cannot back that up with connectivity probes) they lose. If there are two networks (with the same id) that we are equidistant from, the more-successful ends up winning via the routing tables. This situation can occur naturally though, not only via an attack. Consider a partial subnet -- like an arch -- that connects on it's two endpoints to the (otherwise-well-connected) network at large. Now, the case presented thus far is if the two end points are not well connected (and the network gets it's own network id / fully colored), but it is possible that on one end it is connected well enough to not be detected and the large network id (say... 1) is pushed into this arch from the left, whereas the other end (not being well connected) the edge nodes present a different network id to the subnet so a different network id (say... 2) is pushed into the arch from the right. If the subnet is colored "1" through-and-through, the edge nodes on the right may still choose not to route into it (as it appears to be a dungeon/subnet, which it is, as they assign "2", even if "1" is presented). More likely, though, is that half the arch will be colored with each network id; the side closer to the well-connected network will route through it using the dungeon-side as an escape route, and the dungeon side will route through it's opening using the network-side as an escape route. > And I guess the list of failed subnets can only be updated by the > requester - otherwise an attacker could return a DNF saying "already > tried subnets X, Y, Z"? Yes and no... What I had in mind, was stripping away any network id's (from success or failures) which a node does not "recognize" (via successes). We could add to that stripping network id's for which we have assigned to other peers. Perhaps the proper solution would be to ignore/strip extra-failed network id's which come from a route we would not take to that network. Sadly, this makes the distant routing information much slower in coming; similar in nature to the assimilation problem with 0.5. So in the natural case where a node (just put into a network/no distant routing table) gets a failure, that is the end. If that were the extent of the routing, though, only nodes near these gateways would learn about the other network(s). Therefore, in order for the distant network information to propagate, a node which process a request which naturally DNFs, and has HTL left will continue the query (at the same HTL) with the DNF'd network id as the failed network list (which means skipping peers assigned to that network). It makes perfect sense, however, for a node originating a request to try all of the network id's in it's "routable" list (or that is... to repeat the request with the given failures as the dont-try list), and would likely be the common case for success (as all the htl is spent trying to escape from the networks in that list). Also, there is a relationship between the number of network ids which we: (1) will route to, (2) transmit with a packet (e.g. on request/failure/success) (3) recognize, (4) count successes. I think that in order for it to work 1<2<3<4, but I'm not sure. Also, a timeout is most likely required for network info at level-1 (maybe +24hrs from last success); as a big-subnet (which becomes connected or is in network-id-limbo), would have a large number of successes (and therefore be very-high-and-secure in the routing table, but becomes totally obsolete routing wise once it is connected. >> So now we'll tell our peer's >> that we can reach network 'w' (through this peer w/ that success). >> Even >> if it is a Sybil-simulated subnetwork, routing to it (and perhaps >> wether >> or not we advertise it to our peers) will probably end up being >> related >> to success-probability; they could only become relied upon by >> providing >> good data (not censoring), why not use the Sybil net for storage, >> then? > > This sounds promising. I'm not sure all attackers will be unreliable, > though. An attacker might diligently store 99% of keys but censor the > other 1% - but maybe FEC makes that a non-issue. Or the attacker might > provide a fast, reliable storage service in order to monitor as much > traffic as possible - but maybe that's unavoidable in opennet. Well... it would be exceptionally difficult to detect a node that plays nice 99% of the time in any event (opennet or darknet). :) > How do you measure success for inserts? I think that inserts naturally escape dungeons already. I do not suggest modifying their behavior. If it is inserted into a large- enough subnet where it is generally lost, I would hope that subnet is popular enough to be in the routing tables for a distant search. -- Robert Hailey > Or maybe you can just measure > success for requests and assume that inserts must be succeeding if > requests are succeeding? > > Cheeers, > Michael
