Freenet 0.7 - Revision history

Pollex at 11:59, 14 October 2007

2007-10-14T11:59:09Z

← Older revision		Revision as of 11:59, 14 October 2007
Line 175:		Line 175:

	Based on the fact that each node has a position in the reference space and stores only those files, to wich it is nearer that any of its neighbours, Freenet implements a simply greedy routing algorithm for search requests. A request for a key is sent with a certain hops-to-live-limit in order to ensure that it terminates at some point. Every node routes the request to the neighbour with the position nearest to the requested reference. If a node does not have a neighbour that is nearer to the requested reference that itself, it does not route the requests any further, but instead sends it back with an answer ("have file", "don't have file").		Based on the fact that each node has a position in the reference space and stores only those files, to wich it is nearer that any of its neighbours, Freenet implements a simply greedy routing algorithm for search requests. A request for a key is sent with a certain hops-to-live-limit in order to ensure that it terminates at some point. Every node routes the request to the neighbour with the position nearest to the requested reference. If a node does not have a neighbour that is nearer to the requested reference that itself, it does not route the requests any further, but instead sends it back with an answer ("have file", "don't have file").

			=Attacks=


	=References=		=References=

Pollex: /* References */

2007-10-13T15:27:53Z

References

← Older revision		Revision as of 15:27, 13 October 2007
Line 183:		Line 183:
	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Talk, [http://freenetproject.org/22c3vid.html]		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Talk, [http://freenetproject.org/22c3vid.html]

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](tar.bz2 archive)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Java Demo, [http://freenetproject.org/papers/ccc/ccc-freenet-demo.tar.bz2](bz2 archive)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Java Demo, [http://freenetproject.org/papers/ccc/ccc-freenet-demo.tar.bz2](tar.bz2 archive)

Pollex: /* References */

2007-10-13T15:27:31Z

References

← Older revision		Revision as of 15:27, 13 October 2007
Line 181:		Line 181:
	* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)		* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Talk, [http://freenetproject.org/22c3vid.html]~~(video)~~		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Talk, [http://freenetproject.org/22c3vid.html]

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)

Pollex: /* References */

2007-10-13T15:27:11Z

References

← Older revision		Revision as of 15:27, 13 October 2007
Line 181:		Line 181:
	* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)		* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress The Talk, [http://freenetproject.org/22c3vid.html](video)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Talk, [http://freenetproject.org/22c3vid.html](video)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)

Pollex: /* References */

2007-10-13T15:26:58Z

References

← Older revision		Revision as of 15:26, 13 October 2007
Line 181:		Line 181:
	* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)		* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress, [http://freenetproject.org/22c3vid.html](video)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress The Talk, [http://freenetproject.org/22c3vid.html](video)

	* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)		* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)

Pollex: /* References */

2007-10-13T15:26:38Z

References

