GNUnet papers and related work


	GNUnet GNU‘s decentralized anonymous and censorship-resistant P2P framework.

Papers about GNUnet

An Encoding for Censorship-Resistant Sharing (ps)

Christian Grothoff, Krista Grothoff, Tzvetan Horozov and J. T. Lindgren
The paper describes the encoding of content for the file-sharing layer of GNUnet. We describe an array of techniques to encode content such that it can be easily distributed, searched for and retrieved. The encryption scheme allows users to insert the same content under multiple keys; yet multiple keys lead to practically identical copies in the system, reducing storage requirements. Keys can be chosen from natural language and can be combined to boolean queries. Queries and content can not be decrypted by intermediaries without guessing the key. Nevertheless, intermediaries can verify that a reply answers a query. The encoding of the content produces many small blocks, which can be easily distributed over several hosts. This allows the network to balance load. The paper describes how to optimize lookups and extends the scheme with directories and namespaces.

A Transport Layer Abstraction for Peer-to-Peer Networks (ps) GP2PC 2003

Ronaldo Ferreira, Christian Grothoff and Paul Ruth
This paper describes the transport abstraction used by GNUnet. It describes the SMTP implementation in detail, in particular the security considerations that occur when using this protocol. The paper also compares the performance of the UDP, TCP and SMTP transport.

An Excess-Based Economic Model for Resource Allocation in Peer-to-Peer Networks (ps, pdf), WI 3’2003.

Christian Grothoff
This paper describes the economic model behind GNUnet. We describe how accountability is achieved in an anonymous network. Our economy is based on trust, and is used only for resource allocation.
Our economic model is less powerful and much simpler than most schemes for digital cash. Unlike schemes for digital cash, we do not require a trusted authority.

A Quick Introduction to Bloom Filters (ps, pdf)

Christian Grothoff
This paper gives a brief description of the bloom filter data structure.

Bloom filters are used in GNUnet for fast set tests that must be performed for each query.

gap -- practical anonymous networking (ps, pdf, slides), PET 2003.

Krista Bennett and Christian Grothoff
This paper describes how anonymity is achieved in GNUnet, a framework for anonymous distributed and secure networking.
We describe a new scheme for anonymous transfer of data which achieves better anonymity guarantees than traditional indirection schemes and is more efficient. While the building blocks of our technique used to achieve anonymity are identical to previous work, we offer a new perspective on how to achieve anonymity.

Bootstrapping of Peer-to-Peer Networks (pdf), DAS P2P 2008.

Chris GauthierDickey and Christian Grothoff
This paper describes how large peer-to-peer systems could be bootstrapped in a fully decentralized manner.
While this maybe implemented in GNUnet in the future, we currently still use hostlists due to the limited size of the network (the above approach only works well for larger, established P2P networks).

An Analysis of GNUnet and the Implications for Anonymous, Censorship-Resistant Networks (PS), PET 2003.

Dennis Kügler
This paper describes attacks on GNUnet’s anonymous file sharing. The author analyzes a statistical attack with an active adversary that is able to correlate queries (for example, by being the responder). The paper also describes a censorship attack using an adversary that legally requires every peer to provide for every transmitted block a certificate issued by the government that shows that it is legal to share the block. Given such an adversary that legally enforces content filtering on a per-block level, GNUnet can be censored.

Enhancing Web privacy and anonymity in the digital era (pdf), Information Management & Computer Security, 12-3 2004.

Stefanos Gritzalis
This paper presents a review of various privacy and anonymity enhancing systems, including GNUnet (GAP). The review highlights the advantages and disadvantages of the various systems. This paper is probably a good introduction for people interested in anonymity and privacy in general and can be used as a guide towards which systems maybe the right choice for a particular application.

Efficient Sharing of Encrypted Data (ps, pdf), ACISP 2002

