[p2p-hackers] Chord comments

[Roger Dingledine]

----- Forwarded message from "Edwin R. Karat" <karat at MIT.EDU> -----

From: "Edwin R. Karat" <karat at MIT.EDU>
Date: Tue, 04 Sep 2001 12:41:07 -0400
To: Roger Dingledine <arma at MIT.EDU>
Subject: Re: [p2p-hackers] Chord comments

In message <20010904121040.G14872 at moria.mit.edu>, Roger Dingledine writes:
>On Tue, Sep 04, 2001 at 01:06:14AM -0400, Edwin R. Karat wrote:
>> In message <20010903205353.Y14872 at moria.mit.edu>, Roger Dingledine writes:
>> >On Mon, Sep 03, 2001 at 08:45:32PM -0400, Carl Bosley wrote:
>> >> For P > 1, for N >> 1 the overlap is negligible enough that
>> >> 
>> >> (1 - e^{-N/M})^P
>> >> 
>> >> is a good approximation.
>> > 
>> >Excellent. This is what I was looking for.
>> >
>> >I think the overall story is that if you have significantly more possible
>> >IPs at your disposal than the current number of machines in the network,
>> >then you're going to win -- but only against a few targets, not against
>> >everybody.
>> 
>> Whoops.  Actually, if you have a good chance of winning against 1, then
>> you have a good chance of winning against everybody else too, don't you?
>
>With the same set of darts? (Meaning they land in the same places.)

Yes.  With M >> P, then saying that you've compromised one particular
computer only eats up P darts, you still have M-P darts to take over
other computers with.  So, the problem is largely the same with M-P
darts, at which point you have nearly the same probability of
taking over another specified computer.

Analysis 1:

Probability of taking over 2 *specified* computers (in the worst case
with none of the bins in common) is equivalent to doubling P (you are
trying to go for 2P bins, instead of P bins).  In our approximate sum,
(1 - e^{-N/M})^P, this just squares the probability, which is
equivalent to 2 independent trials.  Of course, they are not
independent, but the point is that the dependence is a wash in the
errors of the M >> P approximation.

Seen from a different point of view, taking over a computer takes up P
darts, leaving you with N-P darts.  But to be likely to take over a
specified computer, N is on the order of M, which is >> P.