From flud


Peer-to-Peer Backup

PeerStore: Better Performance by Relaxing in Peer-to-Peer Backup
 author    = {Martin Landers and
              Han Zhang and
              Kian-Lee Tan},
 title     = {PeerStore: Better Performance by Relaxing in Peer-to-Peer
 booktitle = {Peer-to-Peer Computing},
 year      = {2004},
 pages     = {72-79},
 ee        = {},
 crossref  = {DBLP:conf/p2p/2004},
 bibsource = {DBLP,}
 title     = {4th International Conference on Peer-to-Peer Computing (P2P
              2004), 15-17 August 2004, Zurich, Switzerland},
 booktitle = {Peer-to-Peer Computing},
 publisher = {IEEE Computer Society},
 year      = {2004},
 isbn      = {0-7695-2156-8},
 bibsource = {DBLP,}
Samsara: Honor Among Thieves in Peer-to-Peer Storage
@misc{ cox03samsara,
 author = "L. Cox and B. Noble",
 title = "Samsara: Honor Among Thieves in Peer-to-Peer Storage",
 text = "Landon Cox and Brian Noble. Samsara: Honor Among Thieves in Peer-to-Peer
   Storage. In Proceedings of the ACM Symposium on Operating Systems Principles,
   October 2003.",
 year = "2003",
 url = ""

One of the most complete p2p backup papers yet published. The use of 'claims' to ensure symmetric storage trades is clever and very useful. Nice performance analysis and discussion of limitations. Samsara builds on Pastiche, which used a Pastry overlay to do joins.

Claims in flud are similar to those in Samsara, but can use Kr instead of a secret passphrase P. Thus, the claims in flud are constructed as h0 = sha256(Kr,0),... hi = sha256(Kr,i).

Samsara uses replicas instead of coding, and thus has to salt each replica to prevent cheating. Although this is only a minor disadvantage in Samsara, flud avoids it completely.

Claim forwarding is one of the trickiest problems in Samsara, so the system avoids it as often as possible. In flud, we don't plan on implementing claim forwarding at all.

ABS: The Apportioned Backup System
 title = {"ABS: The Apportioned Backup System"}, 
 author = {Joe Cooley and Chris Taylor and Alen Peacock}, 
 institution = {Massachusetts Institute of Technology}, 
 year = {2004}, 
 month = {February}, 
 address = {Cambridge, Massachuesetts}, 
 www_section = {Decentralized Backup}, 
 www_pdf_url = { }, 

Although the flud design has diverged significantly from ABS, it can be considered as flud's predecessor. Ludovic Courtes has a nice summary of the work.

Hydra: A Platform for Survivable and Secure Data Storage Systems
 author = "Lihao Xu",
 institution = "Department of Computer Science, Wayne State University, USA",
 title = "Hydra{\char58} A Platform for Survivable and Secure Data Storage Systems",
 booktitle = "Proceedings of the ACM Workshop on Storage Security and Survivability",
 year = "2005",
 month = "November",
 url = "",
 pages = "108--114",
 address = "Fairfax, VA, USA",
 publisher = "ACM Press",

Nice summary of this at

Reputation & Trust

Reputation in P2P Anonymity Systems
 title = Template:Reputation in P2P Anonymity Systems, 
 author = {Roger Dingledine and Nick Mathewson and Paul Syverson}, 
 booktitle = {Proceedings of Workshop on Economics of Peer-to-Peer Systems}, 
 year = {2003}, 
 month = {June}, 
 www_pdf_url = {}, 
 www_section = {Economics}

Details several reputation systems for use in an anonymous remailer setting and in an anonymous publishing system (Free Haven), but that are more generally applicable to all anonymous p2p systems. Discusses weakly trusted global witnesses, small groups of remailers (cascades), and storage contracts (with shepherds or buddies).

Select Quotes:

"Unlike confidentiality (encryption), anonymity cannot be created by the sender or receiver. Alice cannot decide by herself to send anonymous messages -- she must trust the infrastructure to provide protection, and others must use the same infrastructure."

"It's tempting to scale down the reputation system instead. That is, servers use only local information from their own transactions and trades... Rather than the global gossip system where the whole world learns from a server's first interaction, now each server has a chance to waste the time and resources of every other server (the "screw everyone once" attack)."

Herbivore: A Scalable and Efficient Protocol for Anonymous Communication
 title = {"Herbivore: A Scalable and Efficient Protocol for Anonymous Communication"}, 
 author = {Sharad Goel and Mark Robson and Milo Polte and Emin Gun Sirer}, 
 institution = {Cornell University}, 
 number = {2003-1890}, 
 year = {2003}, 
 month = {February}, 
 address = {Ithaca, NY}, 
 www_section = {Anonymous communication}, 
 www_pdf_url = {}, 

A very nice anonymity system, with a nice explanation of how to leverage dining cryptographers in a p2p setting.

The reason this paper is included in this section is for its use of hashcash to limit an adversary's ability to generate ids targetting a specific range offline. By requiring each node to search for collisions with timestamps in the lower bits of the collision source, old collision values cannot be used in the future, and significant computational resources are required to target specific id ranges.

Hash cash - a denial of service counter-measure
@misc { 
 author = "A. Back",
 title = "Hash cash - a denial of service counter-measure",
 text = "Adam Back. Hash cash - a denial of service counter-measure.",
 url = ""

Describes work extended from the original (1997) hashcash proposal, finding partial collisions in cryptographic functions as a method of imposing cost (in email). Similar to the join cost function in Herbivore. This is not the first paper to describe computational cost functions to prevent spam, for that, see Dwork and Naor's "Pricing vi Processing, Or Combatting Junk Mail" in Advances in Cryptology CRYPTO'92, Lecture Notes in Computer Science No 740, Springer, 1993, pp 139-147

On memory-bound functions for fighting spam
 author = "C. Dwork and A. Goldberg and M. Naor",
 title = "On memory-bound functions for fighting spam",
 text = "C. Dwork, A. Goldberg, and M. Naor. On memory-bound functions for fighting spam. Draft, 2002.",
 year = "2002",
 url = ""

An alternative to hashcash and hash collision cost functions that may be more equitable to diverse CPUs, i.e., less susceptible to Moore's Law.

Taxonomy of trust: Categorizing P2P Reputation Systems
 abstract = {The field of peer-to-peer reputation systems has exploded in the last few years. Our goal is to organize existing ideas and work to facilitate system design. We present a taxonomy of reputation system components, their properties, and discuss how user behavior and technical constraints can conflict. In our discussion, we describe research that exemplifies compromises made to deliver a useable, implementable system.},
 author = {Marti, Sergio   and Garcia-Molina, Hector  },
 booktitle = {Management in Peer-to-Peer Systems},
 citeulike-article-id = {530977},
 doi = {10.1016/j.comnet.2005.07.011},
 journal = {Computer Networks},
 keywords = {p2p, trust},
 month = {March},
 number = {4},
 pages = {472--484},
 priority = {0},
 title = {Taxonomy of trust: Categorizing P2P reputation systems},
 url = {},
 volume = {50},
 year = {2006}

Very comprehensive survey of trust/reputation systems in p2p networks, including nice taxonomy and definitions (including enumeration of threat models).

Key definitions: Transactions, Cooperate/Defect, Strangers, Adversaries.

Behaviors: Churn, Reliability, Privacy

Adversarial Powers: Traitors, Collusion, Front Peers, Whitewashers, DoS

Identities: Anonymity, Spoof-resistance, Unforgeability (centralized)

Incentives: Speed, Quality, Quantity, Money

Punishment: Disconnects, Bans, Fines

Attacks on Trust Evaluation in Distributed Networks
 title = {A Trust Evaluation Framework in Distributed Networks: Vulnerability Analysis and Defense Against Attacks.},
 author = {Yan L. Sun and Zhu Han and Wei Yu and K. J. Ray Liu},
 booktitle = {INFOCOM},
 crossref = {conf/infocom/2006},
 publisher = {IEEE},
 url = {},
 year = {2006},
 description = {dblp},
 ee = {}, date = {2007-07-18},
 keywords = {dblp }

"address the fundamental understanding of trust, quantitative trust metrics, mathematical properties of trust, dynamic properties of trust, and trust models. The attacks against trust evaluation are identified and defense techniques are developed. The proposed trust evaluation system is employed in ad hoc networks for securing ad hoc routing and assisting malicious node detection."

Attack Resistent Trust Metrics
@misc{ levien01attackresistant,
 author = "R. Levien",
 title = "Attack-resistant trust metrics",
 text = "R. Levien. Attack-resistant trust metrics. PhD Thesis,, 2001.",
 year = "2001",
 url = ""

"characterizes the space of trust metrics, under both the scalar assumption where each assertion is evaluated independently... presents a quantitative framework for evaluating the attack resistance of trust metrics"

Levien's experiences with Advogato, as well as discussion of applicability elsewhere.

Economics / Game Theory

An Excess-Based Economic Model for Resource Allocation in Peer-to-Peer Networks
@article{ ebe2003,
   author = "Christian Grothoff",
   title = "{An Excess-Based Economic Model for Resource Allocation in Peer-to-Peer Networks}",
   journal = "Wirtschaftsinformatik",
   booktitle = "Wirtschaftsinformatik",
   volume = "3-2003", 
   publisher = "Vieweg-Verlag",
   url = "",
   month = "June",
   year = "2003"
A Lightweight Currency Paradigm for the P2P Resource Market
@misc{ turner03lightweight,
 author = "David A. Turner and Keith W. Ross",
 title = "A Lightweight Currency Paradigm for the {P2P} Resource Market",
 year = "2003",
 url = "" 

Advocates a system and protocol for an 'ultra-free market economy' where any entity can issue currency and participants can exchange resources by exchanging their currencies. The currencies, as put forth, are administered through a third party.

While overall, there are some neat ideas here, there are also a lot of problems. By requiring third parties to keep track of trust, the trust/reputation requirements are only shifted to involve even more parties (and ones for which self-interest is very difficult to judge). And the possible proliferation of currencies requires that a broker class come forward so that money can be exchanged, but again, where do individuals store their trust/reputation for these brokers? The paper suggests another third-party that will store reputations (but how to trust these?). The opportunity for collusion and gaming of the system seem to be multiplied by all these layers, and self-interest doesn't seem to drive many of the roles that must be played. So, while the paper is bold for emphasizing a 'wild-west' monetary system, it doesn't address lawlessness issues and how to deal with the wide variety of exploits that could arise in such a system.

It does state a couple of correct principles: that of strong identity tied to self-chosen public keys, and that individuals are free to set their own prices for resources.

A Taxonomy of Rational Attacks
@misc{ nielson05taxonomy,
 author = "S. Nielson and S. Crosby and D. Wallach",
 title = "A Taxonomy of Rational Attacks",
 text = "S. J. Nielson, S. A. Crosby, and D. S. Wallach, A Taxonomy of Rational
   Attacks In Proc. of IPTPS, Ithaca, NY. February 2005",
 year = "2005",
 url = ""

A very good taxonomy of rational attacks (just as the title suggests), and a group of general solutions:

  1. eliminate rationality as a concern (out-of-band trust, partial centralization, or trusted software -- all largely non-p2p solutions)
  2. design genuine incentives (these are the simplest to implement and provide the best protection, but hard to devise)
  3. use artificial incentives carefully (prefer non-instantaneous maturation, use reputation, protect auditing infrastructure)

Points to a couple of other important papers, including Douceur's "Sybil Attack" observation that only centrally controlled IDs can prevent a malicious node from assuming many simultaneous identities*, and to the Tangler's document entanglement strategy.

\* this is only true if the central authority can never be tricked into handing out multiple IDs to one entity, or if it charges for this service (to limit multiple IDs by real-world economic factors).

DHT & Structured Query

Kademlia: A Peer-to-peer Information System Based on the XOR Metric
 author    = {Petar Maymounkov and
              David Mazi{\`e}res},
 title     = {Kademlia: A Peer-to-Peer Information System Based on the
              XOR Metric.},
 booktitle = {IPTPS},
 year      = {2002},
 pages     = {53-65},
 ee        = {},
 crossref  = {DBLP:conf/iptps/2002},
 bibsource = {DBLP,}
 editor    = {Peter Druschel and
              M. Frans Kaashoek and
              Antony I. T. Rowstron},
 title     = {Peer-to-Peer Systems, First International Workshop, IPTPS
              2002, Cambridge, MA, USA, March 7-8, 2002, Revised Papers},
 booktitle = {IPTPS},
 publisher = {Springer},
 series    = {Lecture Notes in Computer Science},
 volume    = {2429},
 year      = {2002},
 isbn      = {3-540-44179-4},
 bibsource = {DBLP,}

Contains the seminal, canonical description of the Kademlia DHT.

Non-Transitive Connectivity and DHTs
@inproceedings{ ntr:worlds05,
 title = "Non-Transitive Connectivity and {DHTs}",
 author = "Michael J. Freedman and Karthik Lakshminarayanan and Sean Rhea and Ion Stoica",
 booltitle = "Proc. 2nd Workshop on Real, Large, Distributed Systems ({WORLDS 05})",
 address = "San Francisco, CA",
 month = Dec,
 year = 2005

Points out problems for DHTs with non-transitive connections (non-transitivity is common). The only ones that seem to be an immediate problem for Kademlia (at least as implemented in flud) are: 1) need to implement an 'unreachable' cache and 2) eliminate blind trust. (see question and response in p2p-hackers).

Security Considerations for Peer-to-Peer Distributed Hash Tables
 title = {Security Considerations for Peer-to-Peer Distributed Hash Tables},
 author = {Emil Sit and Robert Morris},
 booktitle = {Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS)},
 year = {2002},
 month = {March},
 address = {Cambridge, MA},

Nice overview of several known security issues in DHTs. Produced the following 6 guidelines: 1) define verifiable system invariants, and verify them; 2) allow the querier to observe lookup progress; 3) assign keys to nodes in a verifiable way; 4) be wary of server selection in routing; 5) cross-check routing tables using random queries; and 6) avoid single points of responsibility.

Outlined the following 9 attacks (many of which are not applicable to kademlia-style DHTs):

  1. unauthentic data: can be solved using cryptographic techniques, such as self-certifying path names (done in flud)
  2. incorrect lookup routing: not an issue in kademlia's recursive routing, as the source of the query is 'observing' all queries already. Suggests assigning keys to nodes in a verifiable way (done in flud).
  3. incorrect routing updates: kademlia's replacement strategy makes it difficult for a malicious node to suceeed. New routes are only added after the node verifies reachability (doing in flud).
  4. partitions: partitions are possible in kademlia, but can be healed by doing some random queries instead of strictly directed ones during lookup (see, for example, Suggests using trust metrics with strong identity (done in flud).
  5. storage and retrieval attacks: Suggests implementing replication, which is core to kademlia (done in flud). Suggests consulting at least two replicas to make sure the data is good (doing in flud). Suggests using strong identities for nodes so that a node cannot 'choose' to become responsible for targetted data (done in flud).
  6. inconsistent behavior: somewhat handled in flud with the trust system (since the trust system is limited to a subset of all nodes -- mainly trading partners -- the trust system doesn't extend to all DHT nodes. All nodes close to a misbehaving node will monitor it and eventually reject it, but not if it deals honestly with close nodes and dishonestly with distant nodes... Replication and limiting nodeID choice help out here).
  7. overloading targetted nodes: DHTs alread handle this. But to be even better, suggests that node ID be assigned randomly (done in flud)
  8. rapid joins and leaves: this is mostly a problem for Chord-like DHTs. Kademlia does not need to move data around when nodes come and go, so it doesn't apply. Additionally, a core piece of the trust metric is availability. Nodes that come and go will gain little trust. Same issues as in #6 apply.
  9. unsolicited messages: this attack is possible, though extremely difficult due to reliance on http as a transport; in order to carry out the attack, the attacker must hijack a short-lived http session and inject its message before the true responder is able to do so. Therefore, the attacker must not only be lucky, but must be lucky presciently.
Improving Lookup Performance over a Widely-Deployed DHT
 title = {Improving Lookup Performance Over a Widely-Deployed DHT.},
 author = {Daniel Stutzbach and Reza Rejaie},
 booktitle = {INFOCOM},
 crossref = {conf/infocom/2006},
 publisher = {IEEE},
 url = {},
 year = {2006},
 description = {dblp},
 ee = {}, date = {2007-07-18},
 keywords = {dblp }

Nice analysis of some optimizations to the Kademlia protocol for efficiency and consistency. Claims to pinpoint the best values for replication and parallelism when using Kademlia. Explains some interesting techniques for enriching the routing structure. Performs a thorough analysis of the Kad (eMule) network through live instrumentation (Kad had ~980,000 nodes in 2005 when this was done).

Miscellaneous Peer-to-Peer

Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs
 author = {William J. Bolosky and John R. Douceur and David Ely and Marvin Theimer},
 title = {Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs},
 booktitle = {SIGMETRICS '00: Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems},
 year = {2000},
 isbn = {1-58113-194-1},
 pages = {34--43},
 location = {Santa Clara, California, United States},
 doi = {},
 publisher = {ACM Press},
 address = {New York, NY, USA},

Took a series of measurements from nearly 65,000 desktop machines at Microsoft.

Transient failures are common, but permanent failures are rare. It is unlikely that even 1% of a large population of nodes all fail at during some short interval.

Describes (perhaps for the first time) convergent encryption.

Measured disk usage, content, and access rates. Measured machine uptime, downtime, lifetime, and correlation. Different tests were performed at different times, but most were performed over a period of several weeks.

Concluded that average disk usage is at 50-53%, and that removing duplicate files across systems reclaims 47% of used file space.

Experiences in Building and Operating ePOST, a Reliable Peer-to-Peer Application
 author = {Alan Mislove and Ansley Post and Andreas Haeberlen and Peter Druschel},
 title = {Experiences in Building and Operating {ePOST}, a Reliable Peer-to-Peer Application},
 booktitle = {Proceedings of EuroSys 2006},
 location = {Leuven, Belgium},
 month = {April},
 year = {2006}

Nice discussion of [unexpected] problems encountered after initially designing ePOST.

Uses a centralized entity ( to assing nodeIDs to discourage Sybil attacks (note that this centralized entity can be tricked into giving out multiple IDs to one entity, so it is not a complete solution).

Lesson 1: Discussed revealing statistics about network partitions and the need to deal with them. On the PlanetLab deployment, the overlay was partitioned 110 times in 3 months (more than once/day)! Usually, these partitions consisted of one large partition, and then one or more very small partitions (avg size 12.4 nodes). ePOST solutions to this problem are largely domain-specific.

Lesson 2: Tolerate partial network connectivity. Same topic here as Non-transitivity paper. Solutions presented are Pastry-specific, and somewhat complex implementation-wise (virtual links), (kademlia is already largely resilient).

Lesson 3: Ensure routing consistency in Pastry. Again, this topic is largely irrelevant to kademlia, and involves some hackish fixes, like adding a watchdog process to monitor the local ePOST instance, etc.

Lesson 4: Withstand large-scale failures. Failures can be correlated, and caused by homogeneity (both in software and in network geography). Solved by introducing more heterogeneity and by using a storage layer with sufficient redundancy to survive massive failures (up to 80%).

Had some good suggestions from experience, such as the observation that storing lots of small files in directories causes OS-level problems and that it may be better to build on top of a DB layer.

Erasure Coding

Design and Evaluation of a Low Density Generator Matrix (LDGM) Large Block FEC Codec
@misc{ roca03design,
 author = "V. Roca and Z. Khallouf and J. Laboure",
 title = "Design and evaluation of a low density generator matrix",
 text = "V. Roca, Z. Khallouf, and J. Laboure. Design and evaluation of a low density
   generator matrix (ldgm) large block fec codec. In Fifth International Workshop
   on Networked Group Communication (NGC'03), Munich, Germany, Sept. 2003.",
 year = "2003",
 url = ""

A must-read if using LDPC/LDGM libs (as flud does). Discusses tradeoffs for choosing k and n, and graphs choice of left-degree (which determines, with seed, the matrix used for coding/decoding) over a wide range of choices for k.

The paper also spends significant time comparing these codecs to RSE, and discussing the inefficiency ratio (number of blocks > n needed to decode)

Since we'll be using a smaller k for flud, it appears that a left-degree of 6 is more optimal, though we need to do some more experiments, as k < 100 doesn't really appear to be shown (perhaps 5 is even better).

Impacts of Packet Scheduling and Packet Loss Distribution on FEC Performances: Observations and Recommendations
 author = {Christoph Neumann and Vincent Roca and Aur\&\#233;lien Francillon and David Furodet},
 title = {Impacts of packet scheduling and packet loss distribution on FEC Performances: observations and recommendations},
 booktitle = {CoNEXT'05: Proceedings of the 2005 ACM conference on Emerging network experiment and technology},
 year = {2005},
 isbn = {1-59593-197-X},
 pages = {166--176},
 location = {Toulouse, France},
 doi = {},
 publisher = {ACM Press},
 address = {New York, NY, USA},

More in-depth analysis of different LDPC/LDGM strategies and impacts. Plots inefficiency ratio against p (probability of transitioning to loss state) and q (probability of transitioning out of loss state). Models 6 different transmission models.

Model 4 (send both source and parity packets randomly) best matches flud behavior. This model reacts best with LDGM Triangle.

On the Practical Use of LDPC Erasure Codes for Distributed Storage Applications
 author = "J. S. Plank and M. G. Thomason",
 title = "On the Practical Use of LDPC Erasure Codes for Distributed
         Storage Applications",
 institution = "University of Tennessee",
 month = "September",
 year = "2003",
 number = "CS-03-510",
 where = ""

"A significant conclusion from this analysis is that while there are indeed practical situations where Reed-Solomon coding clearly outperforms LPDC codes, there are also practical situations where LPDC codes outperform Reed-Solomon coding for all values of n."

Security / Resilience / Robustness

The topology of covert conflict
 author="S. Nagaraja and R. Anderson", 
 title="The Topology of Covert Conflict", 
 institution="University of Cambridge Computer Laboratory", 

Discusses scale-free networks and vertex-order attacks. Analyzes 3 classes of defense against such attacks, and shows that, of the 3, a clique-based defense is most effective. Very interesting analysis, building a 'bridge between network science and evolutionary game theory'.

Although it isn't immediately apparent that flud is scale-free per se, it is possible that some scale free properties will emerge as individual nodes choose storage partners at the storage layer. And although the DHT layer also seems to be non-scale-free, the network beneath the overlay certainly may be.

Defending the Sybil Attack in P2P Networks: Taxonomy, Challenges, and a Proposal for Self-Registration
 author="Jochen Dinger and Hannes Hartenstein",
 title="Defending the Sybil Attack in P2P Networks: Taxonomy, Challenges, and a Proposal for Self-Registration",
 institution="Institut fur Telematik, Universitat Karsruhe (TH), Germany",
 booktitle="DAS-P2P 2006",

Good overview of the Sybil attack in p2p systems, proposed solutions and stopgaps.

While this point is not in the paper, it is generally true that smaller networks are easiest to mount sybil attacks against. But small networks may not be as valuable of targets as large networks. And large networks are, by their largeness, more difficult to perform a sybil attack against. This is especially true if the network performs well under Byzantine conditions -- the attacker's work in generated sybil nodes is proportional to the size of the network.

A Survey of Peer-to-Peer Security Issues
 title =	"A Survey of Peer-to-Peer Security Issues",
 author =	"Dan S. Wallach",
 year = 	"2002",
 bibdate =	"2003-12-19",
 bibsource =	"DBLP,",
 booktitle =	"ISSS",
 crossref =	"conf/isss2/2002",
 pages =	"42--57",
 URL = "",

A good survey of problems and solutions in the p2p security space.

NAT Traversal

Peer-to-peer communication across network address translators
@misc{ ford05peertopeer,
 author = "B. Ford",
 title = "Peer-to-peer communication across network address translators",
 text = "Bryan Ford. Peer-to-peer communication across network address translators.
   In USENIX Annual Technical Conference, 2005.",
 year = "2005",
 url = ""

Nice general overview of NAT traversal techniques. Also outlines some hole-punching techniques for TCP. html edition of the paper.

Characterization and Measurement of TCP Traversal through NATs and Firewalls
@misc{ guha05characterization,
 author = "S. GUHA and P. FRANCIS",
 title = "Characterization and measurement of tcp traversal through nats and firewalls",
 text = "GUHA, S., AND FRANCIS, P. Characterization and measurement of tcp traversal
   through nats and firewalls. In Proceedings of the 2005.",
 year = "2005",
 url = ""

Analysis of effectiveness of NAT traversal with TCP. See also the paper that intruduced STUNT and the STUNT homepage.

Personal tools