Computer Science Department
School of Computer Science, Carnegie Mellon University


Making Contribution-Aware P2P Systems Robust
to Collusion Attacks Using Bandwidth Puzzles

Michael K. Reiter*, Vyas Sekar, Zhenghao Zhang**

September 2008


This report is superceded by Computer Science
Technical Report CMU-CS-09-136

Keywords: Peer-to-Peer, collusion, ballot stuffing, reputation, incentives, security

Many peer-to-peer (P2P) content-distribution systems reward a peer based on its contribution to the system, specifically the amount of data that this peer serves to others. However, validating that a peer did so is, to our knowledge, an open problem; e.g., in a simple form of "ballot stuffing" attack, a group of colluding attackers can earn rewards by claiming to have served content to one another, when they have not. We propose a simple puzzle mechanism to make contribution-aware P2P content distribution systems robust to such collusion. Our construction is novel in that it both ties solving the puzzle to possession of content and, by issuing puzzle challenges simultaneously to all parties claiming to have the same content, prevents one content-holder from solving many others' puzzles. We provide two bounds (in the random oracle model) for adversaries' ability to defeat our puzzle scheme, one closed-form bound and one more precise, efficiently computable, but non-closed-form bound. We additionally evaluate our design in the context of the Maze P2P file-sharing architecture.

25 pages

*Department of Computer Science, University of North Carolina, Chapel Hill, NC
**Computer Science Department, Florida State University, Tallahassee, FL

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by