From asg46@cornell.edu Thu Feb 23 11:58:25 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 k1NGwOt12698 for ; Thu, 23 Feb 2006 11:58:24 -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 k1NGwNmD025569 for ; Thu, 23 Feb 2006 11:58:23 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Thu, 23 Feb 2006 11:58:24 -0500 (EST) Message-ID: <2349.128.84.98.90.1140713904.squirrel@webmail.cornell.edu> Date: Thu, 23 Feb 2006 11:58:24 -0500 (EST) Subject: paper 10 -measurements 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 A MEASUREMENT .. Peer-to-peer systems are designed under the notion that all peers are symmetric with respect to resource availability and consumption. However, empirical studies have proved this idea wrong and suggest that a peer must be assigned a task taking into account the abilities of the peer. the authors discuss the architecture of Napster and Gnutella and use crawlers to measure a number of parameters which result in the following observations: 1) peers have an incentive to report lower bandwidths than they have. 2) number of "free-riders" in both systems is more than 20% 3) Napster peers tend to participate in the system more often than Gnutella peers probably due to better application features. 4) Peers that report uniform bandwidths are uniformly distributed across the bandwidth population. 5) peers are heterogeneous with respect to many characteristics such as Internet connection speed, latencies, lifetimes, shared data. Thus, client-server like behavior is clearly identified in a good amount. although the period over which the measurements were carried out was small, the results should not differ much even for longer periods. MEASUREMENT, MODELING ... this paper compares peer-to-peer load (Kazaa) with Internet traffic. it results in the following comparisons/observations : 1) Kazaa users display "fetch-at-most-once" behavior simply because objects here are immutable. Web traffic display "fetch-repeatedly" behavior as objects here change constantly.Thus, Kazza does not display zipf distribution especially with caching. 2) Kazaa traffic is due to the fact that new objects are inserted into the system while web traffic is due to object updates. 3) kazaa users are more patient. the suggested reason is that it is a batch-mode delivery system where downloads are made in the background while the web is an interactive system where immediate responses are required (resulting in impatient behavior) the average session length in Kazaa was smaller than the median time required to download a small object. This hints that 1) many transactions fail 2) a client may not end up finding a server for a object resulting in periods of no-activity the number of requests to small objects is huge compared to the other objects requested while the majority of bytes transferred are due to large objects. Thus, if our concern is bandwidth consumption then we must pay attention to the small number of requests to large objects but if our concern is to improve overall user experience then we must pay attention to the large number of small object requests. locality awareness would result in much better performance in Kazaa. From lackhand@gmail.com Mon Feb 27 19:36:42 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.6 required=5.0 tests=AWL,BAYES_00,HTML_00_10, HTML_MESSAGE autolearn=no version=3.1.0 X-Spam-Level: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.199] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1S0agt24602 for ; Mon, 27 Feb 2006 19:36:42 -0500 (EST) Received: by zproxy.gmail.com with SMTP id 13so1038820nzp for ; Mon, 27 Feb 2006 16:36:41 -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; b=cB5OJ375pqU3f7wXhG2e9VpcIYzob3SgVNgj0Vvx8v99cO6wCN5ya+2te+2Tzh35te+ZK/V/TFda85tqx3d5EkxRKxnNdJ7hqw1bl2bLMbIpV5VLnpfGaRMkRFi2Qc+Ofs1lz2KDjSfNJtd5A7BRXBCGoqD5MFavfltHVWlr0fc= Received: by 10.37.2.49 with SMTP id e49mr6175239nzi; Mon, 27 Feb 2006 16:36:41 -0800 (PST) Received: by 10.36.147.10 with HTTP; Mon, 27 Feb 2006 16:36:41 -0800 (PST) Message-ID: <9aa7a97d0602271636y4e395510t7fb8f39d2aafd6ee@mail.gmail.com> Date: Mon, 27 Feb 2006 19:36:41 -0500 From: "Andrew Cunningham" To: egs+summary@cs.cornell.edu Subject: PAPER 10 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_7942_1516308.1141087001411" ------=_Part_7942_1516308.1141087001411 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andrew Cunningham arc39 _Samsara:_Honor_Among_Thieves_in_Peer_to_Peer_Storage_ Landon P Cox, Brian D Noble An attempt to ensure fairness in peer to peer storage without falling back on trusted third parties, centralized infrastructure, constraints on data placement, monetary payment, or certified identities. It does this through a symmetric storage relationship. The motivation is that peer to peer storage systems rely on individual nodes consuming storage space in proportion to their contribution, in order to ensure sufficient storage space availability. Some solutions rely on trusted third parties to enforce quotas; this is clearly a sufficient, if unsatisfying, aolution. They suggest symmetric storage -- A stores on B <=3D=3D> B stores on A -- as a grassroots solution. The next insight is that if these relationships don't naturally occurr, they can be manufactured by inserting incompressible blocks of data, storage claims, into the network; by checking if the storag= e claim is still resident on the remote computer, then their data must still be retained on the local one. Also, storage claims may be treated as user objects and stored in the system if desired -- but if they cannot be produced, the node they were assigned to is the penalized node. Though I am impressed by their construction of claims, I am not sufficiently impressed: it relies on two secrets, rather than one large one= ; this seems inefficient. Moreover, it presumably relies on a separate P for each claim, which may or may not make blocks compressible if false; it seem= s that a better idea would be to take deterministic hashes (say, "this holds place for the 3rd block belonging to B") and to use a very large, secure, signing key; even with the encrypted data public, and the data, this only makes certain known-plaintext attacks easier, and does not significantly weaken the scheme, while reducing overhead required to test claims. Similarly, they make small news of occaisional data loss, claiming that it can be backed up from local copies: because all data in the system is incompressible, this means that overhead on the network is multiplied by th= e inverse of failure, even for legitimate users; moreover, the more one store= s for others, the less room one has for storage claims, which must be forwarded into the network -- putting one at the mercy of lazy users (who w= e have a claim on, as well). Thus there is this odd period wherin we wait for chains to become cycles during which we are vulnerable to the behavior of other nodes. _SHARP:_An_Architecture_For_Secure_Resource_Peering_ Yun Fu, Jeffrey Chase, Brent Chun, Stephen Schwab, Amin Vahdat Tackling something of a superset of the previous problem, dealing with total resource management, rather than simply storage space. It assumes responsibility for resouces management, control and sharing across sites & trust domains, reconciling policy-based resource management with resource availability when agents or other actors fail, become unreachable, or abandon their claims. It uses soft-state timed claims, which expire after some period, and agents may oversubscribe resources to improve efficiency and availability, being given probabilistic assurance that their claims wil= l be honored. Oversubscribed claims may be detected, and claims may be delegated accountably. These claims are both unforgable and non-repudiable, with keys being locally assigned. It allows actors to reserve resources, prevent theft of resources, support admission control, and balance global sharing with local autonomy, and must be secure, in that the actors may be mutually distrusting or vulnerable to external attack. This is partially done by issuing the ability to issue requests -- a soft state claim to request resources, but not an actual lock on those resources. This allows farming out of ticket issuance, which is an advantage, and a host of other advantages such as the probabilistic options offered. There are few obvious flaws in this scheme, other than the overhea= d that vending tickets requires; in general, it passes every threat they suggest, and the list is reasonabily comprehensive. _PPAY:_Micropayments_for_Peer-to-Peer_Systems_ Beverly Yang, Hector Garcia-Molina Whether or not the peer to peer network is economically driven for fungible resources, there remains the need to provide an efficient, secure payment mechanism, even if only for unique resources. PPay explots the unique characteristics of peer to peer systems to maximize efficiency while maintaining security properties. It does this without the need for a trusted, centralized (monetary) broker to donate O(n) work for n transactions over the network. The broker is only invoked at the opening an= d closing of accounts, arbitration, and occaisionally to perform services for offline peers; under realistic application loads, it provides quite reasonable broker load values, while guaranteeing detectable and traceable fraud, though in a sense, relative to the value of the goods: they are micropayments, thus requiring light overhead, without guaranteeing fair exchange of goods and payment; conterfeit coins are detectable, but perhaps only after the fact. It purchases much of its efficiency by "moving the issuer into the cloud", having transactions involving a coin purhcased by U going through U; this does not go against the financial institution who issued U the coin in exchange for currency. The ties back to real-world currency seem to mostly be symmetric; while required, this leaves a large security hole where the user with more resources (read: cash) can starve (literally, not "resources") another by misbehaving in conjunction with them. It is unprofitable, but completely legal, and cheaper than many other such eye-for-an-eye attacks, as the coin= s are micropayments, thus small. They claim to be immune to wrongful denial attacks; this isn't quite true. A reassignment may be wrongfully denied, in that the owner refuses to transfer holders; however, it may still be "cashe= d in", making the system mostly immune (not completely) to this attack. In many ways, this shifts load from the broker onto the brokee -- if I request a coin, I am thereafter responsible for all transactions involving that coin, until it "dies". This gives me a very large motivation to cash in my coins as soon as possible, so that I can cease holding their state. Coin renewal solves both this issue and also the related issue of what to do "if the token drops", if the location of a coin is unknown. Since all requests for transferal must go through the owner of the coin or the broker, this is less of an issue, but it is not a non-issue, as it could be the case that the coin is involved in some secondary scheme or mismanaged to the point where its holder is unclear. It is legitimate to say that this is the owner's fault- and- responsibility; it would still be nice to have some way to repair this. The other issue is that the coins do not carry a representation of their value, implying that we must go to the broker to determine the value of the coin, or use equally valued coins -- if we're willing to believe the holder's estimation, why not rely on them for everything, without recourse to a broker; if all coins are the same value, there is an element of lost functionality. This is easy to fix: let the issuer include the value, in addition to the serial number, in each raw coin. _KARMA:_A_Secure_Economic_Framework_for_Peer_to_Peer_Resource_Sharing_ Vivek Vishnumurthy, Sangeeth Chandrakumar, Emin Gun Sirer Karma is another solution to the same problem, where we seek to ensure equitable resource sharing among nodes in the system. It spreads the reswponsibility for "coins" across several banksets, which may be distributed through the overlay. Each node has its account tracked at each member of the bank set, and thus "cheating the system" relies on controllin= g the bank set. It may be increased by donating resources to the system, and therefore can be used in place of the micropayment system above. It is less "secure" than the previous, however, because it does not ultimately rely on a resource signed with the key of the issuing authority; in the previous scheme, the bank could always ensure that the account numbe= r they were handed was issued by a real entity; under this system, my node is a member of the entity responsible for tracking the balance in my account, which can lead to a sort of conflict of interest. It is, however, not intended for real cash, but as a way of tracking resource usage, and for that it is quite adequate, as in order to break the system, one must bring more resources to bear than participating in the system would require. ------=_Part_7942_1516308.1141087001411 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable
    
