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

[Some Guy]

 --- Jim Dixon <jdd at dixons.org> wrote: 
> On Sun, 7 Dec 2003, [iso-8859-1] Some Guy wrote:
> > > > > 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].
> Typo: should read                        4*16
> > > > 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.
> >
> > Hmm, did I mess up I'm sorry.  I think I know why.  This is actually
> > an estimate which becomes accurate at high W.  I think the problem is
> > "replacement".  You could abuse my formula and find out the chance
> > that no cells where populated!
> 
> Your mathematics is incorrect; there is no basis for it in logic.  Now
> you are making an equally unsubstantiated claim that the formula will
> become valid for large W -- ignoring entirely the fact that it is always
> entirely wrong for the first W-1 values, for all W>1.
> 
> > Still I stand by the gerneral logic of the estimate:
> 
> You shouldn't.  The general logic is incorrect.
> 
> > chance of a single bootstrap landing in a particular cell= 1/W
> > chance of a single bootstrap not landing in a particular cell= 1-1/W
> > chance of all K bootstraps not landing in a particular cell = (1-1/W)^K
> > chance of at least 1 of K landing in a particular cell = q = 1 - (1-1/W)^K

The next line is where the error/estimation begins.  I have assumed that the events are
independent and must happen W times.  They aren't independent.
> > chance of this happening in all W cells = p = q^W = (1 - (1-1/W)^K)^W
> 
> Just repeating incorrect logic doesn't make it right.  It's wrong on the
> face of it.  By your logic, the first hashcash calculation has a non-zero
> chance of filling W cells.  For all W>1 that logic is as wrong as can be.
> 
> > There might be a way to calculate this exactly using a bunch of
> > factorials to do the counting.
> 
> Like I said, the mathematics is complicated, which is why I did a
> simulation.  The simulation is straightforward: just generate (in this
> case) a series of 16-bit random numbers and use them as cell indexes. See
> how long it takes to put something in each cell. This is exactly what I
> did.

Actually I took your numbers from your simulation and plugged them into my formula which you hate
so much.  They seem to confirm each other:


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

W=2^16 = 65536

K=2^12*156 = 638976
q= 1- (0.9999847412109375)^638976 = 0.99994170967249360064094019525176
p=0.021922840385630526934224993925961

K=2^12*187 = 765952
q= 1- (0.9999847412109375)^765952 = 0.99999160260626125657796596606785
p=0.57675719510350298170377065036919

K=2^12*196 = 802816
q= 1- (0.9999847412109375)^802816 = 0.99999521532980899077982752516866
p=0.73083402587385380536156059762877

Your simulation results and my estimation seem to back each other up, or at least they're in the
same ball park.

So we can agree for that million node network an advesary can launch nodes into any cell he
chooses if he can do somewhere between 500,000 to 1,000,000 CPU days of work every month.

That's a whole lot of resources!!!

Hypothesis:  Ok this will probably annoy you even more than that formula, but I've got an idea
that to cover all cells K is O(W^2).  This is just a guess.  It seems like it'd have to be more
than O(W).


By the way I think I know how to make it so that a good user can avoid redoing the hash cash every
period, by storing an arbitrarily large file.  This could force the advesary to either redoo all
that K hash cashes every iteration or store K*<the file size>.  

So maybe we let that size be 10GB.  It still takes about a day to get a working ID but then you
just store a 10GB file.  Every period you just have to do a quick lookup on your drive.  Of coarse
the adversary could also avoid doing the hash cashes, by buying K*10GB of space.  How much is 10PB
cost?  

Storage has the benifit that tieing it up doesn't annoy as much.



__________________________________________________________________

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