After many iterations I’ve finally converged to a draft that seems to be able to work (version 0.0.2 will be released soon then!). Let’s take a look!
Because of the main requirement put on hiding peers’ IPs, a node that joins the network sends a message notifying everyone else that he joined. This message has maximum allowed TTL and is broadcast until all nodes gain knowledge about this new node. As everybody tracks where they received this message from with highest TTL, everybody is able to route messages to this node very easily. The main disadvantage is obvious: size of the routing table is in O(n). This is a trade-off for gained privacy, so it’s acceptable. :c)
As peers don’t connect to each other when they want to communicate, but send messages through overlay instead, there’s no problem in being behind NAT or a restrictive firewall. Such nodes only aren’t included in DNS seeds.
It’s easy to see that this topology is inherently redundant. When a node with the best TTL disconnects, its neighbours still have backup (second best) routes via their adjacent nodes. Current proposal includes maintaining of at least 4 connections from each node to the network.
Given the highest-TTL heuristic every packet is routed the shortest possible path to its recipient.
Although I see no reason why this approach shouldn’t work, I’m still looking at the big routing table as that might easily become a scalability issue. Although I have in mind a special approach that could make it possible even for nodes with low resources to participate in the network, this requires more thorough research that would answer some important questions, e.g., what percentage of nodes must be “full” for the network to stay 100% functional, or how much other overlay properties would be affected. Anyway, there might be even a completely different way for tackling this problem. Definitely a subject for my further research! :c)