[freenet-dev] Alpha, Darknet routing, et al.

[Robert Hailey]

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