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

[Some Guy]

 --- Jim Dixon <jdd at dixons.org> wrote: 
> 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.

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!

Still I stand by the gerneral logic of the estimate:
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
chance of this happening in all W cells = p = q^W = (1 - (1-1/W)^K)^W

There might be a way to calculate this exactly using a bunch of factorials to do the counting.
 
> 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))

Yeah I got 4 : 0.7724761962890625.  Of coarse this is a small W.

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

Premix will work as long as a certain fraction of the pickable neighbors at each step are good. 
If that fraction is f=16/17 that's ok.  It can even survive f=10%.  It's just a question of how
long you have to make the chains before you think it's safe enough.
 
> > The DHT would still function pretty well if you left the adversarial
> > nodes in there,
> 
> Proof?

I can demand a certificate on an insert prooving that all members of a cell are hosting the data. 
I can demand a certificate on a request prooving that all members deny having the data.

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

No it's 16:1.  There were 16 normal guys there (on average).  Then some jerk decide to put his
node in there too.  To get it to 16:2 that jerk would have to calculate twice the hash cash.

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

I was hoping you'd jump in with some ideas.  You know way more about ISPs than I do.  I could
imagine an ISP requiring proof that an incoming connection is approved.  Such certificates would
have to exchanged out of bound (or across a spiffy P2P network).

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

You and your 15 quake buddies decide to start a node.  One guy runs the master and picks p and q
and gives you guys N.  Everyone can take a shot and calculating the hash cash.  Only the master
need have the private key though.  Then one of you bootstraps in using that identity.  Every few
neighbors you learn about are given a different IP to connect to.  

When data is routed through your super node it has to take an extra hop.  Hopefully that won't be
so bad if you live in the same town.  You can use a secret has to distribute data between you,
possibly doing it redundantly.
 
If one of the IPs get's hosed, you'll know that it could only have been one of the nieghbors who
knew that IP.  If you can, redial that node. Screw reconnecting it to its neighbors.

In the extream case if you have as many nodes in you cluster as the neighbor count for the super
node should be you can give away one IP each of you neihbors.  If it gets burned, you'll know who
done it!!!  Report him to all your shared neihbors and never connect to him again.

Does that help?

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

Someone has to do the hashcash or something that produces a random result and costs something. 
You can all send me a hundred dollars and I'll give you a random ID, but then you'd have to trust
me. :-P

Hmmm, I may have an alternative idea to use storage space instead of pure CPU.  Maybe you'll like
that better.  I'll try to think it through a bit more.

If you've got some better idea to randomly assign nodes jobs, feel free to suggest.


__________________________________________________________________

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