R5N - Obfuscated mesh routing on hostile networks.

https://lsd.gnunet.org/lsd0004/draft-schanzen-r5n.html

by tinydev • 2 years ago

106 14 2 years ago

lsd.gnunet.org

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?

grothoff3• 2 years 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.

orthecreedence2• 2 years ago

Awesome, this makes sense, thanks for the explanation.

samstave• 2 years 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

jesprenj3• 2 years 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.

jay-barronville2• 2 years ago

Is there an official reference implementation of the protocol available?

grothoff3• 2 years 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/

jay-barronville2• 2 years ago

Awesome, thank you!

schanzen2• 2 years ago

Presentation given at IETF 118: https://datatracker.ietf.org/meeting/118/materials/slides-11...

R5N - Obfuscated mesh routing on hostile networks.

Related Stories