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

Fri Dec 5 19:59:01 GMT 2003

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

These are not crushing numbers.  The Farsite machines are idle over 90%
of the time, so if hashcash = 1 CPU-day, then this is about six months.
If you are building a network, it's going to take that time or longer to
build up to 2^20 machines.  In other words, Farsite could keep up with
you, and I think that certain organizations have the resources to do a
_lot_ better than that.  You know, like a weekend's work.

> The big problem is that being a neihbor of a target cell may be
> enough.  Which brings the bar down two orders of magnitude or so.

Divide by figures by two orders of magnitude and you get: a day or two
to put a rogue node in each cell -- or a matter of hours for the big boys.

> > On the other hand, it is difficult to believe that a large number of
> > people could be persuaded to invest a day of computer time just to get
> > into the network.  I think that most end users would not put more than
> > say tens of minutes into setting up a connection.  This means that the
> > primary effect of imposing this 1 CPU-day up front cost would be to keep
> > the network very small, perhaps to tens of users.
> >
> > In other words, imposing a high hash cash cost of joining the network
> > would not keep out bad guys, but it would certainly keep out the casual
> > user.  Hypothesis: the higher the hash cash cost of joining, the higher
> > the percentage of bad guys in the network.
> >
> > Hash cash might be useful as a defense against individuals with limited
> > resources.  It is not a practical defense against serious adversaries.
> > Of course, a large network might use hash cash to limit nuisance attacks.
>
> Yes Jim I understand you adversion to hash cash.  Perhaps the remixing
> idea, will make it less nessesary.

I _do_ have an aversion to hashcash: I hate throwing away the CPU time.
But my real objections are (a) it just won't work and (b) it will drive
away normal users.

> The hash cash is there to make you pay something to the system to
> start with.  To pay your first few neighbors to waste their time and
> test to you.  Once a relationship cost something, excomunication
> hurts.

But to mercilessly repeat the same point: it only hurts the little guy.
It won't mean anything at all to someone with larger resources (in the
neighborhood of 2^14 desktop machines), and it certainly won't bother
serious antagonists.

However, there is no doubt that it will drive away at least 99% of the
people who might otherwise use your network.

Look at the Freenet stats on Sourceforge.  They have 6-8,000 hits a day on
average but downloads are in the 30-40/day range.  That is, 99.5% of
viewers turn away.  These are real world figures and should be considered
soberly.

Now think of the effect of telling people that installing GOTnet takes a
full day of computer time.

My guess is that of those 30-40 downloads, 10% might actually try to use
Freenet.  It is certainly my impression that there are no more than a few
hundred Freenet nodes.  This is despite Sourceforge hit rates over 10,000
on some days and despite several years of good publicity.

> For example if an insert hits a node and it signs for the data and
> then later a request hits it and it signs that it doesn't have the
> data, you could "bust" that node, by telling all its neighbors and
> they could then drop it from the network.  You would only have to show
> this proof to a small number of nodes.  The cost of getting busted has
> to exceed that damage that can be done by one bad node.

The cost of adopting hashcash as a defensive measure is huge: you lose
your potential users, you shrink your network by several orders of
magnitude.  If you are interested in anonymity, well, you just lost your
cover traffic.  Anonymity requires crowds.  Hashcash drives the crowds away.

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