On the Sybil-Proofness of Accounting MechanismsSven SeukenSchool of Engineering & Applied SciencesHarvard University33 Oxford St., Cambridge, [email protected] C. ParkesSchool of Engineering & Applied SciencesHarvard University33 Oxford St., Cambridge, [email protected] common challenge in distributed work systems like P2Pfile-sharing communities, or ad-hoc routing networks, is tominimize the number of free-riders and incentivize contri-butions. Without any centralized monitoring it is difficultto distinguish contributors from free-riders. One way to ad-dress this problem is via accounting mechanisms which relyon voluntary reports by individual agents and compute ascore for each agent in the network. In Seuken et al. [11],we have recently proposed a mechanism which removes anyincentive for a user to manipulate the mechanism via misre-po rts. However, we left the existence of sybil-proof account-ing mechanisms as an open question. In this paper, we set-tle this question, and show the striking impossibility resultthat under reasonable assumptions no s ybil-proof account-ing mechanism exists. We show, that a significantly weakerform of K-sybil-pro ofne ss can be achieved against certainclasses of sybil attacks. Finally, we explain how limited ro-bustness to sybil manipulations can be achieved by usingmax-flow algorithms in accounting mechanism design.Categories and Subject DescriptorsJ.4 [Computer Applications]: Social and Behavioral Sci-ences—EconomicsGeneral TermsAlgorithms, Design, EconomicsKeywordsMechanism Design, Sybil-Proofness, P2P, Reputation1. INTRODUCTIONDistributed work systems arise in many places, for exam-ple i n peer-to-peer (P2P) file-sharing networks, or in ad-hocwireless networks where individual peers route data pack-ages for each other. Of course, the total amount of workperfo rmed by a population is equal to the total amount ofwork consumed. Moreover, while some degree of free-ridingPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.NetEcon’11, June 5, 2011, San Jose, California, USA.Copyright 2011 ACM ——————– ...$10.00.may be acceptable, the long-term viability of distributedwork systems relies on roughly balanced work contributions.Otherwise, strategic agents may s eek to free-ride on the sy s-tem, i.e., minimize the work they perform and maximizethe work they consume. This problem becomes particularlychallenging when the interactions are bilateral, there is no apriori trust relation between the agents, there is no ability tomonitor activities, no contract covers the interactions, andno currency can be used because the institutional require-ments for payment exchanges a re not available.In Seuken et al. [11], we have recently formalized thisproblem and introduced accounting mechanisms that pro-vide a solution: t hey keep long-term tallies o f work per-formed and consumed and compute a score that approx-imates an agent’s net contributions. Because accountingmechanisms rely on voluntary reports, a major challenge isto provide robustness against strategic manipulations. Thetwo manipulations we consider a re misreports, where anagent overstates the amount of work contributed or con-sumed, and sybil manipulations, where an a gent creates fakecopies of itself. Previously, we have p roposed the Drop-Edgemechanism which selectively ignores some of the reports,thereby providing misrep o rt-proofness [11]. However, wehave left open the question whether sybilproof accountingmechanism exi st. In this paper, we prove that under rea-sonable assumptions, no sybilproof accounting mechanismexists. We show that a sig nificantly weaker form of robust-ness can be achieved for a restricted class of attacks. Finally,we discuss the usefulness of max-flow algorithms for limitedrobustness against sybil manipulations in practice.Accounting vs. Reputation Mechanisms.Misrep o rt and sybil manipulations are well-studied in therelated literature on trust and reputation mechanisms [6].However, the results from this literature do not translateto accounting mechanisms. F irs t, in distributed work sys-tems, every positive report by A about his interaction withB,i.e.,B performed work for A, is simultaneously a neg-ative report about A,i.e.,A received work from B.Thisfundamental tension is not present in reputation mecha-nisms. Second, sybil manipulations are much more pow-erful against accounting mechanisms. For a search engine,for example, the primary concern is that an agent couldincrease the reputation of its website by creating a set ofsybils that are linking to the original website, but an agentdo es not care about the reputation of the sybils themselves.In a distributed work system, in contrast, if an agent cancreate sybils with a positive score, then these sybils mayreceive work from other users without negatively affectingiji510kw =0ijw =100ikw =100ijw =0ikFigure 1: A subjective work graph from agent i’sperspective. Edges where i has direct informationhave only one weight. Other edges can have twoweights, c orrespond ing to the p o ssibly conflictingreports of the two agents involved.the score of the original agent. While various reputationmechanisms have been proposed that are sybil-proof (e.g.,maxflow, hitting-time [2, 12]), these results do not trans-late to accounting mechanisms. Third, once an agent hasa high reputation it can benefit from that for a long time.For example, a website with a high PageRank [8] benefitsfrom lots of visitors without affecting its reputation. In dis-tributed work systems, in contrast, an agent benefits froma high score by getting priority for receiving work in thefuture, which in turn decreases its score again. Thus, ac-counting scores are inherently temporary.Related Work.Despite the differences between accounting and reputationmechanisms, the literature on transitive trust and reputa-tion mechanisms [6] is an important precursor to our ownwork. One of the largest steps forward regarding robustincentives in a real-world P2P system was the BitTorrentprotoc ol [3]. In contrast to previous protocols l ike Napsteror Gnutella, BitTorrent uses a policy with