Krista Bennett, Christian Grothoff, Tzvetan Horozov and Ioana Patrascu
This paper is now obsolete. It has been superceeded by ECRS. The paper describes the encryption of content for the file-sharing layer of GNUnet. We describe a new technique to encode content such that it can be easily distributed, searched for and retrieved. The encryption scheme allows users to insert the same content under multiple keys; yet multiple keys lead to practically identical copies in the system, reducing storage requirements. Keys can be chosen from natural language and can be combined to boolean queries. Queries and content can not be decrypted by intermediaries without guessing the key. Nevertheless, intermediaries can verify that a reply answers a query. The encoding of the content produces many small GBlocks, which can be easily distributed over several hosts. This allows the network to balance load. Single hosts are never hit with requests that take a long time to process.

Since this paper was written, GNUnet has made some more progress in addressing some of the issues with ESED. The current "state of the art" is detailed on the encoding page.

The GNet Whitepaper (ps or pdf)

Krista Bennett, Christian Grothoff, Tzvetan Horozov, Ioana Patrascu and Tiberius Stef
In this paper, we describe the design and implementation of GNet. The methods used for authentication, anonymization, distribution and ranking are described. This paper is the initial design document, it is severely out-of-date.

Related Work

Protocols for Anonymity


Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms: David Chaum
The fundamental paper on onion routing and mixes.

Pipenet: Wei Dai
A theoretical concept for an anonymous network based on pipes between nodes that carry constant amounts of traffic.

Towards measuring anonymity: Claudia Diaz, Stefaan Seys, Joris Claessens and Bart Preneel
This paper describes why it is insufficient to just compute probabilities for the anonymity set. The authors propose to use entropy, the number of bits of additional information that the adversary needs to break anonymity, as the metric for how anonymous a given system is.

Towards an Information Theoretic Metric for Anonymity: Andrei Serjantov and George Danezis
This paper proposes a metric that is essentially equivalent to Towards measuring anonymity but focuses on the analysis of mixes.

Anonymity in Structured Peer-to-Peer Networks: Nikita Borisov and Jason Waddle
This paper discusses how much anonymity structured peer-to-peer networks (based on Chord) can achieve. It uses the entropy metric for anonymity and discusses attacker placement and various variations on the routing algorithms. Well written.

An Analysis of the Degradation of Anonymous Protocols: Matthew Wrigt, Micah Adler, Brian Levine and Clay Shields
This paper describes a general attack that degrades anonymity in all session-based anonymous networks, including Crowds, Onion Routing and Mix-Nets. The main problem is that over time an attacker can learn the identity of the originator if the adversary can accumulate statistical information on a connection and correlate it with the sender.

Responder Anonymity and Anonymous Peer-to-Peer File Sharing: Vincent Scarlata, Brian Levine and Clay Shields
Extention of Crowds, Hords or Onion routing to achieve responder anonymity using proxies or multicast. The multicast solution has similar problems as P5. The paper than goes on implementing a FastTrack style service on top of the anonymous network. Where is the implementation?

Anonymous Webtransactions with Crowds: Michael Reiter and Aviel Rubin
Slides. Think of a Crowd as a self-organized cascade of anonymizing proxies.

Crowds: Anonymity for Web Transactions: Aviel Rubin
Crowds is a system that allows anonymous web-surfing. For each host, a random static path through the crowd is formed that then acts as a sequence of proxies, indirecting replies and responses. Vulnerable when facing adversaries that can perform traffic analysis at the local node and without responder anonymity. But highly scalable and efficient.

CliqueNet: A Self-Organizing, Scalable, Peer-to-Peer Anonymous Communication Substrate: Emin Sirer, Milo Polte and Mark Robson
Cliques are small (3-5) groups of nodes that form a DC-Net. The paper is vague how the larger network is formed, how to deal with small mobs (2-4) that collaborate in a clique, how to do addressing or the distributed database.

Onion Routing for Anonymous and Private Internet Connections: David Goldschlag, Michael Reed and Paul Syverson
A brief introduction to onion routing.

Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems: Adam Back, Ulf Möller and Anton Stiglic

Fault Tolerant Anonymous Channel: Wakaha Ogata, Kaoru Kurosawa, Kazue Sako and Kazunori Takatani
This paper describes a zero-knowledge proof that a mix in onion routing can perform in order to proof that it did route the messages properly. This allows the deployment of a mix-net where malicious mixes can be detected without using dummy-traffic to probe for correctness. Technical.

Mixing Email with Babel: Ceki Gülcü and Gene Tsudik

