Re: [Din] I-D: The R5N Distributed Hash Table

["Schanzenbach, Martin" <[e-mail]>]

Hi Christian,

thanks for checking the draft out.

> On 29. Aug 2022, at 19:18, Christian Huitema <[e-mail]> wrote:
> 
> 
> On 8/29/2022 5:18 AM, Schanzenbach, Martin wrote:
>> Hi dinrg!
>> 
>> I hope this email finds you all in good health.
>> 
>> Wwe wanted to touch ground with you if any of you would be interested in our specification
>> on R5N, a protocol for randomised recursive routing for restricted-route networks. [1]
>> It is a distributed hash table protocol and we currently have two independent implementations.
>> The document is not finished but in a parseable state and feedback is very welcome either way.
>> 
>> This DHT can serve as a basis for GNS, for which there is a draft already quite far into the ISE process [2].
>> In fact, it is what our GNS implementations are using at the moment.
>> 
>> Thank you and have a nice day
>> Martin
>> 
>> [1] https://datatracker.ietf.org/doc/draft-schanzen-r5n/
>> [2] https://datatracker.ietf.org/doc/draft-schanzen-gns/
> 
> The R5N protocol is built on the classic DHT, kamdelia. Starting with a well known algorithm makes a lot of sense, but  I wonder whether some more work is needed regarding locality and security.
> 
> The connectedness of the DHT relies on each node learning about its closest neighbors, where closest means lowest distance between the peer ID, not lowest distance across the network. As the reach of the DHT increases, the network distance between the closest neighbors increases -- the "closest" neighbors will be at random locations across the Internet. Each node will generate network traffic required to maintain the closest list, and the aggregate may end up quite noticeable.
> 

Do you know of any actual data on that? I know this seems to be true intuitively, but the actual impact would be of interest for a discussion.

> The dependency on closest neighbors may also be a security issue. Each node depends on the good behavior of its closest neighbors. Attackers may single out a set of target peer ID, and spend some time generating peer IDs that have a close distance to this target. Once the attackers have secured a position in the list of closest neighbors of their target, they can mount a set of attacks, such as monitoring traffic to the target or denying service to the target.

Yes that is true. But it is partially addressed by the random routing. And the monitoring issue is extremely difficult if not impossible to address at all if you want global routing over public networks.

> 
> The monitoring problem goes beyond just the list of closest neighbors. If attackers create a sufficient number of nodes, they will be able to monitor and possibly disturb a fraction of the traffic. The random routing steps in R5S ensure that resolution starts from random points in the network, which has both good and bad effects. On the good side, it means that repeated queries will follow different paths, which is more robust than always following a fixed path. On the other hand, the randomness almost ensures that a fraction of the queries will hit the attackers' nodes.

Yes, that is correct. We should discuss that in the document. The attacker model needs to be defined and discussed properly anyway.

> 
> Such issues are inherent with the classic DHT technology, but they may be solved in alternative technologies, as demonstrated by Freenet. Of course, this is your project, your choices. But it would be very nice to have some higher emphasis on locality, so that for example resolution of local names does not generate traffic outside the local network -- that would be better for privacy, and also more robust.

I do not understand how either that would work or why you think this is not the case for r5n.
Local nodes (direct neighbours) cache messages (and possibly even store if the replication level is high enough). So ideally this data is available at close nodes, not only on nodes close to the key.
I am not really sure what you are proposing as an alternative. Keys cannot at the same time be stored locally and at the same time be efficiently available to peers outside of it. IMO we can have efficient global routing with O(log n) complexity or local-first routing with significantly more overhead for global routing.
If you have any concrete ideas or papers that we could read in this regard that would be very helpful.

Thanks again and BR
Martin

> 
> -- Christian Huitema
> 
> 
>