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. 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. 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. 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. 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. This wouldn't work on an opennet, however... Cheers, Michael