A Protocol for Anonymous Communication Over the Internet: Clay Shields and Brian Neil Levine
Variant of Crowds using multicast for the reply. Since multicast is anonymity at the expense of potentially many others and also can not be implemented over TCP (must be UDP), this is probably often worse than the original Crowds system.

P⁵: A Protocol for Scalable Anonymous Communication: Rob Sherwood, Bobby Bhattacharjee and Aravind Srinivasan
Onion routing for sender anonymity, limited broadcast for receiver anonymity. Nodes can choose to be more anonymous at the expense of other nodes receiving more traffic. The design uses lots of public key operations and noise.

Introducing Tarzan, a Peer-to-Peer Anonymizing Network Layer: Michael Freedman, Emil Sit, Josh Cates and Robert Morris

Mixminion: Design of a Type III Anonymous Remailer: George Danezis, Roger Dingledine, David Hopwood and Nick Mathewson
Onion routing revisited. With use-once reply blocks for replies to anonymous senders. Note that the use-once is implemented by making the nodes keep track of previous messages. The paper describes nicely all the nifty little extentions and attacks that have been developed around the original mixing schemes.

Buses for Anonymous Message Delivery: Amos Beimel and Shlomi Dolev
Applies graph theory to anonymity. The paper suffers from the fundamental problem that it does not discuss attacks on the scheme, and there are a couple of pretty basic ways to break anonymity. Also, the scheme uses lots of traffic; some variants end up looking much like a pipenet.

TAZ Servers and the Rewebber Network. Enabling Anonymous Publishing on the World Wide Web: Ian Goldberg and David Wagner

k-Anonymous Message Transmission: Luis von Ahn, Andrew Bortz and Nicholas J. Hopper

Anonymity, Unobservability, Pseudonymity, and Identity Management - A Proposal for Terminology v0.18: Andreas Pfitzmann and Marit Hansen

Flash Mixing: Markus Jakobsson

Routing


Routing in the Dark: Pitch Black: Nathan S. Evans and Chris GauthierDickey and Christian Grothoff
Attack on the routing protocol of Freenet 0.7.

Distributed routing in Small World Networks: Oskar Sandberg
Theoretical basis for the routing protocol of Freenet 0.7.

Chord: A scalable peer-to-peer lookup service for Internet applications: Ion Stoica, Robert Morris, Davit Karger, Frans Kaashoek and Hari Balakrishnan
Description of an efficient scheme to locate resources in a distributed, dynamic network. Resources are mapped into a cyclic address space. Each host in the network is associated with a point in that cyclic address space. Content is hosted at the host(s) that is (are) closest to its address. The routing table size is O(log n). The maximum search path is also O(log n) if no nodes fail.

Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems: Antonz Rowstron and Peter Druschel
Like Chord, Pastry is a distributed hash table (DHT) with O(log n) entries in the routing table and a lookup path of O(log n). Pastry has more freedom in building the routing table and can thus take proximity into account, making the lookup even faster.

Exploting network proximity in peer-to-peer overlay networks: Miguel Castro, Peter Druschel, Charlie Hu and Antony Rowstron
The authors give an overview over various ways to use proximity information to optimize routing in peer-to-peer networks. Their study focuses on Pastry and describe in detail the protocols that are used in Pastry to build routing tables with neighbours that are close in terms of the underlying network. They give some analytical and extensive experimental evidence that the protocols are effective in reducing the length of the routing-path in terms of the link-to-link latency that their implementation uses to measure distance.

Distributed Data Location in a Dynamic Network: Kirsten Hildrum, John Kubiatowicz, Satish Rao and Ben Zhao
Another DHT with O(log n) entries in the routing table and a lookup path of O(log n).

A Scalable Content-Addressable Network: Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker
CAN is a distributed hash table (DHT) that routes messages in an d-dimensional space on the shortest path to the node closest to to the hash. As opposed to Chord, Pastry and Tapestry, the routing table does not grow with the number of nodes. On the other hand, the search path can be longer than log n.

Building Low-Diameter P2P Networks: Gopal Pandurangan, Prabhakar Raghavan and Eli Upfal
Scheme to build dynamic, distributed P2P networks of constant degree and logarithmic diameter.

