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

[Michael Rogers]

On Jan 23 2008, Matthew Toseland wrote:
> I am talking about a hypothetical, generalised scheme which doesn't have 
> the nearestLoc: weighted coin on the one extreme, and adaptations of the 
> current scheme without nearestLoc on the other.

OK, thanks.

> 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.

With a hop counter m is 1 + the number of resets, and with a weighted coin 
it's 1/pDrop, right?

> - 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.

Sorry, you've lost me again - we only see each request once, don't we?

Here's how I see it: the path length is n+m. For a weighted coin, n=0. For 
a hop counter, n>0. The attacker gets a positive sample with a probability 
of m/(n+m), and for each positive sample there's a probability of 1/m that 
the previous hop is the originator.

But the samples for a weighted coin are independent, whereas with a hop 
counter they're not, so given enough requests the attacker always learns 
more from a weighted coin.

Cheers,
Michael