I think they are quite different: 1. The Levien's work is in the category of "asymmetric" trust metric, which has been proven to be very resilient to Sybil manipulation. The algorithm is *deterministic*, as it's based on network minimum flow. On the other hand, it's very expensive in terms of computation.
2. SybilGuard, on the other hand, is *probabilistic*, as it's based on random walk in a social network, which would still leave (probably very small) room for Sybil attacks. I believe the algorithm is much less expensive than Levien's. Furthermore, the offline, social relation assumption in SybilGuard is quite strong. A very interesting piece of work is from Ross Anderson, where he uses the bootstrapping graph to detect signs of Sybil attack (http://www.cl.cam.ac.uk/~rja14/Papers/sybildht.pdf) Cheers. Anh. zooko wrote: > On Aug 15, 2008, at 0:31 AM, Pierre-Evariste Dagand wrote: > >>> The paper >>> leaves open the question of Sybil resistance for multiple-hop >>> routes in a >>> decentralized system. >> If your users belong to a social network, SybilGuard might be >> interesting : >> >> http://portal.acm.org/citation.cfm?id=1159945 >> >> The idea is that Sybil users will form a big cluster of identities >> that trust each other while having a small number of "trust relation" >> with honest peers. SybilGuard detects these "attack edges" thanks to >> "verifiable random walks". > > This sounds a lot like Raph Levien's pioneering work on "an attack- > resistant trust metric". > > Raph implemented and ran http://advogato.org which used the trust > metric (as well as being a hub for open source/Free Software hackers > and arguably the earliest instance of a "social networking site"). > > He published his idea on a web page [1] and the idea was widely known > and influential throughout the p2p community circa 2000. > > Unfortunately, Raph never succeeded at getting his idea published in > a peer-reviewed academic journal or conference, so now it is missing > from the references of "SybilGuard". Of course, it is also missing > from the references of the original Sybil paper. It's too bad, in my > opinion, that things which haven't been published in the academic > literature are so invisible to the academic literature. > > Regards, > > Zooko > > [1] http://advogato.org/trust-metric.html > _______________________________________________ > p2p-hackers mailing list > [email protected] > http://lists.zooko.com/mailman/listinfo/p2p-hackers _______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
