how to do censorship resistance (Re: Grapevine Technical Overview)
Bram Cohen
bram@bitconjurer.org
Mon, 27 May 2002 19:42:53 -0700 (PDT)
Stephen Blackheath wrote:
> Another good thing about toroidal space is that you never have to
> traverse more than half of space, because if you did, you'd be better
> off going in the opposite direction.
That's cute, but a bit of a non-issue I think, since a factor of 2 doesn't
change the asymptotic any.
It occurs to me that if you generalize from 6-space to n-space, and
simplify so that each peer is at position 0 or 1 instead of a floating
point, then you wind up with something very similar to kademlia's xor
metric.
Each peer has an id which is 160 bits. The distance between peer A and B
is the number of 1 bits in the xor of A and B's ids.
You can read about kademlia at http://kademlia.scs.cs.nyu.edu/ It's metric
differs from the one I just gave in that it's a tree instead of a mesh.
You can probably do a good job of pruning peers by having each peer find
out about all of it's peers's peers (by querying it's immediate peers) and
having a policy that if it's peer A and it has peers B and C and the
distance between A and C is greater than both the distance between A and B
and B and C (each, not their sum) then it forgets about C.
Note that kademlia does this for robustness, rather than anonymity
purposes, so the way it uses peers is very different from grapevine.
-Bram