Distributed systems that allow any user to enroll his node as a participant must resolve two main challenges to achieve reliability: selecting trustworthy participants, and detecting and containing the damage of deviant nodes. This research addresses these challenges by (a) presenting a new system architecture, F2F, that incorporates decentralized trust relationships among users in determining trustworthy nodes and (b) devising new techniques to detect and contain faults of misbehaving nodes in the context of concrete applications using this new architecture.
This research demonstrates the usefulness of F2F through the design and implementation of two case-study systems: cooperative backup and censorship circumvention. Friendstore provides inexpensive and reliable backup by storing each user's data on a subset of trusted neighbors. Such an architecture allows Friendstore to use less expensive technical means to detect and recover from faults but makes it harder to fully utilize storage resources. This project addresses this challenge using coding techniques that allow a node to efficiently provide data redundancy for multiple neighbors simultaneously. The second case study system, Kaleidoscope, helps users inside censored domains access blocked websites by relaying traffic via a network of proxies. Kaleidoscope uses a novel protocol to disseminate proxy identities over the F2F trust graph so that each node can only collect limited information about others' identities. A few malicious nodes, then, cannot discover a significant fraction of proxies.
This project will produce systems that, if successfully deployed, provide inexpensive online storage to home users and help circumvent censorship for millions of affected users.
Cooperative systems (aka crowd-sourced systems) are prevalent today. Examples range from popular websites (e.g. YouTube, Yelp) which rely on user-submitted content to peer-to-peer systems (e.g. BitTorrent, BitCoin) which rely on user-contributed hardware resources. When building such systems, it is customary to assume that users are cooperative, i.e. they behave as they are told. This assumption vastly simplifies the design and implementation, but makes the resulting system vulnerable to attacks. The goal of this proposal is to develop re-usable primitives to secure various types of cooperative systems. The fundamental challenge in securing cooperative systems stems from the lack of strong user identities in these systems. In other words, it is cheap to for an adversary to create a large number of new identities to overwhelm honest users, an attack referred to as the Sybil attack. A central theme among various projects done under this proposal is to use a weak form of user identity based on the social network of participating users to mitigate the Sybil attack. Our insight is to associate the identity of each user with her social links with other users. Since social relationships take significant human efforts to establish, an attacker is limited to a small number of links with honest users and thus can only have a few usable identities. Intellectual Merits: The proposal has developed a novel admission control protocol called GateKeeper to bound the number of Sybil identities admitted into any cooperative system using the underlying social network among users. This proposal has developed a variety of different cooperative applications: SumUp is a Sybil-resilient online content-voting system. Credo is a collusion-resilient reputation system for peer-to-peer content distribution. Kaleidoscope is a peer-to-peer censorship circumvention system. All of these systems have used social network-based user identities in a novel way. Broader Impacts: The Kaleidoscope system has been deployed among a small community of users to circumvent Internet censorship. Its social-network based technology has inspired Lantern (from Brave New Software Inc.) and uProxy (from Google and University of Washington), two non-profit and commercial systems that are currently being developed and deployed. SumUp has shown strong evidence of Sybil attacks on real-world cooperative systems (Digg.com) and raised awareness of the vulnerability of these systems. Research done in this proposal has trained several Ph.D. and M.S. students. The PI has also used the ideas and software infrastructure developed in this proposal to improve the graduate-level networking class at NYU. Project outcomes: This proposal has produced novel system designs for several cooperative applications (online content-voting, censorship circumvention, cooperative backup, peer-to-peer content distribution). These designs and prototype evaluation have resulted in several publications at competitive peer-reviewed journals, conferences and workshops. One of the graduate students has graduated with a Ph.D. based on work done under this proposal. In addition to publications, this proposal has also led to the dissemination of a public data-set (the Digg social graph and voting history) and the Kaleidoscope open-source censorship circumvention software.
