R5N - Obfuscated mesh routing on hostile networks. (opens in new tab)

(lsd.gnunet.org)

106 pointstinydev1y ago14 comments

14 comments

9 comments · 3 top-level

I'm curious about two things. I don't really understand how the randomized addressing helps with data locality. Is it just saying that XOR gives random results, and so adding random hops before doing lookups gives a higher statistical percentage of reaching nodes?

Also how does this compare to something like libp2p w/ DCUtR for NAT traversal? Is the NAT problem circumvented by the randomized walk routing?

grothoff1y ago

Yes, the random walk relates to the "NAT problem". Basically, due to NAT, peers may not succeed when trying to connect to arbitrary other peers (especially if you assume no TURN servers or other infrastructure to facilitate). The same situation may also arise in mobile ad-hoc networks, where your wireless signals simply don't get everywhere. As a result, the usual greedy routing will get stuck in a local minimal. By prefixing the greedy routing with a random walk, you basically randomize the starting position, and then end up at a random local minima. Replicate at enough local minima (O(sqrt(n)) and do enough (O(sqrt(n)) lookups and the birthday paradox will make it increasingly likely for you to succeed. Without the random walk, both the putter and the getter would greedily route always to their local minimum, and if they differ, never find each other's data.

jesprenj1y ago

Where does sqrt come from? Shouldn't it be log? I don't know much about DHTs, but Kademila (BitTorrent's DHT) has query complexity of around O(log n), with n being the total number of nodes in the network. Kademila also uses random node IDs and XOR disrance metric.

1 more reply

samstave1y ago

I love the way you wrote this.

Can you give some examples fictional scenario where this would be put to use as you state it really well.

Thanks

1 more reply

orthecreedence1y ago

Awesome, this makes sense, thanks for the explanation.

jay-barronville1y ago· 2 in thread

Is there an official reference implementation of the protocol available?

grothoff1y ago

Actually, there are two: One in C at https://git.gnunet.org/gnunet.git/tree/src/service/dht And one in Go at https://git.gnunet.org/gnunet-go.git/