From ns253@cornell.edu Tue Mar 28 00:18:24 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2S5INY09774 for ; Tue, 28 Mar 2006 00:18:23 -0500 (EST) Received: from localhost (cpe-69-207-49-126.twcny.res.rr.com [69.207.49.126]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2S5IMIQ009688 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 28 Mar 2006 00:18:23 -0500 (EST) Date: Tue, 28 Mar 2006 00:18:30 -0500 From: Niranjan Sivakumar To: egs+summary@cs.cornell.edu Subject: PAPER 16 Message-Id: <20060328001830.a2199a09.ns253@cornell.edu> Organization: Cornell Law School X-Mailer: Sylpheed version 2.2.3 (GTK+ 2.8.13; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit The EigenTrust Algorithm for Reputation Management in P2P Networks A Robust Reputation System for P2P and Mobile Ad-hoc Networks EigenTrust is an attempt to create a self-policing, somewhat decentralized method of reputation management in a p2p network. EigenTrust is based on nodes judging their peers based on direct interaction and aggregating local trust values from other peers. A node can theoretically iterate over the entire network to obtain a view of other nodes' trust information, but the system is designed such that trust vectors of all peers will converge as the network expands. Thus, it should not be necessary to crawl very far to obtain a reasonable view. The system uses a concept of pre-trusted peers that are "known" to be trustworthy to combat inactive peers and malicious collectives. The system is then run on top of DHT, such as CAN or Chord, to assign reputation managers for nodes in the network in order to avoid self-evaluation. Multiple managers are assigned for nodes in order to limit the effect of misbehaving managers. A modified Bayesian approach to decentralized reputation management has is presented in the Robust Reputation System paper. This system has two main ratings that are maintained about nodes, reputation and trust. Reputation is the belief in whether a node is participating properly in a network. Trust is whether or not a node is participating properly in the reputation system, i.e. whether the information it provides about other nodes is valid. Nodes maintain first hand information about their interaction with nodes and share this with other nodes. As nodes receive information from other nodes (and update first hand information), the node will only accept data if it is "close" to the reputation value that it has currently. The modification to their Bayesian scheme facilitates reputation fading and redemption to mitigate nodes that capitalize on built up reputation and suddenly misbehave. Both of these systems do not appear to have deployed outside of simulations. The notion of pre-trusted peers, which is claimed to be beyond the scope of the paper, seems to present a major issue in EigenTrust. It appears to be a very important part of their scheme, yet is not fleshed out. This also detracts from the decentralization of the system as the pre-trusted peers will become targets. The claimed anonymity is not described very well, and the mapping of nodes based on a unique, real-world identity to the DHT that assigns reputation managers seems to be problematic. Identities also seem to be a major problem with the modified Bayesian approach, and is mentioned as being a work in progress. From asr32@cornell.edu Tue Mar 28 01:25:36 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2S6PaY21945 for ; Tue, 28 Mar 2006 01:25:36 -0500 (EST) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2S6PZMj014482 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 28 Mar 2006 01:25:35 -0500 (EST) Message-Id: <6.2.1.2.2.20060326163333.0338ce80@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Tue, 28 Mar 2006 01:26:21 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 16 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Eigentrust: PageRank is one of the most successful algorithms of the last 15 years, and EigenTrust seeks to do something similar with trust in a peer-to-peer system. The authors show how to compute the principal eigenvector of a matrix (in this case, the trust matrix) in a distributed and reliable way. The terms of this eigenvector represent the extent to which the corresponding nodes should be trusted. Embarassingly, the system requires a globally agreed set of pre-trusted peers, and the authors go so far as to admit that the algorithm will not perform properly if some of these trusted peers belong to a malicious collective. "Trust the designers of the network" is not a good peer-to-peer design practice. Robust reputation in peer-to-peer One of the chief difficulties in reputation systems is reconciling the information a node collects directly with what it hears. The authors propose that a node should take in reports, and use them if they correspond to a node's own perceptions. In the proposed scheme, the reports are in fact parameters for a Baysian model of the behavior of other nodes. The system also elegantly incorporates aging of information, so a node's bad reputation will dissipate over time provided the node stops acting badly. The system may be vulnerable to a long-term attack in which malicious nodes carefully send reports that are within the acceptance thresh-hold of a given node, to try to push its rankings up or down over time. Credence: Credence is a system that assigns reputations not to principals, but to objects. When a node receives information from another node, they weight this report based on the extent to which they've agreed in the past; this means that a node that spews out random reputation information (uncorrelated with the ratings of a given node) will be discounted. Further, the system will work correctly even if different populations of nodes disagree about the rating to be accorded to an object. Credence relies on participants forwarding votes for each other. In the presence of malicious peers, the votes gathered may not be a fair sample of the votes cast--malicious peers can preferentially forward votes either pro or con. Credence also relies on having unique object identifiers; it seems as though a simple hash of the contents isn't sufficient, since that would mean that a peer cannot tell whether a proffered object is genuine without first downloading it. A last observation: It might be useful to divide the objects being rated into classes, and work out separate correlation coefficients for each class; it could easily be imagined that a given pair of nodes might agree about how to rate some objects, but disagree about others. (It should be possible to do this by having each peer use a different identity for voting on each of its perceived classes; the classification need not be global). Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From sh366@cornell.edu Tue Mar 28 02:13:33 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2S7DWY05401 for ; Tue, 28 Mar 2006 02:13:32 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2S7DWaB013013 for ; Tue, 28 Mar 2006 02:13:32 -0500 (EST) Message-ID: <1805298740.1143530010308.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Tue, 28 Mar 2006 02:13:31 -0500 (EST) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 16 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 3.0 Reputation management is necessary in a peer-to-peer system because participants might abuse its nature of anonymity to behave maliciously. The twp papers to be discussed today present how to rate other participants' reputation in distributed ways. * There are several advantages of reputation systems, in addition to isolate malicious peers. One is to provide incentives of file sharing. In the case that reputable peers are rewarded with higher priority, increased connectivity or greater bandwidth, participants would tend to share rather than to freeload. Another benefit is to make the system tidy. Peers tend to delete inauthentic files for its reputation. This makes it more difficult to replicate junk files in the system. * In a reputation system, a small fraction of reputable peers may become overloaded. * Pre-trusted peers in EigenTrust could be a potential threat to this reputation system. Besides, malicious peers may provide authentic files to earn other peers' trust but actually provide incorrect trust values (higher for malicious peers and lower for good peers) to confuse the aggregation of global trust values. * The EigenTrust mechanism represents trust value of peers by eigenvectors. Peers rate each other for each transaction. These local trust values are normalized and aggregated to global ones in a distributed and node-symmetric approach. * The basic idea is transitive trust: A peer is likely to trust those who provide it authentic files. Their opinions are given higher weights in the trust value aggregation. This is better than the previous approaches which either aggregate the ratings from only a few peers or cause congestions due to the large-scale aggregations. * EigenTrust requires a priori notation of trust, that is, pre-trusted peers, in dealing with inactive peers. The pre-trusted peers are also important as they guarantee convergence of the computation for trust values against malicious collectives, a group of malicious peers who give each other high local trust value and give all other peers low trust values. * This paper proposes a reputation system based on its modified Bayesian approach. Each peer relies mostly on its own observations (first-hand) but makes use of other peers' information (second-hand) when it's helpful. * Two kinds of ratings are maintained in each peer. The reputation rating represents nodes' behaviors in the system (normal or misbehaving). The trust rating represents how honest a node is in the system (trustworthy or untrustworthy). * The approach copes with false rating from other nodes as follows: If the second-hand report comes from a trustworthy peer or is close to the peer's own first-hand observation, (a) the report is used to slightly modify the reputation rating; (b) the trust rating improves if the first-hand and second-hand information are close, and worsens otherwise. According to the description on the webpage: * Credence differs from previous works in that it derives trust metrics on objects rather than peers. * Each peer collects and evaluates the votes from other peers to estimate the reputation of an object. * The peers' votes are weighted depending on the relationships between the peer itself and those peers. * It is also the first implemented peer-to-peer reputation scheme. From nsg7@cornell.edu Tue Mar 28 10:11:11 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SFBBY28441 for ; Tue, 28 Mar 2006 10:11:11 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2SFB9w0018304 for ; Tue, 28 Mar 2006 10:11:09 -0500 (EST) Received: from 132.236.227.119 by webmail.cornell.edu with HTTP; Tue, 28 Mar 2006 10:11:10 -0500 (EST) Message-ID: <1680.132.236.227.119.1143558670.squirrel@webmail.cornell.edu> Date: Tue, 28 Mar 2006 10:11:10 -0500 (EST) Subject: PAPER 16 From: "Nicholas S Gerner" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal EigenTrust is an algorithm for efficiently computing global trust values from local trust values in a distributed way. Specifically, EigenTrust considers the matrix of local trust vectors from each peer. The left principle eigen vector of this matrix represents the global trust vector for the system as a whole when trust values are aggregated by weighted sum, where the local trust values of each peer are weighted by how much that peer is trusted throughout the network. The EigenTrust algorithm is distributed such that every peer has a set of other peers calculating its trust value and each peer is responsible for calculating the trust value of some number of other peers. To retrieve a trust value for a peer, a node uses consistent hashing (under a number of hash functions) and does majority voting to determine the trust value of the peer in question. This computation and some additional mechanisms allow EigenTrust to address malicious collectives and malicious trust computations. The paper goes on to suggest ways to use global trust values (file sharing credibility) and simulates this application with very positive results under a number of threat models. However, the distributed computation relies on each node correctly reporting the set of peers which have downloaded files from the node in order to get the relevant local trust values to compute the global trust value. It seems as if a malicious node could have a relatively small collective and, despite its actual behaviour, report that this collective holds all the relevant local trust values. These could incorrectly boost the malicous node's trust value (and all the negative trust values will never be taken into account). Also the suggested application will penalize malicous nodes which upload inauthentic files, but will not, as is suggested by the paper, address the free-rider problem since the trust score is used only for choosing a peer to download from. In fact, it seems as if nodes have incentive to upload inauthentic files so they will be less burdened with many file uploads (although the paper does show that some degree of load balancing can be achieved at least among well trusted nodes). In "A Roubust Reputation System..." Buchegger and Le Boudec present a reputation and trust system for mobile ad hoc networks. This system uses first hand reports to aggregate wider reputation and trust scores. These scores identify misbehavior and trustworthiness (respectively) independently. Buchegger and Le Boudec argue that these are problems which can be characterized differently and should be addressed separately. The approach is probabalistic in that it models behavior and credibility by two parameters which can be drawn from Beta distributions. These distributions are parameterized and these parameters are altered by first and second -hand observations. The degree to which second-hand observations are considered is altered by the trustworthiness of a peer (untrustworthy peers are ignored unless their report doesn't significantly deviate from the wider aggregate). The specific application suggested is for use in mobile ad hoc networks in order to utilize or ignore neighbors during routing or other network services. An evaluation indicates that using this system (specifically using second-hand reports) can cut misbehaviour detection time by more than a half. However, the application is not well motivated in this paper and further applications are not considered. It's not clear how well such a system would perform in a very mobile environment or with high churn as the reputation and trust still take time to accumulate and are not aggregated system wide (first-hand reports are only published to immediate neighbors). From pjk25@cornell.edu Tue Mar 28 10:47:45 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SFliY07485 for ; Tue, 28 Mar 2006 10:47:44 -0500 (EST) Received: from [128.84.153.247] (rrdhcp152-503.redrover.cornell.edu [128.84.153.247]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2SFkLPo013348 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Tue, 28 Mar 2006 10:46:24 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <8EFB1A32-4982-4C94-8840-186D601813A1@cornell.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Philip Kuryloski Subject: PAPER 16 Date: Tue, 28 Mar 2006 10:43:58 -0500 X-Mailer: Apple Mail (2.746.2) THE EIGENTRUST ALGORITHM: The problem which the authors wish to address with EigenTrust is that P2P networks generally do not have mechanisms for preventing the spread of inauthentic files. The method that they choose is to maintain a global trust value for each node in the network based on that node's upload history, indicating the confidence with which that node is expected to produce authentic files. Each node maintains a local trust value for each node it has interacted with, giving way to a challenge of aggregating these local trust values to generate a global trust value. EigenTrust assumes that the accuracy to which a node reports its local trust values is proportional to the authenticity of files uploaded by that node, and aggregation is achieved by weighting reported local trust values by the local trust value of the node who reported them. This can be cascaded from to neighbors of neighbors of neighbors, etc. Thus, in the global sense, aggregation is achieved by a distributed computation of the left eigenvector of a matrix of normalized local trust values, making it possible to guarantee a convergence to a set of unique global trust values. To secure this process, DHT consistent hashing is used to select a set of score managers, who act as a definitive set of nodes who are queried and averaged to report a trust value for a given node. As malicious nodes cannot choose their DHT identifier, it is difficult for attackers to control a large portion of score managers for a given node. A ROBUST REPUTATION SYSTEM: Reputation systems must balance a critical tradeoff: first-hand reputation is accurate but a small set, and shared information is a large set but may be inaccurate. EigenTrust achieves this by weighting second hand reputation values by first hand trust values. This system, in contrast, accepts second hand reputation values only if they are congruent with local values. This is achieved using a Bayesian approach, modified in the sense that more recent transactions affect trust ratings more strongly that older transactions. Each node begins with an expectation that a node will act incorrectly according to an initial uninformative Beta distribution. This distribution is updated as observations are made. Nodes are not punished for inaccurate information, as this may punish intermediate nodes along multi-hop aggregation of trust. Although they mention that node identities must be authentic, they do not provide a mechanism to achieve this. EigenTrust requires a set of pre-trusted peers to anchor the global ratings. In terms of performance between the two schemes, it is difficult to compare, as EigenTrust is evaluated based on suppression of unauthentic files, while this system is evaluated based on detection of malicious nodes. From asg46@cornell.edu Tue Mar 28 10:53:04 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SFr4Y08636 for ; Tue, 28 Mar 2006 10:53:04 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2SFr2oA013448 for ; Tue, 28 Mar 2006 10:53:02 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Tue, 28 Mar 2006 10:53:03 -0500 (EST) Message-ID: <2375.128.84.98.90.1143561183.squirrel@webmail.cornell.edu> Date: Tue, 28 Mar 2006 10:53:03 -0500 (EST) Subject: paper 16 -- REPUTATION SYSTEMS From: "Abhishek Santosh Gupta" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal Eigen Trust very similar to the Karma paper the paper proposes a reputation system that assigns each peer a unique global trust value based on the peer's history of uploads. the five issues that a reputation system must address are self-policing, anonymity, non-assignment of profit to newcomers, minimal overhead and robustness to malicious set of peers. the authors define a normalized trust value and argue that substantially good results are obtained despite drawbacks in the normalization scheme. each peer stores a trust value associated with every other peer in the system. This trust is updated on communicating with its neighbors. A large number of such communications/iterations result in a global convergence of this trust vector across all nodes. score managers( peers in the network) are used to manage the trust value of a peer. Secure entry algorithm ensures that a node cannot choose its score managers and also prevents Sybil attacks. PRACTICAL ISSUES: a set of pre-trusted peers are used to tackle various threats. in case of inactive peers, pre-trusted peers will be trusted. POSSIBLE FLAWS nothing prevents a set of malicious nodes from increasing each other's trust values since authentic downloads are not penalized ( a node A can increase node B's trust value indefinitely) the paper makes an assumption that a authentic provider of a file will also be honest when it comes to reporting other facts. Thus, an attacker can share authentic files but deliberately misreport information to decrease the percentage of authentic downloads. the authors discuss this setup under 'threat model C" but they compare their model with non-trust based schemes. load balancing also seems difficult as users would like to download with nodes having higher trust values(no incentive to download from lower trust valued peer). new peers may thus suffer as they may not be trusted by other nodes and thus their trust values cannot increase. ROBUST REPUTATION SYSTEM each peer maintains a reputation rating about every other peer in the network.each peer also maintains a trust rating about every other peer in the network which describes how honest the peer is (in the eyes of the local peer). a summary record for each peer is also maintained locally. reputation rating and first hand information is updated by self-observations based on transactions in which the local node is involved. nodes periodically publish their first hand information to a subset of their peers. when a peer B receives this published first hand information from a peer A, based on the "trustworthiness" of A , B updates reputation vector. Trust vectors are always updated. Bayesian approach is used for modifying first-hand information. Reputation fading is enabled by giving less weight to past experiences. In periods of inactivity, the Bayesian parameters are reduced by a certain factor. a deviation test is used to check whether first hand information from a peer should be used or not. peers are classified as normal/misbehaving and trustworthy/untrustworthy based on the defined thresholds (setting these thresholds involves a tradeoff) Sybil attacks discussed and prevented using a secure entry technique. misreporting nodes do not benefit much as they have to lie carefully (such that they do not cross the threshold) reputation fading mitigates "intoxication" ( nodes telling the truth over a sustained period and then start lying) load balancing also seems difficult as users would like to download with nodes having higher trust values(no incentive to download from lower trust valued peer) From gp72@cornell.edu Tue Mar 28 11:10:53 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.9 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SGArY13814 for ; Tue, 28 Mar 2006 11:10:53 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2SGAodO024617; Tue, 28 Mar 2006 11:10:50 -0500 (EST) Message-ID: <2016044341.1143562250238.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Tue, 28 Mar 2006 11:10:50 -0500 (EST) From: Gopal Parameswaran To: egs+summary@cs.cornell.edu Subject: PAPER 16 Cc: gp72@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Mailer: uPortal WEB email client 3.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2SGArY13814 Eigentrust Algorithm This paper addresses discusses a way to deal with accountability in peer to peer networks by making peers use Global trust values based on Power iteration and identification and isolation of malignant peers. In EigenTrust each peer is is assigned a unique global trust value that reflects the experiences of all peers in the network with peer i where the interactions occur in a distributed and node-symmetric manner with minimal overhead on the network besides being attaining the functionalities of a self-policing,anonymous network. Also it should be noted that the network does not assign any profit to newcomers which discourage attacks on the network by ensuring that the reputation should be obtained by consistent good behaviour through several transactions and prevent malicious peers with poor reputations to continuously change their opaque identifiers to obtain newcomers status. By using a probabilistic model the system also attempts to prevent a collective subversion of the system by a group of peers. This system is based on the assumption that there are some peers in the system that are trustworthy and claims that the first few peers for example that join the network early on are known to be trustworthy because they would be the designers of the network and would have less motivation to destroy the system. This assumption however also introduces the possibility that the malignant peers can join when the network is being built and start behaving in a malignant way after a certain period and hte system would not be able to detect that in time. Such a notion of trust does break the reputation schema. Also for the localized trust value to converge it is essential that that there are pre trusted peers in the system and it is important that no pre-trusted peer be a member of a malicious collective which in turn would compromise the system and destroy the reputation system. Thus the system chooses as its primary peers a few peers that are highly trusted as for example the designers of the network and this in turn coul peers since they would be overloaded in the system. This reputation system does however provide a collective measure of responsibility measure and a measure of reputation based on a global list of peers though the list of peers that actually influence the list is actually more definitive and hence more deterministic and chosen at the start of the network. The authors should have also chosen a more probabilistic model for their reputation schema which could have yielded better results without placing restrictions on prior known peers with reputation and should have introduced a learning model that could have done more effective filtering of the malignant peers. Robust Reputation System In this paper the authors propose a learning mechanism to implement a reputation schema that is based on bayesian networks and also by splitting up the reputation system into two parts viz. a reputation rating schema and a trust rating schema. The authors also removes the dependance on selected prior peers and thus helps to make the system really distributed and dynamic where the ratings are dependant on a set of values are that are maintained by others. The reputation rating represents the opinion formed by node i about the node j’s behaviour as an actor in the base system (for example, whether node j correctly participates in the routing protocol of a mobile ad-hoc network, or whether it provides correct files in a peer-to-peer file-sharing system). The trust rating represents node i’s opinion about how honest the node j is as an actor in the reputation system (i.e. whether the reported first hand information summaries published by node are likely to be true). The reputation and trust ratings and first hand information about the node i iss tored by node j in a set of data structures. This system maintains a bayesian network at each of the node where each node models the behaviour of the other nodes and updates the uncertainity by updating hte probability distribution as new observations become available. The system also improves on a standard bayesian network by giving more weightage to more recent information and thus introducing a concept of reputation fading where the dependance on older reputation values are less. Thus the system proves to be an effective reputation based network due to the inherent property of re-evaluation of bayesian networks and the concept of repuation fading newly introduced. This system measure false positives and uses this measure for its test for malignant peers. From km266@cornell.edu Tue Mar 28 11:23:26 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SGNQY17341 for ; Tue, 28 Mar 2006 11:23:26 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-246.twcny.res.rr.com [69.207.37.246]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2SGNPhM019385 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Tue, 28 Mar 2006 11:23:26 -0500 (EST) Message-ID: <000001c65284$06a86de0$f625cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 16 Date: Tue, 28 Mar 2006 11:23:37 -0500 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2527 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 EigenTrust is an algorithm to assign reputation to peers in a p2p network. The motivation behind the paper is that many papers prior to it require global knowledge or need to query every node in the system, making the systems impractical for modern p2p systems. To fix this problem, they have a notion of trusted peers. Trusted peers are nodes in the network with whom you have already worked with (downloaded from, in the case of file sharing) and therefore you assume that they are trustworthy. This seems like a reasonable assumption: if someone is willing to send you their files and you received them without any problems then they are likely to be honest in their reptutation management as well. Because peers are seeking out the trusts from their trusted neighbors, the opinions on peers will eventually converge. Because of this, you do not have to survey the entire network, only a small portion of it. In secure eigentrust, "score managers" computer the trust value of a certain peer. When someone requests the trust value, the score managers give their results and the requesting node takes a vote on the responses. Score managers are assigned by using a DHT: the IP address of the peer that is trying to be contacted is hashed and the node responsible for that value is assigned responsibility as a score manager as well. One of the negatives of the system is the pre-trusted peers. The theory is that when the network was first forming, the first nodes to have joined are likely to be honest. These nodes are then put into the trusted list of all peers. This seems very ineffective. It sounds like a central-server: a single point of failure and all the responsibility is brushed onto it to take care of. In the Bayesian paper, a trust and reputation system are modelled. Each node trusts itself and therefore makes great use of its own ratings. When querying a peer to find out what rating they assigned to a certain node, it only accepts that rating if that rating is close to what it thought the rating should be. In this way, you trust your own data and do not trust other peers. Ratings fade over time in order to not allow malicious peers to build reputation and then start misbehaving suddenly. It seems easy to launch an attack that constantly lowers ratings of peers, although you will have to be clever about it, making sure to start at a level close to what the originating peer thinks of the askee. From tc99@cornell.edu Tue Mar 28 11:34:07 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SGY6Y19860 for ; Tue, 28 Mar 2006 11:34:06 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2SGY4HS012182 for ; Tue, 28 Mar 2006 11:34:05 -0500 (EST) Received: from 128.84.153.83 by webmail.cornell.edu with HTTP; Tue, 28 Mar 2006 11:34:05 -0500 (EST) Message-ID: <1147.128.84.153.83.1143563645.squirrel@webmail.cornell.edu> Date: Tue, 28 Mar 2006 11:34:05 -0500 (EST) Subject: paper 16 From: "Theodore Ming Shiuan Chao" To: egs@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal EigenTrust is a reputation calculation that computes the steady-state of the trust matrix C of all of the nodes, where c_ij is the local trust value that node i places in node j. To prevent trust inflation, the local trust values are normalized (normalizing the sum over j of c_ij for each i), which unavoidable removes absolute information on trust and makes each value an unknown relative value. A major drawback of their scheme lies in the assumption of pre-trusted nodes. They use these to accelerate convergence and argue that it is not necessary for other nodes to know which nodes are pre-trusted; however, the entire notion makes it extremely vulnerable to attackers at the start where the trust tables are mostly empty. In a more general sense, to prevent malicious nodes from vouching for and second-handidly raising the reputation of other malicious nodes, the authors propose implementing it on top of a DHT of some sort. Each node is assigned multiple random score managers. The score managers use several randomly assigned "daughters" to compute the trust value of the node they are responsible for. The second paper proposes using Bayesian learning to compute reputation and trust ratings. It discounts the learned values over time to give more weight to recent observations, and uses the trustworthiness of a node as a guide whether or not to accept a second-hand reputation report. The trustworthiness of a node is itself modified by the perceived accuracy of received reports (the deviation from the expected values based on the current reputation values). A major question I have about these is their performance with the presence of churn. Previous measurement studies have shown a high churn rate in popular P2P file exchange programs (Gnutella, Napster). Both Bayesian learning and EigenTrust rely on convergence over time, which makes them seem unsuitable for a high churn rate. From kelvinso@gmail.com Tue Mar 28 12:10:00 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00, RCVD_IN_BL_SPAMCOP_NET autolearn=no version=3.1.0 X-Spam-Level: Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.230]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2SH9xY29475 for ; Tue, 28 Mar 2006 12:09:59 -0500 (EST) Received: by wproxy.gmail.com with SMTP id i4so257750wra for ; Tue, 28 Mar 2006 09:09:21 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=F7cXHrr1hU0m2sm1YgDg/+9L6VQwVXBR/n5Q0Q3RUwLaUElAR0q8WfnobWauBku8/GYUc26o88HyxRX7doGrVhoYTBokeELDdT1B4ngwncKr/92IeTr/mdTL3tkKq1PPZhg9TPcamwNmRl7isCR61vMDEBSH93uJ/R6/UonOjOo= Received: by 10.54.134.4 with SMTP id h4mr1057800wrd; Tue, 28 Mar 2006 09:09:21 -0800 (PST) Received: by 10.54.80.16 with HTTP; Tue, 28 Mar 2006 09:09:07 -0800 (PST) Message-ID: <6e1ca4560603280909m71f3b15fs27aa739f52cd8dc1@mail.gmail.com> Date: Tue, 28 Mar 2006 12:09:07 -0500 From: "Chiu Wah Kelvin So" To: egs+summary@cs.cornell.edu Subject: Paper 16 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2SH9xY29475 The first paper, "The EigenTrust Algorithm for Reputation Management in P2P Network," presents a decentralized reputation system on top of peer-to-peer network. Each node calculates the local trust values for other peers based on the transaction with the peers. Then, node normalizes the local trust values and aggregates the local trust values from other peers to form the global trust values. The main idea is based on the notion of transitive trust. A peer will usually trust the opinions of those peers who have authentic files. Using this idea, global trust values can be computed using eigenvector of a matrix of normalized local trust values in a distributed manner. However, EigenTrust requires some pre-trusted peers to guarantee convergence and break up malicious nodes, which is a drawback of the system. The second paper, "A Robust Reputation System for P2P and Mobile Ad-hoc Networks," use a modified Bayesian approach to compute reputation rating of others. The main idea is to maintain two rating for every node. The reputation rating represents is the rating of whether the nodes behave correctly or not. And the trust rating represents how trustworthy are the nodes. Also, it keeps track of the rating of the first hand information. For each transaction, the node will update the first hand information and the reputation rating. And it periodically publishes the first hand information to a subset of nodes. If the node is trustworthy or the published first hand information is close to its own reputation rating, then it will update the reputation rating using modified Bayesian approach, and the trust rating.