I have been looking around a bit for existing research on the prevention of Sybil attacks that could be applicable in our situation and I have found a few interesting papers :
SybilLimit (2008) - an improvement on SybilGuard (2006), it might help the understanding to start with this one
For the moment I have just had a general overview of these papers, I will soon have a bit more free time to go a bit deeper to figure out how relevent they are, but I am puting them here in case others also would like to have a look.
They seem to be describing algorithms for a (supposedly honest) node V (verifier) to assert if another node S (suspect) should be trusted or not. They each are based on slightly different assumptions on the graph and give formal bounds on how many sybil nodes could be accepted using them.
I think using this directly would mean having people watch over the network to find sybil nodes / groups and maybe warn the public not to certify them anymore. But possibly the theoretical tools they use could also help us analyse the formal properties of the rules we want to impose on the network.
A lot more interesting information is also to be found in the bibliographies of these papers.
So I’ve been reading and thinking a bit more about this. It seems to me SybilDefender would be quite appropriate in our case. It is the algorithm that can detect the most sybil identities (close to the theoretical limit apparently).
It takes as entry one known honest node, a suspect node, and output whether the suspect is Sybil or not. After that, if you’ve found a Sybil node, another algorithm can find the “Sybil region” around it.
They call it a “centralized” algorithm but by that they only mean that to run the algorithm you need to know:
The entire network topology
One honest node
Thanks to the members and trust relations being recorded on the blockchain the first point is not a problem in our case, the second one is more difficult.
I have been thinking about the following scheme : when a node produces a block, it runs the algorithm using itself as the known “honest” node. Running it for every other node as the suspect would be too expensive, but maybe we can select a given number of nodes randomly based on a seed taken from the previous block. The result would then depend on the member writing the new block (though it should have similar outputs for most people), but would be completely verifiable by others.
If it finds sybil nodes, it issues “warnings” in the new block. These warnings would NOT have a direct effect on the network (like banning members after a certain number of warnings), but would be dissuasive and would make people that gave warned identities certifications reconsider. They could however impact negatively your ability to create new blocks, so that likely sybil nodes are not able to run the algorithm from their point of view in the network and insert false warnings in the blockchain.
It should be noted that the algorithm has a very low false positive rate (also a bit higher but still really low false negative) but that false positives tend to be very close to actual sybil nodes. So if you are not sybil and receive a warning it is a good indication that you should check the people you gave a certification to.
More thought should go to see exactly what influence a Sybil node could have in this scheme, if they are able to produce new blocks. However I think running the algorithm from the point of view of a Sybil node gives characteristic results (e.g. identifying a majority of the network as sybil). So as the algorithm is verifiable by others maybe we could reject blocks from members that present this characteristic?
Thanks for your investigations. Indeed, if anyone is able to run the algorithm, it means we could use the algorithm to reject blocks computed by “sybil” positive nodes, on reception. Depending on this cost, it could even be added to the rules of membership: just like one must be close enough from any other member, one would have not to be considered a Sybil by the algorithm to be able to join in.
I will read the SybilDefender paper some day, and see how costly it is in a first time. The best would be to talk about it on next FMM (6!).