[freenet-dev] Weighted coin is better was Re: Moving to a simple coin was Re: Tunnels vs premix routing

[Matthew Toseland]

On Wednesday 23 January 2008 13:00, Michael Rogers wrote:
> On Jan 23 2008, Matthew Toseland wrote:
> >So which scheme is preferable?
> 
> The weighted coin scheme is bad, but at least the attacks are probabilistic 
> - the nearest location attack is not. If you get two linkable requests from 
> the same peer, both with nearestLoc==prevLoc, one with a target more than 
> 0.25 clockwise from the peer and the other more than 0.25 anticlockwise, 
> the peer *must* be the originator.

If we are assume:
- We are only interested in local predecessor samples i.e. probability that 
originator == requestor.
- We are only considering failed requests.
- There are no timeouts.
- A typical request has m hops where a positive sample may be taken and n hops 
where a negative sample may be taken.

Then negative samples are irrelevant to local predecessor samples because if 
the requestor is local, he will never produce a negative sample.

So the probability that the requestor is the originator depends solely on m:
- The probability of the originator being the requestor given a positive hop 
is 1/m.
- The probability of the originator being the requestor given m positive hops 
(i.e. given n+m hops on average) is 1-((1-(1/m))^m.
- This value decreases as m increases, and appears to approach an asymptote 
around 0.63.
- Therefore, given a reasonable total number of hops (n+m), increasing the 
number that are "positive hops" (m) reduces the attacker's confidence over an 
average (n+m) requests.

So weighted coin is optimal within these parameters. Certainly it is better 
than for example taking the current scheme, removing the nearestLoc, 
increasing the max HTL and reducing the probability of decrementing at max 
HTL:

20 HTL, 25% drop at min HTL, 20% drop at max HTL: m = 5, n = 24, 29 samples => 
5 positive samples => confidence 1.0 - 0.8 ^ 5 = 67%, versus 63% for 29 
samples with no negative hops.
> 
> 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/20080123/9d6ed4fd/attachment.pgp