Building robust P2P systems w/ selfish or malicious peers jinyang@cs.nyu.edu Cooperation (nodes obey protocols, i.e. do not change the programs) Cooperation cannot be assumed when * nodes are controlled by people with different interests * especially difficult if people do not know each other You cannot assume that users naively run the p2p software * they do not run it; what are their benefits from contributing their b/w and storage? * they can modify software * close applications; unplug computers * rate limit applications etc. Case study: file sharing applications (it's a game, sort of) * what's the incentive for peer nodes to join the system? Users want to download files * what do selfish users want? download from, but not upload to others but if everybody is behaving this way, nobody can download anything from system. Prisoner's dilemma from Classic game theory Prisoners A and B decide by themselves whether to cooperate or defect C D C (3,3) (0,5) D (5,0) (0,0) The best strategy is to defect, hence globably an all-defect strategy is suboptimal. What's the best strategy if we can play the game multiple times with a player? "Tit-for-tat": Cooperate the first round, do what your opponent did in the previous round "Tit-for-tat with forgiveness": Occasionally cooperate to try to end a long run of retaliation and counter-retaliation Exchanging data with a peer node is similar to an iterated PD: Break the data exchange to rounds; if remote peer does not upload fast enough (defect), choke his connection (play defect) BT: * One tracker for each file who keeps track of nodes interesting in downloading the file (a swarm). * A big file is broken into pieces identified by SHA-1 hash. * Nodes learn SHA-1 hashes of all piece from the tracker upon join. * Nodes learn a random subset of 50 or so peers from the tracker and connect to them. * Nodes aim to find and maintain a small fixed active subset of connections with good download rates. * Every 10 seconds (round), calculate download rate from existing connections, if not satisfactory, choke them. * BT periodically chooses one random connection for optimistic unchoking - Forgiveness (Beginner might have nothing to upload) - Explore a new player Is BT's tit-for-tat strategy perfect? How is it different from tit-for-tat in iterated PD? * Exchange is not completely fair Nodes have different capacity A node w/ high capacity might not be able to find a fixed small subset of others that can match its download rate. * Node population is big; so a selfish node need not play an iterated PD with one fixed player, instead, he can choose to play one round PD w/ many different players. ---> abuse others' optimistic unchoke BAR Gossip Tit-for-tat from a central policeman Make every exchange fair and discourage a node from deviating from the protocol by sending a proof-of-misbehaviors (POMs) to the central "policeman" Slightly different goals than BT: - BT: encourage nodes to upload at full capacity by correlating upload and download rates. Faster nodes finish sooner - BAR Gossip: live streaming Encourage fair exchange during gossip Policeman introduces accountability in the system by assigning nodes public/private keys. Policeman diseeminates complete membership info to all nodes and eviction notices to all nodes. Protocol proceeds in loosely synchronized rounds. Exchange equal amount of encrypted data (briefcase) first (most bandwidth consuming) and exchange keys later. If keys do not match contents in briefcase, a POM is generated and node is evicted. Reduce the risk that selfish nodes leech on optimistic push(optimistic unchoke) by converting it to a fair exchange; nodes w/ no valid data to exchange may send b/w costing junk Better than BT's optimistic unchoke? (Why shall a node be willing to initiate in optimistic push?) How to prevent a node from not choosing fair exchange partners randomly? - pseudorandom partner selection so the selected partner node can verify that indeed he's a random choice Discussions: * tit-for-tat is for protocols where any pair of players have many rounds of encounter - each round has the same payoff matrix. (the utility is the same for all rounds) * Not all applications are like played like iterated PD - different payoff matrix that might change over time. * It's much easier if one has a central trusted policeman (the broadcaster) - limits players' selfish strategies. - let all agree on the set of good players. Defending against malicious nodes: Malicious (Byzantine) nodes: - goal is to bring maximum harm to the rest - may also behave randomly and unpredictably Byzantine Generals problem: impossible to achieve agreement if more than 1/3 nodes are malicious In traditional replicated state machine distributed systems, agreement is critical. Many times nodes (users) do not cast/collect votes for agreements, but for weaker properties such as * gauge an object (or node)'s goodness * eBay users can vote for buyer/seller's repuation * Google PageRank considers a hyperlink from page A to page B as A voting for B. * news site digg allows users to vote for online blog/news articles Who can vote? * eBay, Digg: any registered users * Sybil attack: a single attacker controls many identities in the system; hence increase its voting influence * how to ensure voters are humans? * how to ensure one person one identity? (Credence: a central certificate authority issues identities to nodes slowly) How are votes to be used? Are individual votes easily verifiable? * Vote on the subjective quality of an object (voice one's opinion) Popular (interesting) files vs. non-interesting ones; (popular things are likely to be good) Good seller vs. bad ones. In contrast, * In Credence, votes are rather objective. Corrupt/decoy files vs. genuine ones (compared to BT; BT does not solve the search problem) Whether a file is purely garbage; or more specificially, if a keyword is relevant to a given file(?) Honest users are likely to vote similarly. --> Each Credence node weights each peer's vote with its past voting history. The most likely a peer votes as me, the more weight I give to it. How to account for peers whose voting history I do not know? - Learn about their weights from peers whose weight I already know and are pretty good. - The final weight is a product of weights of the path from peers I know to that unknown peer.