Sloppy hashing and self-organizing clusters: Michael J. Freedman and David Mazieres

Dynamic Load Balancing in Distributed Hash Tables: Marcin Bienkowski, Miroslaw Korzeniowski and Friedhelm Meyer auf der Heide

Searching in Peer-to-Peer networks


PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities: Francisco Matias Cuenca/Acuna, Christopher Peery, Richard P. Martin and Thu D. Nguyen
PlanetP is a peer-to-peer system in which searching content is done mostly locally. Every peer knows which content is available at which other peers. The index information is represented compactly using bloom filters and distributed throughout the network using push and pull mechanisms.

Practical Techniques for Searches on Encrypted Data: Dawn Xiaodong Song, David Wagner and Adrian Perrig

JXTA Search: Distributed Search for Distributed Networks: Steve Waterhouse

Adapting Publish/Subscribe Middleware to Achieve Gnutella-like Functionality: Dennis Heimbinger

Public Key Encryption with keyword Search: Dan Boneh and Giovanni Di Crescenzo

Secure Indexes: Eu-Jin Goh

A Reputation-Based Approach for Choosing Reliable Resources in Peer-to-Peer Networks: Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, Pierangela Samarati and Fabio Violante

Replication and Migration


On Algorithms for Efficient Data Migration: Joseph Hall, Jason Hartline, Anna R. Karlin, Jared Saia and John Wilkes

Reclaiming Space from Duplicate Files in a Serverless Distributed File System: John R. Douceur, Atul Adya, William J. Bolosky, Dan Simon and Marvin Theimer

Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System: John R. Douceur and Roger P. Wattenhofer

Replication Strategies in Unstructured Peer-to-Peer Networks: E. Cohen and S. Shenker
The paper sets out to solve the problem to find the optimal amount to which a piece of content should be replicated in a peer-to-peer network based on random search. The authors use a statistical approach to proof that the optimal content replication strategy is replication proportional to the square-root of the query rate. They then describe various distributed algorithms that achieve this replication rate. Interestingly, Freenet (and GNUnet) use one of these algorithms, content replication on the reply-path.

Censorship Resistant Publishing


Censorship Resistance Revisited: Ginger Perng, Michael K. Reiter and Chenxi Wang
This paper proposes a formal model for censorship resistance. Given their model of an attacker, the authors show that censorship resistance requires private information retrieval (PIR), which has a complexity of O(n) for updates and queries. They demonstrate that almost none of the previously proposed systems is censorship resistant in this model. This is particularly interesting for GNUnet, despite the paper not mentioning GNUnet at all, for three reasons. First, the given formal notion of censorship resistance closely corresponds to what the content encoding in GNUnet (ECRS) is supposed to achieve. Secondly, the paper shows that for an adversary that is capable of guessing keywords (or content), PIR is required. Note that PIR is not practically feasible due to the O(n) cost associated with it. On the other hand, if the adversary did not have the ability to mount a successful guessing attack, the model matches the ECRS model used by GNUnet exactly. Given this type of attacker, ECRS then delivers censorship resistance (in accordance with the model presented in this paper) with O(1) complexity. Unfortunately, the paper ignores this weaker attacker model as well as ECRS in its discussion. Nevertheless, the discussion of what censorship resistance means as well as the critique of other existing systems makes this paper an important contribution in the field of censorship resistant publishing.

Tangler: A Censorhsip-Resistant Publishing System Based On Document Entanglements: Marc Waldman and David Mazieres
The basic idea is to protect documents by making it impossible to remove one document from the system without loosing others. The underlying assumption that the adversary cares about collateral damage of this kind is a bit far fetched. Also, the entanglement doubles the amount of data that needs to be moved to retrieve a document.

The Eternity Service: Ross Anderson
Proposal for a system that allows storing content anonymously with defenses against attacks. Already a classic.

Censorship Resistant Peer-to-Peer Content Addressable Networks: Amos Fiat and Jared Saia

Anonymizing Censorship Resistant Systems: Andrei Serjantov

The Economics of Censorship Resistance: George Danezis and Ross Anderson

