Reproducing Freenet: A Distributed and Anonymous Data Store
Authors: Victor Ongkowijaya, Satadal Sengupta
This is a reproduction study of Freenet by Clarke et al. for Princeton University, COS 518: Advanced Computer Systems, FA19.
Introduction
Around the time when Freenet [1] was published (2000–01), privacy had not been a central design goal of existing distributed file systems. The authors argued that existing DFSes provided little privacy for both producers and consumers of data. Freenet was an attempt to solve this issue by achieving a multitude of properties: anonymity for all users, deniability for storers of data, decentralization, and resistance to censorship. These goals were achieved in Freenet by employing encryption and signing schemes between cooperative nodes, coupled with an adaptive routing algorithm.
What is our goal?
In this project, we task ourselves with reproducing Freenet’s central features as faithfully as possible. We then compare our experimental results with the results presented in the original paper. More specifically, we aim to evaluate Freenet’s efficiency, scalability, and fault tolerance, which are the primary desired traits of distributed systems. The plots which we aim to replicate are Fig. 2 pg. 13, Fig. 3 pg.14, and Fig. 4 pg.15, respectively, from the original paper. Since implementing the entirety of Freenet’s many mechanisms would be far beyond the scope of this project, we decided to prioritize only on implementing features which would directly affect these evaluations. While important, mechanisms such as ensuring anonymity/deniability, strong encryption, and namespace management do not directly affect our performance metrics; such mechanisms are therefore not implemented.
In the course of this attempt, we faced many challenges with regards to the implementation of specific concepts which are briefly mentioned in the paper but not elaborated upon. Broadly, these include (1) the exact operational details of how Freenet’s routing algorithm works, and (2) parameters used in their evaluation. When facing ambiguity, we attempt to make decisions which we believe would be closest to the authors’ original intent. We recognize that it is likely impossible for a paper to accurately and exhaustively capture all the details of a system, especially one as complex as Freenet. For this reason, we expected our implementation to have deviations from the original.
How does Freenet work?
The Freenet system comprises user nodes that collaboratively share their unused disk space. This space is used to store files as well as a dynamic routing table. Freenet utilizes three types of keys to achieve its desired properties: the keyword signed key (KSK), signed subspace key (SSK), and content hash key (CHK). These keys work together for nodes to identify, encrypt, retrieve, and insert files. Nodes can find each other by a routing protocol similar to IP, where key requests are forwarded from node to node in a chain of proxy requests. Each node then consults its dynamic routing table to determine the forwarding target.
The most important function of Freenet is its data request function. All other requests follow a similar routing model, such as data insertion and node joining. Fig. 1 presents the sequence of routing messages involved in serving an existing file in the network to a requesting node. Node a is the initiator; it sends the request to node b, which in turn sends it to node c. Node c does not possess the data so it replies with a “request failed” message. Node b forwards the request along to its next option, which is node e. Node e forwards it to node f, which forwards it to node b. A loop is detected, and node f backtracks to node e (through failure messages). Node e now tries its other alternative node d, which possesses the file. The file is sent along the path e->b->a, with both nodes e and b caching the file to serve future requests. We implement this scenario in our prototype as a basic correctness check, before proceeding to more complex scenarios. Crucially, Freenet nodes learn more about the network as they process more and more requests. The network graph continually changes as a result.
Implementation
We present briefly specific implementation details pertaining to our Freenet prototype in this section. We chose the Go language for implementing our Freenet prototype. We make use of goroutines for node operations, which allows for better concurrency and flexibility than other alternatives. We deliberated between re-implementing Freenet in an actual distributed system (via AWS or other cloud computing services) and a more simulated approach (via goroutines). Ultimately, we realized that our performance metrics do not require an actual distributed system; properties such as network latency, node failures, or node heterogeneity were not factors in the evaluations done by the original authors. Rather, the primary evaluation metric is the hops-to-live (HTL), similar to the concept of time-to-live (TTL), which measures how many nodes were passed by a request before it succeeded. Therefore, we were able to abstract a node to be a goroutine in one single machine. These goroutines run the code we wrote to behave like a physical node with its own processor, disk, and routing table, capable of communicating with other nodes. We believe this approach will accurately simulate any HTL-based evaluations.
We implement our prototype in approximately 1900 lines of code (primarily in Go and some in Python). The code is available on Github.
Keys and Searching
We implemented the mechanisms of the keyword signed key (KSK) which is the most fundamental key type required to make Freenet work. The other key types, namely the signed subspace key (SSK) and content hash key (CHK), are auxiliary; they provide useful but non-crucial functions such as file updating and namespace management. We identified KSK as the only key-type necessary to implement a fully-functional prototype and to complete the evaluations we planned for.
File Insertion and Retrieval
The file insertion and retrieval mechanisms together form the basis of routing in Freenet. Formally, this routing works as a steepest-ascent hill-climbing search with backtracking. We implemented the algorithm running on every node to handle both file insertions and retrievals, which includes managing the node’s respective files, pending jobs, and routing table. Additionally, nodes are implemented to detect and handle transaction loops through the HTL mechanism and by keeping some state of each transaction in memory.
Data Management
A node can be thought of having a disk (to store files), routing table (to forward packets correctly), and processor (to store the jobs/transactions that are currently being processed or waited on). These resources must be set to a finite capacity in our simulation to accurately model a distributed system. In our experiments, disks have a capacity of 50 files and routing tables have a capacity of 250 entries. Both the disk and routing table follows a least-recently-used eviction strategy, in conjunction with the routing protocol. The processor has a capacity of 100 pending transactions, with a timeout of 5 seconds.
Evaluation
In this section, we present our experimental results and compare and contrast those with the results obtained by the authors in the Freenet paper [1]. We evaluate behavior related to performance, scalability, and fault tolerance in specific since these are the central goals of a distributed system. We try to remain as faithful to the experimental setup in the original paper as possible.
One important thing to note is that “time” has not been clearly defined in the paper, and the original plots do not include a unit. We assume a constant request arrival rate per unit time (or per timestep). More specifically, we assume 2 requests arrive per timestep, where each request is either a file insertion request or a file retrieval request.
Performance
In the following experiments, we spawn 1000 nodes and arrange them in a regular ring-lattice topology (i.e., each node is connected to 2 nodes ahead and 2 nodes behind it), as mentioned in the paper. Random file insertions and retrievals (for existing files) are executed with an HTL of 20. Snapshots are taken every 100 timesteps. Each snapshot comprises of 300 requests for existing files, with an HTL of 500. We measure the number of hops traversed by a request before the requested data is located; if the requested data is not found within the set HTL of 500, the pathlength is considered as 500 which is the maximum possible pathlength. The simulation is allowed to run for 5000 timesteps.
Fig. 2 depicts the evolution of the first, second, and third quartiles of pathlength averaged over 10 trials. We note that the pathlength is initially very high but rapidly decreases as the network starts converging. The median pathlength drops down to only 7 within 1500 timesteps. This is in agreement with the trend observed in the paper.
However, we also note that the pathlength rises slightly after reaching this minimum value. We posit that this is because as more and more requests come into the network and the caches (routing table and data store) are constantly updated, the network takes slightly longer (this effect is most apparent for the third quartile) in terms of pathlength to reach the requested data.
Fig. 3 is a truncated view of Fig. 2, with the exception that we allow the simulations to run for only 2000 timesteps instead of 5000. This shows the state of the network before it starts getting burdened by incessant requests. We present this to illustrate that the behavior is almost identical to that presented in Fig. 2 in the original paper [1].
Next, we repeat the same experiment with the exact same parameters, except that this time the topology is not pre-defined. Instead, a new node joins the network with an HTL of 10 by sending a join request to an existing node at random. The nodes which get updated due to a join is determined using Freenet’s join algorithm (which is based on its routing algorithm).
Fig. 4 shows that in the case of a Freenet-determined topology, the convergence is even sharper, with the median settling down at a value of 4 by ~700 timesteps.
Scalability
In order to test the scalability of the system, we start with 20 nodes connected in a regular ring-lattice structure. Then, we keep adding a new node to the network with an HTL of 10 every 5 timesteps; the join request is sent to an existing node at random. As before, we snapshot the network periodically — we initiate 50 requests of HTL 100 every 250 timesteps (or, 50 new node additions). The results presented are averaged over 10 trials.
Fig. 5 shows the first, second, and third quartiles of request pathlength as these parameters evolve over network size. We observe that the median pathlength increases linearly with exponential network growth, which shows that the system is scalable, and is in agreement with the behavior shown in the Freenet paper. The median pathlength is around 60 with 1000 nodes in the network, while the first quartile remains around 55 even with 10,000 nodes in the network.
Fault Tolerance
In order to evaluate fault tolerance of our system, we again let the network grow to a size of 1000 nodes in a manner similar to the previous experiment (we start from 20 nodes in a ring-lattice topology and then keep adding a new node every 5 timesteps). Random file insertions and retrievals take place regularly as in the previous experiments. After the network with 1000 nodes has converged, we start stopping an existing node every 5 timesteps. The node failure is a fail-stop failure and no other node is informed about the failure until they send a request and get no response until a timeout. We snapshot the network as before at regular intervals, with 100 file requests with an HTL of 500 every 10 node failures (or 1% failure). The results are averaged over 10 trials.
We observe in Fig. 6 that while the network is able to deal with 4–5% node failures without significant impact, it starts to perform badly once the 10% mark is breached. This observation is not in agreement with the paper where the authors show that the request pathlength is significantly low even with 30% node failure. We suspect this is due to our strict interpretation of node failures in the simulation environment; the authors may have chosen a more lenient implementation. Since the paper does not provide explicit details, it is hard to verify this argument.
Conclusion
In conclusion, we believe that we were able to reproduce the core components of Freenet adequately. The lack of explicit detail with respect to some mechanisms and choice of parameter values made it difficult for us to exactly replicate the original system; however, we were able to reproduce the system reliably enough such that most performance trends were in agreement with those in the original paper.
References
[1] Clarke, I., Sandberg, O., Wiley, B., & Hong, T. W. (2001). Freenet: A distributed anonymous information storage and retrieval system. In Designing privacy enhancing technologies (pp. 46–66). Springer, Berlin, Heidelberg.
