Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

R5N - Obfuscated mesh routing on hostile networks.

lsd.gnunet.org

Post reply on HN
Print view View original

11–15 of 15 posts

Re: R5N - Obfuscated mesh routing on hostile networks.

#11

Post by anacrolix »

jesprenj wrote: post #10
grothoff wrote: post #3

Earlier quoted context omitted.

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…

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.

BitTorrent's mainline DHT is O(log n). Base 2. However you can usually skip 2-3 bits per round of queries. This means you can locate any of the 20 million nodes in BitTorrent in about 7 hops. In practice it's about 20 queries and takes about 3-5s. No persistent connections. Barely a few KB of memory for every client. No other real world implementation is that good.

Re: R5N - Obfuscated mesh routing on hostile networks.

#12

Post by jesprenj »

anacrolix wrote: post #11
jesprenj wrote: post #10

Earlier quoted context omitted.

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.

BitTorrent's mainline DHT is O(log n). Base 2. However you can usually skip 2-3 bits per round of queries. This means you can locate any of the 20 million nodes in BitTorrent in about 7 hops. In practice it's about 20 queries and takes about 3-5s. No persistent connections. Barely a few KB of memory for every client. No other real world implementation is that good.

Yes, but where did sqrt come from that the parent commenter mentioned?

Re: R5N - Obfuscated mesh routing on hostile networks.

#13

Post by schanzen »

jesprenj wrote: post #12
anacrolix wrote: post #11

Earlier quoted context omitted.

BitTorrent's mainline DHT is O(log n). Base 2. However you can usually skip 2-3 bits per round of queries. This means you can locate any of the 20 million nodes in BitTorrent in about 7 hops. In practice it's about 20 queries and takes about 3-5s. No persistent connections. Barely a few KB of memory for every client. No other real world implementation is that good.

Yes, but where did sqrt come from that the parent commenter mentioned?

Co-author here. If you look into the R5N paper (link in draft), you can find this term. If you assume a routing performance of O(log n) and O(sqrt (n)) number of lookups to find the value, you get O (sqrt (n) * log n) as overall complexity (last section in paper).

For the argument of the sqrt (n) itself, see the paper.

Edit 1: Quote: "Assuming that T [random path length] is chosen large enough to achieve perfect mixing, sqrt (n / (c−1)) replicas would need to be created in order for a GET request to succeed with about 50% probability according to the birthday paradox."

Edit 2: In a world without local minima the term itself will be 1 (you only need a single lookup and will find the value with 100% probability. In the restricted route scenario you will have to so O(sqrt(n)) lookups.

Re: R5N - Obfuscated mesh routing on hostile networks.

#15

Post by jesprenj »

schanzen wrote: post #13
jesprenj wrote: post #12

Earlier quoted context omitted.

Yes, but where did sqrt come from that the parent commenter mentioned?

Co-author here. If you look into the R5N paper (link in draft), you can find this term. If you assume a routing performance of O(log n) and O(sqrt (n)) number of lookups to find the value, you get O (sqrt (n) * log n) as overall complexity (last section in paper). For the argument of the sqrt (n) itself, see the paper. Edit 1: Quote: "Assuming that T [random path length] is chosen large enough to achieve perfect mixi…

Aha, thanks for that, the paper seems to reason better at first glance, I'll read it.

You mention sybil attacks on Kademlia, especially those that arise because nodes may set their ID and "camp around" some known key in the hash table. How is this addressed here? By glancing over the standard draft, I see the identifier is just a SHA-512 of the pubkey. Wouldn't it be feasible to bruteforce the first some bits of the key and "camp around" some keys a malicious sybil actor wants to deny service to?

Post reply on HN