Publius: A robust, tamper-evident, censorship-resistant web publishing system: Mare Waldman, Aviel Rubin and Lorrie Cranor
Censorship-resistance is accomplished by secret sharing, signing and redundant storage.

Accounting and Trust


Accountability in P2P Democracy: Mandar Kelaskar
Great slides from a presentation that gives an overview on problems and current approaches to accountability in peer-to-peer networks.

Anonymity in Electronic Commerce: Yiannis Tsiounis
Slides why we need anonymous digital cash.

Micropayments and Anonymous E-Cash: Yiannis Tsiounis
Slides about digital cash with minimal transaction costs suitable for micropayments.

Balancing Privacy and Accountability: Yiannis Tsiounis
More about anonymous digital cash and why we need anonymity.

Efficient Electronic cash: New Notions and Techniques: Yiannis Tsiounis
Ph. D. Thesis.

Anonymity Control in E-Cash Systems: George Davida, Yair Frankel, Yiannis Tsiounis and Moti Yung

The Quest for Security in Mobile Ad Hoc Networks: Jean-Pierre Hubaux, Levente Buttyan and Srdan Capkun
A survey paper giving an introduction to security issues in distributed, dynamic networks. This paper lists the major security issues and common paradigms to address them. For their public key infrastructure model, see for comparrisson the original work on the PGP web of trust.

Trust Economies in the Free Haven Project: Brian Sniffen
Bachelor Thesis.

On the Economics of Anonymity: Roger Dingledine and Paul Syverson

Poblano: A Distributed Trust Model for Peer-to-Peer Networks: Rita Chen and William Yeager

PPay: Micropayments for Peer-to-Peer Systems: Beverly Yang and Hector Garcia-Molina

Peer-To-Peer: Harnessing the Power of Disruptive Technologies, Chapter 16: Accountability: Roger Dingledine, Michael J. Freedman and David Molnar

Reliable MIX Cascade Networks through Reputation: Roger Dingledine and Paul Syverson
How to detect that a Mix (E-mail anonymizer) failed to deliver.

A Reputation System to Increase MIX-net Reliability: Roger Dingledine, Michael J. Freedman, David Hopwood and David Molnar

Incentives for Sharing in Peer-to-Peer Networks: Philippe Golle, Kevin Leyton-Brown, Ilya Mironov and Mark Lillibridge

Incentives for Cooperation in Peer-to-Peer Networks: Kevin Lai, Michael Feldman, Ion Stoica and John Chuang
This paper discusses distributed incentive systems for peer-to-peer networks with zero-cost identities. It compares decision making based on private histories (like in GNUnet) with shared histories and concludes that private histories do not scale to larger networks (since a given pair of peers is unlikely to interact repeatedly as the size of the network grows). They note that shared histories also have problems (such as solving maximum-flow problems to establish reputation transitively in a secure fashion). Note that they ignore properties like locality, which, in particular in an anonymizing network like GNUnet where interactions are hardly ever end-to-end, increases the chances that peers will interact repeatedly even in very large networks.

When Can an Autonomous Reputation Scheme Discourage Free-riding in a Peer-to-Peer System?: Nazareno Andrade, Miranda Mowbray, Walfredo Cirne and Francisco Brasilerio
This work describes a scheme that is remarkably similar to the economic model used by GNUnet to discourage free-riding and enocurage contribution. The major difference to GNUnet seems to be that resource consumption does not seem to result in penalizing the requester: all peers only total up the contributions received and allocate their resources to the highest donor, irrespective of the resources requested by that peer previously. The discussion of related work in this paper is severely lacking.

Legal issues


DVD COPY CONTROL ASSOCIATION vs. ANDREW BUNNER: Court of Appleal of the State of California, Sixth Appellate District

Systems


A Measurement Study of Peer-to-Peer File Sharing Systems: Stefan Saroiu, P. Krishna Gummadi and Steven Gribble
Comparrisson between Napster and Gnutella (network topology, host characteristics, etc.).

A Distributed Decentralized Information Storage and Retrieval System: Ian Clarke
Ph.D. Thesis.

Freenet: A Distributed Anonymous Information Storage and Retrieval System: Ian Clarke, Oskar Sandberg, Brandon Wiley and Theodore Hong

