[mnet-devel] Grid Of Trust -- pre-design

[Jim Dixon]

On Sat, 6 Dec 2003, [iso-8859-1] Some Guy wrote:

> > In a 2^20 node network with 2^4 nodes / cell, you have 2^16 cells.
> > Assume that you have 2^12 computers, not at all uncommon for a university
> > campus.  It's also very roughly the number of computers used in the
> > Freesite trials (on a corporate campus).  Every 16 cycles you produce
> > 2^16 hashcash calculations, so 16 is the absolute minimum number of cycles
> > needed.
> >
> > I did a simulation of this.  If my math is correct, then using 2^12
> > machines, it will take
> >   about 156 iterations to fill all but 3 cells
> >   about 160 iterations to fill all but 2 cells
> >   about 168 iterations to fill all but 1 cell
> >   about 187 iterations to fill all cells
> > To get these results I did 4*16 = 64 runs, so I am reasonably confident
> > of the numbers.  I was always able to fill all of the cells in less than
> > 196 iterations [just did another 4 runs to be sure].
>
> Well ok here's what the math looks like.

> <number of cells>=W=2^16
> chance of a single bootstrap landing in a particular cell= 1/W
> Let K= number of bootstrappings of adversary
> chance a particular cell is infiltrated = q = 1 - (1-1/W)^K
> the chance all cells are infiltrated = p = q^W = (1 - (1-1/W)^K)^W

Wrong.  Absolutely wrong.

Just think about it.  You have a network of W nodes.  You calculate
hashcash once.  Your formula says that the chance of all cells being
infiltrated is (1 - (1-1/W)^K)^W.  This is remarkable.  Somehow, according
to your formula, calculating one number gets you into W cells; otherwise
the probability would be zero.

Well, in fact the probability is actually zero for all K < W.

I did the simulation because I was too lazy to do the mathematics.  It's
a bit hairy.  However, it's trivial for W == 2.  Then the chances look
like this:

  K    actual p
  1      0
  2      0.5
  3      0.75
  4      0.875
  ...
  n      (2^(n-1)-1)/(2^(n-1))

Why?  The only way to _fail_ to fill both cells in n iterations is to get
the same result n times in a row.  For n == 1, the probability q is 1, so
p = 0.  When you flip the second coin, the chance of getting a match with
the first is 1/2.  When you flip the third, it's again 1/2.  Call the
probability of getting n matches q.  Then

  q = 1/2^(n-1)

and

  p = 1 - q = 1 - 1/2^(n-1) = (2^(n-1)-1)/(2^(n-1))

giving the result above.  This gives the correct result.  Your formula is

  p = ((1-(1-1/2)^n)^2 = (1 - 1/2^n) ^2

which is uhm wrong.

> So what can an adversary do if he can run a bad guy in each cell?
>
> Premix routing will be safe even if the adversary did run a node in every cell.

Proof?

> The DHT would still function pretty well if you left the adversarial
> nodes in there,

Proof?

>                but you could do better if neighbors would test each
> other's behavior.

Proof?

>                   Any kind of voting would leave the good guys in
> majority 16 to 1.

Your mathematics needs some cultivating.  It might be 15 to 1.

In any case, you need to support these three assertions, not just make
them.

> The real problem is flooding on the IP level.  If and adversary can
> pop in and get the IPs real quick, he can flood any of the nodes he
> wants.  Maybe someday ISPs will give us a solution to this problem.

Another assertion that needs some proving.

> The solution I see is for friends to build small cliques of nodes
> which we can call "super nodes" which then act as a single node in the
> described network.  If a super node has enough independent IPs so that
> it could give out one to every neighbor, it would be safe against
> floods.

On the face of it, this just doesn't make sense.  Explain, please.  Just
how can I loan my IP to the guy across the street?

> The cost is pretty high though.  It pretty much doubles the number of
> hops, not quite since the number of super nodes would be less than the
> number of nodes.  It may also be kind of a pain for new users to find
> a clique to join.  I guess you can always join the clique of the guy
> who told you about the program.
>
> That does however get you past your hash cash problem for new users.
> A new user wouldn't need to burn a CPU*day, if he just joins someone
> else's clique.

Oh, we are dumping hashcash, are we?  That's good news.

--
Jim Dixon  jdd at dixons.org   tel +44 117 982 0786  mobile +44 797 373 7881
http://jxcl.sourceforge.net                       Java unit test coverage
http://xlattice.sourceforge.net         p2p communications infrastructure



-------------------------------------------------------
This SF.net email is sponsored by: IBM Linux Tutorials.
Become an expert in LINUX or just sharpen your skills.  Sign up for IBM's
Free Linux Tutorials.  Learn everything from the bash shell to sys admin.
Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel