[freenet-dev] Moving to a simple coin was Re: Tunnels vs premix routing was Re: Vulnerability in inserting the manifest before finishing

[Matthew Toseland]

On Tuesday 15 January 2008 23:20, Michael Rogers wrote:
> Matthew Toseland wrote:
> >> It's more complicated than that... if the HTL is 10 and the closest
> >> location isn't the previous hop's location, then the attacker knows the
> >> previous hop doesn't decrement at 10. 
> > 
> > It's a function of the input node, not the output node.
> 
> So each node makes a separate decision about whether to decrement max
> HTL requests arriving from each peer (and presumably a separate decision
> for local requests)?

Yes.
> 
> That seems to reduce the anonymity set in a different way: if I receive
> an HTL=10 request and an HTL=9 request from a peer, I know that only one
> of them can be local, and I know that if they're not local they came
> from different upstream peers.

If they are both local they'd both be HTL 10 iirc.
> 
> > The problem is that a weighted coin would increase the 
> > variance in path length *significantly*,
> 
> Do we have any idea what the variance currently is?

Huge I should think. But we always go to at least 10 nodes.
> 
> > cause more no-fault timeouts,
> 
> True.

Indeed - but on the other hand right now we have a *lot* of timeouts, and 
they're mostly caused by problems with queueing, which is solved thanks to 
Robert in 1098. A simple weighted coin would generate very few timeouts: If 
we assume the data isn't found (typical on *long* requests), 2 seconds per 
hop seems a reasonable upper estimate, so there is a 0.2% chance that a 
request goes more than 60 hops and therefore causes a timeout... on the other 
hand we want it to generally respond in much less than that.
> 
> > cause more no-fault failures (too short a path),
> 
> DNF after a short search isn't a big deal, we can always try again.

True. But to the same node? And how do we detect this anyway? Simply by time? 
More alchemy. Report the number of hops on a DNF? Is that safe? If so it 
would be very interesting. Or the traditional alchemical solution - just make 
a maximum of N requests.

Would it create an additional incentive to start several requests in parallel? 
Well, not if they were coalesced... :)

On either a DNF or a timeout, we'd like to route differently the next time, 
because both could be caused by a single malicious node attempting to censor 
a specific key. If short DNFs and timeouts are too common, this could be a 
problem.
> 
> > make request coalescing extremely difficult,
> 
> On the contrary, coalescing would be simplified: all requests can be
> expected to travel the same distance on average, so they can be
> coalesced in the same way requests with equal HTL are currently coalesced.

So you coalesce and then fail quickly. Hmmm. Whereas if you had several 
requests running separately each would have a separate chance of failing 
quickly. So everyone will have to retry.
> 
> > and likewise with ULPRs.
> 
> I don't know enough about ULPRs to comment.

Basically, ULPRs are a combination of failure tables and an unreliable form of 
passive requests. When we get a request, we check whether we've had a request 
for the same key, at at least the same HTL, within a certain timeout period. 
If we have, we check which nodes we have routed it to. If we have already 
routed it to the best node for the key, we refuse the request with a 
RecentlyFailed message. Now, we might want to try each node, or the top two 
or three nodes, to take into account the possibility of a cancer node, but 
that's the principle. Then we remember that the node asked for the data, and 
if we find it, we offer it to all nodes which have asked for it, and 
additionally all nodes which we have asked for it (to make it a semi-reliable 
web instead of an unreliable tree). Thus we eliminate a lot of unnecessary 
traffic (retries, fetches from other nodes), while still having good routing, 
and we propagate the data fast when it is found.

Now, the problem with ULPRs plus simple weighted coin is that if we forward a 
request and get a short DNF because it probabilistically dropped within a few 
hops, we will then block future requests for the same key because we've 
already routed it to the ideal node for the key. This again appears solvable: 
allow more than one request before blocking it - block the request only if 
there have been N requests over the timeout period. This is probably wise 
anyway, since Bad Things may have happened downstream.
> 
> > Is there an alternative?
> 
> A weighted coin is the only possibility that reveals /nothing/ about how
> far the request has travelled so far, because it carries no state. I'm
> not saying that makes it an ideal choice, but perhaps that makes it a
> good starting point for designing an alternative to the current
> mechanism - an alternative that reveals a quantifiable amount of
> information.

I'm coming around to the idea of a simple weighted coin. We already do 
automatic retries everywhere (and despite that we are faster than 0.5 :) ), 
and the complications can generally be worked around.
> 
> > 10 hops is quite 
> > expensive... do we want to have it customisable-per-request? Paranoid 
> > requestors would then stick out... OTOH this might be best, 99% of people 
> > will use the default setting.
> 
> IMO it shouldn't be customisable. If some of the traffic flowing through
> my node belongs to unusually paranoid or unusually confident people who
> modify the weight of the coin, my anonymity is reduced even though I
> stuck with the default.

I was referring to tunnels IIRC. In terms of HTL, I agree.
> 
> > How much information does an attacker gain from linking two 
> > tunnels from the same X ? A fairly high confidence that X is the 
originator, 
> > surely? Higher than the 10% or 20% we're talking about above...?
> 
> For each possible initiator, the attacker would have to work out the
> probability of two random walks from that initiator reaching X - or
> maybe the conditional probability of the second random walk reaching X,
> given that the first random walk reached X?
> 
> For X, the conditional probability is 1. For each n-hop neighbour of X
> it's roughly 1/degree^n. So yeah, if two linked tunnels emerge from X, X
> is far more likely than any other node to be the initiator.

Right...

Okay, supposing we implement a simple weighted coin (say 10% probability). 
This would eliminate the *urgent* need for tunnels. It could easily be 
implemented before 0.7.0, although it would have some knock-on effects in 
various places, and we might have to tune it... It would dramatically reduce 
the predecessor confidence, which right now is rather high for requests with 
HTL=10 and best-so-far equals predecessor location (approximately 1 in the 
number of resets on the request including the originator, may be as low as 1 
in 3), to 1 in 10 (or whatever level we set).
> 
> Cheers,
> Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://emu.freenetproject.org/pipermail/devl/attachments/20080116/e90587e8/attachment.pgp