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

[Jim Dixon]

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

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

This is simply another assertion without any proof.  And how you could
get f==16/17 with 16 members per cell is puzzling in the extreme.

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

Who is the certificate from?  Why should they pay any attention to your
request?  Why shouldn't they lie sometimes?  all of the time?

> I can demand a certificate on a request prooving that all members deny
> having the data.

Who is the certificate from?

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

No proof, no suggestion as to how this is to be done.

> > >                   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 network under discussion has grown.  Throughout the time of growth,
the adversary has steadily added nodes, maintaining an average of one
compromised node/cell.  The ratio is 15:1 because we have 16 nodes/cell.
This has been the premise thoughout this discussion.  We have been
discussing just how difficult this would be to do (answer: not very, for
an adversary with large resources).

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

I don't think that DOS attacks at the IP level are properly part of this
discussion.  DOS attacks are already a permanent feature of the landscape,
and in fact are already dealt with using spiffy p2p networks:  network
operators use OSPF and sometimes BGP announcements to get rid of them,
these announcements being shared among OSPF/BGP-speaking routers organized
in p2p networks. Both protocols support blackholing traffic from and to
specific IP addresses.

If you want to participate in the game at this level, you set up your own
ISP.  Then you can, if you wish, automate the insertion of information
about DOS attacks into your OSPF.  But this requires a major investment
of money and time.  I would be happy to assist, of course, at normal
contract rates ;-)

However, I do have to confess that running your own ISP will add little to
your overall security.  And the ISP becomes a single point of failure:
the bad guy just bribes the ISP to monitor all traffic.

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

Where do the IP addresses come from?  And why can't the bad guys just DOS
the entire lot?  There are techniques for doing this that require very
little bandwidth.

If I understand your scheme correctly, someone is going to have to acquire
a routable CIDR block.  This is at the very least a /24, a block of 256
addresses.  Those addresses have to be handled by a router.  That router
has to have bandwidth to the Internet.  Who pays for all of this?

The router itself becomes a single point of failure, an expensive target.

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

But _everybody_ will know the IP address.  All of the individual addresses
will look like A.B.C.x, where A.B.C is fixed and x is the variable bit.
Finding the router is trivial: run a traceroute to A.B.C.y, where y is any
number between 1 and 255 if it's a /24.  The next to the last traceroute
hop is the interface on the router that points towards the Internet.

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

But there is a simple solution.  N people get together and build an
authentication server cluster which uses a Byzantine protocol to issue
random IDs.  This is reliable so long as fewer than 2/3s of the N nodes in
the cluster have been compromised.  This is actually quite simple to do,
costs very little, and is scalable.

Consider two scenarios:

* Scenario 1: anyone wishing to join the network has to tie up his
  machine(s) for at least an entire day; in one of your proposals, for
  a day out of every month.  Chances are good that the first time you
  do this you screw it up, so it takes two days.  For some people, even
  more days.

* Scenario 2, anyone wishing to join the network has to either
  (2a) go to a Web server and sign up to an existing trustnet
  (2b) round up some friends (by email?) and set up one by adding IP
       addresses to a list
  Total time required: minutes.

Which is more likely to happen?  Especially since once you have done
scenario 2 once, it is trivial to do it again, setting up another
network?

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

Go back to the Sybil paper, which considers using storage space and
decides that it cannot work.

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

Cluster of N authentication servers using a Byzantine protocol.
Initially set up by acquaintances.  Other people can choose to use the
cluster.  If and when its reputation is compromised, they can set up their
own clusters.  Some clusters will become well known, trusted, and very
large, providing excellent cover for those seeking anonymity.

There will be many clusters, most quite small.  That is, there will be a
crowd of clusters, providing excellent cover for those seeking anonymity.

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