Latest Version

People could be forgiven for thinking that the project had somewhat
stagnated given the lack of activity on these mailing lists, so I
wanted to provide an update because this could hardly be further from
the truth.

Oskar Sandberg, Matthew, and I have been developing some ideas for 0.7
which represent an even more fundamental architectural shift than have
been proposed to-date, and which should address one of the most
fundamental shortcomings of Freenet as it relates to Freenet's usage in
a hostile environment, and which I believe represents a significant new
innovation in the P2P-space.

As most people will be aware, Oskar was one of the core Freenet
developers in the first few years of the project. He is now working on
a Ph D? in Mathematics. Over the past few months he and I have been
collaborating on gaining a much deeper mathematical understanding of
how Freenet does what it does. While this work is far from complete,
it has given us some extremely useful insights and much more confidence
in determining what aspects of Freenet's design work well, which don't,
and why.

To understand the new idea, I should start with some theoretical
background. Consider a simple "graph". A graph in the mathematical
sense consists of a set of nodes, some of which are connected to
each-other. At this stage nodes don't have a position in space, all we
know or care about them is which nodes are connected to each-other. We
can assume that connections are bi-directional.

The "diameter" of a graph is the minimum number of nodes you must go
through to get from any one particular node to any other particular
node in the graph. Note that it may not be easy to find this path, but
the important thing is that it exists.

There is a mathematical result which tells us what kind of graphs have
a small diameter. Basically imagine we have three nodes, A is
connected to B, and A is also connected to C. The mathematical result
says that if, given that both are connected to A, there is an increased
probability that B is connected to C, then the graph will have a small
diameter.

So, if we have a graph that has this property then we know that we

we don't necessarily know *how*.

Now imagine that each node in the graph has a position in space, this
can be 1 dimensional, 2 dimensional, 20 dimensional space, it doesn't
matter too much. Imagine that we want to get from one particular node
in this graph to another particular node. A simple approach is, from
our starting node, go to whichever node we are connected to is closest
to the node we want to get to. This approach will work quickly in a
graph that is a "small world". In essence, a small world graph is
where there is a higher probability that nodes which are close together
are connected than nodes which are far apart.

In the ideal case, the probability that two nodes are connected is
proportional to 1/(d^n) where d is the distance between them, and n is
the number of dimensions in the space in which our nodes reside. This
mathematical result is due to Kleinberg.

A small-world graph therefore not only has a small diameter, but
provides an efficient means to find it.

Anyway, back to the story. One of Freenet's weaknesses in terms of its
usefulness in a hostile environment, is that while its goal is to make
it very difficult to determine who is publishing and reading what, it
doesn't make it all that difficult to determine who is running a
Freenet node. This could be problematic in a situation where the act
of running a Freenet node is itself sufficient to incur the wrath of
one's oppressors. Those oppressors can just harvest Freenet node
addresses one by one, it wouldn't be easy, but it wouldn't be
impossible either.

The only real way to address this is to limit the nodes your Freenet
node talks to to people whom you are confident are not working on
behalf of your oppressor. In effect this is the same idea employed by
"darknets", but the problem with darknets is that they don't scale. We
are talking about a darknet that could potentially scale to millions of
users.

Initially it was felt that NGR would allow us to do this, but when,
based on Oskar's and my research, we realised how fundamental the
network topology is to the small world principal, we felt that we
wouldn't be able to maintain a small world link structure if we weren't
able to automatically create links to new nodes.

But then we remembered that human relationships already tend to form
small-world networks (this is the origin of the whole small world
idea), this was a key realisation. If we have a network created by
linking people who know each-other, we know that the network will have
a small diameter, simply because that is how human relationships work
(ie. if I know John, and I know Fred, then there is a greater
probability that John knows Fred than of two randomly selected people
knowing each-other).

But, for a network of low-diameter to be useful, we need to turn it
into a small world network, and this means each node in the network
needs a "position" in space such that Kleinberg's topology holds. Our
first thought was that NGR might be able to do this. Matthew has been
running some experiments to test this theory, and results so-far have
been promising but not yet conclusive.

Meanwhile Oskar and I have been testing some alternative algorithms for
achieving this should NGR fail to do what we need it to do. We have
also had some success in this regard, but again, nothing conclusive
yet.

Assuming we can find a good algorithm for assigning positions or
"identities" to nodes, we are in a pretty good situation as we can now
efficiently route requests for data in our globally scalable darknet.

Anyway, that is where things stand right now - as can be seen it is
still a work in progress, but I hope people agree that this is an
exciting and promising new direction for Freenet that remains true to
Freenet's ultimate goals. If successful, Freenet will be a globally
scalable darknet and will be resistant to a whole class of "harvesting"
attacks.

Lastly, however, I need to point out that our current funding situation
is not healthy, as anyone can see by looking at the website. As a
result, if anyone out there wants to support this effort, and many
already have, then please visit the website and make a donation so that
Matthew doesn't starve while he works on this stuff.

All the best,

Ian.