On Thu, Feb 01, 2007 at 09:28:37PM +0000, Michael Rogers wrote: > Matteo Dell'Amico (http://www.disi.unige.it/person/DellamicoM/) gave an > interesting talk at UCL a few months ago, and I thought his work on > neighbourhood maps might be relevant to Freenet. > > Neighbourhood maps start from the observation that social networks are > fast mixing, meaning that if you take a random walk from any node, the > probability of ending up at a given node quickly becomes independent of > your starting point. That means a local view of the network is in some > sense typical of the network as a whole. And that, in turn, means you > can run algorithms like PageRank over a local view of the network, and > get results that are similar to the results you'd get from a global view > of the network.
PageRank is patented, and picking a fight with Google is a bad idea especially as they gave us 4 summer coders and $2000 last year. > > Matteo uses a local view of the network to compute subjective trust > rankings: each node broadcasts its list of neighbours for a small number > of hops, uses the received broadcasts to build a neighbourhood map, and > runs PageRank over the map using itself as the source. Assuming that > each link in the network represents a trust relationship, the resulting > rankings give subjective trust values to the nodes. I proposed a trust metric a month or two ago. Some sort of mechanism for using the topology to generate a trust metric for nearby nodes is going to be vital. Something which there is literature on would be great, but would almost certainly be patented. Having said that, something we make up is still likely to be covered by some patent somewhere - but at least you don't have the triple damages for using PageRank (FPI is based in California, remember?). Ian has said that we shouldn't pre-emptively not use published algorithms just because they might be patented - but using an algorithm which we know for certain to be patented, and which we did not create, is something else! > > PageRank works by diffusing some property (trust in this case) through a > network, starting from a source. In each round, the source produces one > unit of trust and shares it across its outgoing edges. The trust > arriving on each node's incoming edges is summed, reduced by a damping > factor, and shared across its outgoing edges. A node's rank is the > amount of trust it receives per round when the algorithm reaches > a steady state. Similar to my proposal. > > PageRank has two nice properties when used as a trust metric: you can't > amplify your trust by creating lots of outgoing edges, and you can't > 'trap' trust in a cluster of nodes that link to one another. Both of which we want. > > Why is this relevant to Freenet? Premix routing is supposed to prevent > statistical attacks where a node sees a series of related messages (eg > requests for parts of the same file) and concludes that the sender of > the messages must be nearby. In premix routing, the sender builds a > tunnel to a random node and sends all the related messages through the > tunnel. But how do you select a random node? Even in a darknet, I can > create a hundred Sybil nodes and link them all to my 'real' node, > without having to persuade anyone to trust them. A sender who chooses > randomly from a list of nearby nodes will be likely to select one of my > Sybil nodes, and a random walk will also be likely to end up on a Sybil > node. But if the sender builds a neighbourhood map and uses PageRank to > choose the probability of selecting each node, I gain no advantage by > creating a large number of nodes. Right. > > This wouldn't work on an opennet, however... Opennet would require a totally different premix routing algorithm, probably something like I2P where you choose random nodes from the entire network and try to disguise the tunnel creation. I don't know whether it is worth trying to implement such a thing, as opennet is not viable in hostile environments and such premix could be compromized through Sybil attacks, and it would be significant extra work. However I do worry that once we have opennet nobody will use darknet. :| > > Cheers, > Michael -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070205/f745b974/attachment.pgp>
