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: <https://emu.freenetproject.org/pipermail/devl/attachments/20080123/9d6ed4fd/attachment.pgp>
