[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 15:46, Michael Rogers wrote:
> 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?

Yes, although n is debatable.
> 
> > - 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?

I mean given m requests which qualify as positive samples.
> 
> 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.

Why are samples for a hop counter dependant?
> 
> 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/97a8b662/attachment.pgp