← Older revision		Revision as of 15:26, 13 October 2007
Line 180:		Line 180:

	* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)		* O. Sandberg, "Distributed Routing in Small World Networks", 2005 [http://www.math.chalmers.se/~ossa/swroute.pdf](pdf)

			* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress, [http://freenetproject.org/22c3vid.html](video)

			* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Slides, [http://freenetproject.org/papers/ccc/ccc-slideshow.pdf.bz2](bz2 archive)

			* I. Clarke, O. Sandberg, Lecture on Freenet 0.7, 22nd Chaos Computer Congress - The Java Demo, [http://freenetproject.org/papers/ccc/ccc-freenet-demo.tar.bz2](bz2 archive)

Pollex: /* Technical Implementation */

2007-10-13T15:22:43Z

Technical Implementation

← Older revision		Revision as of 15:22, 13 October 2007
Line 170:		Line 170:
	===Sotring of files===		===Sotring of files===

			As was mentioned above, each node simply stores those files, that have a key wich is nearer to its position than to that of any of its neighbours. Inserting a file is done in two steps. First, the node searches for the file. If the file is found, then there is a collision in the reference space and the insert is rejected. Also, all nodes that routed the search-requests will cache the original file, thus resulting in spreading the information that an attacker may have tried to overwrite. So the insert only happens if the file was not found. The node that terminated the requests did so because none of its neighbours was closer to the reference that itself (this is explained in more detail in Retrieval). This means that this node is the best choice to store the file we want to insert, because there other nodes will most likely search for that reference. So, the file we want to commit is transfered to that node. Note that all communication is always done along the path of the original requests. Shortcuts would violate the prinicple of the Darknet.
	As was mentioned above, each node simply stores those files, that have a key wich is nearer to its position than to that of any of its neighbours. Basicaly

	==Retrieval==		==Retrieval==

			Based on the fact that each node has a position in the reference space and stores only those files, to wich it is nearer that any of its neighbours, Freenet implements a simply greedy routing algorithm for search requests. A request for a key is sent with a certain hops-to-live-limit in order to ensure that it terminates at some point. Every node routes the request to the neighbour with the position nearest to the requested reference. If a node does not have a neighbour that is nearer to the requested reference that itself, it does not route the requests any further, but instead sends it back with an answer ("have file", "don't have file").

	=References=		=References=

Pollex: /* Storing and caching */

2007-10-13T15:10:04Z

Storing and caching

← Older revision		Revision as of 15:10, 13 October 2007
Line 167:		Line 167:

	This algorithm has some security implications when implemented. Every node only has knowledge of its local peers. In order to initialize a swap, it will send a swap request wich will be randomly routed for a certain number of hops. If the node at the other end is currently able to swap (it must not be processing any requests), it will say so, else the swap fails here. Then both nodes have to agree on weather the swap would be usefull. The could do that by exchanging their edge products and their locations. Thus each node could calculate its new edge product and decide weather it is beneficial to swap. The problem with that protocol is, that it is easy to lie and enforce swaps, wich could be exploited for several attacks. In order to make it harder to forge information, the protocol currently implemented exchanges the positions of the nodes and all their peers. This is more secure with respect to enforcing swaps, but it lays open parts of the network topology, wich weakens security.		This algorithm has some security implications when implemented. Every node only has knowledge of its local peers. In order to initialize a swap, it will send a swap request wich will be randomly routed for a certain number of hops. If the node at the other end is currently able to swap (it must not be processing any requests), it will say so, else the swap fails here. Then both nodes have to agree on weather the swap would be usefull. The could do that by exchanging their edge products and their locations. Thus each node could calculate its new edge product and decide weather it is beneficial to swap. The problem with that protocol is, that it is easy to lie and enforce swaps, wich could be exploited for several attacks. In order to make it harder to forge information, the protocol currently implemented exchanges the positions of the nodes and all their peers. This is more secure with respect to enforcing swaps, but it lays open parts of the network topology, wich weakens security.

			===Sotring of files===

			As was mentioned above, each node simply stores those files, that have a key wich is nearer to its position than to that of any of its neighbours. Basicaly

	==Retrieval==		==Retrieval==

Pollex: /* Storing and caching */

2007-10-13T15:08:17Z

Storing and caching

← Older revision		Revision as of 15:08, 13 October 2007
Line 164:		Line 164:
	===Node positioning===		===Node positioning===

	To understand how the storing of file works, it is important to understand the positioning of each node in the reference space. The reference space is the one-dimensional space of all possible reference values. Each node has a position in this reference space. Initially this position is given at random. The only way to change that is for two nodes to switch positions. As was explained above, it is an important property of a small world that each node has many short connections and few long ones. So the two node may decide to switch their positions if it minimizes the overall product of their respective edge-length. This idea was originally proposed by Oscar Sanderg in his paper "[http://www.math.chalmers.se/~ossa/swroute.pdf Distributed routing in Small World Networks]"(pdf).		To understand how the storing of file works, it is important to understand the positioning of each node in the reference space. The reference space is the one-dimensional space of all possible reference values. Each node has a position in this reference space. Initially this position is given at random. The only way to change that is for two nodes to switch positions. As was explained above, it is an important property of a small world that each node has many short connections and few long ones. So the two node may decide to switch their positions if it minimizes the overall product of their respective edge-length. This idea was originally proposed by Oscar Sanderg in his paper "[http://www.math.chalmers.se/~ossa/swroute.pdf Distributed routing in Small World Networks]"(pdf). It is important to realize that switching positions in the keyspace does not affect the links of a node. After switching eahc node will stil have the same neigbours as before, only the distances to them will have changed. Also, the data a node has stored becomes virtually useless, because requests for these files would be routed to the old position of the node. Therefore swaping must not happen too often, or the overall performance of the network will decrease.

			This algorithm has some security implications when implemented. Every node only has knowledge of its local peers. In order to initialize a swap, it will send a swap request wich will be randomly routed for a certain number of hops. If the node at the other end is currently able to swap (it must not be processing any requests), it will say so, else the swap fails here. Then both nodes have to agree on weather the swap would be usefull. The could do that by exchanging their edge products and their locations. Thus each node could calculate its new edge product and decide weather it is beneficial to swap. The problem with that protocol is, that it is easy to lie and enforce swaps, wich could be exploited for several attacks. In order to make it harder to forge information, the protocol currently implemented exchanges the positions of the nodes and all their peers. This is more secure with respect to enforcing swaps, but it lays open parts of the network topology, wich weakens security.
	In that system inserting a file first means finding the node with the position closest to the key of the file. So before you insert a file you actually search for it. If the file is not found (see Retrieval), you send it to the last node in the searchpath. This will be the node with the position closest to your filekey. Note that here allready every node along the path caches the file, thus there are multiple copies of it from the beginning. If, on the other hand, a file with that key allready exists, you get that file sent back to you. Again, note that every node along the path now caches that file, so if you try to overwrite some content, you actually just spread it further troughout the network.

	==Retrieval==		==Retrieval==

Pollex: /* Storing and caching */

2007-10-13T13:42:04Z

Storing and caching

← Older revision		Revision as of 13:42, 13 October 2007
Line 164:		Line 164:
	===Node positioning===		===Node positioning===

	To understand how the storing of file works, it is important to understand the positioning of each node in the reference space. The reference space is the one-dimensional space of all possible reference values. Each node has a position in this reference space. Initially this position is given at random. The only way to change that is for two nodes to switch positions. As was explained above, it is an important property of a small world that each node has many short connections and few long ones. So the two node may decide to switch their positions if it minimizes the overall product of their respective edge-length. This idea was originally proposed by Oscar Sanderg in his paper [http://www.math.chalmers.se/~ossa/swroute.pdf "Distributed routing in Small World Networks"].		To understand how the storing of file works, it is important to understand the positioning of each node in the reference space. The reference space is the one-dimensional space of all possible reference values. Each node has a position in this reference space. Initially this position is given at random. The only way to change that is for two nodes to switch positions. As was explained above, it is an important property of a small world that each node has many short connections and few long ones. So the two node may decide to switch their positions if it minimizes the overall product of their respective edge-length. This idea was originally proposed by Oscar Sanderg in his paper "[http://www.math.chalmers.se/~ossa/swroute.pdf Distributed routing in Small World Networks]"(pdf).

	In that system inserting a file first means finding the node with the position closest to the key of the file. So before you insert a file you actually search for it. If the file is not found (see Retrieval), you send it to the last node in the searchpath. This will be the node with the position closest to your filekey. Note that here allready every node along the path caches the file, thus there are multiple copies of it from the beginning. If, on the other hand, a file with that key allready exists, you get that file sent back to you. Again, note that every node along the path now caches that file, so if you try to overwrite some content, you actually just spread it further troughout the network.		In that system inserting a file first means finding the node with the position closest to the key of the file. So before you insert a file you actually search for it. If the file is not found (see Retrieval), you send it to the last node in the searchpath. This will be the node with the position closest to your filekey. Note that here allready every node along the path caches the file, thus there are multiple copies of it from the beginning. If, on the other hand, a file with that key allready exists, you get that file sent back to you. Again, note that every node along the path now caches that file, so if you try to overwrite some content, you actually just spread it further troughout the network.