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

[Some Guy]

 --- Jim Dixon <jdd at dixons.org> wrote: 
> On Fri, 5 Dec 2003, [iso-8859-1] Some Guy wrote:
> 
> > > The key Grid of Trust premise is that hash cash will provide a
> > > reasonable defense against a variety of attacks.  However, any real
> > > network will necessarily grow from a small number of nodes.  During that
> > > phase virtually anyone will have sufficient computing power to scatter
> > > nodes throughout the network.  If the network were ever to grow to a large
> > > scale, say on the order of 2^20 nodes, it would still be possible for an
> > > adversary with large resources to put a dummy node into each cell.  You
> > > don't need to be a government to do this; many universities, for example,
> > > have sufficient idle capacity.
> >
> > Actually Jim, for a large network it becomes nearly impossible to get
> > a dummy node in "every cell".  Think of it this way if you've got on
> > in 99% of the cells, only 1% of the new nodes you boot strap will get
> > you into a new cell.  It gets really hard after a while.  If you want
> > I can do some math to back this up better.
> 
> 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

Let K= 100,000
q = 1 -(0.9999847412109375)^K =0.78257265884072628822995385743531
p = q^65536 = pretty much zero

Let K= 500,000
q = 1 -(0.9999847412109375)^K =0.99951407328591738343032888979088
p = q^65536 = 1.4663236118039940291203041696009e-14

Let K= 1,000,000
q = 1 -(0.9999847412109375)^K =0.99999976387522854087100754870521
p = q^65536 = 0.98464444270485344649626598788687

Ok somewhere between 500,000 and a million bootstraps and things start to get bad.  Still that's a
lot of processor power the adversary would need.  Consider that IDs could expire in a month and
he'd be forced to constantly replace them.  He'd need 1,000,000/28days = 35,714 CPUs churning
nonstop.  Sure someone could do it, but they'd have to have lots of money.

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.

The DHT would still function pretty well if you left the adversarial nodes in there, but you could
do better if neighbors would test each other's behavior.  Any kind of voting would leave the good
guys in majority 16 to 1.

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.

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.

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.


__________________________________________________________________

Gesendet von Yahoo! Mail - http://mail.yahoo.de
Logos und Klingeltöne fürs Handy bei http://sms.yahoo.de


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