The Free Haven Project: Design and Deployment of an Anonymous Secure Data Haven: Roger Dingledine
Master Thesis.

The Free Haven Project: Distributed Anonymous Storage Service: Roger Dingledine, Michael Freedman and David Molnar
Description of an anonymous publication system with accounting.

Project JXTA: An Open, Innovatie Collaboration: Sun Microsystems
Sun is building a p2p framework.

Eluding Carnivores: File Sharing with Strong Anonymity: Emin Gün Sirer, Sharad Goel, Mark Robson and Dogan Engin

Peer-To-Peer: Harnessing the Power of Disruptive Technologies -- Chapter 12: Free Haven: Roger Dingledine, Michael J. Freedman and David Molnar
Description of the problems that arise when one tries to combine anonymity and accountability. Note that the Free Haven design described here charges for storing data in the network (downloads are free), whereas in GNUnet adding data is free and only the downloads are considered as utilization.

The Gnutella Protocol Specification v0.4: Clip2
A brief description of the gnutella protocol.

Experiences Deploying A Large-Scale Emergent Network: Bryce Wilcox-O Hearn
Describes the authors experiences with MojoNation..

A New Generation of File Sharing Tools: Dan Klinedinst
Discussion of the advantages of Freenet and GNUnet over more traditional peer-to-peer networks.

Introducing MorphMix: Peer-to-Peer based Anonymous Internet Usage with Collsion Detection: Marc Rennhard and Bernhard Plattner
The paper describes the design of a peer-to-peer based mix network. The authors attempt to solve the problem of an adversary joining the network and collecting data using probabilistic assumptions about the behavior of the adversary. The problem with this approach of detecting malicious nodes is that a good adversary can always just adapt to the detection scheme and thereby avoid detection.

Transports


Infranet: Circumventing Web Censorship and Surveillance: Nick Feamster, Magdalena Baazinska, Greg Harfst, Hari Balakrishnan and David Karger
How to steganographically hide prohibited accesses to the WWW in "legitimate" HTTP traffic.

Peer-to-Peer Communication Across Network Address Translators: Bryan Ford, Pyda Srisuresh and Dan Kegel
How to establish connections in a peer-to-peer network in the presence of NAT, with an empirical study of various NAT implementations. Good stuff. And Ian, with a bit of native code it can even be done in Java.

New Covert Channels in HTTP: Matthias Bauer

Publish-Subscribe


Scribe: A large-scale and decentralized application-level multicast infrastructure: M. Castro, Peter Druschel, A. Kermarrec and A. Rowstron
The paper describes an implementation of a publish-subscribe system on top of Pastry. The paper presents a simple interface and a message routing algorithm that is inverting Pastry’s lookup algorithm. The authors provide extensive amounts of empirical measurements of their implementation of the approach on various network topologies and group sizes.

Herald: Achieving a Global Event Notification Service: L. Cabrera, M. Jones and M. Theimer
The paper describes the design goals (and non-goals) of a scalable, peer-to-peer event notification system. Its primary contribution is a comprehensive listing of the problems that any such system will face, such as unreliable or malicious peers or the requirement for heuristics that automatically make reasonable choices for degrees of replication.

Providing content-based services in a peer-to-peer environment: Ginger Perng, Chenxi Wang and Michael K. Reiter

Other


Space/Time Trade-offs in Hash Coding with Allowable Errors: Burton Bloom
The original paper on Bloom filters. The author describes how this probabilistic datastructure can be used to speed up dictionary lookups. This is pretty much what libextractor is doing for the dictionary-based printable plugins.

A Reputation-Based Approach for Choosing Reliable Resources in Peer-to-Peer Networks: Ernesto Damiani, De Capitani di Vimercati, Stefano Paraboschi, Pierangela Samarati and Fabio Violante

Privacy in Electronic Commerce and the Economics of Immediate Gratification: Alessandro Acquisti

Secure Multi-Party Computation: Oded Goldreich

Copyright (C) 2002, 2003, 2004, 2005, 2006 Christian Grothoff.
Verbatim copying and distribution of this entire article
is permitted in any medium, provided this notice is preserved.

go to i18nHTML administration page