Andrew Cunningham
arc39

    _Samsara:_Honor_Among_Thieves_in_Peer_to_Peer_Storage_     Landon P Cox, Brian D Noble
    
    An attempt to ensure fairness in peer to peer storage without falling back on trusted third parties, centralized infrastructure, constraints on data placement, monetary payment, or certified identities. It does this through a symmetric storage relationship. The motivation is that peer to peer storage systems rely on individual nodes consuming storage space in proportion to their contribution, in order to ensure sufficient storage space availability. Some solutions rely on trusted third parties to enforce quotas; this is clearly a sufficient, if unsatisfying, aolution. They suggest symmetric storage -- A stores on B <=3D=3D> B stores on A -- as a grassroots solution. The next insight is that if these relationships don't naturally occurr, they can be manufactured by inserting incompressible blocks of data, storage claims, into the network; by checking if the storage claim is still resident on the remote computer, then their data must still be retained on the local one. Also, storage claims may be treated as user objects and stored in the system if desired -- but if they cannot be produced, the node they were assigned to is the penalized node.
    Though I am impressed by their construction of claims, I am not sufficiently impressed: it relies on two secrets, rather than one large one; this seems inefficient. Moreover, it presumably relies on a separate P for each claim, which may or may not make blocks compressible if false; it seems that a better idea would be to take deterministic hashes (say, "this holds place for the 3rd block belonging to B") and to use a very large, secure, signing key; even with the encrypted data public, and the data, this only makes certain known-plaintext attacks easier, and does not significantly weaken the scheme, while reducing overhead required to test claims. Similarly, they make small news of occaisional data loss, claiming that it can be backed up from local copies: because all data in the system is incompressible, this means that overhead on the network is multiplied by the inverse of failure, even for legitimate users; moreover, the more one stores for others, the less room one has for storage claims, which must be forwarded into the network -- putting one at the mercy of lazy users (who we have a claim on, as well). Thus there is this odd period wherin we wait for chains to become cycles during which we are vulnerable to the behavior of other nodes.
    
    _SHARP:_An_Architecture_For_Secure_Resource_Peering_
    Yun Fu, Jeffrey Chase, Brent Chun, Stephen Schwab, Amin = Vahdat
    
    Tackling something of a superset of the previous problem, dealing with total resource management, rather than simply storage space. It assumes responsibility for resouces management, control and sharing across sites & trust domains, reconciling policy-based resource management with resource availability when agents or other actors fail, become unreachable, or abandon their claims. It uses soft-state timed claims, which expire after some period, and agents may oversubscribe resources to improve efficiency and availability, being given probabilistic assurance that their claims will be honored. Oversubscribed claims may be detected, and claims may be delegated accountably. These claims are both unforgable and non-repudiable, with keys being locally assigned. It allows actors to reserve resources, prevent theft of resources, support admission control, and balance global sharing with local autonomy, and must be secure, in that the actors may be mutually distrusting or vulnerable to external attack.
    This is partially done by issuing the ability to issue requests -- a soft state claim to request resources, but not an actual lock on those resources. This allows farming out of ticket issuance, which is an advantage, and a host of other advantages such as the probabilistic options offered. There are few obvious flaws in this scheme, other than the overhead that vending tickets requires; in general, it passes every threat they suggest, and the list is reasonabily comprehensive.
    
    _PPAY:_Micropayments_for_Peer-to-Peer_Systems_
    Beverly Yang, Hector Garcia-Molina
    
    Whether or not the peer to peer network is economically driven for fungible resources, there remains the need to provide an efficient, secure payment mechanism, even if only for unique resources. PPay explots the unique characteristics of peer to peer systems to maximize efficiency while maintaining security properties. It does this without the need for a trusted, centralized (monetary) broker to donate O(n) work for n transactions over the network. The broker is only invoked at the opening and closing of accounts, arbitration, and occaisionally to perform services for offline peers; under realistic application loads, it provides quite reasonable broker load values, while guaranteeing detectable and traceable fraud, though in a sense, relative to the value of the goods: they are micropayments, thus requiring light overhead, without guaranteeing fair exchange of goods and payment; conterfeit coins are detectable, but perhaps only after the fact. It purchases much of its efficiency by "moving the issuer into the cloud", having transactions involving a coin purhcased by U going through U; this does not go against the financial institution who issued U the coin in exchange for currency.
    The ties back to real-world currency seem to mostly be symmetric; while required, this leaves a large security hole where the user with more resources (read: cash) can starve (literally, not "resources") another by misbehaving in conjunction with them. It = is unprofitable, but completely legal, and cheaper than many other such eye-for-an-eye attacks, as the coins are micropayments, thus small. They claim to be immune to wrongful denial attacks; this isn't quite true. A reassignment may be wrongfully denied, in that the owner refuses to transfer holders; however, it may still be "cashed in"= , making the system mostly immune (not completely) to this attack. In many ways, this shifts load from the broker onto the brokee -- if I request a coin, I am thereafter responsible for all transactions involving that coin, until it "dies". This gives me a very large motivation to cash in my coins as soon as possible, so that I can cease holding their state. Coin renewal solves both this issue and also the related issue of what to do "if the token drops", if the location= of a coin is unknown. Since all requests for transferal must go through the owner of the coin or the broker, this is less of an issue, but it is not a non-issue, as it could be the case that the coin is involved in some secondary scheme or mismanaged to the point where its holder is unclear. It is legitimate to say that this is the owner's fault- and- responsibility; it would still be nice to have some way to repair this. The other issue is that the coins do not carry a representation of their value, implying that we must go to the broker to determine the value of the coin, or use equally valued coins -- if we're willing to believe the holder's estimation, why not rely on them for everything, without recourse to a broker; if all coins are the same value, there is an element of lost functionality. This is easy to fix: let the issuer include the value, in addition to the serial number, in each raw coin.

    _KARMA:_A_Secure_Economic_Framework_for_Peer_to_Peer_Res= ource_Sharing_
    Vivek Vishnumurthy, Sangeeth Chandrakumar, Emin Gun Sire= r
    
    Karma is another solution to the same problem, where we seek to ensure equitable resource sharing among nodes in the system. It spreads the reswponsibility for "coins" across several bankset= s, which may be distributed through the overlay. Each node has its account tracked at each member of the bank set, and thus "cheating the system&= quot; relies on controlling the bank set. It may be increased by donating resources to the system, and therefore can be used in place of the micropayment system above.
    It is less "secure" than the previous, however= , because it does not ultimately rely on a resource signed with the key of the issuing authority; in the previous scheme, the bank could always ensure that the account number they were handed was issued by a real entity; under this system, my node is a member of the entity responsible for tracking the balance in my account, which can lead to a sort of conflict of interest.
    It is, however, not intended for real cash, but as a way of tracking resource usage, and for that it is quite adequate, as in order to break the system, one must bring more resources to bear than participating in the system would require. ------=_Part_7942_1516308.1141087001411-- From sh366@cornell.edu Tue Feb 28 00:29:06 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.4 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 k1S5T5t09951 for ; Tue, 28 Feb 2006 00:29:05 -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 k1S5T4XS028371 for ; Tue, 28 Feb 2006 00:29:05 -0500 (EST) Message-ID: <635318788.1141104542552.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Tue, 28 Feb 2006 00:29:03 -0500 (EST) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 10 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 k1S5T5t09951 Recent studies show that participants in peer-to-peer systems behave selfish – they consume more resources than what they contribute. A distributed resource management is thus needed to coordinate shared resources. The four papers present different approaches to solve these problems of resource exchange in distributed manner. * Smasara is an infrastructure for enforcing fairness in peer-to-peer storage systems. It manufactures symmetric storage relationships by constructing 'claims': each contributing node creates a claim that the corresponding consuming node has to store, and they check each other to ensure that data are correctly stored. * Nodes unresponsive to messages are punished (replicas being discarded) with a probability in proportion to the number of consecutively failed query. This makes dishonest and chronically unavailable nodes unable to maintain data while nodes suffering a transient failure only have to restore several replicas from surviving copies in the system. * Samsara nodes may forward claims to reduce storage overhead, but they are responsible for these claims: they will be penalized if the node storing their claims cheats. This is a dilemma more than a tradeoff. * Behaviors of malicious nodes, such as promise to store data but immediately drop it, can't be prevented in Samsara. Besides, Samsara can't stop nodes from refusing to store data other than for the claims. Many data may never be stored in that case. * SHARP is an architecture for secure distributed resource management across sites and trusted domains. Its key construct is a resource 'claim' – a promise or right to possess resources for designated time interval. It allows principals to formulate and exchange unforgeable assertions about control over resources. * Resources at each site are controlled by a "site authority". They delegate control over their resources to "agents". Programs run within a slice – a partition or share of global resources. The "service managers" contact agents to obtain resources on behalf of the guests, bind the resources to slices, and instantiate the service with the slice. * The resources are obtained during a two-phase process. First, the service manager requests a 'ticket', which represents a soft claim, from an agent. Second, the service manager redeems the ticket with the site authority to for a 'lease', which is a hard claim over concrete resources. A ticket only suggests resource ownership whereas a lease guarantees it. The distinction between them allows coordinated resource management while preserving site autonomy and local control over resources. * With the self-certifying and self-describing property of tickets and secure mechanisms to subdivide and delegate claims, sites may trade their resources with peering partners according to local policies (resource peering). Moreover, agents may over-subscribe resources to improve resource efficiency and availability when claims are lost or left idle. * Even if SHARP eliminates a centralized trusted authority in its framework, the principals that exchange resource claims need to authenticate one another off-line to establish faith in one another’s public keys. * Freeloader-like behaviors are possible in SHARP, since the resource exchanges between sites can be asymmetric. * PPay is a micro-payment system which exploits characteristics in peer-to-peer systems to improve performance while maintaining security properties. The concept of floating, self-managed currency, a transferable 'coin', is proposed in PPay protocol to reduce involvement of the centralized broker. Its security properties are basically ensured by the serial number and public key cryptography among the broker and the users. * As claimed in the paper, micro-payments are payments of small amount, so its mechanism should be lightweight, whose costs don't outweigh value of the payment. Therefore only security where fraud is detectable, traceable and unprofitable is guaranteed in this system. * Several extensions, along with their security considerations, to the basic protocol that improve system performance are described, such as 'limit certificate' from the broker which specifies the number of coins a user is authorized to print, 'layered coins' that can be reassigned among the users, 'coin renewal' to decrease the state users have to keep, and the use of 'soft credit windows' to make pico-payments faster. * The experimental results show that PPay outperforms existing micro-payment schemes in terms of broker load. They also illustrate the settings of parameter values to tune PPay performance. * Even though rarely, the centralized broker is still required in PPay, for users to open and close accounts, for arbitration, and for performing service on behalf of offline peers. * KARMA is a secure economic framework to avoid freeloaders in peer-to-peer systems. Its main component is "karma", a scalar value which captures the amount of resources a peer has contributed and consumed. Each peer has a bank-set that keeps track of its karma balance. * The KARMA file exchange works as follows: consumer A sends to provider B a signed message authorizing bank-set-A to transfer a certain amount of karma to B. B forwards it to bank-set-B, in which each node talks to nodes of bank-set-A to check if A has sufficient karma for that transaction. If yes, the amount is deducted from A's account and credited to B's account. B then has to proceed with the file-transfer to A. * Security issues are addressed. (1) Replay attacks are ruled out in KARMA by the use of sequence number and signatures. (2) An atomic transaction scheme is deployed: the provider sends the consumer the file encrypted with a secret key; the consumer gets the key to decrypt the file if and only if simultaneously the provider gets a certificate of receipt. Malicious provider (accepts payment but fails to complete the transaction) and malicious consumer (receives a resource but claims they didn't) behaviors thus can't happen. * KARMA obviates expensive consensus/agreement protocols in its transfer protocol by (1) secure routing that ensures reliable message delivery and (2) transmission between a k-to-k mapping (majority voting) of the consumer's and provider's bank-set. * To offset inflation and deflation, the outstanding karma is periodically re-valued according to the number of nodes in the system and a correction factor. In addition, the probability of bank-set corruption is very low due to the secure entry algorithm. It would be better if experimental results could be provided in this paper to support the design and development of KARMA. From pjk25@cornell.edu Tue Feb 28 01:52: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=-2.6 required=5.0 tests=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 k1S6q0t29920 for ; Tue, 28 Feb 2006 01:52:00 -0500 (EST) Received: from [192.168.0.103] (user-10mt73g.cable.mindspring.com [65.110.156.112]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1S6pxNm021187 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Tue, 28 Feb 2006 01:52:00 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <2A9AB04A-1D20-4C5A-8949-3F28396F0449@cornell.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Philip Kuryloski Subject: PAPER 10 Date: Tue, 28 Feb 2006 01:54:50 -0500 X-Mailer: Apple Mail (2.746.2) SAMSARA A challenge of p2p network design is to ensure that users in the system contribute to its welfare appropriately based on the benefit they receive; freeriding is curbed. Experience in the Gnutella & Napster networks has shown users will often freeride given the opportunity. The basic principle behind Samsara is the use of incompressible storage claims, essentially manufactured bits of data for use in an "I'll store your data if you'll store mine" scheme. Enhancements of the scheme allow forwarding of claims to balance storage requirements across the network. However, a node remains responsible for claims it forwards, so forwarding is used as a last resort. The authors implement the system on top of a Pastry network for testing purposes. Claims are generated using the sha1 hash of a passphrase known only by the host node concatenated with an on disc location. Nodes periodically query nodes for whom they are storing data for claims, if a response is invalid, that node is free to drop the stored data. A probabilistic punishment scheme is used to forgive nodes for their transient failures. A 5000 node network is simulated, showing good performance from the system. However, there are some limitations. The first is that without claim forwarding, the global storage requirement for the system is doubled. Also, the scheme is only really appropriate for a distributed file storage/replication scheme; pushing data. An adaptation for pull scenarios may be possible, but is not immediately evident. SHARP: SHARP functions as a looser form of Samsara. It is also based on the use of resource claims, however resources are extended beyond pure storage capacity and are transient. Also, claims are broken up into two parts, an advertise-able soft claim which can be redeemed for hard lease on resources in the form of a virtual machine. Asymmetric cryptography is used to ensure that claims are not forged, allowing nodes to punish one another for failing to honor claims. Also, claims are arbitrated by local authorities over nodes who function as local certificate authorities, who detect conflicting claims for resources in their local network and inform nodes redeeming claims. The system is tested on top of PlanetLab. They find that oversubscription (generating too many claims per available resources) improves network resiliency against node failure by allowing nodes to advertise their resources more aggressively. Unfortunately, they do not discuss the implementation of a reputation scheme to punish nodes overselling their resources, and seem to use local authorities as trusted brokers of claims between nodes. From ns253@cornell.edu Tue Feb 28 01:58:09 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.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 k1S6w9t01039 for ; Tue, 28 Feb 2006 01:58:09 -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 k1S6w7E7021490 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 28 Feb 2006 01:58:08 -0500 (EST) Date: Tue, 28 Feb 2006 01:58:06 -0500 From: Niranjan Sivakumar To: egs+summary@cs.cornell.edu Subject: PAPER 10 Message-Id: <20060228015806.17778139.ns253@cornell.edu> Organization: Cornell Law School X-Mailer: Sylpheed version 2.2.0 (GTK+ 2.8.12; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Niranjan Sivakumar Samsara is designed to enforce fairness in p2p systems without resorting to a centralized system or relying on third parties, thereby maintaining the decentralized nature of the network. The system is based on creating $B!H(Bclaims.$B!I(B A $B!H(Bclaim$B!I(B is created when a node in the network requests resources. The $B!H(Bclaim$B!I(B is basically setting aside the same amount of data that has been consumed. Nodes check each other to verify that the claims for the data that they are holding are being maintained. Nodes can also forward claims to $B!H(Bdownstream$B!I(B nodes; that is, nodes that are holding claims on behalf of the node that is now being asked to hold a claim. However, the node that forwards the claim maintains responsibility for the forwarded claim. The system is designed to deal with transient failures through gradated grace periods. This system makes it difficult for $B!H(Bbad$B!I(B nodes to take advantage of the grace period an! d exploit the system. Sharp is another system with a claim based system for fairness. Sharp includes some cryptographic features to protect integrity of claims through public-key encryption. Resources at a given portion of the system are controlled by a site authority. For obtaining a claim, a soft lease, called a ticket, is first obtained from an agent. This does not guarantee resources. Then, the ticket is presented to a site authority to get a hard lease, called a claim, and then will have a certain amount of resources guaranteed for a certain term. Sharp agents can issues more tickets than they can support a probabilistic claim system. The site authority is used to prevent conditions where multiple tickets could result in two nodes fighting over one claim. PPay is a system for making small, secure payments in a p2p system. The system is based off cryptographic virtual $B!H(Bcoins$B!I(B that are somewhat analogous to real world coins. The authors indicate that since this system is designed for small payments, very strong security is not necessary. Thus, rather than actually preventing coin fraud, the system simply works to make coin fraud unprofitable and traceable. The system is largely decentralized, but a broker is involved when creating or closing accounts. Karma is a system designed to incentivize resource sharing through a virtual $B!H(Bcurrency$B!I(B, Karma. Groups of nodes known as bank-sets keep track of how much karma users have. Users $B!H(Bpay$B!I(B karma to consume resources and receive karma for contributing resources. Thus more resources can only be used as more resources are provided to the system. Karma is designed to provide non-repudiation, certification, and atomicity. Public key cryptography is used for transactions in the system, but a scheme has been presented where a public-key infrastructure is not required to have valid key pairs. A number of possible attacks and defenses against them are described in the paper, including sybil attacks, denial of service attacks, and replay attacks. One issue with Samsara seems to be that while the probabilistic punishment system may be sufficient for some applications, there may certainly be applications where the owner of a node may be upset for being punished by losing some portion of their data during an honest failure. Another issues seems to be with responsibility remaining in nodes that forwards claims. This seems to create an issue where misbehaving nodes can cause those forwarding claims to be punished. The oversubscription system in Sharp seems to be quite complex, particularly adjusting oversubscription degree to maintain a target efficiency level, as is indicated in the paper, but clearly implemented. The security features of the PPay appear to limit it to small payments and do not scale well to larger payments as the incentives against coin fraud seem to be in part be based on the small value of the payments. Also, the involvement of a broker does take a system away from being totally decentralized and! p2p. Karma is theoretically interesting, but the feasibility of an implementation is not clear from the paper. From tc99@cornell.edu Tue Feb 28 02:07:05 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.3 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 k1S774t05179 for ; Tue, 28 Feb 2006 02:07: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 k1S774bG029152 for ; Tue, 28 Feb 2006 02:07:05 -0500 (EST) Received: from 24.59.114.243 by webmail.cornell.edu with HTTP; Tue, 28 Feb 2006 02:07:05 -0500 (EST) Message-ID: <8326.24.59.114.243.1141110425.squirrel@webmail.cornell.edu> Date: Tue, 28 Feb 2006 02:07:05 -0500 (EST) Subject: paper 10 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 Both SHARP and PPay utilize similar technologies to establish a accountable P2P resource trading/payment system. In both, layered cryptographic signatures are used to pass tickets/coins around. The layered signatures make it possible to trace the path of any rejected claims or other attacks to identify the malicious or faulty party. Thus, even though it is possible for users to try to abuse the system, the non-repudiation of the payment stubs makes the culprits identifiable in trivial time. A problem with this is that there is no guarantee that the system cannot be abused; merely that the culprits can be identified. However, what does that really mean? You can identify a node or user as malicious and kick them out, but what is to prevent them from re-entering the network under a different alias? PPay suggests requiring an up-front deposit, which works for micropayments that are not very valuable individually. However, neither paper really investigates the security versus performance trade-off of increased auditing to catch malicious nodes earlier. Karma differs sharply from both SHARP and PPay, which require super peers or centralized brokers to distribute tickets for certain organizations in an unspecified network overlay. Karma is designed as a layer on top a ring-based P2P network overlay, and instead of just relying on accountability based on cryptographic receipts, also tries deter fraud by appointing a BankSet to keep track of the balance of each node in the network. By relying on cryptographic puzzles to make it impractically expensive for a malicious user to try to set their own place on the ring, Karma makes it probabilistically unlikely for attackers to be able to control entire segments of the ring, unless a significant fraction of the network is invaded - in which case the network is doomed no matter what. The paper does not deal with durations of cryptographic certificates to refute false claims, but it should be relatively straightforward to extend it to include a signed timestamp. Samsara is a P2P data storage network and not a payment mechanism unlike the other papers. When a node stores data on another node, the node storing gets a claim that it can use for the other node to store data. If a node has insufficient space to store data, it can push a claim to another node that it has a claim for; however, the original is still responsible for the data. Periodically, nodes will check to make sure that the claims are being kept - ie. that the nodes they pushed data on to are still storing the data. If a node A finds out that a node B doesn't have the data anymore, A will probabalistically drop the data B is storing on A. The more consecutive checks B fails, the more data it loses. From asr32@cornell.edu Tue Feb 28 02:22:13 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.1 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 k1S7MCt08206 for ; Tue, 28 Feb 2006 02:22:13 -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 k1S7MBwq022711 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 28 Feb 2006 02:22:12 -0500 (EST) Message-Id: <6.2.1.2.2.20060223232734.02fe92c0@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Tue, 28 Feb 2006 02:22:17 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 10 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Samsara: Samsara is a system for fair disk space exchange. The basic idea is that machine A is willing to store files for machine B, provided that machine B stores a "claim" on behalf of A. This claim can later be transferred, so that B is storing files on behalf of A, in effect. If users are unavailable, their stored data is removed, on a probabilistic basis designed to differentiate short outages from permanent cheating. The system is aimed to stop greedy users, not malicious ones. This is not necessarily a weakness, depending on the target user base. These scheme, to the extent that it works, works only for storage (permanent or RAM). It has a number of shortcomings. Much of the time, one might be willing to store on behalf of others more data than one wishes to store--some users are generous, particularly if the protocol is being used on a corporate or academic intranet. Samsara does encourage such flexible policies. Sharp: Unlike Samsara, Sharp attempts to solve the general resource-exchange problem, by building very basic primitives for resource exchange. The fundamental abstraction in Sharp is the ticket, a non-binding, time-limited, agreement to supply some resource. Tickets are transferrable and divisable, and are cryptographically signed in such a way that the chain of transmission can be audited. Since tickets are non-binding, the ticket issuer can oversubscribe --and then act sensibly if presented with too many tickets. Sharp is an extremely flexible mechanism, that puts few limitations in the way of agents seeking to implement policy. The authors cite oversubscription and transferable tickets as major contributions; this seems a perilous mix. If tickets are passed through k holders, and each holder oversubscribes by a factor of r, then the total OD ratio will be r^k, which can be significantly greater than r even though no particular principal is responsible for this state of affairs; it may be wiser to bar all agents except the original ticket issuer from oversubscription. PPay: Ppay offers a micropayment scheme, suitable for purchasing resources from peer to peer networks. The system divides the world into [trusted] brokers and users, and allows users to transfer coins in a traceable way. PPay in fact offers a number of protocols, for user-user transfers, user-broker transfers, and user-user, mediated by broker. The key motivation is to push work from the broker to the owner of a coin. The PPay model has a number of tunable parameters, in particular, the fees charged by brokers for minting and reassigning coins. The marginal value of money is very different for different individuals; it seems possible that there's no set of fees that is sufficient both to allow a large user base and to ensure that nobody is prepared to run an attack. For instance, I may be willing to spend a significant amount of money to impoverish someone else. The authors simulate their system to measure load on brokers. It seems likely that this could be modelled analytically, giving precise closed-form solutions for broker load in terms of user preference distributions. Though the authors do not mention it, a protocol seems necessary to allow two users to find out if they both trust the same broker, in order to exchange coins that will be accepted. (Imagine user A trying to pay B with a coin issued by the People's Bank of Cuba). It's not clear that the authors are solving the right problem: centralized systems, such as PayPal, seem well adapted to this environment. A last pedantic point: coins are "minted", not "printed". ;) Karma: Karma is a quite general distributed resource exchange system. It only requires a secure P2P substrate, and some resource that can be represented as a byte string, and then offers secure transfers and secure balances. Using secure routing in the overlay, the Karma system is able to replicate node balances in the overlay, and then to only transfer resources when the balance is sufficient. This cleverly exploits existing work in secure routing and simultaneous-exchange: the new insight seems to be that these can be combined, with replicated nodes keeping balances. The scheme is very simple, and secure against balances being altered maliciously as well as non-payment. Karma has a few important vulnerabilities. First, since sybil attacks are possible, an attacker can dishonestly acquire significant Karma. Note that an attacker does not need a majority in any bank-set, but merely a steady drip of sybils to feed him Karma. Karma does not provide any guidance for pricing resources; such prices would presumably be determined by the amount of Karma in circulation--the average disposable income of a node. This means that a powerful attacker or group of attackers could hoard Karma to depress prices (could get a corner on Karma). The Karma is still in the system, so the inflation system will not devalue it, but the Karma won't be in circulation either. (Amusingly enough, Jay Gould tried to do this with gold in 1869.) Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From ids3@cornell.edu Tue Feb 28 09:42: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.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 k1SEfxt05664 for ; Tue, 28 Feb 2006 09:41:59 -0500 (EST) Received: from [128.253.212.208] (r253212208.resnet.cornell.edu [128.253.212.208]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1SEfwrI007585 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Tue, 28 Feb 2006 09:41:58 -0500 (EST) Message-ID: <44046134.3010907@cornell.edu> Date: Tue, 28 Feb 2006 09:41:56 -0500 From: Ivan Stoyanov User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: egs+summary@cs.cornell.edu Subject: PAPER 10 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit These papers make attempts to introduce fairness and accountability in p2p networks. They challenge the assumption that all peers willingly contribute a decent share of resourses to the global pool. Fairness is achieved by using cryptographic receipts/signatures about resources/services consumed. Karma Instead of explaining how it works, I will try to challenge the assumptions it makes about the economics of such a system. The implicit assumption made is that for a typical object in the system, there exist an equilibrium of supply/demand that is for a non-zero price (i.e. different from "free"). However, when two suppliers offer completely identical products/services, the differentiation that the customer makes is solely on price. Therefore, the "market" price of the object will converge towards the marginal cost of producing it, which in the case of digital goods, such as multimedia files, is zero. Supplier can try to offer slightly different "services" by charging more because of their higher bandwidth, but as we noticed in the previous papers, file sharing is a batch-mode system. Once an object is introduced in the system, its price will reach zero or close to zero very quickly. The smallness of the price will depend probably on the size of the object, so the system will converge in a "per megabyte" contribution scheme. If peers really wants to make Karma, they need to insert new objects, ideally popular ones. The price of a high-demand object will initially be very high, probably more than most peers can afford. Once a number of peers download it, the price will quickly spiral to zero. That is fine for most users, again, judging from the "batch-mode" usage pattern. This "market" will be segmented into a very small number of peers who introduce the new and popular objects and have very high Karma, and the rest who have little or no Karma and practically run on the same old "free" p2p network. Sharp and PPay The two systems are quite similar. They use crypto signatures to create and verify "tickets" or "coins". The signature scheme allows for non-repudiation to be introduced, that is, a consumer may deny the consumption of a resource and is not liable for purchases that cannot be proven. The archiecture uses a scheme of layered signatures so that faulty peers can be identified along the path. Unlike Karma, Sharp and PPay require super peers to do the job of centralized brokers. One problems with such approach is that a user may join under a different identity every time they want to download a certain file, similar to downloading the trial version of a product every time it expires. Since there can be guards against that, a user may alternatively simulate a number of identities and exchange dummy files between the controlled peers so that the Karma is accumulated in a single node. This Sybil attack can be made more successful if (ironically) the abusing peer pays Karma to correct peers to solve the crypto puzzles given upon system entry. From gp72@cornell.edu Tue Feb 28 11:13:21 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.3 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 k1SGDLt03697 for ; Tue, 28 Feb 2006 11:13:21 -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 k1SGDJDB016639; Tue, 28 Feb 2006 11:13:19 -0500 (EST) Received: from 128.253.122.16 by webmail.cornell.edu with HTTP; Tue, 28 Feb 2006 11:13:20 -0500 (EST) Message-ID: <3587.128.253.122.16.1141143200.squirrel@webmail.cornell.edu> Date: Tue, 28 Feb 2006 11:13:20 -0500 (EST) Subject: PAPER 10 From: "Gopal Parameswaran" To: egs+summary@cs.cornell.edu Cc: gp72@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 Samsara: This paper discuss enforcement of fairness in peer-to-peer systems to ensure that certain nodes do not share storage space in proportion to their consumption. The authors claim that since the befits of using the system accrues individually but the costs are shared certain users would have little incentive to share and contribute beyond the minimum required. Also on a secondary note many users would under report their available resources to avoid providing them to others. This would destroy the fairness balance in the system. One approach would be to use a centralized administration but that would defeat the purpose and advantages of a peer to peer system and hence instead of looking into a centralized system that would result in centralized administrative overheads the concept of claims and claim forwarding is explored where each node has to provide compensatory storage allocation space for as much storage it is consuming in the network or its neighbor nodes. Samsara is based on a symmetric distribution of storage space between two neighbouring nodes where each of the two pairs stores each others data and if one of the nodes stops storing then the other node also relinquishes the storage facility. As the authors asserts, this system has two main disadvantages, in that they assume that the nodes are reliable and the that the nodes are not subject to transient failures. A transient failure in any node would virtually wipe out the data that is being stored. This issue is corrected by using a probabilistic model for removing data from the nodes for nodes that fail at any time thus ensuring that the data is still present on some node by the time that the node comes back up. The system would punish thus nodes that are off line a lot more and these are assumed to be the cheating nodes. This model also by claim forwarding can form chains that are cyclic and thus eliminating the need for storing the claims at any node. However in the case of such cyclic chain formations the authors claim that the system can tolerate single failures though it is not that evident since if it tolerates single failures in this instance then a cheating node could take advantage of this. Addition of Nodes : When nodes are added to the network then Samara requires that each node should allocate and initialize storage space on the node by logically filling it with storage claims that can be used by another node to fill it with its data and when data is written then claims can be issued for data that is written with a claim generated being a SHA1 hash of the index of the storage location and a secret pass phrase and a symmetric key. This system of storage guarantees that no tampering of the stored data has taken place by taking a hash of the first set of data object and then using that to take the has of the second and so on till all the n objects have been hashed. This is a great method of preventing data being tampered and at the same time ensuring that bandwidth is not wasted in each query. Node failures: Samara with a probabilistic model ensures that even if there is grace period attack on the system the long term impact are nullified since in the long term such nodes would lose data. Sharp: SHARP or (Secure Highly Available Resource Peering) discusses the certified resources management in a peer to peer network for claims by using tickets and leases that allow coordinated resource management while allowing local control of resources. Although most of the focusing this paper is directed at Planet Lab this paper does provide an insight into how certificates can be used to authenticate nodes and how leases or soft state timed claims that expire after a specified period can be used to recover the resources which could get lost when a claim holder fails. Claim holders are given a probabilistic assurance regarding their claims and so that ensures the same added advantages as discussed in the Samsara model with regards to transient failures in the nodes. In Sharp the global resource trading and resource discovery is similar to Samsara in terms of pair wise barter exchange since bartering between two nodes help in removing the need of a central agreement. However since Sharp claims are self certifying the lack of a central agreement makes the system prone to attacks by malignant users who can pretend to be different nodes at different times and still use the lease timeout method to attack the system. That is because each node makes its own identification and certificate. However if the node certification is centralized or based on a centralized certificate store to ensure the validity of the nodes then this system would be more secure. Also the certificate made for each new node that enters the system should have its network card identifier or some other unique identifier stored along with certificates or have certificates generated from the net ID’s to prevent impersonation. In Sharp the resources at each site are controlled by a site authority which maintains hard states about resource status and slices and handles the claims at allocating the resources at that site. The process of the ticket and lease allocation is based on soft claims tickets and hard claims or leases to preserve local autonomy and control over resources. Leases help prevent a failed node or a compromised ticket’s value to eth duration of the ticket’s term. This concept of tickets and leases also help in delegation responsibility to the nodes and ensures that nodes that issue oversubscribed tickets are help responsible and are removed from the system and also are given a chance to restore the status in the system. Thus this system allows for control over the usage of the resources of the network. PPay: Ppay is a protocol to make micro payments in peer to peer systems and treats the idea of a secure network where financial renumeration are made and fraud prevention is done not by preventing fraud but by making it not profitable. This would be more useful in a gaming world where virtual money is used rather than for a real peer to peer application since the elimination of a centralized broker and the usage of transactions that are reconciled only a later stage would really run into issues when dealing with high valued transactions. So as the authors assert this system only works for micro payments. The system is based on transferable coins that can be transferred in a transaction and constitutes an buy or a sell in the network with a local fraud prevention built in , int the form of prevention of a duplicate transfer of a coin. However the protocol is optimistic and in case of node failures would need to wait for the node to come back up at which juncture the transaction is fulfilled or considered to be a fraudulent one and rejected or handled by the broker. This system however using the concept of floating self managed currency that is validated and reconciled when the user leaves the system or cashes in provides a stability to the system. The authors further issues the concept of limit certificates to ensure that only the broker prints the money by having the broker issue limit certificates to the nodes when they join the system. Even though this is a very interesting paper on the extension of peer to peer and its applicability to systems that need not manage small transactions they are are not really suited for any real world financial systems. Karma This paper discusses a peer to peer resource sharing network that handles the issues of nodes that consume more than they contribute by implementing a tracking mechanism where each nodes contribution and consumption is used to create a metric called karma which is used as a financial resource for each node that it needs to consume resources. A node cannot consume a resource from another node if the karma required for the object is less than the karma that he has. It implements by using local banks or banksets which are groups of nodes that keep track of the set of karma that belong to the users. Thus a local bankset controls the karma associated with the local nodes associated with the bankset. For each transfer of a resource a payment is made to the source node by the destination node and the transactions are cleared by the banksets corresponding to the two nodes. Thus it kind of creates the effects of local clearinghouses. Karma also prevents the karma of the nodes to not go out of bound by offsetting the values at end of certain epochs by reducing the values all the across the network though it is not clear how it is achieved when transactions could still be in process. Karma could however have the same potential issues that all the other papers discussed above have, that is since initally every node is given a certain karma, a set of malicious nodes where one node acts as a contributer and a set of other nodes consume from it and re-enter the system every time to claim the initial karma and again claim from the contributer node. Thus the karma of the contributor node could be made to increase. From kelvinso@gmail.com Tue Feb 28 12:09:16 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 wproxy.gmail.com (wproxy.gmail.com [64.233.184.195] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1SH9Ft20441 for ; Tue, 28 Feb 2006 12:09:16 -0500 (EST) Received: by wproxy.gmail.com with SMTP id i4so177539wra for ; Tue, 28 Feb 2006 09:09:15 -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=RULAy1UIgIvLKtWV6+hf/IQ6ppThO0OYpF7AIB5KlO8awD0bsl4gLQC3YO0Qc5IMP3ldQDl5Hmx4FEidLRIXwTUHvhCw4B4RZUbsI6dSwnPVqf6+UXHWXKoVGwZsTzXVVUdX6EmzA7hYn3RBec4dDfVt2+MjA/kE6j+iXXbbX50= Received: by 10.54.119.5 with SMTP id r5mr814412wrc; Tue, 28 Feb 2006 09:09:14 -0800 (PST) Received: by 10.54.81.5 with HTTP; Tue, 28 Feb 2006 09:09:14 -0800 (PST) Message-ID: <6e1ca4560602280909r4e20a1b1w3133974a81efa66b@mail.gmail.com> Date: Tue, 28 Feb 2006 12:09:14 -0500 From: "Chiu Wah Kelvin So" To: egs+summary@cs.cornell.edu Subject: Paper 10 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 k1SH9Ft20441 The first paper, "Samsara: Honor Among Thieves in Peer-to-Peer Storage," presents an infrastructure for symmetric storage exchange between peers. Samsara requires each peer to contribute the same amount of storage when it stores object in other peers. When a node A stores an object in other node B, B needs to store a storage claim in node A, which is incompressible placeholder for storage for resource exchange. Node B periodically checks if the storage claim is still stored on Node A. To reduce the redundant storage needed for storage claim, a node simply forwards the query to another node which holds the storage claim. To distinguished dishonest nodes and nodes with transient failure, node deletes replicas with a probability proportional to the number of consecutive failed query. Therefore, nodes which suffer transient failures can recover replicas from surviving copies in the system. One problem with Samara is that it does not deal with malicious nodes. If a node forwards the query to a malicious node, it may break the claim forwarding and cause object deleted. Nodes with very short session time will have to constantly waste bandwidth to replicate object because of the probability deletion of objects due to transient failure. Also, this paper only presents a solution in very limited problem which is symmetry storage exchange. In the next paper, it attacks a more general problem. The second paper, "SHARP: An Architecture for Secure Resource Peering," presents an architecture for exchanging various resources, such as CPU, memory, instead of just exchanging storage. The three main components in SHARP are site authority, service manager, and agent. A service manager first requests resource from an agent, and then agent will grant resource in form of a ticket which is a soft claim that suggests but does not guarantee resource ownership. Ticket can be delegated to other peer. Service manager will then presents the tickets to the site authority to redeem resources. If the resource is granted by site authority, then it will issue a lease for the resources. This architecture allows site has direct control over resource. At the same time, it uses agent as a level of indirection to coordinate resources management. Also, agent is allowed to oversubscribe resource claims to balance a higher overall resource utilization and number of rejected tickets (because of oversubscribe). However, paper assumes sites are trusted and not malicious. The third paper, "PPay: Micropayments for Peer-to-Peer Systems," present an efficient micropayment protocol. In existing micropayment protocol, the broken usually has a load O(n), where n is the total number of transaction made. PPay uses a concept of floating, and self managed currency to greatly reduce broker load to O(m), where m is the number of coins in the system. Broker B issues coin to a user U (owner of the coin). When a user U pays the coin to other user V, user U will have to sign the coin and send it to V. Whenever V needs to pay other user, V will need to send the coin back to U such that it can reassign to other user. Therefore, broker will not involve in any activity of coins, except the initial assignment and cash out of coins, or when owner becomes offline. This approach leaves traces of invalid coin assignment. Therefore, broker can find out who are the malicious users. However, all the coins have the same value in the system. If the value of resources in the systems are greatly varies, user may need to reassign a lot of coins for buying a single expensive resource, and it is inefficient. The forth paper, "KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing," present a framework on top of DHT to keep track of account of users. Each user will have a bank-set, which is a set of nodes in DHT, to keep track of its current balance of the user. The balance of a user can only be determined by the majority of the nodes in bank-set, so Karma will have an accurate balance of users even the existence of malicious nodes in DHT. Instead of using consensus protocol during transaction between two bank-set for strong consistency, Karma allows temporary inconsistencies in the account balances of users to achieve better performance. Also, Karma periodically recomputes the outstanding account balance to avoid inflation and deflation caused by node joining and leaving the network. However, if there is churn in the system, the recomputed account balance may vary a lot depended on the size of the system at the moment. Kelvin So From km266@cornell.edu Tue Feb 28 12:14:40 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=0.9 required=5.0 tests=AWL,BAYES_00, FORGED_OUTLOOK_TAGS,HTML_10_20,HTML_MESSAGE autolearn=no 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 k1SHEet21952 for ; Tue, 28 Feb 2006 12:14:40 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-68.twcny.res.rr.com [69.207.37.68]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k1SHEdV5004862 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Tue, 28 Feb 2006 12:14:39 -0500 (EST) Message-ID: <000601c63c8a$7ff2a680$4425cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 10 Date: Tue, 28 Feb 2006 12:14:53 -0500 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_0003_01C63C60.94CD5750" 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 This is a multi-part message in MIME format. ------=_NextPart_000_0003_01C63C60.94CD5750 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Samsara is a p2p file storage system that allows you to store x amount = of data on the network in exchange for allowing others to store x data = at your node. The main idea behind Samsara is that storage is not = necessarily symmetric, but that it can artificially be made symmetric by = allowing "claims." Consider two nodes, A and B. A wants to store = something on B and in exchange for this, A sets aside storage space on = itself for B. For B to ensure that A actually does this, it composes a = block of data equal to the size that A allocates for it and then = periodically checks to make sure that A is not cheating. If A is = cheating then there is a chance that B will drop part of A's data on the = floor. This is claimed to not be a serious issue because the = probability is small, especially with replicated data. If C wants to = store something on A then A can give C B's claim while storing C's = actual data. In this way, if B ever asks A to validate the claim, A can = pass this request on to C. The more files in the system, the fewer = claims are needed but the longer the claim chain might end up being. There seems to be numerous attacks on this system. The first, which = the authors mention, is having a node only store claims. This is = advantageous because the node then only gets pinged once in a while to = make sure it is actually storing something, thereby reducing its = bandwidth. The amount of data that is being transferred between nodes = is huge, 32GB in most of their examples. With this much storage, there = is a large incentive to try and crack the key used to generate claims. = Once this key is cracked (which might take a long time, months even) = then you can effectively reduce storage from 32GB to practically = nothing. The incentive is there because of the massive storage overhead = drop. Once a node cracks one hash, it can then try again with = another...once a node amasses several of these, it can have hundreds of = gigabytes of storage set aside for less than a megabyte of local = storage. Furthermore, malicious nodes can be very problematic. If you = forward a claim to a node that drops it on the ground, you are punished. = If you do this several times, your data (or at least part of it) is as = good as gone. SHARP talks about generic resource sharing (not necessarily storage as = in the previous paper) and how resources can be divided between sites = and domains. A node can get a claim to resources from another node = (which may deny this claim later on). The analogy the paper makes is an = airplane ticket: the airline promises a seat to you, but if the flight = is oversold then they might deny you boarding permission when you go to = claim your ticket. These claims are unforgeable, therefore not allowing = you to print up a fake 'boarding pass.' To get resources, a service = manager gets the site authority to give it a claim (gets the boarding = pass). Then the manager tries to claim the claim for a hard-state = claim...basically handing in the boarding pass and then the flight crew = lets you onto the plane. A hard-state claim says that resources WILL be = given to you. Claims are transferable (unlike airline tickets) and/or = tradable. The core of SHARP seems to be almost contradictory. The hope is get = rid of a central agency that you trust and that must endure all of the = work. To do this, they use authorities which still need to be = authenticated. Having lots of these authorities is similar to having a = server farm, or lots of very trustworthy peers. PPay (PeerPay) is a micropayment system which tries to get rid of broker = load. The paper says that all current micropayment systems are O(n) in = the broker, where n is the number of transactions. The basic principle = is that brokers are overburdened in current systems while peers have = little work to do. This does not scale well (as the number of peers = increases and the broker stays constant). To help alleviate this, peers = become responsible for the 'coins' that they are issued by the broker. = Peers can always turn their coins into the broker (therefore making the = system O(n) again), but there is a fee to discourage such behavior. The = broker, therefore, is only involved when issuing new coins (or ranges of = coins, therefore reducing load even more) and when old coins come back = to be cashed. It is also occasionally used for arbitration purposes and = for helping nodes deal with offline peers. A peer owns a coin and that = can be spent by increasing the 'sequence number' and then signing it = over to the new node. This new node can prove that it has the current = coin by showing that it has a higher sequence number. The new node can = then use this coin and sends a reassignment request over to the current = owner of the node who sends the buyer a new assignment. Using several = lemmas, the authors showed that this system is secure. In the end, this system seems like it has too many loopholes. The = authors constantly stress that micropayments might not need high = security because of the small amount of money actually being = transferred. It seems easy for the owner of a node to spend a coin = several times. Once a coin is cashed, his scheme will be found out and = then he can be punished somehow. However, he can be offline then or = have given the broker a fake identity or another of other situations can = arise. It seems like if the amount of money that is being dealt with is = truly small then it might not be worth a person's time to do this...but = 'a small amount of money' is relative, especially when dealing with a = worldwide economy (imagine a person in a 3rd world country with a failed = economy, even micropayments may seem like a lot). The symmetric = picopayment system they introduced (if actually dealing with = picopayments) seems like it would work well for non-monetary systems or = with truly fractionally tiny payments. Karma is similar to PPay, but deals with non-real-money economics. It = has a super-node type setup where there are a set of nodes in the system = that keeps track of the level of karma in the system. If you wanted to = take over the system, you would have to take over the bank-set = (super-nodes). The bank set keeps track of individual users' Karma, = increasing or decreasing it depending on how many resources they give or = take. This is to prevent freeloading in modern p2p systems. Nodes = transfer part of their Karma to other nodes who then provide files or = other resources in exchange. Bank sets verify that the requesting node = has enough Karma to give. Signatures and other security methods are = engaged to prevent nodes from cheating. ------=_NextPart_000_0003_01C63C60.94CD5750 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Samsara is a p2p file storage system = that allows=20 you to store x amount of data on the network in exchange for allowing = others to=20 store x data at your node.  The main idea behind Samsara is that = storage is=20 not necessarily symmetric, but that it can artificially be made = symmetric by=20 allowing "claims."  Consider two nodes, A and B.  A wants to = store=20 something on B and in exchange for this, A sets aside storage space on = itself=20 for B.  For B to ensure that A actually does this, it composes a = block of=20 data equal to the size that A allocates for it and then periodically = checks to=20 make sure that A is not cheating.  If A is cheating then there is a = chance=20 that B will drop part of A's data on the floor.  This is claimed to = not be=20 a serious issue because the probability is small, especially with = replicated=20 data.  If C wants to store something on A then A can give C B's = claim while=20 storing C's actual data.  In this way, if B ever asks A to validate = the=20 claim, A can pass this request on to C.  The more files in the = system, the=20 fewer claims are needed but the longer the claim chain might end up=20 being.
    There seems to be = numerous=20 attacks on this system.  The first, which the authors mention, is = having a=20 node only store claims.  This is advantageous because the node then = only=20 gets pinged once in a while to make sure it is actually storing = something,=20 thereby reducing its bandwidth.  The amount of data that is being=20 transferred between nodes is huge, 32GB in most of their examples.  = With=20 this much storage, there is a large incentive to try and crack the key = used to=20 generate claims.  Once this key is cracked (which might take a long = time,=20 months even) then you can effectively reduce storage from 32GB to = practically=20 nothing.  The incentive is there because of the massive storage = overhead=20 drop.  Once a node cracks one hash, it can then try again with=20 another...once a node amasses several of these, it can have hundreds of=20 gigabytes of storage set aside for less than a megabyte of local=20 storage.  Furthermore, malicious nodes can be very = problematic.  If=20 you forward a claim to a node that drops it on the ground, you are=20 punished.  If you do this several times, your data (or at least = part of it)=20 is as good as gone.
 
SHARP talks about generic resource = sharing (not=20 necessarily storage as in the previous paper) and how resources can be = divided=20 between sites and domains.  A node can get a claim to resources = from=20 another node (which may deny this claim later on).  The analogy the = paper=20 makes is an airplane ticket: the airline promises a seat to you, but if = the=20 flight is oversold then they might deny you boarding permission when you = go to=20 claim your ticket.  These claims are unforgeable, therefore not = allowing=20 you to print up a fake 'boarding pass.'  To get resources, a = service=20 manager gets the site authority to give it a claim (gets the boarding=20 pass).  Then the manager tries to claim the claim for a hard-state=20 claim...basically handing in the boarding pass and then the flight crew = lets you=20 onto the plane.  A hard-state claim says that resources WILL be = given to=20 you.  Claims are transferable (unlike airline tickets) and/or=20 tradable.
    The core of SHARP = seems to be=20 almost contradictory.  The hope is get rid of a central agency that = you=20 trust and that must endure all of the work.  To do this, they use=20 authorities which still need to be authenticated.  Having lots of = these=20 authorities is similar to having a server farm, or lots of very = trustworthy=20 peers.
 
PPay (PeerPay) is a micropayment system = which tries=20 to get rid of broker load.  The paper says that all current = micropayment=20 systems are O(n) in the broker, where n is the number of = transactions.  The=20 basic principle is that brokers are overburdened in current systems = while peers=20 have little work to do.  This does not scale well (as the number of = peers=20 increases and the broker stays constant).  To help alleviate this, = peers=20 become responsible for the 'coins' that they are issued by the = broker. =20 Peers can always turn their coins into the broker (therefore making the = system=20 O(n) again), but there is a fee to discourage such behavior.  The = broker,=20 therefore, is only involved when issuing new coins (or ranges of = coins,=20 therefore reducing load even more) and when old coins come back to be=20 cashed.  It is also occasionally used for arbitration purposes and = for=20 helping nodes deal with offline peers.  A peer owns a coin and that = can be=20 spent by increasing the 'sequence number' and then signing it over to = the new=20 node.  This new node can prove that it has the current coin by = showing that=20 it has a higher sequence number.  The new node can then use this = coin and=20 sends a reassignment request over to the current owner of the node who = sends the=20 buyer a new assignment.  Using several lemmas, the authors showed = that this=20 system is secure.
    In the end, this = system seems=20 like it has too many loopholes.  The authors constantly stress that = micropayments might not need high security because of the small amount = of money=20 actually being transferred.  It seems easy for the owner of a node = to spend=20 a coin several times.  Once a coin is cashed, his scheme will be = found out=20 and then he can be punished somehow.  However, he can be offline = then or=20 have given the broker a fake identity or another of other situations can = arise.  It seems like if the amount of money that is being dealt = with is=20 truly small then it might not be worth a person's time to do this...but = 'a small=20 amount of money' is relative, especially when dealing with a worldwide = economy=20 (imagine a person in a 3rd world country with a failed economy, even=20 micropayments may seem like a lot).  The symmetric picopayment = system they=20 introduced (if actually dealing with picopayments) seems like it would = work well=20 for non-monetary systems or with truly fractionally tiny = payments.
 
Karma is similar to PPay, but deals = with=20 non-real-money economics.  It has a super-node type setup where = there are a=20 set of nodes in the system that keeps track of the level of karma in the = system.  If you wanted to take over the system, you would have to = take over=20 the bank-set (super-nodes).  The bank set keeps track of individual = users'=20 Karma, increasing or decreasing it depending on how many resources they = give or=20 take.  This is to prevent freeloading in modern p2p systems.  = Nodes=20 transfer part of their Karma to other nodes who then provide files or = other=20 resources in exchange.  Bank sets verify that the requesting node = has=20 enough Karma to give.  Signatures and other security methods are = engaged to=20 prevent nodes from cheating.
------=_NextPart_000_0003_01C63C60.94CD5750-- From asg46@cornell.edu Tue Feb 28 12:22:12 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.3 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 k1SHMBt23874 for ; Tue, 28 Feb 2006 12:22: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 k1SHM9SS003679 for ; Tue, 28 Feb 2006 12:22:09 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Tue, 28 Feb 2006 12:22:10 -0500 (EST) Message-ID: <2742.128.84.98.90.1141147330.squirrel@webmail.cornell.edu> Date: Tue, 28 Feb 2006 12:22:10 -0500 (EST) Subject: paper 10 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 P-PAY deals with a secure micropayment mechanism. A broker is used to handle accounts, distribute and cash coins, provide security etc. Thus, the load on a broker is usually heavy and it also serves as a single point of failure and attack. The authors reasonably claim that utmost security is not required and that the payment mechanism must be lightweight so that the cost of the scheme will be less than the value of the payment. the main disincentive for cheating is that the user will not be able to carry out buisness in the future due to bad credit. in order to minimise broker involvement: 1) cashing coins involves a flat fee 2) when a coin has to be reassigned in the case that the owner is not present/or pretends to be absent, the holder and the owner will both be charged a small fee. users require a credit card to join the system which seems like a bad idea. it further raises concerns about user anonymity. SECURITY: all coins are signed by private keys. this enables detection of frauds such as replication,wrongful denial and double spending. COIN RENEWAL : to limit the amount of state kept by a peer, the coin must be renewed during a certain time. note that the worst case time to detect any fraud is equal to the renewal period. Thus the value of this time imposes a tradeoff between broker involvement and fraud-detection time. it also discusses "pico-payments" for small items such as message forwarding or answering queries. KARMA karma represents a scalar value that represents the overall standing of each participant. For each node, a set of k nodes called bankset, keep track of the node's karma increasing it when resources are contributed and decreasing it when resources are consumed. the karma is signed by the node's private key to make it tamper resistant. the bank-set also stores the epoch number which along with other parameters indicates the adjustments made so that the per-capita income is roughly constant. However, each node must be aware of any node joining or leaving the system to compute the correction factor which seems burdensome. the amount of karma for each object is selecting by an auction scheme. each node is assigned an id beyond its control which is based on solving a cryptographic puzzle result which results in a secure entry algorithm preventing sybil attacks. it is based on a assumption that on the whole all objects are consumed in an equal fashion - i.e. the number of downloads for each object per node remains roughly the same. It could be the case that a node shares unpopular objects and as a result its karma does not increase. We can also look at it from another point and argue that it forces nodes to share popular objects so as to increase their karma. In either case, the diversity of system-wide objects decreases. A user may also suffer due to routing policies which do not balance load. SHARP provides a framework for a secure distributed resource management. goals of such a system: 1) reservation of resources 2) prevent stealing of resources held by others 3) admission control 4) balance global resource sharing with local autonomy 5) it must be robust - protect resource availability 6) secure STRUCTURE : Multiple resource managers control different ,possibly overlapping, regions of the global resource pool. it uses the notion of a soft-state claim called a ticket that expires after a certain period so that the system can recover the resources if a claim holder fails. The ticket is presented to the site authority which may reject the ticket or honor it by issusing a lease for any subset of the resources or the term specified on the ticket. All claims are cryptographically signed to make them unforgeable and non-repudiable. oversubscribed claims: they improve resource utilisation but at the same time the probability that a site authority will honor the oversubscribed ticket decreases the with the increase in oversubscription degree. confinement problem : SHARP allows owners of the resource only a bounded amount of time for carelessly certifying some malicious entity access to the resource. The choice of a claim duration represents a tradeoff between agility,robustness and renewal overhead. SAMSARA enforces fairness in a P2P storage system without requiring trusted third parties, symmetric storage relationships, monetary payments or certified identities. it introduces the notion of a storage claim - incompressible placeholders for storage. one node is responsible for issuing those rights while another is responsible for consuming them.A node is responsible for the claims it has forwarded. Thus, nodes would prefer not to forward claims whenever possible. To allow honest nodes to recover from transient failures, a grace period is allowed for responding to queries. however, this leads to an attack whereyby malicious nodes do not store anything but choose replicas only for the grace period, selecting new ones as the period expires. The authors suggest a scheme where failures are exponentially more harmful for consecutive failed queries in order to protect honest nodes. However, the attack above still exists. the nodes also negotitate a Diffe-Hellman key during initial exchange that is subject to man-in-the-middle attacks. sybil attacks do not offer advantages as forwarding a claim yields no advantages. forwarding claims weaken data reliabilty unless a cycle is created whereby data reliablity is restored. the authors also indicate that this placeholders approach would not work for renewable resources such as bandwidth and processor cycles. From victoria@cs.hmc.edu Tue Feb 28 12:38:25 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.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from turing.cs.hmc.edu (turing.cs.hmc.edu [134.173.42.99]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1SHcOt28711 for ; Tue, 28 Feb 2006 12:38:25 -0500 (EST) Received: by turing.cs.hmc.edu (Postfix, from userid 34382) id E34EF5327E; Tue, 28 Feb 2006 09:38:18 -0800 (PST) Date: Tue, 28 Feb 2006 09:38:15 -0800 From: Victoria Krafft To: egs+summary@cs.cornell.edu Subject: PAPER 10 Message-ID: <20060228173815.GA14542@cs.hmc.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i These papers explore solutions to the free rider problem. The networks we have examined so far do not have any way to require peers which use the network to contribute resources to it, and studies have shown that a noticeable portion of the people using a network do not contribute to it. These papers present four different systems which attempt to address this problem; Samsara, PPay, Sharp, and Karma. Samsara is designed to enforce fairness in a peer-to-peer storage system. It does this by requiring that each time peer A stores a file on peer B, peer B is given a claim to an equal amount of space on peer A. After this exchange takes place, A+B both check up on each other, to ensure faithfulness. In order to avoid having a large overhead in claimed but unused storage space, claims can be chained together. That is, if A has a claim on B, and B has a claim on C, B can use its claim on C to satisfy A's claim. However, if C fails or cheats, then B is held responsible. When a node fails, it is punished in a probabilistic fashion. This allows for nodes experiencing transient failures to recover, but their data will probably be removed if the node fails for too long. This does not fix the problems of malicious nodes, or nodes which will refuse to transfer all of the data back when the person who stored the data wants to recover it. In light of the cost of uploading large amounts of data, especially with DSL with slow upload speeds, or traffic shapers, it would be possible for a peer to store data and respond to queries, and only fail when someone attempts to upload a lot of data from it. PPay addresses this problem from a different angle, proposing the idea of a micropayment system, where each peer must pay a small amount for each download. PPay offers a scheme for floating currency, so a broker only needs to be involved to create and delete accounts, and redeem the currency. The requirement that each person using the network have an account with the broker creates a serious problem for many networks, however. Networks which wish to provide a level of anonymity for their users will not be able to do so under this scheme; A could prove that B was part of the network, and the records at the broker will provide B's identity. Sharp is a resource management system which uses the concept of claims from Samsara, but extends them so claims can represent any resource, and can be signed over to a third party. They avoid a centralized server by having each site sign the claims for its resources, giving us self-certifying resource claims. They also demonstrate how individual sites can work together to form an economy, trading resource claims and managing the available resources in a secure fashion. A large scale prototype of this system has been run successfully on PlanetLab. Karma is a system which keeps track of resource consumption and contribution in a peer-to-peer network. For each node, this is represented by a single scalar value, called the node's karma. The karma which each user has is tracked by a group of nodes, called a bank set, and each transaction in the network is counted as it occurs. Every so often, the karma values are re-scaled to prevent inflation or deflation of karma. The Karma protocols rely on the assumption that no more than a fraction of the nodes in the system are malicious; a system running it could still be vulnerable to Sibyl attacks. Also, since each node starts out with some initial karma, a node could simply join, use that karma up, quit, and then re-join with a new identity. The potential damage done by a single node is limited by requiring each node to solve a cryptographic puzzle to join, but this is still a cause for concern. Also, I'm curious how much overhead the Karma system generates; each transaction now requires action on the part of the entire bank set, rather than just the two nodes engaging in the transaction, and the nodes on the path between them. -- Victoria Krafft From xthemage@mac.com Tue Feb 28 12:57: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=-0.9 required=5.0 tests=BAYES_00,DNS_FROM_RFC_POST autolearn=no version=3.1.0 X-Spam-Level: Received: from smtpout.mac.com (smtpout.mac.com [17.250.248.73] (may be forged)) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k1SHvPt04158 for ; Tue, 28 Feb 2006 12:57:25 -0500 (EST) Received: from mac.com (smtpin02-en2 [10.13.10.147]) by smtpout.mac.com (Xserve/8.12.11/smtpout16/MantshX 4.0) with ESMTP id k1SHvOBJ012388 for ; Tue, 28 Feb 2006 09:57:24 -0800 (PST) Received: from [128.84.98.36] (dhcp98-36.cs.cornell.edu [128.84.98.36]) (authenticated bits=0) by mac.com (Xserve/smtpin02/MantshX 4.0) with ESMTP id k1SHvM5f023880 for ; Tue, 28 Feb 2006 09:57:24 -0800 (PST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Oliver Kennedy Subject: PAPER 10 Date: Tue, 28 Feb 2006 12:57:41 -0500 X-Mailer: Apple Mail (2.746.2) Most P2P applications we've studied up to this point involve hosts contributing resources to the system, and generally assume that hosts will contribute as much as they consume. This assumption cannot be held in many cases. This week's papers explore ways of ensuring fairness in P2P exchanges. Note that few P2P systems directly exchange data; node 1 may provide resources to node 2 while node 2 provides resources to 3 and 4. The assumption is that if each node contributes as much as it uses, the system remains stable. Karma is one approach to this problem. Using a typical ring-based DHT, Karma maps each node to a set of "bank nodes." A node joining the system obtains a certain amount of karma. Every time a transaction is performed, the consumer provides the producer with a signed receipt. The consumer's account is charged, and the producer's account is credited. In order to combat inflation or deflation, all balances are normalized over the entire system periodically (over a large period). This scheme suffers from several major problems. Firstly, a client may repeatedly create accounts (the Sybil attack the paper mentions). Since each host is given some initial karma, a host may use multiple host creations to boost its balance. The proposal to use cryptographic puzzles to limit the rate of entry is weak, as processor time may not be the limiting resource. Regardless of implementation, this scheme is also weak to either malicious consumers or malicious providers. Karma has no notion of simultaneous trade, so ultimately the consumer will need to trust the producer (or visa versa). This single point of trust allows a malicious host to cheat another out of karma or services. Samsara takes a slightly different approach. Rather than trying to force a capitalistic model onto a system which doesn't support it, Samsara ensures that it is in each host's best interest to be fair. In this system, hosts exchange blocks of data between themselves (to build a distributed backup service in their example). They periodically check to see if the hosts are storing the data appropriately. Because one host may wish to send blocks to another host which does not need the favor returned, the second host instead sends back a "claim" block. This block is deterministically generated in secure manner so that it takes up no space on the second host, but requires the first host to store it. Samsara notes that in a fair P2P network, service dependency rings are established. Host A serves B who serves C who serves D who serves A. It makes use of this by allowing a host to transfer a claim to a host that it provides a service for. In this example, B stores a claim for A, but it may transfer the claim to C. When A asks B to verify that it still holds the claim, B forwards the request to C. This makes B reliant on C, but C is already reliant on B for service. If one of the periodic validations fail, the host stops providing service with some probability. Since each host stores multiple replicas of their data, transient errors only provide a minor disruption. Consistent leeches on the other hand will not be able to obtain service for any extended time period. Samsara has two major failures. Firstly, it is intricately tied to persistent storage as the measure of service. No clear mapping exists to allow Samsara to mediate processor or network load. Secondly, they note that the periodic verification takes up a non-negligible amount of network bandwidth. They dismiss this by verifying on the day-week scale. This approach may not scale well to a large distributed service such as gnutella where sessions take place over less than an hour. Sharp is a midpoint between these two ideas. Servers (or more generally agents functioning on behalf of servers) create a form of currency via signed promises to devote resources over a specified time period. These promises can be exchanged as currency, subdivided and redistributed. Duplicates can also be made, since the promises are probabilistic in nature. These probabilistic promises are exchanged at the source of the service for hard guarantees of service or a failure message along with a complete chain of promises that identify a single entity as the culprit. Sharp builds in a little bit of overbooking to ensure that loads are kept up in the case of client failure, but excessive amounts of overbooking can easily be traced and the culprits dealt with. Sharp's main flaw is that it requires that each identity be traceable back to a real world entity. Failing that, it is extremely vulnerable to Sybil attacks. Moreover, while ticket falsification may be traced to a particular identity, the model assumes secure service providers, and thus the model maps poorly to a more generic one such as gnutella; a malicious service provider can make itself indistinguishable from a faulty one. -Oliver Kennedy Cogito cogito ergo cogito sum -- "I think that I think, therefore I think that I am." -- Ambrose Bierce, "The Devil's Dictionary"