(Teaser)

1. Introduction

This specification describes the protocol of R5N. R5N is a Distributed Hash Table (DHT). The name is an acronym for “randomized recursive routing for restricted-route networks”.

The core idea behind R5N is to combine a randomized routing algorithm with an efficient, deterministic closest-peer algorithm. This allows us to construct an algorithm that is able to escape and circumvent restricted route environments while at the same time allow for a logarithmically bounded routing complexity.

1.2. System Model

DHTs usually operate as overlay networks consisting of peers communicating over the existing Internet. Hence canonical DHT designs often assume that the IP protocol provides the peers of the overlay with unrestricted end-to-end pairwise connectivity. However, in practice firewalls and network address translation (NAT) [RFC2663] make it difficult for peers operating on consumer end-devices to directly communicate, especially in the absence of core network infrastructure enabling NAT traversal via protocols such as interactive connectivity establishment (ICE) [RFC5245].

Furthermore, not all peer-to-peer networks consistently operate over the Internet, such as mobile ad-hoc networks (MANETs). While routing protocols have been designed for such networks ([RFC3561]) these generally have issues with security in the presence of malicious participants, as they vulnerable to impersonation attacks. The usual solution to these issues is to assert that the entire MANET is a closed network and to require authentication on all control messages. In contrast, the system model for R5N is that of an open network without any kind of authorities that could restrict access only to trusted participants.

1.3. Security Model

We assume that the network is open and thus a fraction of the participating peers is malicious. Malicious peers may create, alter, delay or drop messages. We also assume that an adversary can control (or fake) many peers [Sybil], thus any kind of voting or punishment of malicious peers would be rather pointless.

Honest peers are expected to establish and maintain many connections. We assume that as a result the adversary is generally unable to prevent honest peers from maintaining a sufficient number of direct connections with other honest peers to achieve acceptable performance. As the number of malicious peers and their connections increases, performance of the system should gracefully degrade, and only collapse for peers that an adversary has fully isolated from the benign network.